Compaction and Recovery¶

What this page covers¶

Three mechanisms keep an LSM engine correct and bounded over time:

1. Flush turns a full memtable into an L0 table.
2. Compaction merges tables, discarding overwritten values and deleted keys, so reads do not have to check ever more files and disk space does not grow without bound.
3. Versions and the MANIFEST record which tables are live, so that after a crash the engine knows exactly which files make up the database — and readers never lose a file they are using.

Write amplification theory is in Write Amplification; this page is the implementation and its measured behaviour.

Versions: an immutable list of live tables¶

// tableFile is an open SSTable shared by every version that lists it.
type tableFile struct {
    meta     fileMeta     // number, size, smallest and largest internal key
    path     string
    f        *os.File
    t        *Table
    refs     atomic.Int32
    obsolete atomic.Bool  // removed from the current version by an edit
}

func (tf *tableFile) unref() {
    if tf.refs.Add(-1) == 0 {
        tf.f.Close()
        if tf.obsolete.Load() {
            os.Remove(tf.path) // no version can reach it any more
        }
    }
}

// version is an immutable list of live tables per level.
type version struct {
    levels [numLevels][]*tableFile // L0: newest first, may overlap. L1: sorted, disjoint
    refs   atomic.Int32
}

Every change to the set of tables produces a new version; the old one is never modified. A version holds a reference on each of its tables; the DB holds a reference on the current version; every read and iterator holds a reference on the version it started with. When compaction replaces tables A and B with C:

1. The new version lists C instead of A and B; A and B are marked obsolete.
2. The DB switches cur to the new version and drops its reference to the old one.
3. If no reader holds the old version, its refcount hits zero, it releases A and B, their refcounts hit zero, and the files are closed and deleted. If an iterator still holds the old version, A and B stay readable until it is closed.

This is the same pattern as RCU and epoch-based reclamation (Lock-Free Programming and Memory Reclamation): publish a new immutable snapshot, reclaim the old one when the last reader leaves. The Go GC handles the memory; reference counting is still needed for the files, because the GC knows nothing about disk space or file descriptors.

Version edits and the MANIFEST¶

A version is never written to disk whole. Instead, each change is a version edit, appended to the MANIFEST (using the same log format as the WAL):

type versionEdit struct {
    logNum, nextFile, lastSeq uint64 // engine state as of this edit
    hasLog, hasNext, hasSeq   bool
    added                     []levelFile // (level, file metadata)
    deleted                   []levelFile // (level, file number)
}

The current state is the replay of all edits. logAndApply makes an edit durable, then installs it:

func (db *DB) logAndApply(e *versionEdit, newTables []*tableFile) error {
    if err := syncDir(db.dir); err != nil { // directory entries of the new .sst files
        return err
    }
    db.mu.Lock()
    e.nextFile, e.hasNext = db.nextFile, true
    e.lastSeq, e.hasSeq = db.lastSeq.Load(), true
    base := db.cur
    db.mu.Unlock()
    if err := db.manw.AddRecord(e.encode()); err != nil {
        return err
    }
    if err := db.manifest.Sync(); err != nil { // the commit point
        return err
    }
    nv := applyEdit(base, e, newTables)
    db.mu.Lock()
    old := db.cur
    db.cur = nv
    db.mu.Unlock()
    old.unref()
    return nil
}

The ordering is the whole crash-safety argument:

The edit is the commit point, exactly like a transaction's commit record. Only the background goroutine calls logAndApply, so edits are serialized without holding the DB mutex across the fsync.

Flush¶

func (db *DB) flush(imm *MemTable, logNum uint64) error {
    out, err := db.startTable() // new file number, TableWriter
    if err != nil {
        return err
    }
    it := imm.sl.Iter()
    for it.First(); it.Valid(); it.Next() {
        out.add(it.Key(), it.Value())
    }
    if err := db.finishTable(out); err != nil { // Finish, fsync, reopen for reading
        return err
    }
    e := &versionEdit{logNum: logNum, hasLog: true} // logs older than logNum are now redundant
    e.added = []levelFile{{0, out.tf.meta}}
    return db.logAndApply(e, []*tableFile{out.tf})
}

The edit's logNum says "all data in logs numbered below this is now in tables". After it commits, older .log files are deleted. The background goroutine clears db.imm only after the new version is installed, so a reader always finds the data either in imm or in the new table — possibly both for a moment, which is harmless.

Compaction¶

L0 tables are flushed memtables: each covers an arbitrary key range, so they overlap, and a lookup may need to check every one. When L0 reaches 4 tables, the background goroutine merges all of L0 with the overlapping L1 tables into new, disjoint L1 tables:

The merge uses the merging iterator from Iterators, Snapshots, and Transactions, which yields all entries in internal-key order: for each user key, the newest version first. The drop rules:

