Key-Value Stores, Caches, And WAL Durability

What's being tested

Interviewers probe your ability to design a crash-consistent, single-node key–value engine that balances latency, durability, and memory/disk trade-offs while being implementable by an engineer in a coding interview. They expect clear scoping questions, a layered design (API, in-memory structures, on-disk layout, recovery, concurrency), and justification of trade-offs such as synchronous durability versus throughput. Databricks cares because production tooling (local storage engines, caching layers, metadata services) must be correct under crashes and perform predictably.

Core knowledge

Write-Ahead Log (WAL): append-only log of mutations; guarantees durability if writes are synced to stable storage before acknowledging. Group commit reduces fsync cost; per-write fsync gives stronger durability but higher latency.
memtable and SSTable: common LSM approach uses an in-memory memtable for fast writes and immutable on-disk SSTables written by compaction; provides high write throughput at cost of read amplification.
B-tree vs LSM-tree tradeoff: B-tree gives lower read amplification and predictable range scans; LSM-tree optimizes write throughput and sequential IO on disk; pick by read/write ratio and latency targets.
fsync semantics and filesystems: fsync on ext4/XFS vs O_DIRECT affect durability and ordering; understand that write() without fsync risks data loss on crash. fsync latency dominates small-write throughput.
Write amplification formula: write_amplification = bytes_written_to_disk / bytes_of_user_data; compaction increases amplification — quantify (LSM often 2–10x depending on compaction).
Compaction and GC: background compaction merges SSTables; tune compaction concurrency to limit IO interference and reduce read amplification; ensure compaction is crash-resilient and idempotent.
Atomicity & Recovery: recovery replays WAL then applies any partially-written files; checkpoints reduce recovery time by persisting a consistent on-disk snapshot of in-memory state.
Concurrency control: use fine-grained locks or lock-free concurrent hashmaps for in-memory access; readers should avoid blocking writers (snapshot isolation or versioned reads).
Eviction strategies: LRU, CLOCK, or size-aware eviction for an in-memory cache; consider entry sizes and avoid heavy global locks during eviction.
Persistence modes for caches: write-through (sync to WAL before ack) vs write-back (ack then persist later) — trade latency vs data loss risk.
Atomic replace / rename: use atomic rename() for installing new SSTables/checkpoints to avoid partial files being picked up during recovery.
Testing and metrics: measure p99 latency, throughput, and recovery time; fuzz crashes and power-fail to validate durability guarantees.

Worked example — "Design a key-value store"

Start by clarifying requirements: expected dataset size, read/write ratio, latency SLOs (p99), single-writer or concurrent-writers, durability level (ack after WAL fsync or async). Declare assumptions (single-node, dataset up to ~100GB, memory budget 8–32GB).

Organize the answer into pillars: (1) API and consistency model (simple get/put/delete, optional snapshots); (2) in-memory front (concurrent hash map + memtable) and background flush; (3) on-disk format (append-only WAL, immutable SSTables with checksums); (4) recovery and compaction; (5) concurrency and durability knobs.

Detail one tradeoff: choose LSM-tree with WAL+memtable if writes dominate — justify that sequential IO makes fsync grouping effective; if low-latency reads and range scans dominate, argue for a B-tree style approach. Explicitly call out fsync cost and propose group commit / configurable durability levels.

Close by describing tests and next steps: "If I had more time I'd sketch on-disk block layout (checksums, footer), show pseudocode for recovery and WAL truncation, and propose benchmarks (YCSB) plus crash-fuzz tests."

A second angle — "Design a single-node persistent in-memory cache"

Here the emphasis shifts to strict in-memory performance with optional persistence. Start by clarifying durability semantics: checkpointing vs synchronous WAL. Design pillars: memory-efficient in-memory store (sharded concurrent hashmap), eviction policy tuned to object size and access frequency (LRU or segmented LRU), and a persistence layer that snapshots memory periodically while writing an incremental WAL for recent mutations.

Key differences: minimize write path latency — prefer async persistence (write-back) with a small window of potential data loss, and use background threads to do checkpointing/compaction. Also, reduce contention via sharding and lock-striping; in high-throughput scenarios, measure latency impact of checkpoint fsync and stagger checkpoint start times. For small objects, serialization/deserialization cost matters — use zero-copy or memory arenas when possible.

Common pitfalls

Pitfall: Assuming write() implies durability. Many candidates forget that write() without fsync can lose data on crash; always state when you require fsync or opt for configurable durability.

Pitfall: Sketching a single global lock for all operations. That simplifies correctness but kills throughput; prefer sharded locks, lock-free structures, or read-copy-update/snapshots for readers.

Pitfall: Ignoring recovery complexity. Saying "replay WAL" without addressing partial writes, checksums, and atomic SSTable installation misses correctness; describe atomic file replacement and WAL truncation.

Connections

Interviewers may pivot to distributed versions (introduce consensus via Raft/Paxos for multi-node durability), or to storage-layer details (block-device behavior, fsync latency, O_DIRECT). They might also ask about benchmarking (YCSB) or profiling hotspots (perf, flamegraphs).

What's being tested

Core knowledge

Worked example — "Design a key-value store"

A second angle — "Design a single-node persistent in-memory cache"

Common pitfalls

Connections

Further reading

Practice questions

Related concepts