Lab 03 — Write Path: WAL → MemTable + Crash Recovery

• What this lab adds
• Concept: Why WAL-first is necessary
  • The single-threaded write problem
  • WAL-first: the correct order
  • The four safety windows
• Concept: Write Batches and Atomicity
  • Why batching is needed
  • Sequence number assignment at batch granularity
• WriteBatch data structure
• WriteBatch wire format
  • Encode() annotated
  • Byte-level example: Put("name", "Alice") at seqNum=1
  • Byte-level example: two-op batch
• Decode(): a parse state machine
• Replay(): applying the batch to the MemTable
• The DB struct: field anatomy
  • seqNum: the MVCC clock
  • sync.Mutex: what it protects
• DB.Put execution trace: end to end
• recoverFromWAL: how the MemTable is rebuilt
  • seqNum reconstruction during recovery
  • WAL framing from lab 01: what Recover actually reads
• Crash scenarios: byte-level analysis
• Group commit: the missing optimisation
• Running the tests
  • TestCrashRecovery walkthrough
  • TestBatchWrite walkthrough
• Running the demo
• FoundationDB parallel

What this lab adds

Labs 01 and 02 built the two durable pieces separately:

• Lab 01: the WAL — a CRC-framed append-only log on disk
• Lab 02: the MemTable + MVCC — an in-memory sorted skip list with versioned keys

Lab 03 wires them together into a working durable key-value store:

1. Every Put / Delete is first serialised into a WriteBatch.
2. The batch is appended to the WAL (lab 01) before touching memory.
3. The batch is replayed into the MemTable (lab 02).
4. On Open, any existing WAL is replayed from start to finish, rebuilding the MemTable — so a crash loses nothing that was acknowledged.

The result is a store that survives crashes with no data loss for any operation that returned successfully to the caller.

Concept: Why WAL-first is necessary

The single-threaded write problem

Consider a naïve implementation that writes to memory first, then WAL:

WRONG ORDER:
  1. mem.Add(seqNum, TypeValue, key, value)   ← in-memory only
  2. wal.Append(encoded)                      ← power fails here
  3. seqNum++

If power fails at step 2, the value is in memory but not on disk. On the next Open, the WAL is empty — the write is silently lost. The caller received no error and has no way to know the data is gone.

WAL-first: the correct order

CORRECT ORDER:
  1. wal.Append(encoded)        ← write to disk, fsync
     (power can fail here safely — WAL record not complete, nothing was acked)
  2. mem.Add(...)               ← apply to memory
  3. seqNum++

If power fails during step 1 (mid-write), the WAL record is either absent or has a bad CRC. The lab-01 Recover function stops at the first corrupt record. No acknowledgement was sent to the caller (because wal.Append had not returned), so no data is lost from the caller’s perspective.

If power fails after step 1 completes, recovery replays the record and re-applies it to the MemTable. The caller’s Put had returned successfully, so the data is properly durable.

The four safety windows

Timeline of a single Put("name", "Alice"):

  T0  ──── applyBatch called ──────────────────────────────────────────────
  T1  │    b.Encode() → []byte                   (in memory, no I/O)
  T2  │    wal.Append(bytes) ─────────────────── CRASH SAFE: nothing acked
  T3  │      pwrite(fd, header+payload, ...)      (kernel buffer)
  T4  │      fdatasync(fd)                        (durable on disk)  ←── T4
  T5  │    b.Replay(mem)                          (MemTable updated)
  T6  │    db.seqNum++                            (MVCC clock advanced)
  T7  ──── applyBatch returns (caller acked) ─────────────────────────────

This table proves that WAL-first gives at-least-once application of every acknowledged write. Exactly-once is guaranteed by internal key uniqueness: the MemTable deduplicates on internal key, so replaying the same write twice produces the same result.

Concept: Write Batches and Atomicity

Why batching is needed

A WriteBatch groups one or more operations that must appear atomically: either all are visible, or none are. Without batching, a multi-key update that is interrupted mid-way leaves the database in a partially-updated state.

Bank transfer example:

Without batching (WRONG — can be interrupted between writes):
  db.Put([]byte("account:A"), newBalanceA)   ← WAL record 1 — durable
  db.Put([]byte("account:B"), newBalanceB)   ← power fails here!
  → account A debited, account B not credited — money disappears

