In January I started reading Dynamo: Amazon’s Highly Available Key-value Store. I wanted to understand why a storage system would deliberately return conflicting versions instead of preventing conflicts in the first place.
The answer is the workload. Dynamo was designed for internal Amazon services such as shopping carts, preferences and session state. For these services, refusing a write during a network partition could be worse than accepting the write and reconciling later.
Dynamo is the system described in the 2007 paper. It is an ancestor of several distributed database ideas, but it is not the same product as Amazon DynamoDB.
Paper: Dynamo: Amazon’s Highly Available Key-value Store (PDF)
The requirement shapes the database
Dynamo exposes a small primary-key interface: get and put. It does not try to provide joins, foreign keys or multi-row transactions. Removing those requirements lets the system optimize for a different target:
- Writes should remain available when machines or network paths fail.
- The system should scale by adding ordinary machines.
- Operations should have predictable latency, including at high percentiles.
- Operators should be able to tune durability and consistency for each service.
This is an important design lesson. A distributed database is not “better” because it has more guarantees. It is useful when its guarantees match the application.
Partitioning with consistent hashing
Dynamo hashes both keys and nodes into a circular token space. A key belongs to the first node encountered while moving clockwise around the ring. The next nodes on the ring hold replicas.
If ordinary modulo hashing were used, changing the number of machines would remap most keys. Consistent hashing limits movement to neighbouring ranges. Dynamo also assigns multiple virtual positions to a physical node. Virtual nodes improve balance, let a powerful server own more of the ring and make recovery work easier to distribute.
The ring answers two different questions:
Partitioning: which node coordinates this key?Replication: which N nodes form this key's preference list?The preference list skips duplicate physical nodes so replicas actually represent independent failure domains.
Tunable N, R and W
Dynamo describes replication with three values:
- N: number of replicas for each key.
- W: replicas that must confirm a write.
- R: replicas consulted by a read.
For example, N=3, W=2, R=2 means a write waits for two acknowledgements and a read waits for two versions. When R + W > N, the read and write quorums overlap under normal conditions.
That formula is useful, but it does not magically create strong consistency. Dynamo uses sloppy quorums during failures, concurrent updates can create siblings and clocks can be lost or delayed. The real guarantee depends on routing, failure conditions and the reconciliation policy.
The deeper point is that consistency is configurable. A shopping cart may prefer an available write and merge later, while another workload may require stricter coordination.
Versioning instead of overwriting
In a single-node database, a newer write can simply replace an older value. In a distributed system, two clients may update different replicas while the network is partitioned. Neither update is globally “the latest.”
Dynamo attaches a vector clock to each object version. A simplified clock looks like this:
{node-a: 4, node-b: 2}Each entry records how many updates from a node are included in that version. Comparing two vector clocks gives three useful results:
A descends from B → A contains B's history; keep AB descends from A → B contains A's history; keep BNeither dominates → concurrent versions; keep bothWhen versions are concurrent, Dynamo returns siblings to the caller. The application may know how to merge them. A shopping cart can often merge item sets more meaningfully than the database can.
This moves complexity across the API boundary. Availability improves, but the application must understand conflicts. Last-write-wins would look simpler, yet it can silently discard a valid update when clocks disagree.
Sloppy quorum and hinted handoff
A strict quorum writes only to the key’s normal replica set. Dynamo instead favours availability. If a preferred replica is unavailable, the coordinator writes to another healthy node. That substitute stores a hint identifying the intended owner.
When the failed node returns, the substitute forwards the hinted data and can delete its temporary copy. This is hinted handoff.
normal: coordinator → A, B, CC is down: coordinator → A, B, D (D holds C's hint)recovery: D → CSloppy quorum keeps requests moving during transient failures. It also means the replicas that acknowledged a write may not be the normal preference list, which is one reason simple quorum arithmetic is not the whole consistency story.
Read repair and Merkle trees
Hinted handoff handles temporary unavailability, but replicas can still diverge. Dynamo repairs them in two ways.
Read repair happens on the request path. The coordinator compares versions returned by replicas and sends the newest or reconciled value to stale replicas.
Anti-entropy repair runs in the background. Replicas summarize key ranges with Merkle trees. A Merkle tree hashes data at the leaves and hashes child hashes up to a root. Equal roots imply equal contents for that range. Different roots let nodes recursively find the small region that differs instead of transferring everything.
Merkle trees are valuable because repair traffic is proportional to the disagreement, not the full dataset. The tree must be aligned with partition ownership; moving ranges can require recalculation.
Membership and failure detection
Dynamo avoids a central coordinator for normal operation. Nodes exchange membership and failure information using gossip. A node treats failure detection as a local observation rather than a globally agreed fact.
That distinction matters. In an asynchronous network, “the node is dead” and “I cannot currently reach the node” look the same. Dynamo routes around suspected failures and repairs later rather than blocking while the whole cluster agrees.
Membership changes are initiated explicitly and propagated through the system. This is safer than allowing transient communication failures to automatically remove nodes and move large amounts of data.
What the paper teaches me
Dynamo is a collection of mechanisms supporting one decision: remain writable through failure, then expose or repair disagreement deliberately.
The pieces reinforce each other:
consistent hashing → incremental partition movementreplication → copies across failuressloppy quorum → availability during partial failurevector clocks → detect concurrent historieshinted handoff → recover temporary replica placementMerkle trees → repair long-lived divergence efficientlygossip → decentralised membership knowledgeThe cost is not hidden. Conflict resolution becomes part of the data model, reads may observe multiple versions, background repair consumes capacity and operational reasoning becomes more complex.
The lasting lesson is to start from the failure policy. If the product must accept writes while parts of the system cannot communicate, inconsistency is not an edge case. It is a normal state that needs a representation, an API and a repair path.
Questions I keep from this reading
- Can the domain merge concurrent values without losing meaning?
- Which is more damaging: rejecting a write or returning stale data?
- How are hot keys handled when hashing balances ranges but not popularity?
- What happens when hinted handoff queues grow during a long outage?
- Are repair, compaction and foreground traffic isolated from one another?
- Which consistency statement can the application actually rely on during failure?
Those questions are more useful than memorising N, R and W. They connect the paper’s mechanisms to the application that has to live with them.