Persistent Key-Value Stores

What's being tested

Persistent key-value stores test whether you can combine clean in-memory data structures with binary-safe serialization and file I/O. Interviewers are probing for correctness across overwrites, deletes, restarts, partial writes, arbitrary bytes, and simple durability tradeoffs.

Patterns & templates

• Length-prefixed serialization — encode key_len, value_len, then raw bytes; O(k+v) per record and binary-safe for Unicode/null bytes.

• Append-only log — implement put()/delete() as record appends; recovery scans sequentially in O(file_size) and keeps latest value per key.

• Snapshot plus mutation log — periodically write full map state, then replay newer mutations; faster startup than replaying an unbounded log.

• Atomic flush pattern — write to tmp, call flush()/fsync(), then rename(); avoids replacing good state with a partial file.

• Tombstone deletes — persist deletes as DELETE key records; do not just remove from memory or deleted keys reappear after restart.

• Shard by hash — choose shard with hash(key) % num_shards; keeps files smaller, but recovery must rebuild each shard’s latest-key index.

• Corruption-aware parsing — include magic, version, record_type, and optional checksum; stop cleanly at truncated tail records.

Common pitfalls

Pitfall: Using delimiters like newline or comma breaks for arbitrary byte keys/values; prefer explicit lengths.

Pitfall: Updating the in-memory map before a failed disk write can acknowledge data that will disappear after restart.

Pitfall: Forgetting overwrite semantics causes recovery to return the first value for a key instead of the latest durable record.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.