With batching (CORRECT — both or neither):
  b := &WriteBatch{}
  b.Put([]byte("account:A"), newBalanceA)
  b.Put([]byte("account:B"), newBalanceB)
  db.Write(b)
  → single WAL record; recovery replays both or neither

Sequence number assignment at batch granularity

Sequence numbers are assigned at the batch level: all operations in a batch share the same SeqNum. This means every key in a batch becomes visible simultaneously at the same seqNum — which is the atomic boundary.

Batch at seqNum=100 with 3 ops:
  op[0]: Put("k1", "v1")  → MemTable: internal key ("k1", seq=100, TypeValue)
  op[1]: Put("k2", "v2")  → MemTable: internal key ("k2", seq=100, TypeValue)
  op[2]: Delete("k3")     → MemTable: internal key ("k3", seq=100, TypeDelete)
  → db.seqNum advances from 100 to 101 after the batch

A reader at readSeq=99 sees none of them. A reader at readSeq=100 sees all three. There is no intermediate state where some operations are visible and others are not.

Note: our current DB.Put wraps a single operation per batch and advances seqNum by 1. The DB.Write API allows multi-op batches. The test TestBatchWrite exercises this path.

WriteBatch data structure

// batchOp is a single operation inside a WriteBatch.
type batchOp struct {
    del bool     // true = Delete; false = Put
    key []byte
    val []byte   // nil for Delete
}

// WriteBatch accumulates operations that will be applied atomically.
type WriteBatch struct {
    SeqNum uint64    // assigned by DB.applyBatch just before encoding
    ops    []batchOp // slice grows as Put/Delete are called
}

Put and Delete simply append to ops:

func (b *WriteBatch) Put(key, value []byte) {
    b.ops = append(b.ops, batchOp{key: key, val: value})
}

func (b *WriteBatch) Delete(key []byte) {
    b.ops = append(b.ops, batchOp{del: true, key: key})
}

The batch carries no locks and performs no I/O. It is a pure in-memory accumulator until DB.Write (or DB.Put / DB.Delete) calls applyBatch.

WriteBatch wire format

A WriteBatch is serialised to bytes before being handed to the WAL. The format is a fixed 12-byte header followed by one record per operation:

┌─────────────────────────────────────────────────────────────────────┐
│                      12-byte header                                  │
│  seqNum   (8 bytes, little-endian uint64)                           │
│  count    (4 bytes, little-endian uint32)  ← number of ops          │
├─────────────────────────────────────────────────────────────────────┤
│  op record 0:                                                        │
│    type   (1 byte)  'p' = Put (0x70), 'd' = Delete (0x64)           │
│    kLen   (4 bytes, little-endian uint32)                            │
│    key    (kLen bytes)                                               │
│    vLen   (4 bytes, little-endian uint32)  ← Put only               │
│    value  (vLen bytes)                     ← Put only               │
├─────────────────────────────────────────────────────────────────────┤
│  op record 1 ...                                                     │
│  op record N-1 ...                                                   │
└─────────────────────────────────────────────────────────────────────┘

Encode() annotated

func (b *WriteBatch) Encode() []byte {
    // Pre-calculate total size to avoid reallocations:
    sz := 8 + 4   // header: 8B seqNum + 4B count
    for _, op := range b.ops {
        sz += 1 + 4 + len(op.key)   // type byte + 4B key length + key bytes
        if !op.del {
            sz += 4 + len(op.val)   // 4B value length + value bytes (Put only)
        }
    }
    buf := make([]byte, 0, sz)      // single allocation, exact capacity

    // Write 12-byte header:
    var hdr [12]byte
    binary.LittleEndian.PutUint64(hdr[0:8], b.SeqNum)    // bytes 0-7
    binary.LittleEndian.PutUint32(hdr[8:12], uint32(len(b.ops))) // bytes 8-11
    buf = append(buf, hdr[:]...)

    // Write each operation record:
    for _, op := range b.ops {
        if op.del {
            buf = append(buf, 'd')  // 0x64
        } else {
            buf = append(buf, 'p')  // 0x70
        }
        var klen [4]byte
        binary.LittleEndian.PutUint32(klen[:], uint32(len(op.key)))
        buf = append(buf, klen[:]...)
        buf = append(buf, op.key...)
        if !op.del {
            var vlen [4]byte
            binary.LittleEndian.PutUint32(vlen[:], uint32(len(op.val)))
            buf = append(buf, vlen[:]...)
            buf = append(buf, op.val...)
        }
    }
    return buf
}

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

