Build an LSM-tree storage engine (LevelDB / RocksDB style) (11 scenes)
Scene 06

Compaction — the GC of sorted files

A background process picks several SSTables, merges them in sorted order into one new SSTable that drops shadowed and deleted records, then atomically swaps the old files out — so file count stays bounded and dead bytes get reclaimed without ever blocking the writer.

Previously

Bloom bounded the cost of LOOKING at files. It didn't bound how many there are. Every flush adds another. Sooner or later, we have to remove files — not just skip them.

Scene 06

Compaction — the GC of sorted files

  1. Watch
  2. Try it
  3. Predict
  4. Capture
RAMmemtable (live writes)newKey = ack'd whil…DISKWAL — livePUT newKey=…SSTable shelfL0000007immutableL0000006immutableL0000005immutableL0000004immutableL0000003immutableOPERATIONPUT newKey→ memtable + WAL (uninterrupted by compaction)memtableWALFive SSTables, three of them all hold key k. Compactor wakes up.
What to watch for

Five SSTables on the shelf, three of them holding the same key. Watch the compactor select them, run a merge-sort, and emit a single new file. Foreground writes keep going; the writes-during-compaction counter never stops.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

lsm.compact
merge-sort N inputs → 1 output, drop shadowed/tombstones, atomic swap
def compact(inputs: list[SSTable]) -> SSTable:
    out = open_new_sstable(next_id())
    cursors = [s.iter_sorted() for s in inputs]
    while any(cursors):
        (key, val, seqno) = min_record(cursors)
        if newer_record_exists(key, val, seqno):
            continue                         # shadowed — drop
        if val.is_tombstone and at_bottom_level:
            continue                         # tombstone GC (scene 9)
        out.append(key, val)
    out.fsync()
    atomic_swap_files(remove=inputs, add=[out])  # one tick
    return out
Foreground writes are unaffected
puts always land in the memtable + WAL
def put(key, val):
    # NOTE: no awareness of compaction whatsoever
    wal.append(key, val); fsync_if_policy(wal)
    memtable.insert_sorted(key, val)
    return ok
# inputs are immutable; outputs land via atomic_swap.
# readers see EITHER the old file list OR the new — never a mix.
Sources

Where this sits in Build an LSM-tree storage engine (LevelDB / RocksDB style)

Scene 06 of 11, in the Compaction act — Levels, write amplification, the amp triangle.. A background process merges N immutable SSTables into 1, drops shadowed/deleted records, atomically swaps files. Foreground writes never block.

Up next. Compaction works. But how it picks WHICH files to merge — and how the survivors are organized on disk — is the central LSM design choice. Two strategies; two trade-offs.

All 11 scenes in Build an LSM-tree storage engine (LevelDB / RocksDB style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build an LSM-tree storage engine (LevelDB / RocksDB style) builds on the one before it.All 11 Build an LSM-tree storage engine (LevelDB / RocksDB style) scenes