System Design: Durable Key–Value Store
Context
Design a single-node, embeddable key–value store library with a simple API that must remain correct and durable across process crashes and power failures. Assume a POSIX-like filesystem on SSD/NVMe with 4 KiB sectors.
API
-
put(key, value)
-
get(key)
-
delete(key)
Keys/values are byte arrays; no secondary indexes or transactions beyond single-key operations.
Requirements
-
Durability via a write-ahead log (WAL): format, rotation, and fsync policy.
-
On-disk data structures and layout: how data files and metadata are organized.
-
Crash recovery: how to detect and recover from incomplete operations.
-
Compaction/garbage collection: reclaiming stale versions and tombstones.
-
fsync and batching strategy: throughput/latency trade-offs.
-
Handling torn writes and partial files.
-
Concurrency model: single-writer/multi-reader vs. multi-writer; lock-based vs. optimistic/lock-free; ensuring correctness.
-
Consistency guarantees: e.g., read-after-write, linearizability options.
-
Performance analysis: latency/throughput trade-offs and back-of-the-envelope resource estimates.
-
Minimal testing plan including failure injection and recovery validation.