Input:
  SeqNum = 1
  ops[0] = {del: false, key: "name", val: "Alice"}

Computation:
  seqNum=1:      little-endian uint64 = 01 00 00 00 00 00 00 00
  count=1:       little-endian uint32 = 01 00 00 00
  type='p':      0x70
  kLen=4:        little-endian uint32 = 04 00 00 00
  key="name":    6e 61 6d 65
  vLen=5:        little-endian uint32 = 05 00 00 00
  val="Alice":   41 6c 69 63 65

Encoded bytes (26 bytes total):
  offset  0:  01 00 00 00 00 00 00 00   ← seqNum = 1
  offset  8:  01 00 00 00               ← count  = 1
  offset 12:  70                        ← type   = 'p' (Put)
  offset 13:  04 00 00 00               ← kLen   = 4
  offset 17:  6e 61 6d 65               ← key    = "name"
  offset 21:  05 00 00 00               ← vLen   = 5
  offset 25:  41 6c 69 63 65            ← val    = "Alice"
  ─────────────────────────────────────────────────────────
  total: 26 bytes

This 26-byte payload is then wrapped by the lab-01 WAL framing (7-byte header + 4-byte CRC = 37 bytes on disk total for this single write).

Byte-level example: two-op batch

Put("a", "1") + Delete("b") at seqNum=5:

  offset  0:  05 00 00 00 00 00 00 00   ← seqNum = 5
  offset  8:  02 00 00 00               ← count  = 2
  op[0]:
  offset 12:  70                        ← type   = 'p'
  offset 13:  01 00 00 00               ← kLen   = 1
  offset 17:  61                        ← key    = "a"
  offset 18:  01 00 00 00               ← vLen   = 1
  offset 22:  31                        ← val    = "1"
  op[1]:
  offset 23:  64                        ← type   = 'd' (Delete)
  offset 24:  01 00 00 00               ← kLen   = 1
  offset 28:  62                        ← key    = "b"
  (no vLen or val for Delete)
  ─────────────────────────────────────
  total: 29 bytes

Delete ops are shorter: no value bytes, saving 4 + len(value) bytes per deleted key.

Decode(): a parse state machine

Decode is the inverse of Encode. It reads the fixed header and then iterates through the variable-length per-op records:

func Decode(data []byte) (*WriteBatch, error) {
    // Guard: payload must be at least 12 bytes (header only, zero ops is valid).
    if len(data) < 12 {
        return nil, errors.New("batch: payload too short")
    }
    b := &WriteBatch{}
    b.SeqNum = binary.LittleEndian.Uint64(data[0:8])   // bytes 0-7
    count   := binary.LittleEndian.Uint32(data[8:12])  // bytes 8-11
    pos := 12    // cursor starts after the header

    for i := uint32(0); i < count; i++ {
        // Read 1-byte type field:
        if pos >= len(data) {
            return nil, errors.New("batch: truncated record")
        }
        typ := data[pos]; pos++

        // Read 4-byte key length + key bytes:
        if pos+4 > len(data) {
            return nil, errors.New("batch: truncated key length")
        }
        klen := int(binary.LittleEndian.Uint32(data[pos : pos+4])); pos += 4
        if pos+klen > len(data) {
            return nil, errors.New("batch: truncated key")
        }
        key := make([]byte, klen)
        copy(key, data[pos:pos+klen]); pos += klen   // copy: avoid aliasing WAL buffer

        switch typ {
        case 'd':   // Delete: no value fields
            b.ops = append(b.ops, batchOp{del: true, key: key})
        case 'p':   // Put: read 4-byte value length + value bytes
            if pos+4 > len(data) {
                return nil, errors.New("batch: truncated value length")
            }
            vlen := int(binary.LittleEndian.Uint32(data[pos : pos+4])); pos += 4
            if pos+vlen > len(data) {
                return nil, errors.New("batch: truncated value")
            }
            val := make([]byte, vlen)
            copy(val, data[pos:pos+vlen]); pos += vlen
            b.ops = append(b.ops, batchOp{key: key, val: val})
        default:
            return nil, fmt.Errorf("batch: unknown op type %q", typ)
        }
    }
    return b, nil
}

