Lab 08 — Complete Storage Engine

• What this lab builds
• Architecture
• Thread safety model
• WAL record format (lab08-specific)
  • Byte-level example: Put("name","Alice") at seqNum=5
  • Comparison with lab03 WriteBatch format
• write() execution trace: Put("city","London")
• flushImm lock-release pattern annotated
• compact() lock-release pattern annotated
• applyWALRecord: crash recovery filter annotated
• seqNum = 1 reservation: proof
• bgErr propagation
• Running the 27 tests
  • Test category summary
• Running the demo
• Tuning constants
  • Deriving the optimal flushThreshold
• FoundationDB parallel

What this lab builds

Lab 08 is a self-contained, complete storage engine — no imports from earlier labs. It re-implements every component (WAL, MemTable, skip list, SSTable, manifest, compaction) in a single package with production-quality thread safety, background error propagation, and API parity with the goleveldb interface.

All 7 subsystems are integrated:

Architecture

                  Writes                         Reads
                    │                              │
           ┌────────▼────────┐           ┌────────▼────────┐
           │  sync.Mutex     │           │  sync.Mutex     │
           │  (acquire)      │           │  (acquire)      │
           └────────┬────────┘           └────────┬────────┘
                    │                              │
           ┌────────▼────────┐     ┌──── snapshot mem/imm/l0/l1 pointers
           │ WAL.append(rec) │     │     └────────────────────────────────┐
           │ (fdatasync)     │     │      (release lock; I/O runs free)   │
           └────────┬────────┘     │                                      │
                    │              │      ┌──────────┐                    │
           ┌────────▼────────┐     │      │ MemTable │ ←── check mem      │
           │ MemTable.add    │     │      └──────────┘                    │
           │ (skip list)     │     │      ┌──────────┐                    │
           └────────┬────────┘     │      │ imm (opt)│ ←── check imm     │
                    │              │      └──────────┘                    │
           maybeFlushLocked        │      ┌──────────────────────┐        │
           (if mem ≥ 4 MiB):       │      │ L0 SSTables (newest) │ ←─────┘
           freeze mem → imm        │      │ L1 SSTables          │
           spawn flushImm goroutine└──────└──────────────────────┘
                    │
           ┌────────▼──────────────────────────────────────────────────┐
           │ Background goroutine: flushImm                             │
           │   newSSTBuilder → iterate imm → bld.finish() (fdatasync) │
           │   db.mu.Lock() → manifest.save() → db.imm=nil            │
           │   if len(L0) ≥ 4: spawn compact goroutine                │
           └───────────────────────────────────────────────────────────┘
                    │
           ┌────────▼──────────────────────────────────────────────────┐
           │ Background goroutine: compact                              │
           │   open L0+L1 readers (no lock)                            │
           │   newMergedIter → write new L1 SSTables (no lock)        │
           │   db.mu.Lock() → manifest update → manifest.save()       │
           │   delete old files (best-effort, no lock)                 │
           └───────────────────────────────────────────────────────────┘

Thread safety model

Lab 08 uses a single sync.Mutex (db.mu) to protect all mutable state:

Reads are not taken under db.mu for the actual disk I/O. The lock is held only long enough to snapshot the current pointers:

func (db *DB) Get(key []byte) ([]byte, bool) {
    db.mu.Lock()
    readSeq := db.seqNum - 1     // snapshot the seqNum
    mem := db.mem                // snapshot the pointer
    imm := db.imm                // snapshot the pointer (may be nil)
    l0 := append(...)            // shallow copy the file-name slice
    l1 := append(...)
    db.mu.Unlock()               // ← release BEFORE any disk I/O
    return db.getAt(key, readSeq, mem, imm, l0, l1)
}

This pattern — “lock, snapshot, unlock, then do I/O” — is the key to concurrent reads without blocking writers. Pointer snapshots are safe because:

• db.mem and db.imm point to immutable skip lists (frozen once handed to the flush goroutine).
• SSTable files are immutable once written.

Why not sync.RWMutex? Get holds the mutex for less than a microsecond (just to copy 4 pointers and a slice header), so the benefit of allowing multiple concurrent readers is negligible. The real concurrency comes from releasing the lock before I/O.

WAL record format (lab08-specific)

Lab 08’s WAL format is simpler than lab03’s WriteBatch format. Each record is a single key-value operation:

