The whole design, in writing
Learn system design by building a distributed key-value store like DynamoDB or Cassandra step by step. An interactive guide covering consistent hashing, replication, quorum reads/writes, conflict resolution, gossip membership, and hinted handoff.
Every step of the build above, written out: the problem each piece solves, the option that was taken and the ones that were not, the numbers, and how it fails in production.
The big idea
What is a key-value store?
Sometimes you don’t need SQL — you need a giant, always-on dictionary: put(key, value) and get(key), spread across hundreds of machines, that never goes down even when machines do. A single database can’t offer that.
Build a distributed, replicated store with no single master. Spread keys across many nodes, keep several copies of each, and let any node serve a request. The hard part isn’t the dictionary — it’s staying available and consistent while machines fail.
What the new pieces do
- Clientclient
- Wants a simple contract: store a value under a key, get it back later, at massive scale and without ever going down. No joins, no SQL — just key in, value out.
Step 1 · The skeleton
Any node, one value
A client wants to put and get a key without knowing or caring which of hundreds of machines actually holds it. Routing every request through one master would just recreate the single point of failure we’re trying to avoid. So how does a request find its key?
A client must put/get a key across hundreds of machines, and it must never go down. Routing?
The master is exactly the single point of failure you’re trying to escape — when it dies the whole store stops. Masterful designs trade away the availability you can’t sacrifice here.
If that node dies those clients are stranded, and load can’t rebalance. Ownership must be able to move, and any node must be able to step in.
Every node runs the same code and can locate replicas and serve the request. No special master means no single failure stops the world — symmetry is the whole philosophy.
Let the client hit any node, which acts as the coordinator for that request: it finds the right home for the key and reads/writes there. Every node can coordinate, so there’s no special, fragile master.
What the new pieces do
- Coordinatorbackend
- Whichever node the client hits. It owns the request: locate the replicas, talk to them, and assemble the answer. There is no special master — every node can coordinate.
- Replica Astore
- The first node responsible for a key (the one the ring lands on). Holds the data on local disk, typically as an LSM-tree for fast writes.
Step 2 · Where does a key live?
Consistent hashing
With hash(key) % N, changing the number of nodes remaps almost every key — a catastrophic reshuffle every time you add or lose a machine. At scale, nodes change constantly.
Nodes are added and lost constantly. How do you map keys to nodes?
Changing N remaps almost every key — a catastrophic full reshuffle every time a machine joins or dies. Modulo hashing and a churning cluster are incompatible.
Adding or removing a node moves only the keys between it and its neighbor — about 1/N of the data, not all of it. Virtual nodes spread that load across many survivors.
A key→node table for billions of keys is huge, hot, and another single point of failure. The ring computes ownership locally from the hash — no lookup table needed.
Place nodes and keys on a hash ring. A key belongs to the first node clockwise from its hash. Add or remove a node and only the keys between it and its neighbor move — a tiny fraction, not the whole dataset.
- 1/Nkeys moved on change
- vnodeseven spread
- O(1)key → node
What the new pieces do
- Hash Ringservice
- Maps both keys and nodes onto a circle. A key is owned by the next node clockwise, so adding or removing a node moves only a small slice of keys.
Back of the envelope
- add/remove node ⇒ ~1/N keys move
- vs ~all keys with hash % N
- each node ⇒ many vnodes
- load spreads evenly; a death scatters across many survivors
- key → node = O(1) hash
- computed locally, no directory lookup
Step 3 · Survive a death
Replication
If a key lives on exactly one node, that node’s failure means the key is gone and unreachable. Disks and machines fail constantly at scale — single copies are not an option.
Disks and machines fail constantly. Where do you keep each key?
A single copy means the key is unreachable the instant that node fails, and backups are minutes-to-hours stale. At this scale a node is always down somewhere.
Full replication is ruinously expensive on storage and write cost, and pointless — you only need enough copies to survive a few failures, not all of them.
Three consecutive ring nodes (N=3) each hold a copy, so the key survives up to two failures and reads can hit the healthiest replica. The preference list skips vnode duplicates so copies land on distinct machines.
Store each key on the N nodes following its position on the ring (its “preference list”). With N=3, three consecutive nodes each hold a copy, so the key survives failures and can be read from whichever replica is closest or healthiest.
- N=3copies / key
- ring-adjacentreplicas
- 2failures tolerated
What the new pieces do
- Replica Bstore
- The next node clockwise on the ring. Holds a copy so the key survives one node’s death and can serve reads in parallel.
- Replica Cstore
- The third copy. With N=3, the key lives on three consecutive ring nodes, so it tolerates two failures and spreads read load three ways.
Back of the envelope
- N=3 copies on adjacent ring nodes
- survives 2 simultaneous failures
- preference list skips vnode dups
- copies land on distinct machines / racks
- read any healthy replica
- spreads read load N ways
Step 4 · Consistent or available?
Quorum reads & writes
With three copies, who’s the source of truth? Waiting for all replicas means one slow node stalls every request; trusting one risks reading stale data right after a write. CAP says you can’t have perfect consistency and availability under partitions.
With 3 copies, how many do you wait for on a read and a write?
One slow or dead replica now stalls every request — you’ve traded away availability entirely. Strict all-replica waits defeat the point of replicating.
Fast, but a read right after a write can hit a replica that hasn’t seen it — stale data. With no overlap guarantee you can’t promise the latest value.
When the read set and write set must overlap, every read sees the last write. R=W=2 on N=3 gives strong consistency with one-node fault tolerance — and you can re-tune per workload.
Use a quorum: a write succeeds after W replicas ack; a read consults R. Choose R + W > N and every read set overlaps the last write set — so you always see the latest value. Tune R and W to slide between fast and strongly-consistent.
- R + W > Noverlap rule
- W=2,R=2common N=3
- tunableC vs latency
What the new pieces do
- Quorum R/Wservice
- The tunable knob: a write waits for W replicas, a read for R. Make R + W > N and every read overlaps the latest write — consistency you can dial.
Back of the envelope
- R + W > N ⇒ sets overlap
- every read intersects the last acknowledged write
- N=3: W=2, R=2
- strong consistency + 1-node fault tolerance
- W=1 fast writes / R=1 fast reads
- slide the knob per workload
Step 5 · Two truths
Resolving conflicts
During a network partition, two replicas can each accept a write to the same key. When the partition heals, they disagree — and with W < N this is expected, not a bug. Which value wins?
A partition lets two replicas each accept a write to the same key. On heal, who wins?
Rejecting writes during a partition sacrifices the availability that’s this system’s whole reason to exist. In an AP store concurrent writes are expected, not preventable.
LWW is simple but silently drops a real concurrent update, and clock skew makes "last" unreliable. Fine for some data, data-loss for a shopping cart.
Vector clocks capture causality, so the system distinguishes a newer write from genuine divergence and can surface both siblings for the app (or a merge function) to reconcile — carts merge, counters add.
Attach version metadata to every write. Last-write-wins (by timestamp) is simple but can drop data. Vector clocks capture causality, detecting true conflicts and surfacing both versions (siblings) for the application — or a merge function — to reconcile.
What the new pieces do
- Conflict Resolverservice
- Two replicas can hold different values for the same key after a partition. Vector clocks (or last-write-wins) decide which version survives, or surface both.
Step 6 · Who’s alive?
Gossip membership
Coordinators need to know which nodes are up and who owns which ring range — but a central membership registry would be another single point of failure and a bottleneck.
Nodes gossip: each periodically exchanges health and ring state with a few random peers. Within seconds the whole cluster converges on a shared view of membership — fully decentralized, no coordinator required.
What the new pieces do
- Gossip Membershipbus
- Nodes periodically swap health and ring info peer-to-peer. No central registry — the cluster collectively knows who is up and who owns what.
Step 7 · Heal while degraded
Hinted handoff & read repair
If a target replica is temporarily down during a write, do you reject the write (hurting availability) or accept it and risk that replica permanently missing the update?
A target replica is down during a write. Reject the write, or accept it?
That makes writes fail whenever any replica is down — and something is always down at scale. You’d be choosing consistency over the availability you promised.
Hinted handoff keeps writes always-succeeding: a stand-in node stores the write and forwards it when the rightful replica returns. Read repair and Merkle-tree anti-entropy converge the rest.
Then that replica is permanently stale and quorums silently weaken. You must track the missed write (a hint) and replay it — accepting without healing just hides divergence.
Accept it: a healthy node stores a hint and replays the write to the rightful replica once it returns (hinted handoff). Meanwhile, reads that notice a stale replica push the fresh value back to it (read repair), and background anti-entropy (Merkle trees) reconciles the rest.
You did it
You just designed a key-value store.
Everything you assembled, in order
- Any node coordinates — no master, no single point of failure.
- Consistent hashing maps keys to nodes; only 1/N keys move on change.
- Each key replicated to the next N nodes on the ring for durability.
- Quorum reads/writes with R + W > N give tunable consistency.
- Vector clocks detect and resolve conflicting concurrent writes.
- Gossip spreads membership and ring state with no central registry.
- Hinted handoff and read repair keep replicas converging through failures.