Why copy on key and value? The data slice comes from the WAL’s read buffer. If we stored data[pos:pos+klen] directly, the key would share memory with the WAL buffer — modifying or discarding the WAL buffer would corrupt the batch. copy ensures the batch owns its key/value bytes.

Why explicit bounds checks before every read? The WAL guarantees CRC integrity per record, so a correctly-written record will always decode cleanly. But during development (or if a third-party tool corrupts the WAL), the bounds checks return descriptive errors rather than panicking on a nil-slice index.

Traced decode of the two-op batch above (29 bytes, seqNum=5):

pos=0:  read seqNum = 0x0000000000000005 = 5  (bytes 0-7)
pos=8:  read count  = 0x00000002         = 2  (bytes 8-11)
pos=12: start loop i=0
  pos=12: typ = 0x70 = 'p'              pos→13
  pos=13: klen = 0x00000001 = 1         pos→17
  pos=17: key = [0x61] = "a"            pos→18
  case 'p':
  pos=18: vlen = 0x00000001 = 1         pos→22
  pos=22: val = [0x31] = "1"            pos→23
  append batchOp{del:false, key:"a", val:"1"}
pos=23: start loop i=1
  pos=23: typ = 0x64 = 'd'              pos→24
  pos=24: klen = 0x00000001 = 1         pos→28
  pos=28: key = [0x62] = "b"            pos→29
  case 'd':
  append batchOp{del:true, key:"b"}
pos=29: loop done, count=2 satisfied
→ WriteBatch{SeqNum:5, ops:[{Put "a"→"1"}, {Delete "b"}]}

Replay(): applying the batch to the MemTable

// Replay applies all operations to mem using the batch's SeqNum.
func (b *WriteBatch) Replay(mem *lab02.MemTable) {
    for _, op := range b.ops {
        if op.del {
            mem.Add(b.SeqNum, lab02.TypeDelete, op.key, nil)
        } else {
            mem.Add(b.SeqNum, lab02.TypeValue, op.key, op.val)
        }
    }
}

mem.Add calls EncodeInternalKey(userKey, seqNum, kt) and inserts the result into the skip list. All ops in the batch share the same b.SeqNum — they all become visible at the same snapshot point.

Replay is idempotent: calling Replay twice with the same batch inserts the same internal keys twice. The skip list’s Put method checks for exact duplicate internal keys and updates the value in place — so the second replay produces the same state as the first. This makes WAL recovery safe even if the process crashed mid-replay and the same record is replayed again on the next open.

The DB struct: field anatomy

type DB struct {
    mem    *lab02.MemTable  // in-memory write buffer; all reads served from here
    wal    *lab01.WAL       // append-only log; every write goes here first
    seqNum uint64           // MVCC clock; monotonically increasing
    dir    string           // directory path for WAL file
    mu     sync.Mutex       // serialises all operations (see below)
}

seqNum: the MVCC clock

seqNum starts at 0 when the DB is first created. It increments by 1 after every applyBatch call. Since each DB.Put or DB.Delete creates a single-op batch, seqNum effectively increments by 1 per write.

DB.Get reads db.seqNum as the readSeq passed to MemTable.Get. This means Get always reads the latest committed state — it uses the current clock value, so it sees all writes up to and including the most recent one.

seqNum timeline:
  Open():   seqNum = 0          (or recovered from WAL replay)
  Put("k1", "v1"):  seqNum 0 → 1
    → MemTable: ("k1", seq=0, TypeValue) = "v1"
  Put("k1", "v2"):  seqNum 1 → 2
    → MemTable: ("k1", seq=1, TypeValue) = "v2"
  Get("k1"):  readSeq = db.seqNum = 2
    → MemTable.Get("k1", 2) finds ("k1", seq=1) → "v2" ✓

sync.Mutex: what it protects

The DB.mu mutex serialises all read and write operations. Every exported method acquires and releases it:

