Amazon Dynamo Explained: The Database That Refused to Reject Writes
A deep dive into Amazon's Dynamo paper: consistent hashing, vector clocks, sloppy quorums, Merkle trees, and the design philosophy that inspired Cassandra, Riak, and DynamoDB.
Imagine a shopping cart that’s not allowed to reject a write. Not during a disk failure, not during a network partition, not even if an entire data center goes dark. A customer hits “Add to Cart” and that request has to succeed, every time, no matter what’s on fire behind the scenes.
That’s not a hypothetical for Amazon. It’s a requirement. And it’s the requirement that a traditional relational database, with its locks and its transactions and its insistence on being correct before being available, simply can’t meet.
The paper Dynamo: Amazon’s Highly Available Key-value Store (DeCandia, Hastorun, Jampani, Kakulapati, Lakshman, Pilchin, Sivasubramanian, Vosshall, Vogels - SOSP 2007) is the story of how Amazon built a data store around that requirement instead of around correctness. It’s one of the most influential systems papers of the last twenty years, the direct ancestor of Cassandra, Riak, and Amazon’s own DynamoDB, and its central move is almost contrarian: it makes the write path dumb and always-on, and pushes the hard part, figuring out what actually happened, onto reads.
What Problem Was Amazon Solving?
By the mid-2000s, Amazon’s e-commerce platform was built from hundreds of loosely coupled services, each with its own storage needs. A single page render could fan out to over 150 internal services. Many of these services needed nothing more than primary-key lookups: shopping carts, session state, product catalogs, best-seller lists. No joins, no complex queries, no relational schema.
Running all of that on relational databases had become the actual bottleneck. Most of what an RDBMS offers, complex querying, strong transactional guarantees, was overkill for these access patterns, and the replication technologies available for scaling those databases out consistently chose consistency over availability whenever a partition or failure occurred. That’s the opposite of what a shopping cart needs. A customer should be able to add an item to their cart even if a disk is failing, a network route is flapping, or, in the paper’s own memorable phrasing, a data center is being taken out by a tornado.
So the real question wasn’t “how do we make our database faster”. It was:
How do we build a data store that is always writeable, even in the face of network partitions and server failures, and that scales by adding commodity hardware one node at a time?
Why Brute Force Wasn’t an Option
The obvious approach is the one every relational database already takes: synchronous replication. A write isn’t acknowledged until enough replicas have confirmed it, which guarantees that once you read your data back, it’s correct and current.
That’s exactly the approach that breaks under Amazon’s operating conditions. At the scale of tens of thousands of servers across many data centers, components fail continuously. That’s not an edge case to be engineered around, it’s the steady-state condition the system has to run in. Decades of distributed systems research had already established the uncomfortable tradeoff at the heart of this: when network failures are possible, you cannot have both strong consistency and high availability at the same time. You have to pick one to sacrifice.
Amazon picked consistency. Specifically, they decided that rejecting a customer’s write was a worse outcome than occasionally serving them a slightly stale or divergent read. So instead of asking “how do we make writes stronger,” the team asked “how do we make writes trivially easy to accept, and push all the hard reconciliation work to whenever the data is actually read?”
The Core Insight
Dynamo’s design rests on a handful of decisions that reinforce each other, but the load-bearing one is this: conflict resolution happens on reads, not writes, and, wherever possible, the application resolves conflicts, not the database.
Most systems do it the other way around: reject or serialize writes so that reads stay simple. Dynamo inverts that on purpose. A write is accepted as long as any reachable node in the system can durably store it. If that means two different customers’ updates to the same shopping cart end up on different physical replicas, so be it, the system will present both versions the next time anyone reads that key, and let the application (or, failing that, a last-write-wins timestamp) decide how to merge them.
This single inversion is what makes the rest of Dynamo’s architecture make sense:
Consistent hashing partitions data across nodes so the system can add or remove a node without reshuffling the whole keyspace.
Vector clocks let the system distinguish “this update descended from that one” from “these two updates happened independently and conflict,” without needing a centralized clock or coordinator.
Sloppy quorums and hinted handoff let writes succeed even when the “correct” replica for a key is temporarily unreachable, by writing to a substitute node instead of blocking.
Merkle trees clean up the mess left behind by all of the above, quietly reconciling replicas that drifted apart during a failure.
Put together, the shape of the system is: accept the write almost anywhere, encode enough metadata to reconstruct what happened later, and spend your engineering effort on making reconciliation cheap and safe rather than on making writes strict.
The Tradeoff
The most consequential decision in the paper isn’t a specific algorithm, it’s the choice to expose inconsistency to the application instead of hiding it.
Most databases treat conflict resolution as their own problem to solve internally, typically with a blunt policy like “last write wins.” Dynamo does support that mode, and some services use it (session state, where losing a stale write to a fresher one is harmless). But for anything where losing an update actually matters, like a shopping cart, Dynamo hands both versions back to the client and says, effectively, you know your data model, you decide how to merge these.
The tradeoff:
More complexity pushed onto application developers, in exchange for a data store that never has to choose between rejecting a write and losing one.
This is a deliberate rejection of the industry-standard approach at the time. ACID guarantees are convenient for developers, but Amazon’s own operational experience had shown that data stores providing full ACID guarantees tend to have poor availability. Since Amazon’s applications were already built to expect failures and inconsistencies as a normal condition of operating at scale, porting them to a model that surfaces those inconsistencies explicitly turned out to be a relatively small lift; the harder problem was greenfield application design, which required real thought about which conflict-resolution mode fit the use case.
Architecture
Dynamo is what the paper calls a zero-hop DHT: every node maintains enough routing information locally to send a request directly to the nodes that should handle it, without bouncing through intermediate hops the way structured peer-to-peer systems like Chord or Pastry do. That choice is deliberate. Multi-hop routing adds variance to response times, and variance is exactly what you don’t want if your SLAs are measured at the 99.9th percentile, which is how Amazon measures essentially everything.
Partitioning. Keys are hashed with MD5 into a 128-bit space, treated as a ring. Each physical node owns multiple random positions (”virtual nodes”) on that ring, so that when a node joins or leaves, the resulting load shift is spread evenly across many other nodes instead of dumping it all on one neighbor.
Replication. Each key is replicated at N hosts (a per-service configurable, typically 3). The node that owns a key’s position on the ring is the coordinator, and it replicates the key to the N-1 nodes that follow it clockwise. The full list of nodes eligible to serve a key is its preference list, which is intentionally longer than N so there’s slack to absorb failures.
Quorum knobs. Each service tunes two more numbers: R, the minimum number of nodes that must respond to a read, and W, the minimum number that must acknowledge a write. Setting R + W > N gives you quorum-like overlap between reads and writes. Crucially, these are configurable per service, not fixed system-wide, because different services have wildly different tolerance for staleness versus latency. A common production configuration was (N, R, W) = (3, 2, 2): tolerate one node down on either path, without paying for full N-way confirmation.
Notice what’s absent from that write path: no cross-node locking, no blocking on a majority if you don’t want to, no rejection just because the “ideal” replica is briefly unreachable.
Vector Clocks: Encoding “We Don’t Know Which One Is Right”
This is the mechanism I found most interesting in the paper, because it solves a problem most systems just paper over: how do you tell the difference between “this write is newer” and “these two writes genuinely don’t know about each other”?
A plain timestamp can’t do this reliably across machines with unsynchronized clocks. Dynamo instead attaches a vector clock to every version of every object: a list of (node, counter) pairs recording which coordinators have handled writes to that object and how many times. Comparing two vector clocks tells you one of two things: one is a strict ancestor of the other (safe to discard the ancestor), or neither dominates the other, meaning they’re concurrent, conflicting edits that a human or application has to reconcile.
Walking through the paper’s own example makes the mechanic concrete:
D3 and D4 are siblings, not ancestor and descendant. A node that only ever saw D1 or D2 can tell, on receiving D4, that both are now obsolete and can be garbage collected. But a node holding D3 that receives D4 can’t resolve it automatically, the two branches reflect changes that aren’t reflected in each other, so both versions get returned to the next reader, who (or whose application logic) merges them into a new version, D5, which folds the counters from every branch into a single clock.
For a shopping cart, that merge is straightforward: union the item sets from both versions. Nothing gets silently dropped. The tradeoff, as the paper is upfront about, is that this can occasionally resurrect a deleted item, a customer removes something from their cart, a concurrent branch that predates the deletion gets merged back in, and the item reappears. Amazon judged that failure mode (an item you have to remove twice) as dramatically preferable to the alternative (an “add to cart” that silently vanishes).
One practical wrinkle: vector clocks can grow unbounded if many different nodes end up coordinating writes to the same key, which mostly happens during network partitions or failures rather than in normal operation. Dynamo caps this by storing a timestamp alongside each (node, counter) pair and truncating the oldest entry once the clock exceeds a threshold (the paper uses 10). The authors admit this is a blunt instrument that can theoretically corrupt the ancestry chain, but note, with a bit of dry honesty, that it hasn’t actually caused problems in production and so hasn’t been investigated further.
Handling Failures Without Ever Blocking
Sloppy quorums and hinted handoff. A strict quorum system would still make Dynamo unavailable during a partition, if the “correct” N nodes aren’t all reachable, a strict scheme refuses the operation. Dynamo instead relaxes membership: reads and writes go to the first N healthy nodes on the preference list, wherever they happen to sit on the ring. If node A is briefly down, the replica that should have landed on A gets written to the next healthy node instead (say, node D), tagged with a hint saying “this really belongs to A.” Once A recovers, D forwards the hinted replica back and drops its own copy. The write never had to wait for A to come back.
This is also how Dynamo survives losing an entire data center: preference lists are constructed to span multiple data centers, so a full regional outage still leaves enough of a key’s preference list reachable elsewhere to keep serving traffic.
Merkle trees for anti-entropy. Hinted handoff only helps if the outage is short enough that the hint eventually finds its way home. For longer-lived divergence, each node maintains a Merkle tree per key range it hosts, a hash tree where every leaf hashes a key’s data and every parent hashes its children. Two nodes syncing a shared key range just compare root hashes first: if they match, everything underneath is identical and no data has to move. If they don’t, the nodes walk down the tree comparing child hashes until they isolate the specific keys that drifted, transferring only those. It turns “are these two multi-gigabyte replicas identical” from an expensive full comparison into a handful of hash exchanges.
What Breaks First? Load Balance, Not Bandwidth
Once the system is spread across a ring, the next question is whether that spread is actually even. Dynamo went through three different partitioning strategies in production before landing on one that worked well, and the failure modes of the earlier two are instructive.
Strategy 1, random tokens per node with partitioning tied directly to token position, was the original design. It had three separate problems in practice: bootstrapping a new node meant scanning other node’s local stores for the right key ranges, which was resource-intensive and, under heavy holiday load, sometimes took almost a full day to complete; every membership change forced expensive Merkle tree recalculation across many nodes; and there was no clean way to snapshot the whole keyspace for archival, since key ranges had no fixed boundaries.
The fix was to decouple partitioning (how the hash space is divided) from placement (which physical nodes own which partitions). Strategy 3, which Dynamo settled on, divides the space into a fixed number of equal-sized partitions up front and assigns each node a fixed count of them, independent of token randomness. Measured against strategy 1 at equivalent metadata overhead, this reduced the memory needed for membership information by three orders of magnitude while achieving better load-balancing efficiency, and it made both bootstrapping and archival dramatically simpler, because a partition maps to a single file that can be moved or archived as a unit instead of requiring a scan.
The broader lesson buried in that migration: the scheme you ship first because it’s the natural extension of a well-known algorithm (plain consistent hashing) is not necessarily the scheme that survives contact with your actual operational workflows (bootstrapping, archival, background maintenance). Those operational costs didn’t show up in the original design’s complexity analysis at all.
The Numbers That Made It Real
A few figures from the paper are worth sitting with:
Applications built on Dynamo received successful, non-timed-out responses for 99.9995% of requests, with no data loss event recorded up to the time of publication.
Across a 24-hour profiling window of the shopping cart service, 99.94% of reads returned exactly one version of the object. Only 0.00057% saw 2 versions, 0.00047% saw 3, and 0.00009% saw 4. Divergent versions are the exception, not the norm, even in a system explicitly designed to tolerate them.
Interestingly, the paper notes that the growth in divergent versions correlated with concurrent writers, not failures, and was mostly driven by automated client programs rather than human shopping behavior.
Moving request coordination logic into the client library instead of routing through a load balancer cut 99.9th-percentile read and write latency from roughly 69ms down to about 30ms, by eliminating an extra network hop and letting clients route directly to the correct preference-list nodes.
A small in-memory write buffer (as few as a thousand objects) cut 99.9th-percentile write latency during peak traffic by a factor of 5, at the cost of durability if a node crashed before flushing, a tradeoff explicitly offered as an option rather than forced on every service.
The 99.9th-percentile latencies were consistently an order of magnitude higher than the average latencies, a gap the authors attribute to request-load variability, object size variance, and locality effects, and a big part of why Amazon insists on measuring SLAs at the tail rather than the mean.
Why This Paper Matters Beyond Dynamo
Dynamo’s direct descendants (Cassandra, Riak, Voldemort, and eventually Amazon’s own hosted DynamoDB) borrowed its techniques so thoroughly that it’s easy to forget how counterintuitive the core bet was at the time. A few ideas are worth carrying into systems that have nothing to do with key-value stores:
Availability and consistency are a dial, not a binary, and the right setting is a business decision, not a technical one. Dynamo doesn’t pick a single tradeoff for every use case; it exposes N, R, and W as knobs so a shopping cart and a session store can land in completely different places on the same infrastructure.
Pushing complexity to the read path, rather than the write path, is a legitimate design choice when writes are the operation you can least afford to reject. It’s uncomfortable because it means the “happy path” read now has to handle multiple versions, but that discomfort is far more contained than the discomfort of a rejected write.
The scheme that looks simplest on a whiteboard is not the scheme that survives your actual operational workflows. Strategy 1’s failure wasn’t algorithmic, it was operational: slow bootstrapping, expensive re-hashing, hard-to-archive data. Those costs only show up once you run something in production for a while.
Tail latency, not average latency, is usually what your customers experience, especially once a request has to satisfy more than one dependency (R or W replicas, in Dynamo’s case). Optimizing for percentiles instead of means shows up repeatedly, from the choice to measure SLAs at p99.9 to the decision to let clients route directly instead of trusting a load balancer.
My Takeaways
What stands out almost twenty years later is how honest the paper is about what it doesn’t solve. Vector clock truncation can theoretically corrupt ancestry and the authors say so plainly. Deleted shopping cart items can resurface and they say that too. Full membership gossip doesn’t scale past a few hundred nodes and they flag it as a known limitation rather than hiding it. That kind of candor about the sharp edges of a production system is rarer in systems papers than it should be, and it’s part of why this one held up.
The other thing that stuck with me: Dynamo isn’t really a paper about a clever algorithm. Consistent hashing, vector clocks, quorum systems, Merkle trees, gossip protocols, none of these were new in 2007. The contribution was combining them around a single, unusually clear design principle, never reject a write, and then following that principle all the way down through partitioning, versioning, and failure handling until the whole system was internally consistent with it. That’s a useful model for any system design problem: pick the one property you genuinely cannot compromise on, and let it discipline every other decision, rather than trying to optimize for everything at once and ending up with a system that’s mediocre on all axes.
Eighteen years later, “eventually consistent, application-resolved, quorum-tunable” is a phrase that describes half the databases powering the modern internet. Dynamo is the paper that made that phrase sound like engineering instead of a compromise.