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

1. Durability via a write-ahead log (WAL): format, rotation, and fsync policy.
2. On-disk data structures and layout: how data files and metadata are organized.
3. Crash recovery: how to detect and recover from incomplete operations.
4. Compaction/garbage collection: reclaiming stale versions and tombstones.
5. fsync and batching strategy: throughput/latency trade-offs.
6. Handling torn writes and partial files.
7. Concurrency model: single-writer/multi-reader vs. multi-writer; lock-based vs. optimistic/lock-free; ensuring correctness.
8. Consistency guarantees: e.g., read-after-write, linearizability options.
9. Performance analysis: latency/throughput trade-offs and back-of-the-envelope resource estimates.
10. Minimal testing plan including failure injection and recovery validation.