Lab 05 — MemTable Flush to L0

• What this lab adds
• Concept: Double-buffering (active + immutable MemTable)
  • Write stall: when double-buffering is insufficient
• Concept: WAL rotation
  • WAL segment lifecycle and crash safety
• Concept: Atomic file rename
• Manifest format
• Read path: mem → imm → L0 (newest first)
  • Read amplification in L0
• maybeFlush annotated
• flushImmutable annotated
• Running the tests
  • TestFlushTriggered walkthrough
  • TestCrashAfterFlush
  • TestManifestRecovery
• Running the demo
• FoundationDB parallel

What this lab adds

Labs 01–04 can now write durable SSTables. Lab 05 wires the flush trigger into the write path, making the engine self-managing:

1. Each Put/Delete appends to the WAL and updates the active MemTable.
2. After every write, maybeFlush() checks mem.ApproximateSize().
3. When the active MemTable exceeds FlushThreshold (4 MiB), it is frozen into the “immutable” MemTable (db.imm), a fresh MemTable and new WAL segment take over all new writes, and a background goroutine writes imm to a new L0 SSTable.
4. After the flush completes, the SSTable path is written to the MANIFEST (atomically via rename), imm is set to nil, and the old WAL segment is deleted — its data is now safely persisted in the SSTable.

After Close, all acknowledged data is on disk in SSTables. On Open, only the current CURRENT.wal is replayed; SSTables are read directly.

Concept: Double-buffering (active + immutable MemTable)

Flushing 4 MiB to an NVMe drive takes ~4 ms. Flushing to an HDD can take hundreds of milliseconds. If writes had to pause while the flush ran, the throughput would drop to zero for the duration of every flush cycle.

Double-buffering eliminates this stall by maintaining two MemTable slots:

Normal state (no flush in progress):
  db.mem = active MemTable    ←── all writes land here
  db.imm = nil

Flush triggered (mem.ApproximateSize() >= 4 MiB):
  db.imm = old db.mem         ←── frozen; background goroutine drains this
  db.mem = new empty MemTable ←── writes continue here immediately
  db.wal = new WAL segment    ←── new writes go to CURRENT.wal

Background flush completes:
  SSTable written to 000003.sst
  MANIFEST updated
  db.imm = nil                ←── released
  old WAL segment deleted

The write path holds db.mu only for the pointer swap (microseconds), not for the flush I/O (milliseconds). The background goroutine holds no lock during disk I/O; it acquires the lock only to update db.imm and db.manifest.

Write stall: when double-buffering is insufficient

If db.mem fills again before db.imm is flushed, maybeFlush() finds db.imm != nil and does nothing — the write proceeds, but db.mem can grow unboundedly. In production engines, writes are stalled (blocked) until the flush completes. Our implementation skips the stall for clarity:

func (db *DB) maybeFlush() {
    if db.imm != nil || db.mem.ApproximateSize() < FlushThreshold {
        return   // imm != nil: flush in progress, do not freeze again yet
    }
    // ... freeze and launch background flush ...
}

RocksDB’s WriteStallCondition is triggered at 2 × FlushThreshold and blocks the caller until the flush completes.

Concept: WAL rotation

Each MemTable is associated with exactly one WAL segment. When the active MemTable is frozen:

Before freeze:
  db.mem   = MemTable A   (contains writes at seqNum 100..199)
  db.wal   = CURRENT.wal  (contains the WAL records for writes 100..199)