func (db *DB) Put(key, value []byte) error {
    db.mu.Lock()
    defer db.mu.Unlock()
    // ... applyBatch ...
}

func (db *DB) Get(key []byte) ([]byte, bool) {
    db.mu.Lock()
    defer db.mu.Unlock()
    return db.mem.Get(key, db.seqNum)
}

Why reads need the lock too?

Consider Get reading db.seqNum while a concurrent Put is executing applyBatch:

Goroutine A (Put):                    Goroutine B (Get):
  b.Replay(db.mem)                  ← MemTable partially updated
                                      db.mem.Get(key, db.seqNum)  ← races here
  db.seqNum++

Without the lock, Goroutine B could read a seqNum that has already advanced past the partially-applied batch, or read a seqNum that is about to advance — either way, it may observe an inconsistent snapshot.

The mutex ensures Get either sees the state before a write (if it acquires the lock before the write) or after (if the write completed first). There is no intermediate state.

TOCTOU without the lock (time-of-check-to-time-of-use):

Without locking:
  T1: Goroutine B reads db.seqNum = 5
  T2: Goroutine A completes Put, db.seqNum → 6, new key in MemTable
  T3: Goroutine B calls db.mem.Get(key, 5)   ← stale seqNum, may miss new key

With the lock: Goroutine B either runs entirely before T2 (seqNum=5, correct snapshot) or entirely after (seqNum=6, also a correct snapshot).

Limitation: this design allows zero concurrency. Every Get blocks on every concurrent Put. Production engines use a sync.RWMutex for reads (multiple concurrent readers, exclusive writers) or a lock-free skip list (lab 02 concurrent section) to allow parallel reads.

DB.Put execution trace: end to end

func (db *DB) Put(key, value []byte) error {
    db.mu.Lock()          // acquire exclusive lock
    defer db.mu.Unlock()  // release on return

    b := &WriteBatch{SeqNum: db.seqNum}  // assign current seqNum to batch
    b.Put(key, value)                    // enqueue single op
    return db.applyBatch(b)              // WAL + MemTable + seqNum++
}

// applyBatch is the core write path, called under db.mu.
func (db *DB) applyBatch(b *WriteBatch) error {
    encoded := b.Encode()               // serialise to bytes (no I/O)
    if err := db.wal.Append(encoded); err != nil {
        return fmt.Errorf("db wal append: %w", err)   // WAL error: abort
    }
    // WAL record is durable (fdatasync completed inside wal.Append)
    b.Replay(db.mem)                    // update MemTable
    db.seqNum++                         // advance MVCC clock
    return nil
}

Full call stack for db.Put([]byte("name"), []byte("Alice")):

db.Put("name", "Alice")
  └─ db.mu.Lock()
  └─ WriteBatch{SeqNum: 0}
  └─ b.Put("name", "Alice")  → ops = [{del:false, key:"name", val:"Alice"}]
  └─ db.applyBatch(b)
       └─ b.Encode()
            → buf[0:8]  = 00 00 00 00 00 00 00 00  (seqNum=0)
            → buf[8:12] = 01 00 00 00               (count=1)
            → buf[12]   = 70                        (type='p')
            → buf[13:17]= 04 00 00 00               (kLen=4)
            → buf[17:21]= 6e 61 6d 65               (key="name")
            → buf[21:25]= 05 00 00 00               (vLen=5)
            → buf[25:30]= 41 6c 69 63 65            (val="Alice")
            → returns 30-byte slice
       └─ db.wal.Append(encoded)
            ├─ lab01.WAL: write 7-byte header (type + length + CRC16)
            ├─ pwrite(fd, encoded, 30 bytes)
            └─ fdatasync(fd)   ← blocks until durable on disk
       └─ b.Replay(db.mem)
            └─ mem.Add(0, TypeValue, "name", "Alice")
                 └─ ikey = EncodeInternalKey("name", 0, TypeValue)
                       = [6e 61 6d 65  01 00 00 00 00 00 00 00]
                         (name        tag: seqNum=0, type=Value)
                 └─ sl.Put(ikey, "Alice")   ← skip list insert
       └─ db.seqNum++ → 1
  └─ db.mu.Unlock()
  └─ return nil  ← caller acked; write is durable

