Want to try it yourself first?
Answer each stage in the practice workspace, sketch the architecture, or run a timed mock, then come back here to compare.
The problem
A key-value store does one thing: store a value under a key and give it back later. On one machine that's a hash map plus a file. The interview question is about doing it across dozens of machines: splitting the keys so each machine holds a fair share, keeping copies so no single failure loses data, letting the caller choose between speed and consistency, and continuing to accept reads and writes while a node is dead. Every database you use is a key-value store underneath, so this design also explains how Cassandra, DynamoDB and Riak work.
Watch: Design a Key-Value Store
Consistent hashing puts nodes and keys on a ring, so each key belongs to the first node clockwise and adding a node only moves one slice; virtual nodes spread that load evenly. Every key is copied to the next 3 nodes, and quorums with R + W > N (2 + 2 > 3) make every read see the latest write. Gossip heartbeats detect dead nodes, hinted handoff keeps writes flowing while one is down, and Merkle trees repair only the ranges that differ. Conflicts are resolved by last-write-wins or vector clocks, and each node stores data in a commit log, memtable and SSTables with Bloom filters and compaction.
Functional Requirements
The core features we need to support:
put(key, value): store a value (up to, say, 1 MB; typically around 1 KB) under a key.get(key): return the latest value for a key, or "not found".delete(key): remove a key (implemented as a write of a tombstone, as we'll see).- Tunable consistency per request: a caller can ask for a fast, possibly stale read, or a slower read that is guaranteed to see the latest acknowledged write.
- Always writable: a single node failure (or two, depending on settings) must not stop reads or writes.
Example. A shopping-cart service calls put("cart:42", {...}). The key hashes to a spot on the ring, the write goes to the three nodes that own that spot, and the call returns once two of them confirm. A second later, get("cart:42") asks two of the three and returns the newest version.
Out of scope for a first pass: range scans and secondary indexes, multi-key transactions, and SQL. Mention them so the interviewer knows you're scoping on purpose.
Scale Requirements
Rough numbers to anchor the design:
- 10 TB of unique data with 1 KB average values → about 10 billion keys.
- Replication factor 3 → 30 TB stored across the cluster.
- 100,000 reads/s and ~10,000 writes/s at peak.
- Bandwidth: 100k × 1 KB ≈ 100 MB/s of values returned to clients, before replication traffic.
How many nodes?
- Storage: assume ~2 TB of usable disk per node (a 4 TB SSD kept about half full, because compaction temporarily needs free space). 30 TB / 2 TB = at least 15 nodes.
- Headroom: plan ~20 nodes, so the cluster still fits when a node is down or rebuilding, and has room to grow.
- Throughput: 100,000 reads/s spread over 20 nodes ≈ 5,000 reads/s per node, comfortably within what one SSD-backed node can serve. (With R = 2 each read touches two replicas, so each node does about 10,000 replica reads/s; writes add 10,000 × 3 / 20 = 1,500 replica writes/s per node.)
With 256 virtual nodes per machine, that's 20 × 256 = 5,120 tokens on the ring, and each machine holds about 30 TB / 20 = 1.5 TB, or ~1.5 billion keys.
Non-Functional Requirements
- High availability. Writes must succeed even when a node is down. This is the defining choice of a Dynamo-style store: it is AP under the CAP theorem.
- Durability. An acknowledged write must survive a node crash (commit log on disk) and a permanent node loss (copies on other nodes).
- Low latency. Single-digit milliseconds at p99 for gets and puts. That means no cross-node coordination beyond the quorum, and no leader election in the request path.
- Horizontal scalability. Adding a node should move only a small, even slice of the data.
- Tunable consistency. Eventual consistency by default; stronger guarantees when the caller asks for them via R and W.
- No single point of failure. Every node runs the same code and can coordinate any request (leaderless, peer to peer).
API
consistencypicks W or R for this one call:ONE,QUORUM(2 of 3), orALL.contextis the version metadata (a timestamp or vector clock) returned byget. Passing it back on the nextputtells the store which version you're replacing, which is how conflicts are detected.- If the store keeps conflicting versions,
getcan return more than one value (siblings) and the client merges them.
Any node can receive a request. The node that handles it is the coordinator for that request: it finds the replicas for the key and runs the quorum.
Data Model
| Store | Shape | Notes |
|---|---|---|
| Record | key → value, version (timestamp or vector clock), tombstone? | a delete is a record with tombstone = true |
| Ring / membership | list of (token, node) + node status | every node holds a full copy, spread by gossip |
| Commit log | append-only file of writes | replayed on restart to rebuild the memtable |
| Memtable | in-memory sorted map, ~64–256 MB | flushed to an SSTable when full |
| SSTables | immutable sorted files on disk + index + Bloom filter | merged by compaction |
| Hints | target_node → list of writes it missed | replayed when the target comes back |
| Merkle trees | hash tree per key range | compared between replicas for anti-entropy |
Tombstones can't be dropped right away: a replica that missed the delete would otherwise "resurrect" the old value during repair. They are kept for a grace period (Cassandra's default is 10 days) and removed by compaction afterwards.
High-Level Design
A put:
- The client sends
put("cart:42", v)to any node, which becomes the coordinator. - The coordinator hashes the key, finds its position on the ring, and walks clockwise to collect the first 3 distinct physical nodes: the preference list, say B, C, D.
- It sends the write to all 3 in parallel. Each node appends to its commit log, updates its memtable, and acks.
- As soon as W = 2 acks arrive, the coordinator returns success. The third write still completes in the background.
A get:
- The coordinator sends the read to the replicas and waits for R = 2 responses.
- If the versions match, it returns the value. If one is older, it returns the newest and sends the newer version to the stale replica (read repair).
There is no leader: every node has the same role, the ring is shared by gossip, and the client library can even hash keys itself and send each request straight to a replica, saving a hop.
Deep Dive: Consistent Hashing and Virtual Nodes
Why not hash(key) % nodes? Going from 20 to 21 nodes changes the result for about 20/21 ≈ 95% of keys, so nearly all the data moves.
Consistent hashing. Hash both keys and nodes onto the same ring (say 0 to 2^64 − 1). A key belongs to the first node clockwise from its hash. Adding a node only takes over the keys between it and its predecessor, about 1/21 ≈ 5% of the data.
Ring example. Five nodes A, B, C, D, E sit clockwise on the ring. A key that hashes just past A belongs to B, and with N = 3 its preference list is the next 3 distinct nodes clockwise: B, C, D.
Virtual nodes. With one position per machine, the gaps on the ring are uneven: one machine can own twice the range of its neighbor. So each physical machine takes 256 positions (tokens). Three effects:
- Load evens out: each machine owns hundreds of small slices instead of one big one.
- When a machine dies, its slices are spread across many machines, not dumped on one neighbor.
- A bigger machine can take more tokens than a small one.
Preference list. For replication factor N = 3, walk clockwise from the key and take the first 3 tokens that belong to different physical machines (skipping tokens that map to a machine already chosen, and ideally to different racks or availability zones).
Deep Dive: Replication and Tunable Quorums
Every key lives on N = 3 replicas. The caller picks how many must answer:
| Setting | W | R | Behavior |
|---|---|---|---|
| Quorum | 2 | 2 | R + W = 4 > 3: every read overlaps the write set, so it sees the latest acknowledged write. Tolerates 1 node down. |
| Fast writes | 1 | 3 | Writes return after one ack; reads must ask everyone. |
| Fast reads | 3 | 1 | Reads hit one node; a write fails if any replica is down. |
| Fastest | 1 | 1 | Lowest latency, but a read can miss the latest write (eventual consistency). |
Why the overlap works. With W = 2, at least 2 of the 3 replicas have the new value. With R = 2, the read asks 2 of the 3. Two sets of size 2 drawn from 3 nodes must share at least one node, so the read always includes a copy with the newest version, and the coordinator returns the one with the higher version.
Latency. A quorum waits for the 2nd-fastest of 3 replicas, not the slowest, so one slow node doesn't hurt p99.
Caveat. R + W > N gives overlap only among the nodes in the preference list. Sloppy quorums (next section) relax this during failures, which is the price of staying writable.
Deep Dive: Surviving a Node Dying
This is the heart of the design. Node failures are split into temporary (a reboot, a network blip, minutes to hours) and permanent (a dead disk).
1. Temporary failure: sloppy quorum + hinted handoff. Take the 5-node ring A–E. The preference list for cart:42 is B, C, D, and B is down.
- A strict quorum would still succeed with W = 2 (C and D), but with a second replica down, writes would fail.
- A sloppy quorum instead sends B's copy to the next healthy node clockwise past the preference list: E. The write goes to C, D and E, and E stores the value with a hint: "this belongs to B".
- When gossip reports that B is back, E hands the write off to B and deletes its copy. Hints are only kept for a limited window (Cassandra's default is 3 hours) so they don't pile up forever.
Result: writes keep succeeding while B is down, and B catches up within seconds of returning.
2. Missed updates: read repair. A read with R = 2 that sees C at version 7 and B at version 6 returns version 7 and writes it back to B. Hot keys repair themselves.
3. Permanent failure: Merkle-tree anti-entropy. Hints expire and cold keys are never read, so replicas still drift. Each replica builds a Merkle tree per key range: leaves are hashes of key ranges, and each parent is the hash of its children. Two replicas compare the root hash; if equal, the whole range is in sync. If not, they descend only into the children that differ. Comparing a range of 1 billion keys with 2^15 leaves takes ~15 levels of hash comparisons and transfers only the leaves that actually differ.
If B is declared permanently dead, an operator (or automation) removes it from the ring. Its 256 token ranges are taken over by many other machines, which stream the data from the surviving replicas, so the rebuild is spread across the cluster instead of hammering one neighbor.
Deep Dive: Gossip Membership and Failure Detection
- Gossip. Every second, each node picks a few random peers and exchanges heartbeats and its view of the cluster: node list, tokens, status, and a heartbeat counter per node that only its owner increments. The newer view wins for each entry.
- Spread. Information roughly doubles every round, so news reaches all nodes in about log₂(N) rounds: for 20 nodes, around 5 seconds.
- Failure detection. If a node's heartbeat counter hasn't increased for about 10 seconds, peers mark it suspected down. Cassandra refines the fixed timeout with a phi accrual detector: it learns each peer's normal heartbeat interval and outputs a suspicion level, so a node on a slow network link isn't falsely marked dead.
- Local, not global. Being "down" in gossip only stops coordinators from sending requests to that node and triggers hinted handoff. It does not remove the node from the ring; that is an explicit, slower decision, because a network partition looks exactly like a dead node.
- Seed nodes. A new node bootstraps by contacting a few well-known seed nodes, then learns everything else through gossip.
Deep Dive: Conflict Resolution
Because writes go to whichever replicas are reachable, two versions of the same key can exist at once.
Option 1: last-write-wins (LWW). Every write carries a timestamp; the highest one wins. Simple and used by Cassandra.
- Downside: clocks drift. If node A's clock is 50 ms ahead, its write can win over a write that actually happened later, and the other write is silently lost.
- Fine for data where a lost concurrent update is acceptable (a user's last-seen time, a cached profile).
Option 2: vector clocks. Each version carries a list of (node, counter) pairs, e.g. [A:2, B:1].
- If one clock is ≥ the other in every entry, it's a newer version: discard the old one.
- If neither dominates (
[A:2, B:1]vs[A:1, B:2]), the writes were concurrent. The store keeps both as siblings and returns both on the nextget. - The client merges them (for a shopping cart, take the union of items) and writes back with the merged context, which collapses the siblings.
Trade-off: LWW is simpler and needs no client logic but can lose writes; vector clocks never lose a write but push merging onto the application. Dynamo used vector clocks; Cassandra and DynamoDB use LWW-style resolution.
Deep Dive: The Storage Engine (LSM Tree)
Each node uses a log-structured merge tree, which turns random writes into sequential ones.
Write path:
- Append the write to the commit log (write-ahead log) on disk. This makes it durable; on a crash the log is replayed.
- Insert it into the memtable, an in-memory sorted map.
- When the memtable reaches ~128 MB, write it to disk as an immutable, sorted SSTable and start a new memtable. The commit log segment can then be dropped.
Read path:
- Check the memtable.
- Check SSTables from newest to oldest. For each one, first check its Bloom filter: if it says "not here", skip the file with no disk read. At 10 bits per key the false-positive rate is about 1%; for ~1.5 billion keys per node that's ~1.9 GB of RAM.
- If the filter says "maybe", use the SSTable's sparse index to jump to the right block and read it.
Compaction. Over time a key can appear in many SSTables (old versions, tombstones). Background compaction merges SSTables, keeps only the newest version of each key (dropping overwritten values), and drops tombstones older than the grace period. Size-tiered compaction is cheaper for write-heavy loads; leveled compaction keeps reads to about one SSTable per level at the cost of more rewriting. Compaction needs free disk space for the merged output, which is why nodes run at about 50% full.
Wrap-Up & Trade-offs
A solid answer hits these points:
- Partitioning: consistent hashing with virtual nodes (e.g. 256 per machine), so adding or losing a node moves only a small, even slice of data.
- Replication: N = 3 copies on the next distinct machines clockwise (the preference list), spread across racks or zones.
- Tunable quorums: W = 2, R = 2 gives R + W > N overlap; W = 1 / R = 1 for speed at the cost of stale reads.
- Node failure: sloppy quorum + hinted handoff for temporary outages, read repair for hot keys, Merkle-tree anti-entropy for everything else, and token ranges re-streamed from replicas for permanent loss.
- Membership: heartbeats gossiped to a few random peers every second; no heartbeat increase for ~10 s → suspected down; no central coordinator.
- Conflicts: last-write-wins (simple, can lose writes) vs vector clocks with siblings (no lost writes, client merges).
- Storage: commit log + memtable flushed to SSTables, a Bloom filter per SSTable, and compaction that drops overwritten values and expired tombstones.
CAP / PACELC. During a Partition, this design chooses Availability over Consistency (sloppy quorums keep accepting writes). Else, in normal operation, it trades Latency against Consistency through R and W. Strongly consistent systems (Spanner, etcd) make the other choice: they refuse writes without a majority and pay for it in latency.
Common follow-ups: range queries (needs order-preserving partitioning, which risks hot spots), multi-datacenter replication (per-DC quorums like Cassandra's LOCAL_QUORUM), hot keys (caching or splitting the key), and lightweight transactions (Paxos on top for compare-and-set).
Common follow-up
One of the three replicas for a hot key range dies in the middle of a write burst and doesn't come back for six hours. Walk through what happens to writes, reads, and the data on that node, from the first failed request until it's fully caught up (or replaced).