Case Study — Dynamo & DynamoDB

One business requirement, and everything follows

Dynamo (SOSP 2007) is the rare architecture you can derive from a single sentence about money. The paper states that the shopping cart requires that an "Add to Cart" operation can never be forgotten or rejected. A refused write is a customer who does not buy the thing. Beside it sat a target measured at the tail rather than the mean: a representative internal SLA in the paper is a response within 300 ms for 99.9% of requests at a peak load of 500 requests per second.

The rest is forced:

Availability beats consistency, permanently — the AP corner of CAP, with no runtime flag to flip.
A single leader per key blocks writes when that leader is unreachable, so there is no leader. Any replica in the preference list accepts writes.
A strict quorum blocks writes when the key's home nodes are partitioned away, so the quorum gets to be sloppy.
Concurrent writes to different replicas therefore become normal traffic, not an anomaly.
Something must detect them without trusting wall clocks: vector clocks.
Nothing in a key-value store knows how to merge two carts, so the client resolves.

Each step is compelled by the one above it. That chain is the transferable part.

The technique catalogue

Technique	Problem it solves	What it costs
Consistent hashing on a ring, with virtual nodes	Partitioning and incremental scalability: adding a node moves ~K/N keys; vnodes fix clumping and let bigger machines take more positions	Ring state on every node; nothing for a single hot key
Sloppy quorum plus hinted handoff	Write availability during partitions: accept on the first N reachable healthy nodes, store a hint for the rightful home	Voids R + W > N — a read of the home replicas can miss the write
Vector clocks	Detecting genuinely concurrent versions instead of silently discarding one	Size grows with coordinating nodes; Dynamo truncates at a threshold (the paper says 10 pairs), after which descendant relationships can be inexact
Merkle tree per key range	Anti-entropy: find the few differing keys without shipping the dataset	Trees must be rebuilt when ranges move on membership change
Gossip membership with seed nodes	Decentralised membership and failure detection, no coordinator to lose	Eventually consistent view of the ring; seeds exist to prevent logical partitions

Three of these have their own lessons worth re-reading together: the ring and virtual nodes in partitioning, sloppy quorums and Merkle trees in quorums, and why vector clocks rather than timestamps in clocks. The paper reports (N, R, W) = (3, 2, 2) as the common configuration — the same balanced default the quorum lesson lands on.

The famous consequence

When two writes are concurrent, Dynamo cannot order them, so it keeps both. A later read returns siblings: multiple versions, handed to the caller. The store refuses to guess.

For the cart, the application's merge is a union of item sets. That makes add to cart unloseable, which was the whole requirement. It also means a removal recorded on one branch loses to the item's presence on the other. The paper is direct: an add-to-cart operation is never lost, however deleted items can resurface.

Read that as an engineering decision, not a defect. Amazon weighed a resurrected item (customer removes it again, mildly annoyed) against a refused write (abandoned purchase) and chose. The paper also quantifies the rarity: profiling the cart service for 24 hours, 99.94% of requests saw exactly one version, and the remainder saw two, three or four.

What DynamoDB the product actually is

DynamoDB launched in 2012 and has its own paper (USENIX ATC 2022). It is not the 2007 design with a control plane bolted on. It is a different system:

Single-leader replication per partition. A partition's replication group elects a leader using Multi-Paxos; only the leader serves writes and strongly consistent reads. Any replica can serve an eventually consistent read. This is the leader-based model the original paper deliberately rejected — see consensus and Raft.
Mixed replica types. Storage replicas hold a write-ahead log plus a B-tree; log replicas hold only recent log entries, making them cheap quorum members that restore durability fast without copying a whole B-tree.
Strong consistency per request. The client asks for a consistent read and pays in cost and availability; otherwise it takes the cheaper eventually consistent path.
No siblings, no vector clocks in the API. Conflicts are prevented by the leader, not surfaced to the caller. Applications needing atomicity use conditional writes or transactions.
Scale the paper never faced. During the 66-hour Prime Day event in 2021, DynamoDB peaked at 89.2 million requests per second.

Why the change? Client-side resolution exported a distributed-systems problem to every application team that touched the store. A correct merge must be idempotent, commutative and associative, and when it is wrong it is wrong silently. Very few product teams should be writing one.

