Design a Key-Value Storage Library

Problem Design a key-value storage library (embeddable, like RocksDB/LevelDB in spirit): get/put/delete with optional persistence, usable by applications in-process.

Functional requirements

• API: put(k, v), get(k), delete(k), optional TTL and batch operations; iteration/range scan as a stretch.
• Durable across restarts (persistence), configurable cache/eviction for memory-bounded operation.

Non-functional requirements

• Reads p99 < 1 ms from memory; writes durable without killing throughput (target ~100K ops/sec discussed).
• Concurrent access from many threads; crash safety — no torn/partial writes.

Key components

• In-memory index: hash map (point lookups) vs skip list / balanced tree (ordered scans).
• Persistence: write-ahead log for durability + periodic compaction; contrast LSM design (memtable → SSTables, background compaction; write-optimized) vs B-tree/page store (read-optimized, in-place updates).
• Eviction policy (LRU/LFU) when used as a bounded cache; concurrency via striped locks or a single-writer + MVCC snapshot-read model.

Deep dives / trade-offs

• WAL fsync policy: per-write durability vs group commit throughput.
• Read/write/space amplification in LSM vs B-tree; bloom filters to save disk reads.
• Crash recovery: replaying the log, checksums, idempotent compaction.