LSM Trees & Write Amplification
In short: a log-structured merge tree never edits a file on disk. A write
only ever touches an in-memory memtable; once that fills up, it flushes —
sorted, once — into a new sstable at the top level, L0. Once a level
holds enough sstables, compaction merges them into one bigger sstable one
level down, dropping any stale values along the way. Every flush and every
compaction writes bytes to disk, so the same record can get paid for more
than once before it settles into its final level — that repeated cost is
write amplification. The trade buys something real: writes are always a
cheap append, never a random-access rewrite. Reads pay the other side of the
bill, scanning sstables newest-first until a key turns up — which is exactly
where a Bloom filter per sstable earns its keep, by saying "definitely
not here" and skipping the scan entirely.
Flush a memtable, then pay for it again at compaction
Quarry's engine buffers writes in memory, flushes them sorted, and merges sstables down through the levels once a level gets crowded:
Nine writes, but 14 bytes end up written to disk: two flushes of 3
entries each (6 bytes), then — because L0 just reached the compaction
threshold of 2 sstables — one compaction that merges those two sstables,
deduplicating k1 and k2 down to their newest values, into a fresh
5-entry sstable in L1 (5 more bytes). A third flush (3 more bytes) lands
the last three writes back in L0, for 14 total. k1 and k2 each got
written twice: once at flush, once again at compaction. That's the whole
definition of write amplification: 14 / 9 ≈ 1.56 bytes written per byte the
caller actually asked to write.
A Bloom filter turns a scan into a skip
Reading a key means checking the memtable first (free — it's already in RAM), then scanning sstables newest-first until the key turns up or every sstable has been checked. Quarry keeps a small Bloom filter (section 8) alongside each sstable so a probe that would come back empty can be skipped instead of scanned:
k7 costs 1 probe either way — it's sitting in the newest sstable, so there
was never a wasted scan to skip. k1 and ghost both drop from needing a
probe into the L0 sstable (which doesn't contain them) down to zero
wasted probes there, because each sstable's Bloom filter correctly rules them
out before any scanning happens. A filter can only ever save a probe or cost
nothing extra — it never causes a real key to be missed.
Quick practice
writes = [("a", 1), ("b", 2), ("a", 3)]
memtable = {}
for k, v in writes:
memtable[k] = v
print(len(memtable))levels_before = [[("k1", 1)], [("k1", 2), ("k2", 3)]]
merged = {}
for sst in levels_before:
for k, v in sst:
merged[k] = v
print(sorted(merged.items()))🎯 Your turn
Build lsm_report(writes, memtable_limit, compaction_threshold, queries, m, k): run writes through the flush/compaction pipeline, measure write
amplification, then probe every key in queries once plainly and once with a
Bloom filter per sstable.
lsm_report([('k1','v1'),('k2','v2'),('k3','v3'),('k1','v4'),('k4','v5'), ('k5','v6'),('k2','v7'),('k6','v8'),('k7','v9')], 3, 2, ['k7','k1','ghost'], 32, 3)→{'write_amplification': 1.56, 'probes_without_bloom': 5, 'probes_with_bloom': 2}
Hint: run_lsm does the flush/compaction simulation — reuse it rather
than re-deriving it. write_amplification is just bytes_written / len(writes), rounded. Sum probe_count and probe_count_bloom across every
query for the two totals.
Press ▶ Run, try the Live App chips, then ✓ Check.