Dynamo: Amazon's Highly Available Key-value Store
2007 · SOSP · ~14 min read
Read the original paperA shopping cart must accept writes even while servers and whole data centres fail. Dynamo shows what you give up to make that true, and how to live with it.
The problem: the cart must never say no
Amazon’s shopping cart has one rule that outranks all others: a customer who clicks “add to cart” must succeed. A failed write is a lost sale and a lost customer. That rule has to hold while disks fail, servers fail, and whole data centres lose contact with each other, which at Amazon’s size is not a possibility but a daily event. And it must hold fast: the paper’s service level is measured at the 99.9th percentile, 300 milliseconds for a peak of 500 requests a second, because the slowest customers are the ones with the fullest carts.
The relational databases of 2007 could not promise this. They kept replicas consistent by making every write wait for agreement, and a replica that cannot reach the others must either refuse writes or risk diverging. Brewer’s CAP conjecture had put the choice plainly: during a network partition you keep consistency or availability, not both. Amazon chose availability, on purpose, and built a store around the consequences.
The idea: accept every write, resolve the conflicts later
Dynamo is a key-value store that is always writable. Any replica will accept a write even when it cannot talk to the others, and the system makes no attempt to prevent two replicas from accepting different writes to the same key at the same time. Instead it keeps both versions, detects the conflict when the key is next read, and hands the versions to the application to reconcile. For a shopping cart, reconciliation is a union: nothing a customer added is ever lost, though something they deleted may briefly reappear. The paper is candid that this is a business decision encoded in a database.
How it works
The paper is a catalogue of techniques, each solving one sub-problem, and most of them are now standard equipment. Consistent hashing places both keys and nodes on a ring; a key belongs to the first N distinct nodes clockwise from it, so adding or removing a node moves only the keys next to it. Each physical node owns many virtual nodes scattered around the ring, so load and the work of recovery spread evenly.
Keys hash to a point on the ring and belong to the next N distinct nodes clockwise. Virtual nodes spread each physical node around the ring so that load and recovery are shared evenly.
| key | owners (clockwise) | |
|---|---|---|
| cart:alice | B → D → E | — |
| cart:bob | D → E → C | — |
| cart:carol | D → E → C | — |
| cart:dan | E → C → A | — |
| cart:erin | E → C → A | — |
| cart:frank | D → E → C | — |
| cart:gina | E → C → A | — |
| cart:hal | D → E → C | — |
With R + W > N, any read set and any write set share at least one node, so a read returns the newest version on some replica. Dynamo lets you pick: W = 1 makes writes fast and available, R = 3 then pays for it on reads.
Versions are tracked with vector clocks, one counter per node that has touched the value. If one clock dominates another, the store knows which version is newer and discards the old one silently; if neither dominates, the writes were concurrent and both are returned. In production the paper found this was rare: 99.94 per cent of requests saw exactly one version.
Availability during failure comes from sloppy quorums and hinted handoff: if a replica is unreachable, the write goes to the next healthy node on the ring with a hint saying who it was for, and is handed back when the replica returns. Replicas that drift apart are reconciled in the background by comparing Merkle trees of their key ranges, so only the differing pieces are transferred. Membership and failure detection run on gossip, with no central coordinator anywhere in the system, which is itself a statement about availability.
What it changed
Dynamo was the engineering paper behind the NoSQL movement. Cassandra, built at Facebook a year later, combined Dynamo’s ring with Bigtable’s data model; Riak and Voldemort reimplemented the paper almost directly; the word “eventually consistent” entered everyday engineering vocabulary. Amazon’s own sequel is instructive: when Dynamo became the DynamoDB service in 2012, the team dropped vector clocks and application-side reconciliation, which developers found too hard, and offered a simple choice between eventually and strongly consistent reads instead. The techniques survived; the programming model was tamed.
Where you meet it today
- DynamoDB, Cassandra, ScyllaDB, Riak. The ring, the quorums and tunable consistency are the user-facing model of all of them.
- Consistent hashing everywhere. Load balancers, CDNs, distributed caches and Kafka partition assignment all use it to move as little as possible when membership changes.
- CRDTs. The reconciliation Dynamo left to the application was later formalised as data types that merge automatically, used in collaborative editors and Redis.
- Your own conflict policy. Any system with offline writes, from mobile apps to Git, faces the paper’s question: keep both, merge, or last-writer-wins.
The original. Read it after this page; the explainer above is a map, not a substitute.
The CTO who co-authored the paper on what it got right, what changed, and how it became DynamoDB.
The sequel: what fifteen years of running the idea as a service taught the team.