Amazon DynamoDB — the reference production implementation

It is 2004. Amazon.com is the biggest e-commerce site in the world. Their shopping-cart service — the thing that has to accept a "add to cart" click at all times, from any user, at any scale — is running on a single MySQL master with slaves. Every year at Christmas the traffic spikes 5×. Every year the shopping cart goes down for hours. Every year Amazon loses tens of millions of dollars.

Werner Vogels, then Amazon's CTO, made a radical call: availability matters more than consistency for the shopping cart. It is better to accept a write that might briefly disagree with another write than to reject the write and lose a customer. They built a new system on that principle. In 2007 they published the paper. They called it Dynamo. In 2012 they wrapped it in an API and released it as a hosted service: DynamoDB. Today it stores petabytes for millions of customers and never goes down.

Consistent hashing is the load-distribution primitive that makes the whole thing work. Everything else — replication, conflict resolution, failure handling — is layered on top of it.

The shape of the ring

Dynamo uses a 128-bit hash space — 2¹²⁸ positions, which is roughly 3.4 × 10³⁸. This is not because they needed 340 undecillion positions. It is because they chose MD5 as the hash function, which naturally produces 128 bits, and used the full output as the position. Cheaper than truncating. Overkill in a good way — collision probability is astronomically zero even with millions of virtual tokens.

Each physical host owns roughly 100 virtual tokens (they call them vnodes in the paper, but the term for that exact position on the ring is token). Each token is computed as MD5(host_name + "#" + token_index). So host-A#0, host-A#1, ..., host-A#99 each produce a random-looking 128-bit position. Together they cover the ring evenly — statistically, host A holds ~100/T of the ring, where T is the total token count across all hosts.

The preference list — the whole innovation in three lines

Here is what makes Dynamo special. For every key, Dynamo does not just find one node clockwise. It finds the first N distinct physical hosts going clockwise. This list — in order — is the preference list. N is a per-table setting; typically N = 3 for production tables.

The subtlety is "skip tokens whose host is already in list." With 100 tokens per host, the first three tokens clockwise might all belong to the same host — which would give you RF=1, not RF=3. Skipping duplicate hosts guarantees three distinct physical replicas even when tokens cluster.

The quorum — N, W, R

With a preference list of N replicas, Dynamo picks up one more clever idea. Each write does not need to hit all N replicas immediately. Each read does not need to hit all N either. The knobs are:

The rule: W + R > N guarantees that at least one replica in every read set overlaps with the write set — so readers see the latest write. With N=3, W=2, R=2 you get strong consistency at the cost of not being able to write or read when 2 of 3 replicas are unreachable. Amazon typically picks N=3, W=2, R=2 for strong consistency or N=3, W=1, R=1 for maximum availability (accepting the risk of a temporarily stale read).

Failure handling — hinted handoff

What if one of the N preference-list nodes is down when a write arrives? Amazon does not want the write to fail (availability first). So Dynamo uses hinted handoff: send the write to the next healthy node in the ring, storing a "hint" that this write was meant for host X. When host X comes back, the temporary custodian ships the hint to X. The preference list is eventually restored.

Anti-entropy — Merkle trees

Over time, replicas drift — network glitches, missed writes, clock issues. Dynamo periodically syncs pairs of replicas to detect and repair divergence. But comparing two replicas key by key would be prohibitively expensive for millions of keys. So Dynamo builds a Merkle tree of each replica's key range and compares just the root hashes first. If roots match, the ranges are identical — no data exchanged. If roots differ, drill down into the subtree that differs. In practice, tiny amounts of data flow for anti-entropy; only the diffs travel.

Cluster membership — gossip

How do all the nodes know the ring topology? Every node knows every other node's tokens. This ring state is propagated via gossip: each node periodically picks a random peer, exchanges membership info, and merges. In O(log N) rounds, every node knows every other node — comparable to how a rumour spreads through a crowd. Cassandra copied this pattern directly from Dynamo.

DynamoDB in 2012 — what changed from Dynamo?

The end-to-end write path

What to remember

References

• DeCandia et al. (2007) — "Dynamo: Amazon's Highly Available Key-value Store." SOSP '07. The paper. 16 pages. Read it end to end.
• Vogels (2008) — "Eventually Consistent." ACM Queue. Werner Vogels' own explanation of why Amazon picked availability over consistency for user-facing services.
• Amazon DynamoDB Developer Guide — docs.aws.amazon.com/dynamodb. The current public documentation. See especially the "Partitions and Data Distribution" chapter.
• Sivasubramanian et al. (2013) — "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service." USENIX. The DynamoDB paper (as opposed to the Dynamo paper).
• Elhemali et al. (2022) — "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service" (updated). Discusses the changes made between 2012 and 2022, including adaptive capacity and global tables architecture.