Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

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.

Advanced 25 min Last reviewed

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) and get(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:

FieldPurpose
keyhashed to place the item on the ring
valueopaque bytes
vector_clocklist of (node, counter) pairs, to detect concurrent versions
tombstonemarks 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

Dynamo-style key-value store: write, read, failure and repair paths Six storage nodes A to F sit on a hash ring. The key's preference list is A, B and C. Write path: the client sends a put to coordinator A, which writes locally and to B and C and succeeds after two acknowledgements. Read path: A asks B and C, returns after two replies and repairs any stale replica. Failure path: C is down, so A writes to D with a hint for C, and D hands the data back later. Background path: nodes gossip membership, and B and C compare Merkle trees to repair differences. put k W=2 / R=2 get k C is down write + hint for C hand back Merkle compare gossip Client put(k, v) A B C D E F coordinator hash ring, clockwise key k -> A, B, C Figure 1. Every node is equal; any node can coordinate. A key lives on the next three nodes clockwise. Step through the write, read, failure and background repair paths.
  1. 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.
  2. 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).
  3. 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.
  4. 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.

Vector clocks detect concurrent updates to a shopping cart Client 1 writes the cart twice through node A, giving clock A:2. During a partition client 2 updates the older version through node B, giving A:1, B:1. Neither clock dominates the other, so a later read returns both versions and the client merges them into one cart with clock A:3, B:1. Client 1 Node A Node B Client 2 put cart=[milk] -> v1 {A:1} put cart=[milk, eggs] -> v2 {A:2} partition: B never sees v2 put cart=[milk, bread] from v1 -> v3 {A:1, B:1} get: {A:2} and {A:1,B:1} are concurrent merge [milk, eggs, bread] -> {A:3, B:1} Figure 2. {A:2} and {A:1, B:1} are concurrent: each has a counter the other lacks. The store keeps both and the application merges them, so no item is lost.

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.

merkle.pyruns with python3 (standard library)
# 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

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Start at N=3, W=2, R=2. Fail one node: do reads and writes still work? Fail two.
  2. Set W=1, R=1 for speed. What guarantee is lost, and when could a read miss your latest write?
  3. 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

FailureImpactMitigation
One node downIts ranges lose a replicaSloppy quorum and hinted handoff keep writes going
Node down for daysHints pile up on stand-insDeclare it dead, re-replicate its ranges; anti-entropy fills gaps
Network partitionBoth sides accept writesVector clocks surface siblings for the application to merge
Hot keyOne preference list overloadedClient-side caching; split the key; more replicas for reads
Slow replicaTail latency risesReturn after the fastest R or W; do not wait for all N
Adding many nodes at onceHeavy data movementVirtual nodes spread the transfer; throttle rebalancing

Trade-offs we made

OptionWins whenLoses 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

  1. 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).

  2. 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.

  3. 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.

  4. 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.

  5. 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.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up