Storage & Durability

Durability Pipeline

• Append operation to WAL
• Apply to memtable
• Flush to SSTables
• Compact runs in background
• Recover by replaying persisted history

Invariants

• Replay WAL in append order
• Last write wins for same key
• Memtable is newer than all SSTables
• Newer SSTables are checked before older ones
• Tombstone with ts >= gcBefore deletes key
• Tombstone with ts < gcBefore is ignored (GC'd)

Failure Flows

• Crash after WAL append: replay restores operation
• Crash after memtable apply: replay rebuilds memory
• Crash before compaction: read path still resolves by recency

LSM Read Path

• Pick newest memtable entry for key
• Value in memtable returns immediately
• Live tombstone in memtable returns deleted
• GC'd tombstone in memtable falls through to SSTables
• In SSTables: Bloom filter skip, then binary search by key

Multi-Way Compaction

• Group versions by key across all runs
• Sort candidates by (timestamp desc, runIndex asc)
• Live tombstone deletes key
• GC'd tombstone is skipped
• First surviving value is output

Build

• WAL replay
• LSM read path
• Multi-way compaction with GC-aware tombstones