Binary Serialization And Persistent Key-Value Stores

What's being tested

Demonstrates designing reversible, delimiter-free binary serialization and a crash-consistent persistent key-value store: encoding arbitrary bytes/Unicode, managing offsets/indexes, and safe disk writes. Interviewers probe correctness across edge cases, complexity reasoning, and simple durability guarantees.

Patterns & templates

• Length-prefix encoding: store a fixed-width (e.g., 4- or 8-byte) big-endian length before bytes; decode by reading length then exact payload, O(n) serialize/deserialize.

• Varint / zigzag for compact integer lengths: saves space for small values; implement decode loop carefully to avoid infinite loops.

• Append-only log + in-memory index: append records to file, keep HashMap<key, offset> for O(1) get; rebuild index by scanning on startup.

• Per-record checksum (e.g., CRC32) after payload to detect partial writes or corruption before using a record.

• Atomic replace pattern: write to temp file, fsync data and metadata, then rename to swap files atomically on POSIX.

• Compaction/GC: background pass copies live entries to new file, then atomic swap; avoid holding long-lived locks during compaction.

• Edge-size handling: support empty keys/values and very large blobs by streaming IO and limiting in-memory buffers.

Common pitfalls

Pitfall: Using a byte delimiter (e.g., \0) fails for arbitrary binary data — always prefer length-prefix or escape-free encodings.

Pitfall: Forgetting to fsync metadata (fsync on directory after rename on some platforms) breaks durability guarantees on crash.

Pitfall: Rebuilding index by naive memory structures without bounds can OOM on millions of keys — consider sharding, sparse indexes, or on-disk B-tree.

Practice these

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