Storage & Durability

Durability is about one promise:

If the process crashes, you can recover a correct state from persisted history.

This module uses a simplified LSM storage model to make that promise concrete.

Learning goals

• Explain why write-ahead logging (WAL) must happen before in-memory apply.
• Trace crash recovery from a log back to final key-value state.
• Apply LSM read-order rules across memtable and SSTables.
• Reason about tombstones, gcBefore, and when deletes can be ignored.
• Implement compaction behavior that preserves newest-correct value per key.

End-to-end mental model

Think in this order:

1. A write arrives.
2. You append the write to WAL (durable step).
3. You apply it to memory (fast step).
4. Later, memtable is flushed to immutable SSTables.
5. Background compaction merges old and new runs.
6. Reads consult newest data first, while respecting tombstones.

Crashes can happen between any two steps. Durability means recovery logic still reconstructs a state consistent with persisted records.

Core invariants

These invariants drive every problem in this module:

• WAL ordering invariant:

Apply entries in exact append order. Last write wins for the same key.

• WAL delete invariant:

A delete removes a key from final visible state.

• Read precedence invariant:

Memtable is newer than SSTables. Among SSTables, earlier in list is newer.

• Tombstone visibility invariant:

A tombstone with Timestamp >= gcBefore is still live and must delete key.

• Tombstone GC invariant:

A tombstone with Timestamp < gcBefore is treated as collected and ignored.

• Compaction winner invariant:

Per key, pick newest candidate by timestamp; if tied, newer run wins.

If any invariant is violated, you will either resurrect deleted values or lose new writes.

Failure flows you should be able to reason about

Crash after WAL append, before memtable apply

• WAL has the operation.
• Memtable may not have it.
• Recovery replay restores the operation.

Crash after memtable apply, before flush

• WAL has the operation.
• Memtable is gone after restart.
• Replay rebuilds equivalent state.

Tombstone aging during reads

• New tombstone (ts >= gcBefore) must hide older values.
• Old tombstone (ts < gcBefore) no longer blocks older values in this model.

Worked example: WAL replay

Log stream:

1. set a=1
2. set b=2
3. delete a
4. set a=3

Replay state:

• after 1: {a:1}
• after 2: {a:1,b:2}
• after 3: {b:2}
• after 4: {a:3,b:2}

Final answer is sorted by key: [{a,3},{b,2}].

Worked example: LSM read path with tombstones

Query key: k, gcBefore=10.

• Memtable has {k, tombstone, ts=8}.

The tombstone is GC'd (8 < 10), so ignore it.

• Newest SSTable has {k, tombstone, ts=12}.

This tombstone is live (12 >= 10), so key is deleted. Stop search.

If that newest SSTable tombstone were missing, read would continue to older tables until a value is found.

Worked example: multi-way compaction

Runs are newest to oldest:

• run0: k@7 tombstone, x@5=v5
• run1: k@6=v6, x@4=v4
• run2: k@2=v2

Case A: gcBefore=5

• k@7 tombstone is live, drop k.
• x@5=v5 wins.

Output: x@5=v5.

Case B: gcBefore=8

• k@7 tombstone is GC'd, ignore it.
• next candidate k@6=v6 wins.
• x@5=v5 still wins.

Output: k@6=v6, x@5=v5.

Implementation blueprint (intentionally explicit)

WAL replay

• Keep state map[string]string.
• Iterate entries in order:
  • Deleted=true: delete(state, key)
  • else: state[key] = value
• Extract keys, sort ascending, build output slice.

LSM get

• Scan all mem entries for target key; pick highest timestamp.
• If mem winner is value: return immediately.
• If mem winner is tombstone:
  • ts >= gcBefore: return not found.
  • else continue to SSTables.
• For each SSTable newest to oldest:
  • skip if MaybeHasKey=false
  • binary search by key
  • if found value: return it
  • if found tombstone:
    • ts >= gcBefore: return not found
    • else continue older tables
• If nothing survives: not found.

Multi-way compaction

• Group all entries by key.
• Sort keys ascending for deterministic output.
• For each key:
  • sort candidates by (timestamp desc, runIndex asc)
  • walk sorted candidates:
    • live tombstone (ts >= gcBefore): emit nothing, stop key
    • GC'd tombstone (ts < gcBefore): skip
    • value: emit first value, stop key

Common mistakes checklist

• Stopping memtable scan at first key match (wrong if newer entry appears later).
• Forgetting that equal timestamps break ties by newer run.
• Treating all tombstones as deletions even when GC'd.
• Ignoring deterministic output ordering.
• Searching all SSTables linearly by key instead of binary search inside table.

What you will build

• WAL replay to reconstruct a key-value store
• LSM-style run merge (compaction)
• LSM read path with Bloom filters and tombstones
• Multi-way LSM compaction with tombstone GC