During freeze (under db.mu):
  1. db.imm  = MemTable A           (hand off to background flush)
  2. db.mem  = new MemTable B       (empty; will receive writes 200+)
  3. Close CURRENT.wal
  4. Rename CURRENT.wal → 000003.wal  (numbered = belongs to MemTable A)
  5. Open new CURRENT.wal             (for MemTable B's writes)

After flush completes:
  000003.sst written (contains MemTable A's data, durable)
  000003.wal deleted  (MemTable A's data is in the SSTable; WAL no longer needed)

This bounds WAL disk usage: at most one numbered WAL (being flushed) plus the current CURRENT.wal exist simultaneously. Total WAL disk usage ≤ 2 × FlushThreshold = 8 MiB.

WAL segment lifecycle and crash safety

Our simplified recovery only replays CURRENT.wal. Full recovery from numbered WALs is left as an exercise (lab 08 includes it).

Concept: Atomic file rename

The MANIFEST records which SSTable files exist. If the manifest were written in place and the process crashed mid-write, the manifest would be partially updated — some SSTable entries might be missing or corrupt.

POSIX rename(src, dst) is atomic with respect to crashes: any observer (including a crash recovery process) sees either the old file at dst or the new file at dst — never a partially-written intermediate.

func (m *Manifest) Save() error {
    data, _ := json.MarshalIndent(m, "", "  ")

    // 1. Write new content to a temporary file:
    tmp := m.dir + "/MANIFEST.tmp"
    os.WriteFile(tmp, data, 0o644)
    // Crash here: MANIFEST.tmp may be partial; MANIFEST is still the old valid copy.

    // 2. Rename atomically:
    return os.Rename(tmp, m.dir+"/MANIFEST")
    // After this returns: MANIFEST is the new file.
    // Crash during rename: either old or new MANIFEST, never partial.
}

Why not just write to MANIFEST directly?

WRONG:  os.WriteFile(dir+"/MANIFEST", data, 0644)
  → If data is 1 KB and the OS writes in 512-byte chunks:
    Chunk 1 written, crash → MANIFEST has 512 bytes of new data + rest of old data
    → corrupt manifest → all SSTable paths lost → data loss

The write-to-tmp + rename pattern is used in LevelDB, RocksDB, PostgreSQL, and almost every production database for this exact reason.

Manifest format

{
  "levels": [
    ["data/000003.sst", "data/000006.sst"],  ← L0: oldest first (newest = index -1)
    []                                        ← L1: empty until lab06
  ]
}

Written to MANIFEST.tmp then atomically renamed to MANIFEST. On Open, Load reads this file to know which SSTs to open.

Read path: mem → imm → L0 (newest first)

func (db *DB) Get(key []byte) ([]byte, bool) {
    db.mu.Lock()
    mem := db.mem                  // snapshot pointer
    imm := db.imm                  // snapshot pointer (may be nil)
    l0 := db.manifest.Levels[0]   // copy slice header
    seq := db.seqNum
    db.mu.Unlock()                 // release lock before any I/O

    // 1. Check active MemTable (most recent writes):
    if v, ok := mem.Get(key, seq); ok {
        return v, true
    }
    // 2. Check immutable MemTable (being flushed; still has data not yet on disk):
    if imm != nil {
        if v, ok := imm.Get(key, seq); ok {
            return v, true
        }
    }
    // 3. Search L0 SSTables newest-first:
    for i := len(l0) - 1; i >= 0; i-- {
        r, _ := lab04.Open(l0[i])
        ikey := lab02.EncodeInternalKey(key, seq, lab02.TypeValue)
        v, ok := r.Get(ikey)
        r.Close()
        if ok {
            _, _, kt := lab02.DecodeInternalKey(ikey)
            if kt == lab02.TypeDelete { return nil, false }
            return v, true
        }
    }
    return nil, false
}

Why search L0 newest-first? L0 files are produced by independent flushes and may have overlapping key ranges. Two L0 files can both contain key “apple” at different seqNums. The newest file (highest file number) was produced from the most recently flushed MemTable and contains the highest seqNums — so it wins.

If we searched oldest-first, we might return a stale value from an older file and miss the newer value in a later file.

Read amplification in L0

With 4 L0 files, a Get for a missing key opens, reads, and closes 4 SSTable files — 4 disk seeks. With 16 L0 files, it’s 16 disk seeks. This is read amplification: the number of files grows linearly with the number of flushes. Lab 06 compaction controls this by merging L0 files into non-overlapping L1 files, reducing Get at L1 to exactly 1 file regardless of how many records were written.

maybeFlush annotated

func (db *DB) maybeFlush() {
    // Guard: don't trigger a second flush if one is already in progress.
    if db.imm != nil || db.mem.ApproximateSize() < FlushThreshold {
        return
    }

    // Freeze the current MemTable:
    db.imm = db.mem
    db.mem = lab02.NewMemTable()   // fresh MemTable for new writes

    // Rotate the WAL:
    db.wal.Close()
    walPath := fmt.Sprintf("%s/%06d.wal", db.dir, db.nextFileNum.Add(1))
    if wal, err := lab01.Open(walPath); err == nil {
        db.wal = wal   // new writes go to this segment
    }

    // Launch the background flush goroutine:
    imm := db.imm   // capture pointer before releasing lock
    db.flushWg.Add(1)
    go func() {
        defer db.flushWg.Done()
        db.flushImmutable(imm)
    }()
}

maybeFlush is always called under db.mu. The goroutine it spawns must re-acquire db.mu when updating db.imm and db.manifest after the flush.

flushImmutable annotated

func (db *DB) flushImmutable(imm *lab02.MemTable) {
    // 1. Assign a file number and build the SSTable:
    num := db.nextFileNum.Add(1)   // atomic increment, no lock needed
    path := fmt.Sprintf("%s/%06d.sst", db.dir, num)

    bld, _ := lab04.NewBuilder(path)
    it := imm.NewIterator()         // iterate all internal keys in sorted order
    for ; it.Valid(); it.Next() {
        bld.Add(it.Key(), it.Value())
    }
    bld.Finish()   // writes index + footer + fdatasync
    bld.Close()
    // At this point: 000NNN.sst is durable on disk.

    // 2. Update the manifest and release the immutable MemTable:
    db.mu.Lock()
    db.manifest.AddL0(path)   // add SST path to L0 list
    db.manifest.Save()        // write MANIFEST.tmp → rename to MANIFEST
    db.imm = nil              // signal: flush complete, slot is free
    db.mu.Unlock()
    // db.mu not held during bld.Finish() — the slow I/O runs concurrently
    // with ongoing writes to db.mem.
}

The critical insight: db.mu is held for the in-memory pointer swap (step 2) but not during the multi-millisecond SSTable write (step 1). This ensures the write path is never blocked waiting for disk I/O.

Running the tests

cd leveldb
go test ./lab05/... -v -count=1

Expected output:

=== RUN   TestFlushTriggered
--- PASS: TestFlushTriggered (0.07s)
=== RUN   TestReadAfterFlush
--- PASS: TestReadAfterFlush (0.06s)
=== RUN   TestCrashAfterFlush
--- PASS: TestCrashAfterFlush (0.07s)
=== RUN   TestManifestRecovery
--- PASS: TestManifestRecovery (0.07s)
PASS
ok      github.com/10xdev/leveldb/lab05

TestFlushTriggered walkthrough

Writes enough data to exceed FlushThreshold (4 MiB). Calls db.Close() which calls db.flushWg.Wait() to ensure the background goroutine has completed. Then checks that db.manifest.Levels[0] is non-empty — at least one L0 SSTable was created.

TestCrashAfterFlush

1. Write data, flush (via Close).
2. Delete CURRENT.wal (simulate crash after WAL was truncated).
3. Reopen the DB.
4. Verify all data is still readable from L0 SSTables.

This proves that data in a completed SSTable is durable even if the WAL is lost.

TestManifestRecovery

1. Write 10 keys, close.
2. Open again — MANIFEST lists the L0 SSTable.
3. Read back all 10 keys.
4. Verify they come from the SSTable, not a WAL (WAL is empty after close).

Running the demo

go run ./lab05/demo

Expected output:

writing 10000 records …
flush triggered (mem > 4 MiB) — background flush running
closed; reopened
read after reopen: key000000 = val000000  ✓
…

FoundationDB parallel

In FDB, the equivalent of our flush goroutine is the storage server applying mutations from the transaction log to its B-tree. The storage server runs continuously; our flush goroutine is a simplified version of the same concept — batching writes into an immutable snapshot and writing them to a durable file.

The key difference: FDB’s storage server applies writes incrementally as transactions commit (one page update per transaction), whereas our flush writes an entire 4 MiB MemTable at once. FDB’s approach has lower latency for the first read after a write; our approach has lower per-write overhead.

FDB’s equivalent of the MANIFEST is the coordinator state, recording the current cluster topology and which storage servers own which key ranges. Coordinator state is also updated atomically (via Paxos) and replicated across multiple coordinator processes for fault tolerance — a distributed version of our write-to-tmp + rename pattern.