Design Crash Recovery for a Single-Node Key-Value Store
Design a single-machine key-value engine whose WAL, snapshots, replay, and compaction preserve acknowledged writes across crashes.
Problem statement
For this exercise, assume you are building the storage engine for a single-node key-value store with put, get, delete, snapshot, and recover operations. Focus on the exact write-ahead-log ordering, acknowledgment point, in-memory index, snapshot boundary, crash recovery, tombstones, checksums, and compaction.
Walk through failures after each important write step and explain what is recovered. Then discuss read, write, and space amplification and identify the capacity boundary that would force a distributed design. Replication and cross-node consensus are deliberately out of scope for the core design.
What to build
- Put or delete one key and acknowledge only under the stated restart-durability policy.
- Return the latest committed value or not-found from the in-memory and on-disk state.
- Create a recoverable snapshot without stopping writes for the full snapshot duration.
- After a crash, restore the latest valid snapshot and replay the complete WAL suffix without resurrecting deleted values.
At scale
- For this exercise, store 50 million keys with 32-byte keys and 512-byte average values on one machine.
- For this exercise, sustain 200,000 operations per second with a 50/50 read-write mix and p99 reads below 10 ms in the healthy case.
- For this exercise, a durable write is acknowledged after its WAL record is on stable storage; group commit may add at most 5 ms of healthy-path latency.
- For this exercise, restart recovery should finish within 10 minutes after an unclean shutdown, and a torn or corrupt tail record must not corrupt earlier committed state.