K-Way Merge: The Engine of Compaction

Every compaction reads N sorted SSTables and produces one sorted output stream. The algorithm: k-way merge using a min-heap.

The Pattern

This runs in O(N log K) where N is total entries and K is iterator count. The heap holds the current head of each iterator; pop the smallest, advance that iterator, repush.

Handling Duplicates (Same Key, Multiple Versions)

If two iterators emit the same key, the heap pops them in undefined order between equal keys. For compaction we need to keep the newest version and drop the rest (subject to snapshot retention).

Two common approaches:

1. Tuple sort by (key, -seq). Make the heap order keys ascending but seqs descending. The first entry per key is the newest.

2. Peek-ahead. Pop the smallest. If the next entry has the same key, pop it too. Keep the one with the larger seq. Repeat until the head differs.

Both work. RocksDB uses (1).

Skipping Obsolete Versions

Once we've yielded the latest visible version of a key, all older versions of that key can be skipped — unless some snapshot still needs them. The compaction tracks the smallest active-snapshot seq; any version with seq < that threshold AND a newer version present is garbage.

This is the single rule that gives LSM trees their MVCC semantics for free.

Tombstone Propagation

A tombstone (delete marker, Ch 7) shadows older versions of the same key. When emitting:

• If the entry is a tombstone and we are NOT at the bottommost level → emit it (the tombstone must still propagate down to suppress older versions in deeper levels).
• If the entry is a tombstone and we ARE at the bottommost level → drop it (no older versions can exist below; nothing to suppress).

Block-At-A-Time

In a real engine the iterators don't yield one entry at a time — they yield decoded blocks. The merge processes a block worth of entries, then moves to the next. This batches the heap operations and amortizes per-entry overhead.

CPU Profile

On a 1 GB compaction with k=10 iterators:

• ~10M heap operations
• Decoding 10x 1 GB of compressed blocks
• Encoding ~1 GB of new compressed blocks

Compaction is CPU-bound (compression/decompression dominate) on fast storage, I/O-bound on slow storage.