Amazon Dynamo Explained: Eventual Consistency
On this page
Dynamo's requirement: never refuse a cart update
Amazon's shopping cart had one overriding requirement: customers must always be able to add items, even when servers or data centers fail. An unavailable cart costs sales directly; a cart that briefly shows a stale item costs little. The 2007 paper "Dynamo: Amazon's Highly Available Key-value Store" describes the design that met it, and it shaped a generation of databases.
The trade-off was explicit: choose availability during partitions (AP, Day 5) and low latency the rest of the time (EL, Day 6), and handle the resulting conflicts deliberately.
Dynamo's building blocks
| Problem | Dynamo's technique | Course day |
|---|---|---|
| Spread data over nodes | Consistent hashing with virtual nodes | 11 |
| Keep copies | Each key on the next N distinct nodes clockwise | 7 |
| Balance consistency and latency | Tunable N, W, R quorums | 9 |
| Concurrent updates | Vector clocks to detect conflicts; siblings returned to the application | 4, 10 |
| Temporary node failures | Sloppy quorum with hinted handoff | 9 |
| Permanent divergence | Anti-entropy with Merkle trees | below |
| Membership and failure detection | Gossip protocol | 20 |
A Dynamo write: sloppy quorum and hinted handoff
- The client sends
put(cart:42, ...)to any node, which becomes the coordinator. - The coordinator finds the key's N = 3 replicas on the ring and sends the write with an updated vector clock.
- One replica is down. Instead of failing, the coordinator writes to the next healthy node, with a hint: "this belongs to node C". (That's a sloppy quorum.)
- Once W = 2 replicas acknowledge, the write succeeds.
- When C returns, the substitute hands the data over (hinted handoff).
A Dynamo read: siblings and read repair
- The coordinator asks R = 2 replicas.
- If their versions are causally ordered (vector clocks), it returns the newest.
- If they're concurrent, it returns all versions as siblings; the application merges them (for carts: union of items) and writes back the merged version.
- Replicas that returned stale data are updated: read repair.
Anti-entropy with Merkle trees
Hinted handoff and read repair miss data that's rarely read or whose hints were lost. In the background, replica pairs compare data using Merkle trees: a tree of hashes where each leaf covers a range of keys and each parent hashes its children. Comparing roots tells you instantly whether two replicas match; if not, walk down only the branches that differ. Two replicas holding millions of keys find a handful of differences after exchanging a few hashes.
Here's that walk on two replicas of 100,000 keys, where one replica missed a single update:
# merkle.py: find where two replicas differ by comparing hashes from the root down
import hashlib
def sha(s): return hashlib.sha256(s.encode()).hexdigest()
def bucket(key, n): return int(sha(key), 16) % n # which key range a key falls in
def build(data, n=1024): # n leaves, a power of two
ranges = [[] for _ in range(n)]
for k in sorted(data):
ranges[bucket(k, n)].append(f"{k}={data[k]}")
tree = [[sha(";".join(r)) for r in ranges]] # leaf: hash of one key range
while len(tree[-1]) > 1: # parent: hash of its two children
lvl = tree[-1]
tree.append([sha(lvl[i] + lvl[i + 1]) for i in range(0, len(lvl), 2)])
return tree # tree[-1][0] is the root
def diff(t1, t2, level, i, stats):
stats["compared"] += 1
if t1[level][i] == t2[level][i]:
return [] # identical subtree: skip it all
if level == 0:
return [i]
return diff(t1, t2, level - 1, 2 * i, stats) + diff(t1, t2, level - 1, 2 * i + 1, stats)
a = {f"cart:{n}": "v1" for n in range(100_000)}
b = dict(a); b["cart:4242"] = "v2" # one replica missed one update
ta, tb = build(a), build(b)
stats = {"compared": 0}
ranges = diff(ta, tb, len(ta) - 1, 0, stats)
print("ranges that differ:", ranges, "| hashes compared:", stats["compared"])
print("keys to exchange:", sum(1 for k in a if bucket(k, 1024) in ranges), "of", len(a))ranges that differ: [52] | hashes compared: 21
keys to exchange: 101 of 100000Twenty-one hash comparisons narrowed 100,000 keys down to one range of about a hundred, and only those keys are sent across. With one leaf per key range, the work grows with the number of differences times the tree's height, not with the size of the data. Cassandra builds trees like these during nodetool repair, one per token range, and streams only the ranges whose hashes differ.
Dynamo's legacy: Cassandra, Riak and DynamoDB
- Cassandra (2008) took Dynamo's partitioning and replication (ring, tunable consistency, hinted handoff, read repair, Merkle-tree repair, gossip) and combined it with Bigtable's data model. It uses last-write-wins per column instead of vector clocks and siblings, trading correctness under concurrency for simplicity.
- Riak followed Dynamo closely, including vector clocks (later dotted version vectors) and CRDT data types.
- Amazon DynamoDB (2012) shares the name and lessons but is a different, managed system: it uses leader-based replication per partition with Paxos, offers strongly consistent reads on request, and later added transactions.
The enduring lessons: decide the consistency trade-off per business need, make failure normal rather than exceptional, and push conflict handling to where the domain knowledge lives.
Check yourself
When a target replica is unreachable, another node accepts its writes temporarily, storing them with a hint saying who they belong to, and delivers them once the replica returns. Writes stay available during short outages, at the cost of temporarily weaker quorum guarantees.
Vector clocks showed the versions are concurrent, so the store can't pick a winner safely; the application merges them, for example by uniting cart items.
Replicas compare hashes from the root down and only examine branches whose hashes differ, so few hashes need exchanging to find differences.
When a read finds replicas with different versions, the coordinator writes the newest version back to the stale ones, so frequently read data converges quickly.
A refused cart update loses a sale, while a merged cart with an extra or reappearing item is a minor annoyance. The business cost decided the trade-off.