This is the distributed-systems fundamentals question. Almost everything in it — consistent hashing, quorums, gossip, LSM trees — reappears in other designs, so it is the highest-value problem on the sheet to actually understand.
Requirements
Functional
get(key)andput(key, value).- Values up to ~10 KB.
Non-functional
- Highly available; no single point of failure.
- Horizontally scalable — add nodes, get capacity.
- Low latency, and tunable consistency: the caller decides how strict.
CAP, concretely
Under a network partition you must choose:
- CP — refuse writes on the minority side rather than diverge. HBase, ZooKeeper, etcd.
- AP — accept writes everywhere and reconcile later. Dynamo, Cassandra, Riak.
Design the AP system, because it is the interesting one and it is what "design a key-value store" conventionally means. State the choice explicitly — saying "we accept eventual consistency in exchange for availability, and here is how we reconcile" is the answer.
Consistent hashing
Naive hash(key) % N remaps almost every key when N changes, which means a full
reshuffle on every node addition. Consistent hashing fixes it:
K/N, not all of them.Adding or removing a node only moves the keys between it and its predecessor — **K/N keys instead of all of them.**
Virtual nodes are essential. With one ring position per physical node, the split is
lumpy and removing a node dumps its entire range on one neighbour. Give each physical node
100–200 positions and load evens out, heterogeneous hardware can be weighted by position
count, and a departing node's load is spread across everyone.
Replication
Store each key on the N nodes clockwise from its ring position, skipping virtual nodes that map to the same physical machine — otherwise "three replicas" can be three copies on one box. Spread replicas across racks and availability zones for real fault tolerance.
Quorum consistency
N = replicas (typically 3)
W = nodes that must acknowledge a write
R = nodes that must respond to a read
W + R > N ⟹ read and write sets overlap ⟹ strong consistency| Setting | Behaviour |
|---|---|
| W=1, R=1 | Fastest, weakest. Eventual consistency |
| W=N, R=1 | Fast reads, slow writes. Good for read-heavy |
| W=1, R=N | Fast writes, slow reads |
| W=2, R=2, N=3 | The usual default — strong consistency, tolerates one node down |
W + R > N forces the write set and the read set to share a node — which is what makes the read strongly consistent.This is the real deliverable of the design: consistency becomes a per-request knob rather than a property of the system.
Conflict resolution
With W < N, two clients can write concurrently to different replicas. Options:
Last-write-wins by timestamp. Simple, and silently discards one write. Clock skew makes
it worse than it sounds. Cassandra defaults to this.
Vector clocks. Each replica keeps a counter; a value carries the vector of counters it
saw. Comparing two vectors tells you whether one causally descends from the other (keep the newer) or they are concurrent (a genuine conflict). Concurrent versions are returned to the client as siblings to reconcile — which is how Dynamo's shopping cart merges by union, so a removed item can reappear but nothing is ever lost.
Failure handling
Gossip for membership: each node periodically exchanges its view of the cluster with a
few random peers, so knowledge of a failure spreads without a central coordinator or an all-to-all heartbeat mesh.
Hinted handoff for temporary failures: if a replica is down, another node accepts the
write with a hint about where it belongs and forwards it when the owner returns. This is what keeps writes available during a brief outage.
Anti-entropy with Merkle trees for permanent divergence: each replica builds a hash
tree over its key range, and two replicas compare roots, then descend only into subtrees that differ. Divergence is found in O(log n) transfers instead of shipping the whole dataset.
Storage engine
Writes go to an in-memory memtable plus a write-ahead log; when the memtable fills it is flushed as an immutable sorted SSTable; background compaction merges SSTables. This is an LSM tree, and it turns random writes into sequential ones — the reason write-heavy stores prefer it to a B-tree.
Reads may have to check several SSTables, so each carries a Bloom filter: a compact probabilistic structure that answers "definitely not here" or "maybe here", eliminating most disk reads. Bloom filters are a favourite follow-up in their own right.
Follow-ups to expect
- Hot keys — one key overwhelming its replicas: add a cache layer, or shard the key.
- Range queries — not supported by hashing; that needs range partitioning, with the
hot-spot risk that brings.
- Read repair — when a read finds stale replicas, write the fresh value back inline.
- Sloppy quorum — accept writes on any N healthy nodes, not strictly the owners,
maximising availability during partitions.
- Rebalancing — moving data when a node joins, without stalling live traffic.
Track this problem on the System Design sheet.
Frequently asked
What is consistent hashing and why are virtual nodes needed?
Consistent hashing places both keys and nodes on a ring, assigning each key to the next node clockwise, so adding or removing a node only remaps K/N keys instead of nearly all of them. Virtual nodes give each physical machine many ring positions, which evens out an otherwise lumpy distribution, allows weighting by hardware capacity, and spreads a departing node's load across the whole cluster rather than dumping it on one neighbour.
What does W + R > N mean?
With N replicas, W nodes acknowledging each write and R nodes responding to each read, W + R > N guarantees the read set and write set overlap on at least one node — so a read always sees the latest acknowledged write. N=3, W=2, R=2 is the common default: strongly consistent while tolerating one node being down.
How does a key-value store resolve concurrent writes?
Either last-write-wins by timestamp, which is simple but silently discards a write and is vulnerable to clock skew, or vector clocks, which record causality so the system can tell whether one version descends from another or the two are genuinely concurrent. Concurrent versions are returned to the client as siblings for application-level reconciliation.