┌──────────────────────────────────────────────────────────────────────┐
│  8 bytes   │ 1 byte  │  4 bytes  │  key bytes  │  value bytes        │
│  seqNum LE │ keyType │  keyLen LE│             │                     │
└──────────────────────────────────────────────────────────────────────┘

Byte-level example: Put("name","Alice") at seqNum=5

Encoding:
  encodeWALRecord(5, typeValue, "name", "Alice")

  buf[0:8]  = 05 00 00 00 00 00 00 00   ← seqNum=5, little-endian uint64
  buf[8]    = 01                         ← typeValue=1
  buf[9:13] = 04 00 00 00               ← keyLen=4 (len("name")), LE uint32
  buf[13:17]= 6e 61 6d 65               ← "name" in ASCII
  buf[17:22]= 41 6c 69 63 65            ← "Alice" in ASCII (no length prefix!)

Total: 22 bytes.

Value has no length prefix. The entire suffix after buf[13+keyLen] is the value. This works because each WAL record is framed by the WAL layer (CRC + length header from lab01). The WAL frame tells the reader exactly how many bytes are in each record, so the value length = recordLen - 13 - keyLen.

Comparison with lab03 WriteBatch format

write() execution trace: Put("city","London")

Call: db.Put("city","London")
  → db.write(typeValue, "city", "London")

1.  db.mu.Lock()
    seq = db.seqNum         (e.g. 42)
    db.seqNum++             → db.seqNum = 43

2.  rec = encodeWALRecord(42, typeValue, "city", "London")
    = [2a 00 00 00 00 00 00 00   ← seqNum=42 LE
       01                         ← typeValue
       04 00 00 00               ← keyLen=4
       63 69 74 79               ← "city"
       4c 6f 6e 64 6f 6e]       ← "London"

3.  db.wal.append(rec):
    WAL frame: CRC32(rec) + len(rec) as 3-byte header + rec body
    Appended to CURRENT.wal; fdatasync() called.

4.  db.mem.add(42, typeValue, "city", "London"):
    Internal key = encodeInternalKey("city", 42, typeValue)
              = [63 69 74 79  01 2a 00 00 00 00 00 00]
    Skip list insert with this internal key.

5.  db.maybeFlushLocked()
    if db.mem.approximateSize() < 4 MiB: return (likely case)

6.  db.mu.Unlock()

Return nil (success)

flushImm lock-release pattern annotated

func (db *DB) flushImm(imm *memTable) {
    // ── Outside lock: allocate file number (atomic, not mutex) ──
    db.mu.Lock()
    num := db.nextFileNum.Add(1)   // atomic increment; no deadlock risk
    db.mu.Unlock()

    path := fmt.Sprintf("%s/%06d.sst", db.dir, num)

    // ── Outside lock: all SSTable I/O ──
    bld, err := newSSTBuilder(path)
    if err != nil { /* error path: set bgErr under lock, imm=nil */ }

    it := imm.newIter()           // imm is immutable; no lock needed to read it
    for it.valid() {
        bld.add(it.key(), it.value())   // sequential writes to .sst file
        it.next()
    }
    bld.finish()   // fdatasync — this is the expensive step
    bld.close()

    // ── Under lock: update manifest, clear imm slot ──
    db.mu.Lock()
    defer db.mu.Unlock()

    db.manifest.Levels[0] = append(db.manifest.Levels[0], path)
    db.manifest.NextSeq = db.seqNum     // checkpoint seqNum for crash recovery
    db.manifest.save()                  // write MANIFEST.tmp → rename atomically
    db.imm = nil                        // signal: flush complete, slot is free

    // Trigger compaction if L0 has grown too large:
    if len(db.manifest.Levels[0]) >= compactL0Trigger {
        db.bgWg.Add(1)
        go func() { defer db.bgWg.Done(); db.compact() }()
    }
}

Why is imm safe to read without a lock? Once db.imm = db.mem and db.mem = newMemTable() execute under the lock, imm is frozen — no writer will ever call imm.add() again. The flushImm goroutine is the only reader. Go’s memory model guarantees that the goroutine sees all writes to imm that happened before the goroutine was launched (the go statement acts as a synchronization point).

compact() lock-release pattern annotated

