Amazon Dynamo: What the Paper Means in Production

The paper in brief

"Dynamo: Amazon's Highly Available Key-value Store" by Giuseppe DeCandia and colleagues appeared at SOSP in 2007. It describes a storage system built for Amazon's e-commerce platform, with the shopping cart as the motivating example. The central stance is that for such services, always accepting writes matters more than always having a single agreed view of the data, so Dynamo is an eventually consistent system.

Key ideas

Consistent hashing. Keys and nodes are placed on a ring, so adding or removing a node moves only a portion of the data. Virtual nodes let a physical machine own several positions on the ring, which smooths load and lets stronger machines take more.

Replication and tunable quorums. Each key is stored on N nodes. A read waits for R replies and a write waits for W acknowledgments. Choosing R plus W greater than N gives overlapping quorums, while smaller values favor speed and availability. The paper reports common configurations such as three replicas, with two for reads and two for writes.

Sloppy quorums and hinted handoff. When a node is down, another node temporarily accepts its writes and hands them back when it recovers, so writes keep succeeding during failures.

Versioning with vector clocks. Concurrent updates produce multiple versions of an object. Vector clocks detect that the versions are concurrent, and the system returns all of them to the client to reconcile. For the shopping cart, reconciliation merges items.

Anti-entropy and membership. Replicas compare Merkle trees to find and repair differences, and a gossip protocol spreads membership information without a central coordinator.

What breaks in practice

Pushing reconciliation to the application is the hardest part. Merging two shopping carts is easy, and merging arbitrary business data is not. The paper itself notes that a deleted item can reappear in a cart, which is an honest example of the cost of conflicts being resolved by a merge rule. Teams adopting this style must design data types that merge safely, and many do not.

Quorum arithmetic does not equal strong consistency. With sloppy quorums, even overlapping settings do not guarantee a read sees the latest write, because the nodes that took the write may not be the ones in the read set. Treating tunable consistency as a dial that reaches linearizability is a frequent misunderstanding.

Operations are real work. Rings need rebalancing, anti-entropy needs bandwidth, and the paper reports tuning partitioning strategy over time to improve load distribution and the speed of bootstrapping nodes.

Vector clocks can grow, and the paper describes truncating them when they exceed a size threshold, which trades away some precision. Many descendants chose simpler last-write-wins by timestamp, which silently drops concurrent updates and depends on clocks that disagree.

The paper also describes a design for a trusted internal environment, with no emphasis on authentication between nodes, and a flat peer-to-peer structure that suits a single organization.

Modern descendants

Apache Cassandra combines Dynamo's distribution ideas with a Bigtable-style data model. Riak and Project Voldemort followed the paper more closely. Amazon DynamoDB, launched as a managed service in 2012, is a different system from the one in the paper and shares its name and some lineage rather than its architecture, so the paper should not be read as DynamoDB's design document. Conflict-free replicated data types are the research line that formalizes merges that always converge, and they answer the reconciliation problem the paper left to developers.

Key takeaways

• Dynamo accepted eventual consistency to keep writes available during failures.
• Consistent hashing with virtual nodes makes scaling out and failure handling incremental.
• Quorum settings and sloppy quorums do not give strong consistency, however they are tuned.
• Conflict resolution moves to the application, so data models must be designed to merge.
• DynamoDB the service is not the system in the paper, despite the shared name.