recoverFromWAL: how the MemTable is rebuilt

func (db *DB) recoverFromWAL(path string) error {
    // lab01.Recover reads all CRC-valid records from the WAL file.
    // It stops at the first record with a bad CRC (partial write at crash).
    records, err := lab01.Recover(path)
    if err != nil {
        return err   // I/O error reading the file itself
    }

    for _, rec := range records {
        // Decode the raw bytes back into a WriteBatch:
        b, err := Decode(rec)
        if err != nil {
            // Corrupt batch payload (shouldn't happen if CRC passed, but defensive):
            continue
        }
        // Re-apply every op to the fresh MemTable:
        b.Replay(db.mem)
        // Track the highest seqNum seen so far:
        if b.SeqNum >= db.seqNum {
            db.seqNum = b.SeqNum + 1   // resume from after the last committed batch
        }
    }
    return nil
}

seqNum reconstruction during recovery

After crash, db.seqNum must resume from where it left off — not from 0. If it started from 0, a new write at seqNum=0 would conflict with the already-replayed data in the MemTable.

The loop if b.SeqNum >= db.seqNum { db.seqNum = b.SeqNum + 1 } finds the maximum seqNum in all replayed batches and sets the clock to one past it.

Example:

WAL contains 5 records with SeqNums: 0, 1, 2, 3, 4
After recovery loop:
  After record 0: db.seqNum = 0+1 = 1
  After record 1: db.seqNum = 1+1 = 2
  After record 2: db.seqNum = 2+1 = 3
  After record 3: db.seqNum = 3+1 = 4
  After record 4: db.seqNum = 4+1 = 5
First new write after recovery uses seqNum=5 — no collision.

WAL framing from lab 01: what Recover actually reads

The lab-01 WAL wraps each payload in a 7-byte frame:

┌──────────┬──────────────────────────┬──────────┬────────────────────┐
│ type (1B)│  payload length (4B LE)  │ CRC (2B) │  payload (N bytes) │
└──────────┴──────────────────────────┴──────────┴────────────────────┘

lab01.Recover reads each frame, verifies the CRC over payload, and returns the raw payload bytes if the CRC matches. On a partial write (crash during pwrite), the frame’s length field may exceed available bytes, or the CRC will not match — in either case, Recover stops and returns only the records that were fully flushed.

On-disk layout for three Put calls:

WAL file after Put("name","Alice") + Put("city","London") + Put("lang","Go"):

  Record 0: [frame header 7B] [26 bytes: seqNum=0, Put("name","Alice")]
  Record 1: [frame header 7B] [27 bytes: seqNum=1, Put("city","London")]
  Record 2: [frame header 7B] [22 bytes: seqNum=2, Put("lang","Go")]
  Total: 3 × 7 + 26 + 27 + 22 = 96 bytes on disk

At process restart, lab01.Recover returns [][]byte with 3 entries: the 26, 27, and 22-byte payloads. recoverFromWAL decodes each and replays into a fresh MemTable.

Crash scenarios: byte-level analysis

Power-loss behaviour on consumer SSDs: many consumer NVMe drives do NOT honour fdatasync in their firmware and keep data in volatile DRAM buffers. Under power failure without a capacitor, those writes are lost even after fdatasync returned. Enterprise SSDs include power-loss protection (PLP) capacitors. LevelDB/RocksDB document this and recommend testing with FALLOC and crash injection tools like dm-log-writes.

Group commit: the missing optimisation

Our implementation flushes the WAL (calls fdatasync) once per write. An fdatasync on NVMe takes ~100 µs. At 1 write per flush:

Maximum single-threaded write throughput:
  1 / 100 µs = 10,000 writes/second

Real LevelDB/RocksDB use group commit: multiple concurrent writers share a single fdatasync. The first writer to acquire the write lock becomes the “leader”; subsequent writers join a queue. The leader:

1. Collects all queued batches.
2. Encodes them into a single WAL write.
3. Calls fdatasync once.
4. Wakes all queued writers.

With 100 concurrent writers and group commit:

All 100 writes share 1 fdatasync = 100 µs total
Per-write latency:        ~100 µs (same as before for each caller)
Aggregate throughput:     100 writes / 100 µs = 1,000,000 writes/second  (100× improvement)