func (db *DB) compact() {
    // 1. Snapshot file lists under lock:
    db.mu.Lock()
    l0 := append([]string(nil), db.manifest.Levels[0]...)
    l1 := append([]string(nil), db.manifest.Levels[1]...)
    db.mu.Unlock()          // ← release lock before opening files

    // 2. Open all source SSTables (I/O, no lock):
    var sources []rawIter
    for _, p := range append(l0, l1...) {
        r, _ := openSST(p)
        sources = append(sources, r.newIter())
    }

    // 3. K-way merge + write new L1 files (I/O, no lock):
    mi := newMergedIter(sources)
    var newL1 []string
    // ... build new SSTables, dedup, drop tombstones ...

    // 4. Commit new L1 to manifest under lock:
    db.mu.Lock()
    db.manifest.Levels[0] = nil      // clear all L0
    db.manifest.Levels[1] = newL1   // replace L1
    db.manifest.NextSeq = db.seqNum
    db.manifest.save()
    db.mu.Unlock()

    // 5. Delete old files (best-effort, no lock):
    for _, p := range append(l0, l1...) { os.Remove(p) }
}

Steps 2 and 3 — which may take 50–200 ms for 16–32 MiB of data — run entirely without the lock. Writes continue freely to db.mem during this time. The lock is held for step 1 (~1 µs) and step 4 (~1 µs + manifest.save latency).

Is it safe to open L0 files while a flush might be adding to L0? Yes. compact() took a snapshot of l0 at step 1. Any new L0 files added after that snapshot are not in l0, so compact() does not open them. Those new files will be picked up by the next compaction.

applyWALRecord: crash recovery filter annotated

func (db *DB) applyWALRecord(rec []byte) error {
    // Decode the WAL record:
    seqNum := binary.LittleEndian.Uint64(rec[0:8])
    kt := keyType(rec[8])
    keyLen := binary.LittleEndian.Uint32(rec[9:13])
    key := rec[13 : 13+keyLen]
    value := rec[13+keyLen:]

    // KEY INSIGHT: Skip records already captured in SSTables.
    // manifest.NextSeq is the seqNum that was live when the last flush
    // completed.  Any WAL record with seqNum < NextSeq is already
    // represented in an SSTable.  Replaying it would add a duplicate
    // version to the MemTable — harmless but wasteful.
    if seqNum < db.manifest.NextSeq {
        return nil   // already in an SSTable; skip
    }

    db.mem.add(seqNum, kt, key, value)
    if seqNum >= db.seqNum {
        db.seqNum = seqNum + 1   // advance seqNum past the replayed record
    }
    return nil
}

The crash scenario this handles:

1. Write seqNums 1..100 → all in CURRENT.wal
2. Flush triggered: flushImm writes seqNums 1..100 to 000003.sst
3. MANIFEST saved with NextSeq=101
4. CURRENT.wal still exists (not deleted yet)
5. CRASH

On reopen:
  manifest.NextSeq = 101
  WAL replay: reads records 1..100 from CURRENT.wal
  applyWALRecord: seqNum < 101 → skip (all 100 records)
  MemTable is empty after replay — correct!
  All data is in 000003.sst, found via MANIFEST.

Without the seqNum < manifest.NextSeq guard, recovery would add duplicate versions of every key to the MemTable, causing a second flush to generate a duplicate SSTable. The MergedIterator’s dedup would still return correct answers, but at higher cost.

seqNum = 1 reservation: proof

if db.seqNum == 0 {
    db.seqNum = 1  // reserve 0 so empty-DB snapshots see nothing
}

GetSnapshot() returns snap.seqNum = db.seqNum - 1. If db.seqNum = 0:

snap.seqNum = db.seqNum - 1 = 0 - 1 = uint64 max = 18446744073709551615

A snapshot with readSeq = MaxUint64 would see every record ever written including future ones — incorrect. By starting at 1:

db.seqNum = 1 → snap.seqNum = 0
All stored records have seqNum ≥ 1.
MergedIterator filter: seqNum ≤ 0 → false → no records visible.
Empty-DB snapshot correctly sees nothing. ✓

bgErr propagation

Background goroutines (flushImm, compact) can encounter I/O errors — disk full, permissions failure, corrupt state. The error is stored in db.bgErr under db.mu and then checked by the next write operation:

func (db *DB) write(kt keyType, key, value []byte) error {
    db.mu.Lock()
    defer db.mu.Unlock()

    if db.bgErr != nil {
        return db.bgErr   // surface background error to the next writer
    }
    // ... rest of write path ...
}