The partition key decides your throughput

Capacity in DynamoDB is allocated per partition, not per table. A single partition tops out around 3,000 read capacity units, 1,000 write capacity units, and 10 GB. Provision 100,000 WCU on the table and one partition key still cannot absorb more than its partition's share.

So a low-cardinality or skewed partition key — status = ACTIVE, today's date, a celebrity account — concentrates load on one partition. You get throttling while table utilisation sits in single digits, which reads as a bizarre bug until you know the model. Adaptive capacity shifts spare capacity toward hot partitions and can isolate a frequently accessed item, but it cannot lift the per-partition ceiling.

What generalised, and what did not

The catalogue generalised completely. Cassandra took the ring, virtual nodes, tunable quorums, Merkle-tree repair and gossip more or less wholesale; ScyllaDB reimplemented that model in C++; Riak was close to a literal implementation, siblings included; and pieces recur wherever multi-region systems need membership without a coordinator.

The conflict model did not. Cassandra chose last-write-wins on timestamps rather than expose siblings — cheaper for developers, and lossy exactly as the clocks lesson warns. Riak kept siblings but added CRDT data types in 2.0 so the database could merge counters, sets and maps without an application-supplied function. DynamoDB removed the problem with a leader. Three escapes from one conclusion: pushing conflict resolution onto application developers did not survive contact with application developers.

In interviews

"Design a highly available key-value store." — Derive it, do not list it. Availability requirement, therefore leaderless, therefore sloppy quorums, therefore conflict detection. The derivation is the signal.
"How does Dynamo handle conflicting writes?" — Vector clocks detect concurrency, siblings go back to the client, the client merges. Then volunteer the consequence: deleted items can resurface, and that was accepted.
"Is DynamoDB eventually consistent?" — By default yes, but strongly consistent reads are available per request from the leader replica. Use it to show you know the product is not the paper.
"Your table throttles at 5% of provisioned capacity." — Hot partition. Capacity is per partition; ask what the partition key is, then propose write-sharding or a cache.
"When would you accept eventual consistency?" — When a refused write costs more than a temporarily wrong read and a sane merge exists. Carts, view counts, sessions yes; balances and inventory no.

What to take away

Dynamo's whole architecture follows from one requirement: add-to-cart must never be rejected.
The catalogue — consistent hashing with vnodes, sloppy quorums and hinted handoff, vector clocks, Merkle trees, gossip — is foundational and reused everywhere.
Siblings mean the client merges; a union merge is why deleted cart items reappear, by design.
DynamoDB is a different system: leader per partition via Multi-Paxos, optional strongly consistent reads, no client-side conflict resolution.
Throughput and storage are per partition, so the partition key sets your real ceiling.
The techniques survived; making application developers resolve conflicts did not.

Check yourself

In the 2007 Dynamo paper, why could an item a customer deleted reappear in their shopping cart?
Dynamo returns all concurrent versions to the client rather than picking one. The cart reconciles by unioning items, which guarantees an add is never lost but means a removal on one branch loses to the item's presence on the other. The paper states this outcome explicitly as an accepted consequence.
Which statement describes DynamoDB the product rather than the Dynamo paper?
DynamoDB is not the paper's design. It uses single-leader replication per partition with Multi-Paxos leader election, offers strongly consistent reads on request from the leader, and removes client-side conflict resolution. The other three options describe the 2007 leaderless system.
A DynamoDB table provisioned at 40,000 WCU is throttling writes while overall utilisation stays near 5%. Most likely cause?
Throughput and storage are allocated per partition, with a single partition capped near 1,000 WCU. A low-cardinality or skewed partition key concentrates load on one partition, which throttles long before the table-level number is reached. Adaptive capacity helps but cannot exceed the per-partition ceiling.
What does a sloppy quorum with hinted handoff buy, and what does it give up?
A sloppy quorum accepts the write on whatever healthy nodes are reachable and stores a hint naming the intended home node. Availability and durability improve, but because the write may sit outside the key's home replicas, a later read of those replicas can miss it, so the overlap argument no longer holds.