for m.First(); m.Valid(); m.Next() {
    k := m.Key()
    uk, seq, t := ukey(k), trailer(k)>>8, ValueType(trailer(k)&0xff)
    if curKey == nil || !bytes.Equal(uk, curKey) { // first (newest) entry of a new user key
        curKey = append(curKey[:0], uk...)
        lastSeqForKey = maxSeq
        // cut a new output file here if the current one is big enough
    }
    drop := false
    switch {
    case lastSeqForKey <= oldest:
        drop = true // a newer entry for this key is visible to every reader
    case t == TypeDeletion && seq <= oldest:
        drop = true // a tombstone at the bottom level shadows nothing
    }
    lastSeqForKey = seq
    if !drop {
        out.add(k, m.Value())
    }
}

oldest is the oldest live snapshot (or the latest sequence if none). The rules, in words:

1. Shadowed versions. If a newer version of this key already exists with a sequence every reader can see (≤ oldest), no reader can ever see this older one. Drop it. If the newer version's sequence is above the oldest snapshot, that snapshot cannot see the newer version and still reads this one — keep it.
2. Tombstones at the bottom. A deletion marker exists only to shadow older values in lower levels. L1 is the bottom level here, and all overlapping L1 tables are compaction inputs, so nothing older can exist below: drop the tombstone too, once every reader can see it. In a multi-level engine, a tombstone can only be dropped when no deeper level contains the key's range.
3. Output files are cut only between user keys, so all versions of one key stay in one L1 table and "at most one L1 table contains a key" remains true for Get.

Measured write amplification¶

1 M random writes (13-byte keys, 100-byte values = 107 MB of user data), 4 MB memtables, over three key-space sizes:

Every byte is written at least twice (WAL + flush). Compaction cost depends on how big L1 is: with 20,000 keys L1 stays around 2 MB, and merging into it is cheap; with 2 M keys, each of the 10 compactions rewrites nearly all of L1 (random keys overlap every L1 file), and L1 keeps growing. In a two-level design, compaction cost per write grows linearly with database size — unbounded.

That is the reason real engines have multiple levels with a fixed size ratio (LevelDB/RocksDB: each level 10x the previous): a compaction from Lₙ into Lₙ₊₁ touches about 10 tables of Lₙ₊₁ per table of Lₙ, regardless of total size, so write amplification is roughly ratio × number of levels — about 10–30x, but logarithmic in data size instead of linear. Tiered compaction (Cassandra's STCS, RocksDB's universal) trades lower write amplification for more overlapping files and higher read and space amplification (LSM Tree).

Write stalls¶

If writes arrive faster than flush and compaction can absorb:

• The memtable fills while the previous one is still being flushed → the commit goroutine waits (cond.Wait() while imm != nil).
• L0 accumulates tables because compaction is behind → reads slow down (more tables to check); at 12 L0 tables the engine stops writes until compaction catches up.

case db.imm != nil, len(db.cur.levels[0]) >= l0StopWritesTrigger:
    db.cond.Wait() // stall: the background goroutine is behind

Stalls are backpressure, not a bug: the alternative is unbounded L0 growth and read latency that degrades until the system falls over. Production engines add a slowdown stage before the stop (RocksDB delays each write by a little once L0 passes a threshold) so latency degrades smoothly instead of hitting a wall. Stall time is one of the most important metrics to export from any LSM-based system.

Recovery¶

Open rebuilds the state after a clean shutdown or a crash:

Writing a fresh manifest at every open keeps the MANIFEST from growing forever (it would otherwise accumulate every edit since the database was created). Its first record is a snapshot edit listing all live tables; switching CURRENT to it is atomic.

Files left behind by a crash — a half-written .sst from an interrupted flush, a log already covered by a flush — are not referenced by the recovered version and are simply deleted.

Common pitfall¶

Dropping a tombstone too early. A compaction from L1 into L2 in a multi-level engine sees Delete(k) at sequence 900 and no older version of k among its inputs, and drops the tombstone "because it shadows nothing". But L3 — not part of this compaction — still holds Put(k, v) from sequence 100. With the tombstone gone, the old value resurrects: a key the application deleted reappears. The rule is that a tombstone may be dropped only if no level below the output level can contain the key — LevelDB checks this with IsBaseLevelForKey against the key ranges of deeper levels. Deleted data coming back is one of the most damaging bugs a storage engine can have, and the model-based tests in Testing and Benchmarking exist to catch it: delete keys, force compactions, and check they stay deleted.

Review questions¶

1. Why does a new version get created for every change instead of modifying the current one?
2. What is the commit point of a flush or compaction, and what happens to files written before it if the process crashes?
3. State the two drop rules for compaction. When must an older version of a key be kept even though a newer one exists?
4. Why did write amplification grow from 2.2x to 6.6x as the key space grew, and how do multi-level engines bound it?
5. Why does Open write a new MANIFEST instead of appending to the old one?