Compaction: The Merge That Pays for Cheap Writes

An LSM store with no compaction is a stack of flushes. Every overwrite of a key leaves the old version in an older file; every delete leaves the value *and* a tombstone; every flush adds a file whose range overlaps all the others. Three things degrade together: space (every stale version is still on disk), read cost (every point read checks every file, every range scan merges every file), and memory (a bloom filter and index per file). The engine is correct — newest wins — but it gets slower every hour.

The remedy follows from the files being sorted: k sorted runs merge into one sorted run in a single sequential pass, reading each input once and writing the output once. That is the merge of Merge Sort running over files instead of arrays, and the cursors are the same-direction Two Pointers (Same Direction) pattern generalised to k inputs — engines use a Min-Heap of cursors so the next smallest key is found in O(log k).

Inputs: SSTables A (newest), B, C. One cursor each. Loop: find the smallest key under any cursor; among the cursors on that key, the entry with the highest sequence number is the live version; emit it (or handle it as a tombstone), count the others as stale, advance every cursor that was on that key. When all cursors are exhausted, the output file is complete: fsync it, publish the new file list (a manifest entry), delete A, B and C once no reader still holds them.

The counters that matter: bytes read (the sum of the input files), bytes written (the output), stale versions dropped, tombstones dropped or carried. Bytes written divided by the bytes the application originally wrote is the compaction's contribution to write amplification — the subject of Write, Read and Space Amplification.

A tombstone exists to shadow older versions in older files. Dropping it is safe only when there is nothing left for it to shadow: every file that could hold an older version of the key has been merged with it. In leveled compaction that is the bottom level — a merge into the last level drops both the tombstone and whatever it shadowed. In size-tiered compaction a merge of three small files cannot drop a tombstone, because a bigger, older tier below may still contain the value; the tombstone is carried into the output.

Drop it too early and the old value resurrects: the next read walks past where the tombstone used to be and finds the stale value in an older file. This is a real bug class in distributed LSM stores, which is why Cassandra keeps tombstones for gc_grace_seconds (ten days by default) so that every replica has had a chance to see the delete before any replica purges it. The UPDATE, DELETE and Dead Tuples lesson shows the B+ tree world's version of the same problem: dead tuples that VACUUM may reclaim only once no snapshot can still see them.

The merge is the same; the strategy decides *which* files and *where the output goes*, and that decision sets the engine's amplification profile. Size-tiered waits until there are ~4 files of roughly the same size, merges them into one file of the next size class, and leaves other tiers alone. A byte is merged about once per tier, so writes are cheap; but a tier holds several overlapping runs, so reads may check all of them and a key overwritten many times occupies space in each run until that tier is merged.

Leveled organises the store as levels L1, L2, … each a single sorted run of fixed-size (~64 MB) non-overlapping files, each level ~10× the previous. When level N exceeds its budget, one file is picked and merged with the ~10 files of level N+1 that overlap its range; the output replaces those files. A read checks at most one file per level, and space overhead is bounded by the size ratio (~10%). But merging one file into ten rewrites ten bytes of old data per byte of new data, at every level: the highest write amplification of the three designs.

Compaction is a debt: ingest creates files faster than reads would like, and background threads pay the debt down. When they fall behind — a burst of writes, a slow disk, too few threads — level 0 grows. Every extra L0 file is one more bloom filter per point read and one more run per range scan, so read latency degrades first. Engines then protect themselves: RocksDB slows writes at 20 L0 files and stops them at 36; Cassandra logs "compaction is behind" and its read latency climbs. A write stall is the engine refusing writes until compaction catches up, and it is the most common production incident in LSM systems.

The underlying conflict is physical: compaction reads and writes at full sequential bandwidth on the same device that serves foreground reads, flushes and WAL fsyncs. A 64 MB-per-second compaction stream on a 500 MB/s disk is 13% of the bandwidth gone, plus the block-cache churn as new files replace the ones readers had cached. The controls are rate limits on compaction I/O, separate threads for flushes so they are never queued behind a large merge, and placing WAL and data on different devices. The Performance Internals: Why the Slow Node Is Slow lesson lists "compaction behind" among the branches of a slow-read investigation.