Papers
Dynamo: Amazon's Highly Available Key-value Store
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, Werner Vogels · SOSP (21st ACM Symposium on Operating Systems Principles), 2007
The Always-On Problem
Amazon's platform is built from many independent services, and even a small increase in unavailability at any one of them — like the shopping cart — can cost real revenue and erode customer trust. By the mid-2000s, the engineering team observed that most of the services storing state only needed simple key-value access by primary key, not the full relational model or complex queries that traditional databases offered. Yet the databases they had been using still forced trade-offs that hurt availability: they were hard to scale horizontally, required careful manual partitioning, and would refuse or delay operations when some replicas were unreachable, treating consistency as more important than being able to respond at all. The paper's authors argued that for many of these stateful services, sacrificing strict consistency in exchange for the ability to always accept a write or return a read — even a possibly stale one — was the right trade-off, since customers were rarely harmed by minor staleness but were always harmed by an error page. This motivated a new design point: an incrementally scalable data store, where adding nodes for more capacity does not require large migrations, that treats write availability as its central design goal and only guarantees consistency will eventually be reached rather than immediately.
Partitioning and Replication: The Consistent Hashing Ring
To spread data and load across many machines without requiring a central coordinator, Dynamo arranges all nodes on a logical ring using consistent hashing: each node is assigned one or more positions (tokens) on the ring, and a key is stored starting at the first node whose position follows the key's hash value going clockwise. This scheme keeps redistribution costs low when the number of nodes changes — adding or removing a machine only shifts the keys owned by its immediate ring neighbors rather than reshuffling the whole dataset, which is what made scaling capacity up or down an operational rather than an architectural event. For durability and availability, each key is not stored on just one node: Dynamo walks clockwise from the key's position and replicates it onto the next N-1 distinct physical nodes it encounters, forming what the paper calls a preference list — the default configuration used N=3, so each piece of data normally lived on three different machines. Because the preference list is derived purely from the ring position, any node can compute, without contacting anyone else, exactly which nodes should hold a copy of a given key, which is essential for a system where no single node is a coordinator of record. Using virtual nodes (multiple tokens per physical machine) also let Dynamo balance load more evenly and let heterogeneous hardware take a proportionally larger or smaller share of the ring.
Trading Consistency for Availability: Sloppy Quorums, Hinted Handoff, and Vector Clocks
Dynamo lets operators tune two numbers per read or write: R, the number of replicas that must respond to a read, and W, the number that must acknowledge a write, out of the N replicas in a key's preference list. Setting R+W greater than N gives quorum-like overlap that reduces the chance of reading stale data, while setting R+W at or below N favors lower latency and higher availability at the cost of more possible staleness — the paper reports typical production settings of N=3, R=2, W=2. Critically, Dynamo does not require all N preferred nodes to be reachable to accept a write: if one of them is down, the write is sent instead to another node further down the ring, tagged with a "hint" recording which node it was really meant for — a technique called hinted handoff — and that node forwards the data once the original replica recovers. This "sloppy quorum" is what lets Dynamo call itself always writeable even during failures or network partitions. The side effect is that concurrent writes to the same key, made without knowledge of each other, can create divergent versions. Instead of picking one arbitrarily, Dynamo tags every version with a vector clock — a per-node counter set — so it can tell whether one version causally descends from another or whether they conflict. Versions it cannot causally order are all returned to the requesting application, which is expected to merge or choose between them (as, famously, merging two divergent shopping carts by unioning their items).
Staying in Sync Without a Master: Read Repair, Merkle Trees, and Gossip
Because sloppy quorums and hinted handoff let replicas fall temporarily out of sync, Dynamo needs background mechanisms to bring them back into agreement without any central coordinator ever being involved. The simplest mechanism is read repair: whenever a read touches multiple replicas and their versions disagree, the coordinating node pushes the most recent version back out to the stale replicas as part of handling that same read, so popular keys tend to self-heal quickly just from normal traffic. For keys that are not read often, Dynamo also runs an anti-entropy process between replica pairs using Merkle trees — hash trees where each leaf hashes a small range of keys and each parent hashes its children, so two replicas can compare just their root hashes first and only recurse into the branches that differ, instead of comparing every key individually. This keeps the bandwidth and computation needed to detect divergence proportional to the amount of actual difference between replicas, not to the size of the data set. Finally, Dynamo has no central registry of which nodes are alive or which nodes own which ring positions: instead, every node periodically gossips its own ring/membership view to a randomly chosen peer, and the two merge their views. Combined with a purely local failure detector (a node stops considering a peer alive after enough failed contact attempts, independently of any global vote), this lets the whole membership picture converge without any single point of coordination or failure.
Legacy: From Dynamo to the NoSQL Generation
Dynamo was never released as external software by Amazon — the 2007 paper described an internal system — but its ideas spread directly into the systems that followed it. One of Dynamo's own co-authors, Avinash Lakshman, went on to co-create Apache Cassandra, carrying over the ring-based consistent hashing partitioning and gossip-based membership almost directly, while combining them with a Bigtable-style column-family data model. Riak, built by Basho, and Voldemort, built at LinkedIn, are also widely described as direct implementations of the Dynamo design: both use consistent hashing rings, tunable N/R/W-style quorums, and vector clocks (or a similar causality mechanism) for conflict detection. Years later, Amazon itself shipped a managed service literally named DynamoDB, which kept the "always available, horizontally scalable" philosophy of the original paper while simplifying the operational model over time rather than exposing quorum tuning directly to every customer. More broadly, the Dynamo paper is usually cited alongside Google's Bigtable paper as one of the two founding influences on the wider NoSQL movement of the late 2000s and 2010s, because together they showed that giving up strict relational guarantees and even strict consistency could unlock horizontal scalability and availability that the previous generation of relational databases struggled to provide at internet scale.
See the ideas at work
Practice the designs that use this paper in the System Design school.