Our single-threaded sync.Mutex design makes group commit trivially inapplicable — there is only ever one writer at a time. Group commit is only useful with concurrent writers fighting for the WAL. Lab 03 prioritises correctness and clarity over throughput.

Running the tests

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

Expected output:

=== RUN   TestPutGet
--- PASS: TestPutGet (0.00s)
=== RUN   TestCrashRecovery
--- PASS: TestCrashRecovery (0.00s)
=== RUN   TestBatchWrite
--- PASS: TestBatchWrite (0.00s)
=== RUN   TestDeleteAfterRecovery
--- PASS: TestDeleteAfterRecovery (0.00s)
PASS
ok      github.com/10xdev/leveldb/lab03

TestCrashRecovery walkthrough

This test directly verifies the WAL-first guarantee:

func TestCrashRecovery(t *testing.T) {
    dir := t.TempDir()                     // fresh temp directory

    // Phase 1: write 5 keys and close (WAL flushed on Close).
    db, _ := Open(dir)
    for i := 0; i < 5; i++ {
        db.Put([]byte(fmt.Sprintf("key%d", i)), []byte(fmt.Sprintf("val%d", i)))
        // After each Put: WAL record durable on disk, MemTable updated.
    }
    db.Close()   // flushes WAL file handle (POSIX close)

    // Phase 2: reopen — simulates process restart after crash.
    db2, _ := Open(dir)
    // Open calls recoverFromWAL which replays all 5 WAL records.
    // MemTable is rebuilt from scratch; seqNum resumes from 5.
    for i := 0; i < 5; i++ {
        v, ok := db2.Get([]byte(fmt.Sprintf("key%d", i)))
        // MemTable.Get(key, readSeq=5) finds each key at seqNum 0..4.
        if !ok { t.Errorf("key%d not found after recovery", i) }
    }
}

The t.TempDir() directory is deleted by the test framework after the test completes. Phase 2’s Open finds the WAL file written by Phase 1 and replays it. The test does not actually crash the process — it simulates a clean close followed by reopen, which is the same code path as crash recovery (the WAL is replayed regardless).

TestBatchWrite walkthrough

b := &WriteBatch{}
b.Put([]byte("a"), []byte("1"))
b.Put([]byte("b"), []byte("2"))
b.Put([]byte("c"), []byte("3"))
db.Write(b)

db.Write assigns batch.SeqNum = db.seqNum (= 0) and calls applyBatch. All three ops are encoded in a single WAL record and replayed with the same seqNum. A reader at readSeq=0 sees all three simultaneously — they form one atomic unit. If the process crashed between wal.Append returning and Replay completing, recovery would re-apply all three or none.

Running the demo

go run ./lab03/demo

Expected output:

put  name     = Alice
put  city     = London
put  lang     = Go
closing (WAL flushed) …
reopening …
reading after recovery:
  name     = Alice
  city     = London
  lang     = Go

The demo writes three keys, closes (simulating a clean shutdown), reopens (replaying the WAL), and reads the recovered keys. The WAL file is in the temp directory created by os.MkdirTemp — deleted automatically on demo exit.

FoundationDB parallel

In FDB, a committed transaction is the cluster-level equivalent of our WriteBatch.Encode() + wal.Append(). The transaction log (tlog processes) is replicated across 3+ machines using a Paxos-like protocol. fdatasync is replaced by “majority of tlog replicas acknowledged the write”.

FDB’s CommitVersion is the direct equivalent of our seqNum:

• In our engine: seqNum is a uint64 in the DB struct, incremented under db.mu on each commit.
• In FDB: CommitVersion is assigned by the sequencer (a single elected process), ensuring total order across thousands of concurrent clients on dozens of machines.

FDB’s transaction log (tlog) is the direct equivalent of our WAL:

• Both are append-only.
• Both are written before the in-memory state is updated.
• Both are replayed on restart.

FDB’s storage server rebuilds its in-memory B-tree from the tlog on restart — equivalent to our recoverFromWAL rebuilding the MemTable from CURRENT.wal.

The key architectural difference: FDB’s tlog replication means that even if the machine running the sequencer loses power, another machine has the full log and can continue. Our single-node WAL has no such replication — if the disk fails, data is lost.