Dynamo: Amazon's Highly Available Key-value Store

SOSP 2007. The shopping cart had to accept writes even during failures, so Dynamo picks availability and resolves conflicts later.

How it works

• Partitioning: consistent hashing, with virtual nodes to spread load evenly.
• Replication: each key lives on N nodes. Reads need R replies and writes need W, and R + W > N behaves like a quorum.
• Sloppy quorum and hinted handoff: if a replica is down, another node takes the write and hands it back later.
• Versioning: vector clocks keep conflicting versions apart. The client merges them on read.
• Anti-entropy: Merkle trees find out-of-sync key ranges cheaply.
• Membership: gossip, with no central coordinator.

The trade-off

Merging carts on read means a deleted item can come back. Amazon accepted that: a cart that sometimes shows a removed item beats a cart that refuses to save.