Dynamo: Amazon's Highly Available Key-value Store
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, et al.2007SOSP 2007
Read it on doi.org(opens in a new tab)Why this one
Dynamo is where a lot of engineers first see a system that chooses availability over consistency on purpose and then has to live with the consequences in the open. The techniques are the syllabus for half a module - consistent hashing for placement, virtual nodes so that adding a machine does not move most of the data, sloppy quorums and hinted handoff so writes survive a partition, vector clocks and application-level reconciliation so the divergence that follows can be repaired. What makes it worth reading rather than summarising is the honesty: the shopping-cart example spells out that the database is handing the conflict back to you, and that this is a product decision, not a database feature.
What to take away
- N, R and W are dials you set per workload. R + W > N is a choice, not a law.
- Consistent hashing plus virtual nodes is the reason rebalancing is cheap - the /labs ring visualiser makes this concrete.
- If you allow concurrent writes you have signed up to resolve conflicts. Decide where that code lives before you ship.
Reads with
- Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
dynamo's partitioning and virtual nodes are built on this placement idea
- Time, Clocks, and the Ordering of Events in a Distributed System
dynamo's vector clocks extend its happens before model to track divergent writes
- Cassandra: A Decentralized Structured Storage System
cassandra turns dynamo's availability first replication into a wide column database