This is analogous to Go’s error-channel pattern: the background goroutine communicates failure to the foreground, which returns the error to the caller. The database is then in a degraded state and should be closed.

In production engines (RocksDB), background errors are additionally exposed via a StatusCode that the user can query at any time, and some errors trigger automatic recovery (retry the flush, skip the corrupt file, etc.).

Running the 27 tests

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

Expected output (abbreviated):

--- PASS: TestOpenClose (0.00s)
--- PASS: TestPutGet (0.01s)
--- PASS: TestDelete (0.00s)
--- PASS: TestPersistenceAcrossReopen (0.05s)
--- PASS: TestIteratorOrder (0.00s)
--- PASS: TestSnapshotIsolation (0.00s)
--- PASS: TestSnapshotIterator (0.00s)
--- PASS: TestFlushAndReopen (0.05s)
--- PASS: TestCompaction (0.18s)
--- PASS: TestCompactionDeduplicates (0.21s)
--- PASS: TestTombstoneNotVisible (0.08s)
--- PASS: TestConcurrentWrites (0.09s)
--- PASS: TestConcurrentReads (0.04s)
--- PASS: TestWriteAfterClose (0.00s)
--- PASS: TestManifestRecovery (0.06s)
--- PASS: TestWALCrashRecovery (0.04s)
--- PASS: TestSnapshotRelease (0.00s)
--- PASS: TestReadYourWrites (0.00s)
--- PASS: TestLargeValues (0.02s)
--- PASS: TestManyFlushes (0.52s)
--- PASS: TestScanRange (0.01s)
--- PASS: TestSnapshotScanIsolation (0.01s)
--- PASS: TestOverwriteKey (0.01s)
--- PASS: TestDeleteNonExistent (0.00s)
--- PASS: TestBgErrSurfaces (0.00s)
--- PASS: TestCompactProducesNonOverlappingL1 (0.19s)
--- PASS: TestSeqNumRestoredAfterReopen (0.03s)
ok      github.com/10xdev/leveldb/lab08

Test category summary

Run with -race to also validate the thread safety model:

go test ./lab08/... -race -count=1

Running the demo

go run ./lab08/demo

The demo runs six scenarios:

1. Basic Put/Get/Delete — confirms the core API works.
2. Sorted iteration — writes 10 out-of-order keys, iterates and verifies they come back in sorted order.
3. Snapshot isolation — takes a snapshot, writes new values, verifies the snapshot still sees old values.
4. Persistence across reopen — writes keys, closes DB, reopens, reads back.
5. Write throughput — writes 5,000 keys × 256 bytes and reports keys/s.
6. Snapshot iterator — range scan using a snapshot.

Tuning constants

Deriving the optimal flushThreshold

Assume:

• Target L0 compaction frequency: once per minute.
• Write rate: 50 MB/s (NVMe with group commit).
• Time between flushes: 4 MiB / 50 MB/s = 80 ms — too frequent.

For 1-minute intervals: threshold = 50 MB/s × 60s = 3 GB — use 3 GiB. But this requires 3 GiB of RAM just for the MemTable. Real systems use a write buffer size of 64 MiB–1 GiB, trading compaction frequency for RAM.

FoundationDB parallel

Lab 08 is the complete equivalent of what runs inside a single FDB storage server — minus network replication. FDB adds:

• Distributed WAL: the transaction log is striped across 3+ log servers. Every commit is acknowledged only after a majority of log servers have durably written the entry. Our wal.append + fdatasync is the single-node version of this quorum write.

• Sharding: key ranges are partitioned across many storage servers. Each storage server runs an instance of exactly the engine we built here. The data distributor rebalances shards when a server is overloaded or a server fails.

• Flow and simulation testing: FDB is written in a cooperative threading model called Flow, which enables the simulator to inject arbitrary network delays, disk failures, and process crashes at any point in execution — and verify that the database is always consistent. Our go test -race is a pale shadow of this: it detects data races but not logical consistency under failure.

• Conflict detection: FDB’s proxy checks at commit time whether the transaction’s read set was modified by a concurrent committed transaction. Our MVCC allows concurrent writes to the same key; FDB rejects them and requires the client to retry with the new value.

• Redwood storage engine: FDB’s modern storage engine is a B+-tree with versioned pages, replacing the older SQLite-based storage. The internal key encoding (key || version) is identical in concept to our userKey || (seqNum<<8 | keyType).