System Design HLD-19.04
Design a distributed key-value store
Design a Dynamo-style key-value store: consistent hashing, quorum replication, vector clocks, hinted handoff, Merkle tree repair and gossip.
The problem
Build a storage system with a tiny interface, get(key) and put(key, value), that holds hundreds of terabytes across a hundred or more machines, keeps answering when machines die or the network splits, and never makes a customer see "cannot add to cart". This is the problem Amazon described in its Dynamo paper, and the design it produced, together with descendants such as Cassandra and Riak, is the classic answer.
The difficulty is that every desirable property fights another. Spreading data over many nodes means some node is always failing. Keeping copies for safety means copies can disagree. Waiting for all copies to agree means waiting for the slowest or a dead one. The design is a set of techniques, each solving one of these problems, and the skill is knowing which knob trades what.
Requirements
Functional
put(key, value)andget(key), values up to about 1 MB, opaque to the store.- Concurrent writes to the same key must not silently lose data; conflicts are surfaced to the application.
Non-functional
- Scale: 10 billion keys, 100 TB of data, 500,000 reads and 100,000 writes per second at peak.
- Availability: writes always accepted, even during node failures and network partitions ("always writeable").
- Latency: p99.9 under tens of milliseconds for reads and writes.
- Durability: data survives the loss of any two machines.
- Elasticity: add or remove nodes without downtime, moving as little data as possible.
- Tunable consistency: per-use choice between faster reads and fresher reads.
Out of scope
- Range scans and secondary indexes, transactions across keys, strong (linearizable) consistency by default.
Estimates
- Raw storage: 10 billion keys at 10 KB average is 100 TB. With three replicas, 300 TB.
- Nodes: at 4 TB per node and 70 percent maximum fill, each node holds 2.8 TB, so about 107 nodes. Round to 120 for headroom and growth.
- Write load per node: each write goes to 3 replicas, so 300,000 replica writes per second over 107 nodes is about 2,800 per node. An append-friendly storage engine handles that easily ( Storage engines: B-tree vs LSM-tree ).
- Read load per node: with reads asking 2 replicas, 1,000,000 replica reads per second over 107 nodes is about 9,300 per node, most served from memory caches.
- Membership traffic: gossip with 120 nodes, each talking to one random peer per second, is 120 tiny messages per second, negligible.
API
get(key) -> [(value, context), ...] one or more versions
put(key, context, value) -> ok
The context is opaque to the client: it carries the version information (the vector clock) from the read. A client that read two conflicting versions merges them and writes back with the combined context, which tells the store the conflict is resolved. Per-request options let callers choose consistency, for example get(key, r=1) for a fast possibly-stale read.
Data model
There is no schema: a key is a byte string, the value an opaque blob. Each stored version carries:
| Field | Purpose |
|---|---|
key | hashed to place the item on the ring |
value | opaque bytes |
vector_clock | list of (node, counter) pairs, to detect concurrent versions |
tombstone | marks a delete, so it can replicate like a write |
Each node stores its share in a local storage engine, typically an LSM tree for fast writes, and keeps one Merkle treeA tree of hashes where each parent is the hash of its children, so comparing two roots tells you whether two datasets are identical, and walking down finds exactly where they differ. per key range it owns.
High-level design
- Write path (N=3, W=2) Any node can take the request; it forwards to the first healthy node of the key's preference list, A, which becomes coordinator. A stamps a new vector clock, writes locally, sends the write to B and C, and reports success once 2 of the 3 have acknowledged.
- Read path (R=2) A asks the replicas and answers once 2 have replied. If their versions differ, it returns the newest, or all concurrent versions, and writes the newest back to the stale replica in the background (read repair).
- Failure path: hinted handoff C is unreachable, so A writes the third copy to the next node on the ring, D, tagged with a hint saying it belongs to C. The write still gets its quorum. When gossip reports C alive again, D hands the data back and deletes its copy.
- Background: gossip and Merkle repair Every second each node gossips its view of membership with a random peer, so joins and failures spread without a master. Replicas of the same range periodically compare Merkle trees and copy only the keys that differ.
Deep dives
Deep dive 1: Partitioning with consistent hashing
Hash each key onto a ring, and give each node positions on the same ring. A key belongs to the first node clockwise from its hash, and its replicas to the next N-1 distinct nodes: that list is the key's preference listThe ordered list of nodes responsible for a key: its owner plus the next replicas clockwise on the ring, skipping virtual nodes of machines already in the list.. Adding a node takes over only the keys in the arcs it now owns, about 1/n of the data, instead of reshuffling everything as hash mod n would ( Consistent hashing ).
With one position per node, arcs are uneven and a new node takes load from just one neighbour. Giving each machine many virtual nodesMany positions on the hash ring for one physical machine, which evens out load and spreads the work of joins and failures across many machines. evens out the load and means a failed machine's ranges are picked up by many machines rather than one. Bigger machines get more virtual nodes, which handles mixed hardware.
Deep dive 2: Replication and quorums
Each key has N replicas. A write succeeds after W acknowledgements and a read returns after R replies. If R + W > N, every read set overlaps every write set in at least one replica, so a read sees the latest acknowledged write ( Quorums and leader election ). The common setting is N=3, W=2, R=2: survives one failed replica for both reads and writes, and every read overlaps the last write.
The knobs trade against each other. W=1 makes writes fast and available but risks losing a write if that single node dies before replicating. R=1 makes reads fast but possibly stale. W=N makes reads easy but any one slow node stalls writes. Note that Dynamo uses a sloppy quorum: when a preference-list node is down, the write goes to the next healthy node instead (hinted handoff), so the "W nodes" may not be the usual ones. That keeps writes available during failures at the cost of the strict overlap guarantee until hints are delivered.
Deep dive 3: Conflicts and vector clocks
With sloppy quorums and partitions, two clients can update the same key on different replicas at the same time. Last-write-wins by timestamp is simple but silently drops one update, and clocks are not trustworthy across machines ( Time and clocks ). A vector clockA list of counters, one per node that has coordinated writes to an item; comparing two lists tells whether one version descends from the other or whether they are concurrent. records causality instead.
Version X descends from Y if every counter in X is at least the one in Y; then Y can be discarded. If neither descends from the other, they are siblings and both are returned. For a shopping cart the merge is a union, which may resurrect a deleted item, and the Dynamo paper accepts that, because losing an "add to cart" is worse. Clocks are truncated when they grow past a size limit, which is rarely a problem because few nodes coordinate writes to any one key.
Deep dive 4: Failures, repair and membership
The system handles three kinds of trouble with three techniques:
- Temporary failures: hinted handoff, shown in step 3. The stand-in node keeps the data with a hint and returns it when the owner is back.
- Permanent divergence: replicas drift when hints are lost or a node is replaced. Anti-entropyA background process that compares replicas and repairs any differences, instead of waiting for reads to find them. compares replicas using Merkle trees, so in-sync ranges cost one hash comparison.
- Membership: no master tracks which nodes are alive. Each node periodically gossips its membership view with a random peer, and changes spread to everyone in a number of rounds that grows with the logarithm of the cluster size ( Membership, gossip and failure detection ).
Here is anti-entropy on a small scale: two replicas of 16 keys, one value differs.
# Anti-entropy with a Merkle tree: two replicas hold the same 16 keys
# except one. Compare hashes top-down and only descend where they differ.
import hashlib
def h(s):
return hashlib.sha256(s.encode()).hexdigest()[:8]
def build(items):
"""Return tree levels, leaves first. Each leaf hashes one key range."""
level = [h(f"{k}={v}") for k, v in items]
levels = [level]
while len(level) > 1:
level = [h(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
levels.append(level)
return levels
keys = [f"user:{i:02d}" for i in range(16)]
a = [(k, f"v1-{k}") for k in keys]
b = list(a)
b[11] = (keys[11], "v2-changed") # replica B has a newer value
ta, tb = build(a), build(b)
print("root A", ta[-1][0], " root B", tb[-1][0])
compared, todo = 0, [(len(ta) - 1, 0)] # (level, index), start at root
diff = []
while todo:
lvl, i = todo.pop()
compared += 1
if ta[lvl][i] == tb[lvl][i]:
continue # whole subtree in sync: skip it
if lvl == 0:
diff.append(keys[i])
else:
todo += [(lvl - 1, 2 * i), (lvl - 1, 2 * i + 1)]
print(f"hashes compared: {compared} (a full scan compares {len(keys)} values)")
print("keys to repair:", diff)Output
root A e0d8be5a root B 68704758
hashes compared: 9 (a full scan compares 16 values)
keys to repair: ['user:11'] The walk compared 9 hashes and found the one key to repair. That saving looks small for 16 keys, but it grows with size: with a million leaf ranges, one difference costs about 40 comparisons (two per level for 20 levels, plus the root) instead of a million. The catch is that Merkle trees are built per key range, so when ranges move during joins and leaves, their trees must be rebuilt.
Try it
Try this:
- Start at N=3, W=2, R=2. Fail one node: do reads and writes still work? Fail two.
- Set W=1, R=1 for speed. What guarantee is lost, and when could a read miss your latest write?
- With N=5, find the smallest W and R that still overlap and survive two failed nodes for both reads and writes.
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| One node down | Its ranges lose a replica | Sloppy quorum and hinted handoff keep writes going |
| Node down for days | Hints pile up on stand-ins | Declare it dead, re-replicate its ranges; anti-entropy fills gaps |
| Network partition | Both sides accept writes | Vector clocks surface siblings for the application to merge |
| Hot key | One preference list overloaded | Client-side caching; split the key; more replicas for reads |
| Slow replica | Tail latency rises | Return after the fastest R or W; do not wait for all N |
| Adding many nodes at once | Heavy data movement | Virtual nodes spread the transfer; throttle rebalancing |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Always writeable (AP, sloppy quorum) | Writes succeed during failures and partitions | Reads can be stale; clients must merge siblings |
| Vector clocks + client merge | No update silently lost | More complex clients and API; possible resurrected deletes |
| Last-write-wins instead | Simple; no siblings | Concurrent updates silently dropped; depends on clocks |
| N=3, R=2, W=2 | Overlapping quorums, tolerates one failure | Every request waits for the second-fastest replica |
| Leaderless (every node equal) | No leader election, no single point of failure | Harder reasoning about consistency than a leader-based store |
Extensions
- Strongly consistent operations for some keys, using a consensus protocol per range ( Consensus: Raft ), as many later stores offer.
- Multi-data-centre replication: put replicas of each key in several data centres, with a local quorum for latency.
- CRDT values such as counters and sets that merge automatically, removing the need for client merges.
- Range scans by ordering keys within each node, at the cost of uneven partitions.
In the wild
Amazon
Amazon's Dynamo (opens in a new tab)This post introduces the Dynamo paper presented at SOSP 2007. The driving requirement was that customers can view and add items to their shopping cart even when disks fail, network routes flap or data centres are lost, so Dynamo favours availability and is designed to be always writeable. Its summary table maps problems to techniques that match this lesson one for one: consistent hashing for partitioning, vector clocks reconciled during reads, sloppy quorum and hinted handoff for temporary failures, Merkle tree anti-entropy for permanent ones, and gossip for membership. It also notes that services measure performance at the 99.9th percentile rather than the average, and that the common configuration is N=3, R=2, W=2.
Check yourself
-
N=3, W=2, R=2. Why does a read see the latest acknowledged write?
Show answer
B. Any 2 readers and 2 writers out of 3 share at least one replica R + W > N forces overlap: some replica in every read set holds the latest write (strict quorums, no sloppy substitutes).
-
Replica C is down during a write. What does hinted handoff do?
Show answer
B. Writes C's copy to the next healthy node with a hint, to hand back when C returns The write keeps its quorum and the stand-in returns the data later, keeping writes available.
-
Versions with clocks {A:2} and {A:1, B:1} are found. What are they?
Show answer
C. Concurrent: neither descends from the other Each has a counter higher than the other's, so both are kept as siblings for the application to merge.
-
Why compare Merkle trees instead of every key during anti-entropy?
Show answer
A. Hashes are smaller than values, and identical subtrees are skipped with one comparison Comparison cost grows with the number of differences times the tree depth, not with the total number of keys.
-
Why give each machine many virtual nodes on the ring?
Show answer
B. To even out load and spread a failed machine's ranges over many machines Many small arcs per machine average out unevenness and spread the work of joins and failures.
Recap
- Consistent hashing with virtual nodes places keys and moves little data when nodes change.
- N replicas with W and R quorums tune durability, latency and freshness; R + W > N overlaps.
- Sloppy quorums and hinted handoff keep writes available when replicas are down.
- Vector clocks detect concurrent updates; the application merges siblings instead of losing writes.
- Merkle trees repair divergence cheaply, and gossip spreads membership without a master.
Next up
- Crack the system design round learning path