Design a key-value store
The smallest distributed database that still forces every hard choice: a get can read a value the system already wrote, yet hand you a stale one — and whether that happens is decided by arithmetic, not by hope.
The dominant constraint: freshness is overlap
A leaderless, Dynamo-style store (DDIA Ch. 5) sends every write to all N replicas and acknowledges as soon as W of them reply; every read fans out to R replicas and takes the freshest answer. The pigeonhole argument is the whole game: if the write touched W nodes and the read touched R nodes, and R + W > N, then by counting there is no way to pick R nodes that all miss the W that were written — at least one read replica must carry the new value. Set the numbers and the contract falls out:
The two quorum rows are the load-bearing calculation of this entire case. With N=3, W=2, R=2 you have bought yourself a guarantee that no amount of bad luck in node selection can produce a stale read on a healthy cluster — the read and write sets are forced to intersect. Drop to W=1, R=1 (the "fast and loose" config) and R+W = 2 \le N = 3: a write can land on node A while your subsequent read happens to hit only node B, which has not yet received the replication stream. You read a value you yourself just overwrote. That is not a bug — it is exactly what W=1,R=1 promises. The knobs are a contract, and the candidate who can say "R+W>N overlaps the sets; W=1,R=1 opens a stale window" has understood DDIA Ch. 9's central result.
The storage numbers steer hardware, not consistency. One billion 1 KB values is ~1 TB of logical data; replication factor 3 triples it to ~3 TB physically stored. Then the LSM engine's compaction transiently doubles a level's footprint while it merges old and new SSTables side-by-side before deleting the inputs — so provision for ~6 TB of peak disk, not 3 TB. A cluster sized to the steady state stalls writes the first time compaction runs (see the failure table). Headroom for compaction is a first-class capacity input, not slack.
Clarify the contract
Treat the prompt as a product contract before a box diagram. The store must:
- Put / get / delete by key — opaque values, no secondary indexes, no range scans, no transactions across keys. That narrowness is what lets us partition freely.
- Scale storage and write throughput past one machine — so partitioning is mandatory, not optional.
- Survive node failure without losing an acknowledged write — durability is defined relative to the ack, which ties it to W.
- Expose a legible consistency knob — let the caller trade freshness for latency per operation via R / W.
- Self-heal divergent replicas in the background.
Equally important is what it need not do: no multi-key atomicity, no joins, no SQL, no strict serializability. If the interviewer asks for cross-key transactions, that is a different (and much harder) machine — say so. The value of a KV store is precisely that the contract is small enough to partition and replicate without coordination on the hot path.
Data model & API
Keep the surface tiny; the API should express the operation, never leak the ring, the memtable, or the SSTable layout.
| Operation | Signature | Notes |
|---|---|---|
| put | put(key, value, W) → {version} | Returns a version stamp (version vector / timestamp) the client keeps for read-your-writes and CAS. |
| get | get(key, R) → {value, version} | R picks freshness vs latency per call; may return multiple sibling versions if writes conflicted. |
| delete | delete(key, W) → {version} | Writes a tombstone, not a hole — a delete is a write (see deep dive 3). |
| cas | cas(key, expected_version, value) | Conditional write; the principled fix for the lost-update race below. |
The on-disk record per key is (key, value, version, tombstone?). The version is the quiet hero: it is what read repair compares, what CAS checks, and what version vectors extend to detect concurrency rather than guess at it.
Linearized design — follow a put, then a get
- Route the key. Hash the key onto the consistent-hashing ring and walk clockwise to find its N replicas. The ring mechanics — virtual nodes, why hashing beats
mod, how rebalancing moves only 1/N of keys — are taught in full in C02; here we just use the ring to name the replica set and move on. - Durably log the mutation. The coordinator (any node, or the client) sends the write to all N replicas. Each replica appends it to its write-ahead log (sequential disk, fast) and inserts it into an in-memory memtable before replying "ack."
- Wait for W acks. The write returns success once W replicas have acked. With N=3, W=2 the value is on at least two disks before the client hears "ok" — survive any one node and the write lives.
- Flush and compact. When a memtable fills, it is flushed to an immutable sorted file (an SSTable) at level L0. Background compaction merges SSTables into larger, fewer, deeper levels (deep dive 2).
- Serve a get. The coordinator queries R replicas. Each replica answers from its memtable + SSTables (newest first, short-circuited by bloom filters). The coordinator returns the version with the highest stamp.
- Repair on the read path. If the R replicas disagree, the coordinator returns the freshest and writes it back to the stale replicas — read repair (DDIA Ch. 5). A background anti-entropy scan with Merkle trees catches keys that are read rarely.
The first bottleneck shows up at step 4. LSM storage makes writes nearly free (sequential WAL + in-memory insert), which is exactly why a write-heavy KV store reaches for it — but it defers all the cost to compaction. Here is that write path, and a read fanning across the levels:
Deep dives
1. N / R / W are product promises, not magic numbers
The inequality R + W > N is necessary for fresh reads but not sufficient — and naming the gaps is the senior move (DDIA Ch. 9). The clean overlap argument quietly assumes the write reached a clean quorum of the key's real home nodes, that there is a single notion of "latest," and that writes are ordered. Each assumption can break:
- Sloppy quorum + hinted handoff. Under a partition, Dynamo lets a write satisfy W on any reachable nodes — not the key's designated replicas — and stores a "hint" to forward later. The write is durable, but the W nodes that took it may not overlap the R nodes a later read consults. R+W>N held arithmetically; the sets it was counting were the wrong ones. Sloppy quorum buys availability and gives up the freshness guarantee for the duration.
- Clock skew. If "freshest" is decided by a wall-clock timestamp, a replica with a fast clock can stamp an older write as newer and win the merge. Quorums say nothing about clocks.
- Concurrent writes. Two clients writing the same key "at the same time" produce two values with no happens-before order. A quorum read sees both; which is correct is a question the store cannot answer alone.
So R+W>N is the floor, not the ceiling. The honest pitch: "N=3,W=2,R=2 gives overlapping quorums and read-your-writes on a healthy cluster; under partitions I fall back to sloppy quorum and accept a stale window, repaired by read repair and anti-entropy; and I detect concurrency with version vectors rather than trusting clocks."
2. LSM-tree vs B-tree — the amplification you choose
Both are valid storage engines (DDIA Ch. 3); they differ in which amplification you pay. An LSM-tree only ever appends: WAL is sequential, memtable inserts are in-RAM, flushes write whole sorted files. That makes writes cheap and disk-friendly. The bill arrives twice later: a point read may have to check several SSTables across levels (read amplification, mitigated by bloom filters that let a read skip files that definitely lack the key), and every byte is rewritten several times as it migrates down the levels (compaction / write amplification). A B-tree updates pages in place: a point read is a predictable O(\log n) page walk, but every write may rewrite a full page (and the WAL entry), giving steady write amplification and random I/O.
| LSM-tree (SSTables) | B-tree | |
|---|---|---|
| Writes | Sequential, fast; cost deferred to compaction. | In-place page updates; random I/O, write amplification up front. |
| Point reads | May touch many SSTables; bloom filters keep it ~O(levels). | Predictable O(log n) page walk — the better tail. |
| Space | Better compression (sorted, immutable); transient ~2× during compaction. | Page fragmentation; values not duplicated across levels. |
| Hazard | Compaction backlog stalls writes; read amp grows if it falls behind. | Read tail predictable, but write throughput capped by random I/O. |
For a write-heavy KV store the LSM is the default precisely because sequential writes win — which is why Cassandra, RocksDB, and Dynamo-lineage stores use it. Choose the B-tree when point-read latency must be tight and predictable and the write rate is modest (the classic relational engine).
3. Deletes are tombstones — and a tombstone dropped too early resurrects the dead
In an append-only LSM you cannot erase the old value in place — it sits in some older SSTable. So a delete writes a tombstone: a marker version that says "this key is gone as of version V." Reads that find a tombstone return "not found"; compaction eventually drops the tombstone and the values it shadows. The subtle, dangerous part is when compaction may drop the tombstone. Suppose replica C was down or partitioned when the delete happened and never received the tombstone. If the other replicas compact the tombstone away too soon, then when C comes back, anti-entropy compares states, sees C "has" a value the others "lack," and dutifully replicates the deleted value back to life across the cluster.
gc_grace_seconds, default 10 days) ≥ the maximum time a node can be down and still rejoin, and a hard operational rule that a node down longer than that grace period must be wiped and rebuilt, never simply restarted — or it resurrects every key it missed a tombstone for.
Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Leaderless quorum vs single-leader | Availability + writes during single-node failure; no failover gap. | Conflict resolution, sibling versions, weaker ordering. | Multi-region or high-write, availability over linearizability. |
| LSM vs B-tree | Sequential, high write throughput. | Read + compaction amplification; compaction operational risk. | Write-heavy KV workloads (the default here). |
| R+W>N (strong) vs W=1,R=1 (fast) | Guaranteed fresh reads / read-your-writes. | Higher tail latency; lower availability per op. | Balances, locks, anything where a stale read is a correctness bug. |
| Version vectors vs last-write-wins | Detects concurrency; never silently drops a write. | Returns siblings the client/app must merge. | You cannot tolerate silent data loss (carts, counters). |
The sharpest trade is the last one. Last-write-wins is the cheapest conflict policy and the one that silently loses data. Picture two concurrent writes to the same key: client X sets v1, client Y sets v2, neither saw the other. LWW keeps whichever carries the larger timestamp and discards the other — and because timestamps come from wall clocks, a node with a fast clock can make the earlier write win. One of two acknowledged writes vanishes with no error, no log line, nothing. Version vectors instead record that v1 and v2 are concurrent (neither dominates) and return both as siblings, pushing the merge to the application (shopping carts union the items). You pay in a more complex client contract; you buy never silently destroying an acknowledged write. This is the lost-update story of DDIA Ch. 9, and it is the trap behind the senior question below.
Failure modes
| Failure | What happens | Mitigation |
|---|---|---|
| Replica divergence | Replicas drift after a missed write / partition. | Read repair on the hot path; scheduled anti-entropy with Merkle-tree checksums for cold keys. |
| Compaction backlog | Writes outrun compaction; read amplification and disk both balloon toward the ~6 TB peak. | Throttle writes, rate-limit compaction, or add capacity before L0 file count explodes. |
| LWW silent data loss | Concurrent writes + clock skew drop an acknowledged write with no error. | Version vectors to detect concurrency; CAS for read-modify-write; NTP is necessary but never sufficient. |
| Tombstone resurrection | A long-down replica re-spreads a deleted value. | GC grace ≥ max downtime; wipe-and-rebuild any node down past grace. |
| Hot partition | One popular key/range saturates its replica set. | Split the key, front it with a cache, or use adaptive partitioning (DDIA Ch. 6). |
Interview prompts you should be ready for
- Last-write-wins silently lost a write — walk me through how. (senior answer) Two clients write the same key concurrently, neither having read the other's value, so there is no happens-before order. LWW keeps exactly one — the higher timestamp — and discards the other. Because timestamps are wall-clock, a node with a fast clock can make the older write win, so the loser isn't even the "earlier" one. No error is raised; an acknowledged write just disappears. The fixes are to stop pretending the writes were ordered: use version vectors to detect that they were concurrent and surface both as siblings for the app to merge, or require CAS so a write that didn't see the latest version fails loudly instead of clobbering it. NTP narrows the skew but never closes it — clocks are not a correctness mechanism (DDIA Ch. 8, 9).
- Why does R+W>N guarantee a fresh read, and when does the guarantee evaporate? (senior answer) Pigeonhole: a write lands on W replicas, a read polls R replicas, and if R+W>N the two sets cannot be disjoint, so a read always touches at least one node with the latest write. It evaporates under sloppy quorum (the W writes went to non-home nodes, so the read set may miss them), under clock skew (if "freshest" is timestamp-decided), and under concurrent writes (no single "latest" exists). So R+W>N is necessary, not sufficient.
- Why an LSM-tree over a B-tree here? (senior answer) A KV store is write-heavy and the LSM turns writes into sequential WAL appends plus in-RAM inserts — far cheaper than a B-tree's in-place random page writes. The cost is deferred: read amplification across levels (bounded by bloom filters) and compaction write amplification. I'd pick a B-tree only if point-read tail latency had to be tight and predictable and the write rate were modest.
- How do deletes work, and how can a deleted value come back? (senior answer) A delete is a tombstone write, not an in-place erase. If compaction drops a tombstone before every replica has seen it, a replica that missed the delete still holds the value; on rejoin, anti-entropy sees that "extra" value and replicates it back — resurrection. The guard is a GC grace period that exceeds the longest a node can be down and rejoin, plus wiping any node that's been down longer.
- You set N=3, W=2, R=2 — what's your durability and availability story? (senior answer) Durability: a write isn't acked until it's on two of three replicas' disks (WAL fsync), so any single node loss preserves it. Availability: with one node down you can still reach W=2 and R=2, so writes and reads continue; lose two and you can't form a quorum, so I'd fall back to sloppy quorum for availability at the cost of the freshness guarantee, then repair.
- Where does a key live, and why not just hash mod N machines? (senior answer) Consistent hashing onto a ring with virtual nodes — covered in C02. Plain hash-mod-N remaps almost every key when the machine count changes; the ring moves only ~1/N of keys on a membership change, which is what makes scaling and node failure survivable without a full reshuffle.
- Your compaction is falling behind under write load — what do you see and do? (senior answer) L0 SSTable count climbs (read amplification rises because each read checks more files), disk creeps toward the ~6 TB transient peak, and write latency degrades. I throttle or shed writes, rate-limit/parallelize compaction, and add capacity. The root cause is sizing for steady-state disk and ignoring the ~2× compaction transient — provision for the peak, not the average.
Related foundation lessons
This case sits at the intersection of three foundation lessons. The key reaches its replica set via the consistent-hashing ring built in C02 — route the key there, don't re-derive virtual nodes here. The quorum and leader/follower mechanics, hinted handoff, and read repair are the subject of lesson 08; the consistency-vs-availability framing of R+W>N and what "stale read" even means is lesson 09's CAP material applied to a real store. The hot-partition failure mode and how rebalancing moves keys are lesson 07.