Classic of the Week — Dynamo: Amazon's Highly Available Key-Value Store

Almost every distributed database you touch today inherited something from a single 2007 SOSP paper. Cassandra is essentially its open-source descendant; Riak, Voldemort, and a decade of “eventually consistent” architecture trace back to the same document. This Papers We Love Tokyo session — the chapter’s inaugural talk, presented by Corrina Sivak — is a rare thing: a walkthrough by someone reading it as a working engineer rather than as an authority, complete with audience interruptions, honest “this might be a gap in my understanding,” and a genuinely useful comparison of what the paper described versus what AWS actually ships today.

The shopping cart problem

The paper’s motivating workload is the Amazon shopping cart, and the constraints are unusually clean:

• Tens of millions of requests per day (in 2007).
• A write to your cart must never be rejected — a rejected add-to-cart is a lost sale.
• Latency budget around 100ms.
• Only key-value access is needed — the cart is “what’s your account, what’s in your cart.”
• Merge logic is simple: track additions and deletions, and merging is list concatenation.

That last property is what makes the whole design viable. Dynamo pushes conflict resolution up to the application, and the shopping cart is an application that can absorb it.

Choosing AP over C

The talk spends useful time on CAP before making the punchline explicit: Dynamo gives up consistency in exchange for availability and partition tolerance. That choice cascades into eventual consistency — if you stop writing to an item, it will eventually converge on the last written value, but you get no promise about when.

The API is two calls. get(key) returns one or many versions of the item plus an opaque context carrying version metadata. put(key, context, object) writes back — often a version you merged yourself. Sivak flags early what she returns to at the end: modern DynamoDB does not expose this context at all.

The paper’s technique table doubles as the talk’s outline: partitioning, high availability for writes, handling temporary failures, recovering from permanent failures, and membership/failure detection.

Partitioning: from modulo to a ring

Traditional hashing — hash the key, mod by node count — has a fatal operational property: add one node and nearly every key moves. At Amazon’s scale you cannot afford to recopy your entire cluster to add capacity.

Consistent hashing fixes this by mapping keys onto a ring whose number of positions never changes. Adding a node takes over a contiguous arc rather than reshuffling everything, so you remap roughly K/N keys. As Sivak puts it, this is now simply how multi-node database clusters do placement.

Then she poses the follow-up problem to the room, which is the right pedagogical move: on a small ring, one node can own more than half the arc. That’s hot spotting — one node absorbing most of the traffic, with visibly higher CPU and memory than its peers.

The fix is virtual nodes: slice the ring into many small arcs and assign them across physical nodes, so load distributes evenly regardless of where keys land.

Replication and preference lists

Replication falls out naturally from the ring. With replication factor N, the node that owns the key is the coordinator, and you simply walk the ring to the next N−1 nodes. The resulting list of nodes holding a key is the preference list — a term that recurs throughout the paper.

An audience question surfaces the real cost here: adding a node now means moving not just the data it becomes responsible for, but replicated data that must shift too. Sivak’s answer is the honest one — yes, it’s complicated, and that complexity is the price of the efficiency.

Sloppy quorums and hinted handoff

Two tunables dominate Dynamo deployments: R (nodes required for a successful read) and W (nodes required for a successful write). In theory, if R + W > N you always read the latest value.

“In theory” is doing real work in that sentence, because Dynamo uses a sloppy quorum: if a node in the preference list is dead, you don’t fail the write — you skip it. The companion mechanism is hinted handoff: the write goes to the next available node, which stores it in a separate local database with a hint about where it belongs, and a background job delivers it home once the target recovers.

This is precisely where “eventually consistent” earns its name — and where an audience member’s story about adding an item to an Amazon cart, seeing an empty cart, and finding the item minutes later becomes a live demonstration of the paper. Sivak’s editorial note is the practical lesson:

“I see people write very robust systems on DynamoDB and I don’t think they necessarily understand the consistency guarantees they’re getting back… it’s fine for 95% of cases, but it’s the 5% where you should at least understand what it’s doing.”

Vector clocks

That opaque context is a vector clock — which Sivak deflates nicely as “really just the version.” It’s a list of (node, write count) tuples. Walk the worked example:

1. Write to node 3 → [(S3, 1)]. Write again → [(S3, 2)].
2. Node 3 goes down. Client 1 writes foo to node 2, client 2 writes bar to node 1. Now you have two divergent descendants: [(S3,2),(S2,1)] and [(S3,2),(S1,1)].
3. With R = 2 you read both and get both values back — this is the get returning multiple versions.
4. The application reconciles (for the cart: concatenate) and writes back a merged clock that is a superset of both, so future reads can identify the older versions and discard them.

Modern DynamoDB dropped this — deemed too complicated for customers, which Sivak concedes “totally makes sense,” while noting it’s also clear why you’d want it. She points to CRDTs as the modern alternative, which hadn’t been invented when the paper was written.

Anti-entropy: Merkle trees and gossip

When a node returns from an outage it holds stale data, and you cannot reconcile by comparing every value — that’s O(N), and N is enormous. Merkle trees solve it: hash each data block, and each parent is the hash of its children’s hashes. Comparing root hashes tells you instantly whether two replicas diverge, and you descend only into subtrees that disagree.

Membership and failure detection ride on a gossip protocol — every few seconds nodes exchange Merkle tree data and cluster membership with peers. An audience member asks whether gossip is expensive; the answer is that it’s bounded by the preference list, so with 10 nodes and replication factor 3, each node is talking to three peers, not nine.

What modern DynamoDB actually does

This is the section that justifies revisiting the paper in 2026. The differences are substantial:

Timestamp versioning is simpler and works most of the time, but it inherits clock drift, which gets worse the more data centres you span — a real problem at DynamoDB’s scale. And losing R/W tuning removes real capability: the paper describes configurations like N=3, W=3, R=1 to use Dynamo as a cache. The pragmatic reading, in Sivak’s words, is that when AWS built the consumer version “they didn’t expect people to know what they’re doing. Which is valid.”

Cassandra, notably, remains the closest living implementation of the paper as written.

Key takeaways

1. Dynamo’s design is downstream of one product decision — never reject a cart write — and the paper is a case study in letting a business constraint pick your CAP corner.
2. Consistent hashing is the durable contribution: a fixed-size ring means adding capacity moves ~K/N keys instead of everything.
3. Virtual nodes exist to kill hot spotting, a failure mode that still bites production systems today (Sivak has seen it in Elasticsearch).
4. Sloppy quorum + hinted handoff is what “highly available” actually means — skip the dead replica, stash the write elsewhere, deliver it later.
5. R + W > N guarantees freshness only without sloppy quorum. The tunables are advertised more strongly than they hold.
6. Vector clocks push conflict resolution to the application, which is powerful and is exactly why AWS removed it from the managed product.
7. Merkle trees turn replica reconciliation from O(N) into a tree descent — the same trick that later underpinned blockchains and Git.
8. Modern DynamoDB is not the paper. Timestamp last-write-wins (with clock drift), no R/W tuning, multi-tenant. Read the 2022 follow-up paper for the current design; read Cassandra for the original.

Source

• Talk: Corrina Sivak on Dynamo: Amazon’s Highly Available Key-Value Store
• Speaker: Corrina Sivak (software engineer, Henge; previously infrastructure observability at Datadog)
• Origin: Papers We Love Tokyo — inaugural chapter session
• Paper: DeCandia et al., Dynamo: Amazon’s Highly Available Key-Value Store, SOSP 2007
• Duration: 42m 59s
• URL: https://www.youtube.com/watch?v=RnHS0Yn8jH4