K-Way Merge: The Engine of Compaction

K-Way Merge: The Engine of Compaction

Every compaction strategy — size-tiered or leveled — ultimately reduces to the same primitive operation: take several sorted sources of key-value entries and merge them into one sorted output, resolving duplicate keys along the way. This is k-way merge, and it's the single most important algorithm in the whole LSM-tree codebase; you'll reuse it for compaction, for range scans, and for read-path iteration.

Why not just concatenate and sort?

You could concatenate all input files and sort the combined list, but that's wasteful: each input is already sorted. Merging preserves that sortedness incrementally and only needs to look at the current "head" of each source at any time — O(N log k) instead of O(N log N), where k is the number of sources (small — a handful of SSTables) and N is the total number of entries (potentially huge).

The min-heap approach

The standard technique: put the head element of every source into a min-heap, keyed by (key, ...). Repeatedly pop the minimum, emit it (after dedup logic — more below), and push the next element from whichever source you just popped from.

This gives you entries in ascending key order, and — because of how the tuple is ordered — ties on key are broken by descending seq, so the newest version of a duplicated key always surfaces first out of the heap.

Handling duplicate keys: the seq number

Because different SSTables can hold different versions of the same logical key (an old put, an overwrite, a delete), a naive merge would emit every version. Compaction's whole point is to collapse them down to one visible entry per key — the one with the highest seq (sequence number / timestamp). The trick: since your heap already pops entries in (key, seq DESC) order, the first time you see a brand-new key is automatically the entry with the highest seq for that key. Every subsequent pop with the same key can simply be skipped — no need to compare seqs manually; the ordering already did that work for you.

last_key = None
on pop (key, seq, val):
    if key != last_key:
        emit (key, seq, val)
        last_key = key
    # else: an older, shadowed version — drop it

Correctness pitfalls to watch for

• Within-source ordering matters. Each source is required to be sorted by (key ASC, seq DESC) — if a source violated that (e.g. seqs ascending), the "first occurrence wins" trick breaks and you'd need an explicit max-tracking pass instead.
• Heap tie-breaking must be deterministic — always include the source index as a final tuple element so Python's heap never tries to compare non-comparable payload values (like strings vs each other in confusing ways) when keys and seqs are equal.
• Streaming, not batch. A production k-way merge never loads all sources into memory — it pulls one record at a time from disk-backed iterators. Your exercise reads everything up front for simplicity, but the heap discipline is identical to the real, streaming version you'll build later when SSTable iterators are backed by actual file handles.

Master this pattern and compaction, range scans, and multi-level reads all become the same 20 lines of code with different inputs.