On this page

Amazon Dynamo: The Paper Behind Leaderless Stores

In October 2007, at SOSP, a group of Amazon engineers led by Giuseppe DeCandia published "Dynamo: Amazon's Highly Available Key-value Store." It was not the first paper to describe consistent hashing, quorums, vector clocks, or gossip. Every one of those ideas was older. What the paper did was show that you could combine them into one production system, run it at the core of the world's largest online store, and trade consistency for availability on purpose, as a business decision, without apologising for it.

That combination — later called leaderless or Dynamo-style replication — shaped a generation of databases: Cassandra, Riak, Project Voldemort, and in spirit many more. It also gave interviewers a whole vocabulary: sloppy quorum, hinted handoff, read repair, N/R/W, siblings. This page goes through the paper in the order its authors reasoned about it: the requirement, the architecture, each mechanism with a worked example, what is and is not guaranteed, the numbers they reported, and what later systems kept or threw away.

How this page relates to the rest of Archon

The building blocks have their own deep pages: Consistent Hashing, Vector Clocks & Lamport Timestamps, Gossip Protocols and Failure Detectors. Here we focus on how Dynamo composes them and why. For the AWS service with a similar name, see DynamoDB Internals. For the most widely deployed descendant, see Cassandra Internals.


1. The Problem: A Shopping Cart That Must Never Refuse a Write

1.1 The business requirement

The paper opens with a statement about money rather than algorithms: even the slightest outage has significant financial consequences and hurts customer trust. Amazon's platform in 2007 served tens of millions of customers at peak, on tens of thousands of servers spread across many data centres. At that scale something is always broken — disks fail, switches flap, a rack loses power, a data centre is cut off by a storm. The authors treat failure as the normal state, not an exception.

The canonical customer is the shopping cart service. Their requirement: a customer must always be able to add an item to the cart, even if disks are failing, network routes are flapping, or whole data centres are being destroyed by tornadoes (the paper's own example). A cart that occasionally shows an item that was deleted is a small annoyance. A cart that rejects "Add to Cart" during the holiday rush loses sales directly.

So the central design choice comes from the business:

When the system must choose between rejecting a write and accepting a write that might later conflict with another one, accept the write and resolve the conflict later.

In CAP terms Dynamo picks availability under partition. More precisely, it picks availability for writes. Most databases of the time resolved conflicts at write time: a write that cannot reach a majority, or cannot get a lock, is rejected. That keeps reads simple. Dynamo reverses this. Writes always succeed, and conflict resolution moves to read time, where the application can see every conflicting version.

1.2 The constraints the authors stated

The paper is explicit about its assumptions, and they matter, because the design only makes sense inside them:

ConstraintWhat the paper saysDesign consequence
Query modelSimple reads and writes of a single item, identified by a key, values are binary blobs, usually under 1 MB. No operation spans multiple items.No multi-key transactions, no secondary indexes, no relational schema.
ACIDStrong ACID guarantees tend to hurt availability. Dynamo targets applications that can live with weaker consistency; it provides no isolation and allows only single-key updates.Each key is an independent replicated register (or a set of versions).
EfficiencyServices have strict latency requirements, measured at the 99.9th percentile.Every mechanism is judged by its effect on tail latency, not the mean.
EnvironmentInternal use only. The operating environment is assumed non-hostile; no authentication or authorization inside Dynamo.No Byzantine fault tolerance — compare Byzantine Fault Tolerance.
Scale per instanceEach service runs its own Dynamo instance; the initial design targeted up to hundreds of storage hosts per instance.Full membership on every node is acceptable (see §8).

Four design principles follow:

  1. Incremental scalability — add one node at a time with minimal disruption.
  2. Symmetry — every node has the same responsibilities; no special leader or master.
  3. Decentralisation — favour peer-to-peer techniques over central control.
  4. Heterogeneity — use more capable hardware in proportion to its capacity.

1.3 Why the 99.9th percentile

Amazon's page rendering engine may call 150 or more services to build one page, and many of those calls fan out further. If one dependency is slow for one in a hundred requests, nearly every page sees some slow call. So Amazon wrote SLAs as "respond within 300 ms for 99.9% of requests at a peak client load of 500 requests per second" — the paper's example SLA. The authors explain why they chose 99.9 rather than the mean or median: a mean-based SLA hides exactly the customers who hurt you most. Those are often the heaviest users with the longest histories, whose requests do the most work.

This is why Dynamo cares about things like which replica coordinates a write and whether to buffer writes in memory. A design that is fine on average but has a long tail fails the requirement.


2. Architecture

The paper's Table 1 is the best summary of Dynamo: five problems, five techniques. Here it is in our own words:

ProblemTechniqueAdvantage
PartitioningConsistent hashing with virtual nodesIncremental scalability; adding a node moves only its share of keys
High availability for writesVector clocks, reconciled at read timeVersion size does not depend on how often a key is updated
Temporary failuresSloppy quorum + hinted handoffStays available and durable while some replicas are down
Permanent failuresAnti-entropy with Merkle treesSynchronises divergent replicas in the background while sending little data
Membership & failure detectionGossip-based membership and local failure detectionKeeps the system symmetric; no central registry
flowchart TB
    subgraph Clients["Clients"]
        LB["Generic load balancer"]
        PA["Partition-aware client library"]
    end

    subgraph Ring["Dynamo ring — every node is identical"]
        direction LR
        A["Node A"]
        B["Node B"]
        C["Node C"]
        D["Node D"]
        E["Node E"]
    end

    subgraph Node["Inside one node"]
        RQ["Request coordination\n(state machine per request)"]
        MEM["Membership & failure detection\n(gossip)"]
        HH["Hinted-handoff store"]
        MT["Merkle trees per key range"]
        SE["Pluggable storage engine\n(BDB, MySQL, in-memory + persistent)"]
    end

    LB -->|"any node, then forward"| A
    PA -->|"directly to a coordinator"| B
    A <-->|"gossip"| B
    B <-->|"gossip"| C
    C <-->|"gossip"| D
    D <-->|"gossip"| E
    E <-->|"gossip"| A
    RQ --> SE
    RQ --> HH
    MT --> SE
    MEM --> RQ

Some points worth noting:

  • No master. Any node can receive any request. Nodes differ only in the key ranges they own and in being seeds (well-known nodes used to bootstrap gossip, §7).
  • The coordinator is chosen per request. For a key, the node that handles the request is the coordinator. It is normally the first healthy node in the key's preference list.
  • Storage is pluggable. The paper lists Berkeley DB Transactional Data Store, BDB Java Edition, MySQL, and an in-memory buffer with a persistent backing store. Applications chose based on object size; BDB handled objects of tens of kilobytes, MySQL larger ones.
  • Each node is written in Java and built on a common event-driven messaging layer (Java NIO). Each client request runs as a state machine inside the coordinator: identify replicas, send requests, wait for the minimum number of responses, handle timeouts, collect versions, run reconciliation if needed, and do read repair.

2.1 Interface and data model

The whole API is two calls:

get(key)                    -> (list of objects, context)
put(key, context, object)   -> ok
  • The key is hashed with MD5 into a 128-bit identifier. That identifier decides placement.
  • The object is an opaque byte array. Dynamo does not interpret it.
  • The context is opaque to the caller. It carries system metadata — chiefly the vector clock of the versions the caller read. The client must send the context back on the next put. That is how Dynamo learns which version this write replaces.
  • get may return more than one object. If replicas hold concurrent versions that Dynamo cannot order, it returns all of them (siblings) and leaves the merge to the application.

This last point is the most important difference between Dynamo and a "normal" key-value store. The client is part of the consistency protocol. A client that writes without sending back the context it read is telling Dynamo "this write does not descend from anything". That creates a new sibling every time.


3. Partitioning: Consistent Hashing, Virtual Nodes, Preference Lists

3.1 The ring

Dynamo maps the 128-bit hash space onto a circle. Each node picks positions on the circle (tokens). A key belongs to the first node clockwise from the key's hash. When a node joins or leaves, only the keys between it and its neighbour move. Consistent Hashing covers the mechanics and alternatives; here we focus on the problems the Dynamo authors hit.

Basic consistent hashing has two weaknesses, and the paper names both:

  1. Random positions give uneven load. With one token per node, some nodes own much larger arcs than others.
  2. It ignores heterogeneity. A server twice as powerful should own about twice the data.

Their fix is virtual nodes: each physical node owns many tokens. A more powerful node gets more tokens. When a node fails, its many small ranges are spread across many survivors, instead of one neighbour taking all its load. When a node joins, it takes small slices from many nodes.

3.2 Replication and the preference list

Each key is stored on N nodes. The coordinator for key k is the first node clockwise from hash(k). It stores k and also replicates it to the next N−1 distinct physical nodes clockwise. The list of nodes responsible for a key is its preference list.

Two details make this harder than it sounds:

  • Skip virtual nodes of the same physical host. With virtual nodes, the next N−1 positions might belong to the same machine. Then the "replicas" would all live on one host. The preference list is built by walking clockwise and skipping positions owned by physical nodes already chosen.
  • The list is longer than N. Every node keeps a preference list for each key range that has more than N entries. The extra entries are the fallback nodes used during failures (§4). The paper also says the list is built to span multiple data centres, so one data centre failure does not take out every replica.
flowchart LR
    K(["key 'cart:alice'\nMD5 → position 0x7F3…"]) --> P1
    subgraph ring["Clockwise from the key's position"]
        direction LR
        P1["vnode on B\n(coordinator)"] --> P2["vnode on B\n(skip — same host)"]
        P2 --> P3["vnode on D\n(replica 2)"]
        P3 --> P4["vnode on A\n(replica 3)"]
        P4 --> P5["vnode on E\n(fallback 1)"]
        P5 --> P6["vnode on C\n(fallback 2)"]
    end

For N = 3, the top N of the preference list is (B, D, A). E and C are fallbacks used only when someone in the top N is unreachable.

3.3 Three partitioning strategies — the paper's most underrated section

Section 6.2 of the paper describes how Amazon's partitioning scheme changed in production. Many summaries skip it. It is one of the most useful parts for system designers.

Strategy 1 — T random tokens per node, partition by token value. This is classic consistent hashing with virtual nodes. Each node picks T random tokens. The ranges between consecutive tokens are the partitions. The problems showed up in operations, not in theory:

  • When a node joins, it must steal key ranges from other nodes. The nodes handing off data must scan their local storage to find the keys in the moved ranges. That is expensive, and it competes with customer traffic. During busy periods, bootstrapping a new node could take almost a day.
  • Every join or leave changes many ranges, so the Merkle trees for those ranges must be recomputed (§6).
  • There was no easy way to take a snapshot of the whole key space, because ranges were random and different on every node. That made archiving complicated.

The root issue: in Strategy 1, partitioning and placement are the same thing. Moving a token both changes which keys form a partition and which node holds them.

Strategy 2 — T random tokens per node, equal-sized partitions. The hash space is cut into Q fixed, equal-sized ranges. Tokens are still random, but only decide placement. This was a transition step. The paper reports it had the worst load-balancing efficiency of the three.

Strategy 3 — Q/S tokens per node, equal-sized partitions. The hash space is cut into Q fixed partitions (Q much larger than N·S, where S is the number of nodes). Each node owns Q/S of them. When a node leaves, its partitions go to the remaining nodes. When one joins, it takes partitions from the others, keeping the Q/S-per-node balance.

Strategy 3 wins because partitioning is now separate from placement:

  • A partition is a fixed unit. It can be stored as its own file, so moving a partition means moving files, not scanning a database.
  • Merkle trees are per fixed partition and do not need recomputing when ownership changes.
  • Archiving the whole data set means archiving each partition file.
  • Membership information is small: a map from Q partitions to nodes.

The paper's measurement: Strategy 3 had the best load-balancing efficiency (the ratio of average to maximum per-node request load) of the three. It also needed the least membership metadata.

The modern echo

Strategy 3 is what almost every successor does. Riak has a fixed ring size (default 64 partitions) assigned to nodes. Cassandra moved from manual token assignment to num_tokens virtual nodes, and later added smarter token allocation. Kafka has fixed partitions per topic. DynamoDB has partitions that split and move as units. Whenever you design a sharded system, pick a fixed partition count well above the node count and move whole partitions — this is the Dynamo lesson in one sentence. See Sharding.


4. Writes and Reads: (N, R, W), Sloppy Quorums and Hinted Handoff

4.1 Strict quorums first

Dynamo uses a quorum-like protocol with three settings:

  • N — how many nodes store each key.
  • W — how many nodes must acknowledge a write before it is reported as successful.
  • R — how many nodes must respond to a read before the result is returned.

If , then any read set and any write set out of the same N nodes must overlap in at least one node:

So a read sees at least one replica that took the latest successful write. Latency is set by the slowest of the R (or W) fastest replicas, so R and W are typically set below N. The common configuration the paper reports is (N, R, W) = (3, 2, 2).

4.2 The write path

sequenceDiagram
    autonumber
    participant Cl as Client
    participant Co as Coordinator (B)
    participant D as Replica D
    participant A as Replica A

    Cl->>Co: put(key, context, value)
    Note over Co: Build new vector clock from the context,<br/>increment B's counter, write locally
    par replicate to the other top-N nodes
        Co->>D: write(key, value, clock)
        Co->>A: write(key, value, clock)
    end
    D-->>Co: ack
    Note over Co: Local write + D = 2 acks = W, reply now
    Co-->>Cl: ok
    A-->>Co: ack (late, still applied)

The coordinator creates the new version's vector clock, writes it locally, sends it to the other N−1 nodes in the preference list, and reports success once W−1 of them reply (its own write counts as one). The write is still sent to all N; the remaining replicas just aren't waited for.

4.3 The read path and read repair

sequenceDiagram
    autonumber
    participant Cl as Client
    participant Co as Coordinator (B)
    participant D as Replica D
    participant A as Replica A

    Cl->>Co: get(key)
    par ask all top-N nodes
        Co->>D: read(key)
        Co->>A: read(key)
    end
    D-->>Co: version v2, clock B2
    Note over Co: Own copy v2 + D's v2 = R responses
    Co-->>Cl: [v2], context = clock B2
    A-->>Co: version v1, clock B1 (stale)
    Note over Co: B2 descends from B1, so A is behind
    Co->>A: write v2 (read repair)

The coordinator asks all N nodes and waits for R responses. If they hold versions that are causally ordered, it returns the newest. If some are concurrent, it returns all of them. After replying, it looks at any late responses. If a replica returned a stale version, the coordinator writes the latest version back to it. This is read repair. It is cheap, it happens only for keys people actually read, and it fixes most drift for hot data. Cold keys need anti-entropy (§6).

A latency trick from the paper: the coordinator for a write is chosen as the node that answered the preceding read fastest. That node's answer is in the context the client returns. This makes it more likely that the next write goes to a node that has the latest data, and it spreads load. It also raises the chance of "read-your-writes" consistency. The paper notes that requiring the first node in the preference list to coordinate writes would create uneven load, so it does not.

4.4 Sloppy quorums: the part that buys availability

Strict quorums have a problem. If two of the three home nodes for a key are unreachable, W = 2 cannot be met, and the write fails. That breaks the shopping-cart requirement.

Dynamo's answer is the sloppy quorum: reads and writes go to the first N healthy nodes in the preference list, not necessarily the first N nodes. If a home node is down, the next node on the ring takes the write instead.

4.5 Hinted handoff

The substitute node must know that the data is not really its own. Dynamo attaches a hint to the write — metadata naming the intended recipient.

sequenceDiagram
    autonumber
    participant Co as Coordinator (B)
    participant D as Replica D
    participant A as Replica A (down)
    participant E as Fallback E

    Co->>D: write(k, v)
    Co-xA: write(k, v) — timeout
    Note over Co: A is unreachable from here.<br/>Next healthy node in the list is E
    Co->>E: write(k, v, hint = A)
    D-->>Co: ack
    E-->>Co: ack
    Note over Co: W = 2 satisfied, so the write succeeds
    Note over E: E keeps the hinted copy in a<br/>separate local store and scans it periodically
    A->>A: recovers
    E->>A: deliver hinted (k, v)
    A-->>E: ack
    Note over E: Delete the hinted copy

The hinted replica lives in a separate local database on E. E scans it periodically. When it sees that A is reachable again, it delivers the writes to A and deletes its copy. The system keeps N copies of every write even during the outage. They just are not all on the right nodes yet.

With hinted handoff, you can set W = 1 and Dynamo will accept a write as long as any single node in the system can take it. The paper says that, in practice, most Amazon services in production set a higher W to meet their durability needs.

4.6 What sloppy quorums give up

This is the caveat many summaries miss. With a sloppy quorum, no longer guarantees that a read sees the latest write. The overlap argument in §4.1 assumed both sets come from the same N nodes. During a failure, the write set might be {B, D, E} while a later read set is {A, C}, if A just recovered before getting its hints and the read went elsewhere. The sets need not overlap.

The paper is honest about this. It calls the scheme "sloppy" for exactly this reason. Dynamo's quorum settings are a durability and latency knob, not a consistency guarantee. Anyone who says "Dynamo with R + W > N is strongly consistent" has misread the paper.

SettingStrict quorum (all N are home nodes)Sloppy quorum (Dynamo)
ensures a read overlaps the last writeYes, if no concurrent writesNo — only when no fallback nodes were used
Write succeeds with fewer than W home nodes upNoYes, while any W healthy nodes are reachable
Durability during outageRejects the writeN copies kept, some on fallback nodes
Concurrent writes create siblingsStill yes — quorums alone don't order concurrent writesYes

4.7 Worked example: choosing (N, R, W)

A service stores user session blobs. Losing a session annoys a user; reading a slightly stale one is harmless. Each node has p99.9 local latency of about 10 ms; cross-data-centre round trips are about 60 ms.

OptionWrite waits forRead waits forBehaviour
(3, 1, 1)fastest 1fastest 1Lowest latency. Each write durable on just one node at ack time. A read may miss the latest write often.
(3, 2, 2)2 of 32 of 3Paper's common choice. One slow or dead replica doesn't hurt. Overlap under normal operation.
(3, 3, 1)all 31Fast reads, slow and fragile writes — one slow node stalls every write.
(3, 1, 3)1all 3Reverse: "always writable", slow reads.

The paper describes one deliberate use of R = 1, W = N: a high-performance read engine for data that is read very often and written rarely, such as product catalogue and promotional items. With R = 1, any single replica can answer. The cost is that a write needs all N up.

For the session store, (3, 2, 2) is the natural default. If the preference list spans two data centres, the second ack will often come from the remote one. Then every write pays ~60 ms. Many Dynamo descendants added data-centre-aware levels (Cassandra's LOCAL_QUORUM) for exactly this reason.


5. Versioning: Vector Clocks and Client-Side Reconciliation

5.1 Why timestamps are not enough

Because a sloppy quorum may accept writes on both sides of a network partition, two clients can update the same key concurrently, each based on the same earlier version. A store must then either:

  1. Pick one — for example, by wall-clock timestamp (last write wins). One update is silently lost. If clocks are skewed, the "later" one may actually be older. See Clock Synchronization.
  2. Keep both and let someone who understands the data merge them.

Dynamo chose option 2 by default, because for a shopping cart, losing an "Add to Cart" is the worst outcome. To do that it must tell concurrent versions apart from versions that replace each other. That is exactly what vector clocks do.

5.2 How Dynamo uses them

Each version of an object carries a vector clock: a list of (node, counter) pairs. When a coordinator writes a new version, it takes the clock from the client's context and increments its own entry.

For two clocks X and Y:

  • X descends from Y if every counter in X is ≥ the matching counter in Y. Then Y is obsolete and can be discarded.
  • If neither descends from the other, they are concurrent. Both are kept.

Syntactic reconciliation — dropping versions that an existing version descends from — is done by Dynamo automatically. Semantic reconciliation — merging truly concurrent versions — is done by the client.

5.3 Worked example: a cart split by a partition

Alice's cart key lives on nodes P, Q, R (N = 3, W = 2). We use our own scenario, not the paper's.

sequenceDiagram
    autonumber
    participant Ph as Alice's phone
    participant P as Node P
    participant Q as Node Q
    participant La as Alice's laptop

    Ph->>P: put(cart, ctx = none, [book])
    Note over P: v1 = [book], clock (P,1)
    Note over P,Q: Network partition — P and Q cannot talk
    Ph->>P: get(cart)
    P-->>Ph: [book], ctx (P,1)
    Ph->>P: put(cart, ctx (P,1), [book, lamp])
    Note over P: v2 = [book, lamp], clock (P,2)
    La->>Q: get(cart)
    Q-->>La: [book], ctx (P,1) — Q got v1 earlier
    La->>Q: put(cart, ctx (P,1), [book, mug])
    Note over Q: v3 = [book, mug], clock (P,1)(Q,1)
    Note over P,Q: Partition heals, replicas exchange data
    La->>Q: get(cart)
    Q-->>La: siblings v2 (P,2) and v3 (P,1)(Q,1), merged context
    Note over La: Neither clock descends from the other.<br/>App merges into [book, lamp, mug]
    La->>Q: put(cart, ctx (P,2)(Q,1), [book, lamp, mug])
    Note over Q: v4 clock (P,2)(Q,2) — descends from both

Step by step:

VersionContentsVector clockRelation
v1[book](P,1)—
v2[book, lamp](P,2)descends from v1
v3[book, mug](P,1),(Q,1)descends from v1, concurrent with v2
v4[book, lamp, mug](P,2),(Q,2)descends from v2 and v3

Compare v2 = (P,2) with v3 = (P,1),(Q,1). v2 has a larger P counter. v3 has a Q counter that v2 lacks (treat as 0). Neither dominates, so both are returned. The client sends back a context that is the join of both clocks. The coordinator Q increments its own entry, and v4 replaces both.

5.4 The shopping cart merge — and its famous flaw

The cart application merges siblings by taking the union of "add" operations. The paper is candid about the result: an add is never lost, but a deleted item can resurface. If Alice deletes the lamp on one side of a partition and adds a mug on the other, the union brings the lamp back.

This is the cost of choosing "never lose an add" over "never resurrect a delete". It is a business decision: a resurrected item is caught at checkout, while a lost item is a lost sale. Later work turned this into a design method. An add-wins set (OR-Set) handles adds and removes concurrently without resurrection, by tagging each add with a unique id. That is one of the CRDTs. Riak 2.0 shipped CRDT data types for exactly this reason.

5.5 Clock growth and truncation

Vector clocks grow by one entry per coordinator that has written the key. Normally that's the top N nodes, so clocks stay small. During failures and fallbacks, other nodes coordinate writes and add entries. Dynamo caps the size: each (node, counter) pair also stores a timestamp of when that node last updated the item. When the number of pairs passes a threshold (the paper gives 10 as an example), the oldest pair is removed.

The paper admits this is unsafe in principle. Truncation can make Dynamo think two versions are concurrent when one actually descends from the other. That causes unneeded siblings, not lost data. They also say that the problem had not appeared in production, so they had not studied it deeply. The cleaner fix came later: dotted version vectors keep clocks per replica rather than per client or coordinator, and handle "sibling explosion" properly. Riak adopted them. See Dotted Version Vectors.

5.6 How often do conflicts actually happen?

The paper measured the shopping cart service over 24 hours:

Versions seen by a readShare of requests
exactly 199.94%
20.00057%
30.00047%
40.00009%

The authors also noted that divergent versions were caused less by failures than by concurrent writers — and that these were usually automated clients (robots), not humans. Conflict resolution is rarely needed, but when it's needed, it must be correct.

5.7 Other reconciliation choices

Not every Dynamo service wanted siblings. The paper lists three common configurations:

  1. Business-logic reconciliation — the cart: return siblings, the client merges.
  2. Timestamp-based reconciliation — Dynamo itself keeps the version with the largest physical timestamp: last write wins. Example: a service maintaining customer session information.
  3. High-performance read engine — R = 1, W = N, for read-heavy data.

Option 2 is what Cassandra later made the only behaviour (per column, by timestamp). It is much simpler to use, and it silently loses concurrent updates. That trade-off defines much of the Dynamo family's history.


6. Anti-Entropy with Merkle Trees

Hinted handoff works when failures are short. When a hinted node dies before handing off, or a disk is replaced, replicas can drift for a long time. Read repair only fixes keys that are read. Dynamo needs a background process that compares replicas and fixes differences: anti-entropy.

Comparing replicas key by key would send all the data over the network. Dynamo uses Merkle trees instead. A Merkle tree is a hash tree: leaves are hashes of individual keys' values, and each parent is a hash of its children. Two replicas compare root hashes. If they match, the key range is identical — done, with one hash exchanged. If not, they compare children and go down only into branches that differ.

flowchart TB
    subgraph R1["Replica P — key range 7"]
        P0["root h(0-3)"] --> P1["h(0,1)"]
        P0 --> P2["h(2,3)"]
        P1 --> PL0["h(k0)"]
        P1 --> PL1["h(k1)"]
        P2 --> PL2["h(k2)"]
        P2 --> PL3["h(k3) = x9"]
    end
    subgraph R2["Replica Q — key range 7"]
        Q0["root h(0-3)'"] --> Q1["h(0,1)"]
        Q0 --> Q2["h(2,3)'"]
        Q1 --> QL0["h(k0)"]
        Q1 --> QL1["h(k1)"]
        Q2 --> QL2["h(k2)"]
        Q2 --> QL3["h(k3) = 4c"]
    end
    P0 -. "roots differ" .- Q0
    P1 -. "equal — skip whole subtree" .- Q1
    PL3 -. "differs — sync k3 only" .- QL3

With a range of K keys, finding one differing key costs about hash exchanges rather than K. Dynamo keeps one Merkle tree per key range (per partition) that a node hosts. Two nodes sharing a range exchange the roots of their trees for it.

The paper names the disadvantage directly: when a node joins or leaves, key ranges change, and the affected trees must be recalculated. That was one of the costs that pushed Amazon from partitioning Strategy 1 to Strategy 3 (§3.3). With fixed partitions, the trees stay valid when ownership moves.

Cassandra kept this design, as nodetool repair. Its operational pain — building trees is heavy on I/O, and a repair that doesn't finish within the tombstone grace period can bring deleted data back — is a direct descendant of this section. See Cassandra Internals.


7. Membership and Failure Detection

7.1 Explicit membership

A surprising choice: Dynamo does not add or remove nodes automatically based on failure detection. The authors argue that most node outages are short, so they should not trigger rebalancing. An administrator issues an explicit command (via a command-line tool or a browser) to add a node to the ring or remove it. The node serving that request writes the change and its timestamp to persistent storage. This history of membership changes then spreads by gossip.

Gossip: every second, each node picks a random peer and the two reconcile their membership change histories. Token mappings spread the same way. Eventually every node knows every other node's key ranges. That gives zero-hop routing: any node can forward a request directly to the right coordinator. This is a deliberate contrast with DHTs like Chord, which need hops — Dynamo trades membership state on every node for lower and more predictable latency. See Gossip Protocols for convergence math.

7.2 Seeds prevent logical partitions

If an admin adds node A, then adds node B by contacting a different node, A and B might each think they're members of the ring without knowing about each other: a logical partition. Dynamo prevents this with seeds — nodes found through an external mechanism (static configuration or a configuration service) that every node knows. Every node eventually gossips with a seed, so the membership views merge.

7.3 Local, temporary failure detection

Failure detection in Dynamo is local and informal. If node A cannot reach B when sending it a request, A considers B failed and uses the fallback nodes in the preference list. A periodically retries B. There is no cluster-wide agreement on who is alive. The paper explains why that's enough: explicit join and leave commands handle permanent membership, so failure detection only needs to keep a node from sending requests to peers it can't reach. Early Dynamo versions had a decentralised failure detector maintaining a globally consistent view of failure state; it was removed as unneeded.

This is a useful point for interviews. Not every system needs a perfect failure detector. If every failure response is "try the next node" and every write is safe to accept on a fallback, a local, possibly wrong suspicion costs little. See Failure Detectors for when you do need agreement.

7.4 Adding and removing nodes

When node X joins with some tokens, other nodes stop owning certain ranges and offer them to X. After X confirms, they transfer the data. Because many nodes hand over a small slice each, the work is spread out. The paper reports that this approach spreads the load of bootstrapping and gives a uniform distribution of keys, which matters for meeting the latency SLA.


8. Guarantees — Precisely

It is easy to describe Dynamo too generously. Here is what the paper actually promises:

PropertyWhat Dynamo providesCaveat in the paper
Write availabilityA write is accepted as long as W healthy nodes anywhere on the preference list (including fallbacks) can be reached.Most services set W > 1, so a full cut-off still fails. Writes need a reachable coordinator.
DurabilityAcknowledged after W nodes stored it; N copies kept, possibly via hints.With the in-memory buffer optimisation (§10), a crash can lose buffered writes. The paper uses one "durable write" replica to reduce this risk.
ConsistencyEventual consistency: if writes stop, all replicas converge.No bound on how long. No read-your-writes promise. does not give overlap under sloppy quorums.
Conflict handlingConcurrent versions are kept and returned to the client; nothing is silently dropped unless the application chose last-write-wins.Vector clock truncation can produce false conflicts. Merge correctness is the application's job.
Isolation / transactionsNone. Single-key operations only.No multi-key atomicity, no compare-and-set in the paper's API.
Ordering across keysNone.—
SecurityNone inside the cluster.Assumes a trusted network and trusted clients.

The cleanest way to say it: Dynamo offers per-key, eventually consistent, multi-version storage with application-assisted conflict resolution, tuned for availability and tail latency.


9. Fault Tolerance Summary

Put the mechanisms together and you get layered protection, each layer covering a different duration of failure:

flowchart LR
    F["Failure"] --> T{"How long?"}
    T -->|"one request"| L1["Coordinator times out,<br/>uses next replica"]
    T -->|"seconds to hours"| L2["Sloppy quorum + hinted handoff<br/>keep N copies"]
    T -->|"read touches stale replica"| L3["Read repair<br/>fixes it inline"]
    T -->|"hint lost, disk replaced"| L4["Merkle-tree anti-entropy<br/>syncs in background"]
    T -->|"node gone for good"| L5["Admin removes node,<br/>ranges reassigned"]
    T -->|"data centre lost"| L6["Preference lists span<br/>data centres"]

Two subtle points:

  • The coordinator is not a single point of failure. If the client's coordinator dies mid-request, the client times out and retries, and any node can coordinate. Writes must be safe to retry. In Dynamo they are: a retried write just becomes a new version with a newer clock (or a sibling).
  • Background work is throttled. Hinted handoff, anti-entropy and data transfer all compete with customer traffic. The paper describes an admission controller that watches foreground latency (for example, disk read latency and lock contention) and gives background tasks time slices only when the foreground is healthy. It is a small section that saves a lot of production incidents.

10. Performance Numbers From the Paper

All numbers below come from the paper's Section 6, measured on Amazon production systems in 2006–2007. Treat them as what was observed then, on that hardware, not as benchmarks.

10.1 Latency against the SLA

The paper shows a month of average and 99.9th-percentile read and write latencies during the December 2006 holiday season. The 99.9th-percentile latencies were roughly an order of magnitude higher than the averages, and stayed within the target of a few hundred milliseconds. Writes were slower than reads because they always access disk. Latency followed the daily request-rate pattern.

10.2 Buffered writes

For services that needed tighter tail latency, Dynamo added an object buffer in main memory. Writes go to the buffer and a writer thread flushes them to storage periodically. Reads check the buffer first. The paper reports that with a buffer of just 1,000 objects, the 99.9th-percentile write latency dropped by a factor of 5 during peak traffic.

The price is durability: a crash loses buffered writes. The mitigation is clever. The coordinator picks one of the N replicas to do a "durable write" — a write that goes straight to storage — while the others use the buffer. Because only W responses are needed, the slower durable write doesn't hurt latency, but at least one copy is on disk.

10.3 Server-driven vs client-driven coordination

Requests could reach Dynamo in two ways: through a generic load balancer to a random node (which forwards to a coordinator), or through a partition-aware client library that downloads membership and goes straight to a coordinator. The paper's Table 2 compares them:

p99.9 readp99.9 writeavg readavg write
Server-driven68.9 ms68.5 ms3.9 ms4.02 ms
Client-driven30.4 ms30.4 ms1.55 ms1.9 ms

Removing one network hop cut the tail by more than half. The client library polls a random Dynamo node every 10 seconds for membership updates. This is the same reason Cassandra drivers are "token-aware" and DynamoDB SDKs talk to request routers that know the partition map.

10.4 Load balance

The paper measured, over 24 hours, the fraction of nodes "out of balance" (load more than 15% off the average). At low load it was about 20%, at high load about 10%. Imbalance falls as load rises, because popular keys spread over more nodes. It is a reminder that uniform hashing balances keys, not traffic; hot keys remain a problem. See Sharding.

10.5 Divergence

See §5.6: 99.94% of shopping-cart reads saw a single version.


11. What Dynamo Got Right, What It Got Wrong, and What Came After

11.1 Right

  1. Measuring at the 99.9th percentile. The whole paper's design discipline comes from this, and it is now standard practice.
  2. Separating partitioning from placement (Strategy 3). Every serious sharded system does this today.
  3. Making the availability trade-off explicit and configurable with N, R, W, and per-application reconciliation.
  4. Layered repair — hinted handoff, read repair, anti-entropy — each covering a different failure duration.
  5. Admission control for background work. Repair traffic that harms customer latency is itself an outage.

11.2 Wrong, or at least costly

  1. Pushing conflict resolution to every client. Siblings and contexts are hard to use correctly. A client library that drops the context on write creates siblings forever. Many teams chose last-write-wins to avoid it, giving up the main benefit.
  2. "Eventually consistent" was too weak for many applications. Developers wanted read-after-write and conditional updates. The paper's model offered neither.
  3. Vector clocks keyed by coordinator grow and need unsafe truncation. Dotted version vectors fixed this.
  4. Full membership on every node works for hundreds of nodes. The paper notes that scaling to tens of thousands of nodes would make the routing table expensive to maintain and suggests hierarchical extensions as future work.
  5. Operational complexity. The paper's design was fine for Amazon's storage teams. The 2022 DynamoDB paper (below) reports that Dynamo's self-managed model meant each service team had to become experts in running it, which limited adoption inside Amazon.

11.3 How DynamoDB, the service, differs from the paper

DynamoDB (launched 2012) shares a name and some ideas, not an architecture. The USENIX ATC 2022 paper "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service" (Elhemali et al.) describes it:

Dynamo (2007 paper)DynamoDB (the service)
Who runs itEach service teamAWS, fully managed, multi-tenant
ReplicationLeaderless, sloppy quorumLeader-based: each partition is a replication group using Multi-Paxos, replicas across 3 Availability Zones
WritesAny coordinator, W acksLeader accepts; acks after a quorum (2 of 3) persist the log record
ReadsR replicas, may return siblingsEventually consistent (any replica) or strongly consistent (leader) — the caller chooses per read
ConflictsVector clocks, siblingsNo siblings within a Region; the leader orders writes. Multi-Region global tables resolve conflicts with last-writer-wins (newer versions also offer a multi-Region strong consistency mode)
RoutingGossip, zero-hop on every nodeRequest routers + a partition metadata service
Data modelOpaque blobsItems with attributes, partition + sort key, secondary indexes, conditional writes, transactions (since 2018)
RepairHinted handoff, Merkle treesLog replicas for fast healing, continuous verification, backups to S3
CapacityNot modelledProvisioned or on-demand throughput, adaptive capacity, global admission control

In other words, AWS kept the goals (predictable tail latency, horizontal scale, high availability) and the partitioning lessons, and replaced leaderless replication with consensus per partition. That gives strongly consistent reads, conditional writes and transactions — what developers wanted — while Multi-Paxos with fast leader failover keeps availability high in practice. Details on DynamoDB Internals.

11.4 The descendants

timeline
    title The Dynamo family
    2006 : Bigtable paper (data model later borrowed by Cassandra)
    2007 : Dynamo paper at SOSP
    2008 : Cassandra open-sourced by Facebook : Project Voldemort at LinkedIn
    2009 : Riak by Basho
    2012 : DynamoDB launches — leader-based, managed
    2014 : Riak 2.0 adds CRDT data types and dotted version vectors
    2022 : DynamoDB paper at USENIX ATC
SystemWhat it kept from DynamoWhat it changed
Apache Cassandra (Facebook, 2008; Lakshman & Malik)Ring, virtual nodes, gossip, hinted handoff, read repair, Merkle-tree repair, tunable consistencyBigtable-style wide-column model on an LSM tree; last-write-wins by timestamp per cell instead of vector clocks; consistency levels like ONE, QUORUM, LOCAL_QUORUM; later lightweight transactions via Paxos, and (in newer development lines) the Accord protocol for general multi-key transactions. A phi-accrual failure detector.
Riak KV (Basho, 2009)The closest to the paper: vector clocks, siblings, sloppy quorums, hinted handoff, fixed-size ringDotted version vectors to stop sibling explosion; CRDT data types (counters, sets, maps); active anti-entropy with persistent hash trees
Project Voldemort (LinkedIn)Consistent hashing, vector clocks, read repair, pluggable storageSimpler, used heavily for read-only batch-computed data (built offline in Hadoop and swapped in)
ScyllaDBCassandra's Dynamo-style modelC++ rewrite, shard-per-core; later Raft for metadata and tablets

If you have read Cassandra Internals, you now know where most of its distribution layer comes from.

11.5 Where the field went

The broad trend since 2007 has been away from leaderless replication for primary data and toward per-shard consensus (Raft or Paxos groups), as in DynamoDB, Spanner, CockroachDB and TiDB. Consensus got faster, cloud networks got more reliable, and developers strongly prefer not having to merge siblings. Leaderless designs remain strong for very high write rates, multi-data-centre active-active writes, and data that merges naturally (time series, counters, logs, CRDT-friendly state). The idea that survived best is not leaderlessness itself but thinking about conflicts as a design problem — which is how CRDTs and local-first software came about.


12. Lessons for System Design Interviews

When a design question asks for "a highly available key-value store", "a shopping cart", or "a session store", the interviewer is usually looking for Dynamo-style reasoning. See the Key-Value Store interview walkthrough. The lessons that transfer:

  1. Start from the business failure mode. "Which is worse: rejecting a write or showing a stale/merged value?" The answer chooses your replication model. Say it out loud.
  2. Separate partitioning from placement. Fixed partitions, many more than nodes, moved as whole units. Mention that this makes rebalancing, repair and backups cheap.
  3. Quorum math has an asterisk. only gives overlap with strict quorums and no concurrent writers. If you add sloppy quorums for availability, say that you lose that overlap.
  4. Know three conflict strategies: last-write-wins (simple, loses data), siblings with application merge (correct, hard to use), CRDTs (correct and automatic, only for data types that fit).
  5. Layer repair by failure duration: retry, hinted handoff, read repair, anti-entropy.
  6. Talk about tail latency. Mention p99.9, the fan-out argument, client-side routing to save a hop, and why W and R below N help.
  7. Gossip is fine for membership at hundreds of nodes; mention the scaling limit and that large systems often use a coordination service instead (see ZooKeeper).
  8. Know the DynamoDB contrast. Interviewers like candidates who know that "DynamoDB is not Dynamo" and can explain why AWS moved to Multi-Paxos per partition.

A common interview mistake

Saying "we'll use Cassandra with QUORUM reads and writes, so it's strongly consistent." It is not linearizable: concurrent writes are ordered by client timestamps, hinted writes and read repair can reorder visibility, and failed writes that partially succeeded can appear later. For linearizable single-key operations you need a consensus-based mechanism (Cassandra's lightweight transactions, or a Raft/Paxos store). See Consistency Models.


13. Interview Questions

1. Why did Dynamo resolve conflicts at read time instead of write time?

Resolving at write time requires coordinating the writers — locks, a leader, or a majority — and when that coordination isn't possible (a partition, failed nodes), the write must be rejected. The shopping cart requirement says writes must never be rejected. So Dynamo accepts every write, records causality with vector clocks, and shows conflicts to the reader, who has the application knowledge needed to merge them.

2. With N=3, R=2, W=2, can a Dynamo read miss the latest acknowledged write? Give a scenario.

Yes. Home nodes are A, B, C. A and B are unreachable from the coordinator, so the write goes to C and fallback D (hinted for A). W = 2 is met. Then the partition heals partly: a read reaches A and B, which haven't received the hint yet. R = 2 is met, both return the old value. The read set {A, B} and write set {C, D} do not overlap. This is why sloppy quorums break the argument.

3. What problem does hinted handoff solve, and what is its main limitation?

It keeps writes available and keeps N copies when home replicas are temporarily down, by storing writes on a fallback node with a hint naming the intended owner. The limitation: if the fallback node fails before delivering the hint, those copies are lost from the home node's perspective, and replicas stay divergent until anti-entropy runs. Hints also don't make the data visible to reads routed to the home node.

4. Explain how a Merkle tree reduces the cost of anti-entropy, and why changing partition boundaries is a problem.

Two replicas compare root hashes per key range; equal roots mean identical data with one exchange. If roots differ, they recurse only into differing subtrees, so finding a few differing keys costs roughly logarithmic exchanges instead of sending every key. The trees are built per key range. If ranges change because a node joins or leaves (as in random-token partitioning), the trees for affected ranges must be rebuilt — costly scans. Fixed partitions avoid that.

5. Compare Dynamo's three partitioning strategies. Why did Strategy 3 win?

S1: random tokens define both partitions and placement — rebalancing requires scanning storage, rebuilding Merkle trees, and archiving is hard. S2: equal-sized partitions but random token placement — a transition step with the worst balance. S3: Q fixed equal partitions, each node holds Q/S — partitions become files that move whole, Merkle trees stay valid, membership metadata is small, and load balance is best.

6. Why does the shopping cart sometimes resurrect deleted items? How would you fix it?

Siblings are merged by unioning their contents. A delete on one branch and an unrelated change on the other: the union contains the deleted item again, because a plain set can't tell "never added" from "added then removed". Fix: an observed-remove set (OR-Set) CRDT where each add has a unique tag and a remove deletes only the tags it has seen. A concurrent add with a new tag survives, but a removed one doesn't come back.

7. What does it mean for a vector clock to "descend from" another, and what does truncation risk?

Clock X descends from Y if every counter in X is greater than or equal to Y's (missing entries count as zero). Then Y is an ancestor and can be dropped. Truncation removes the oldest entries once the clock is too long. A truncated clock may no longer show that it descends from an older one, so the system reports a false conflict — extra siblings rather than lost data.

8. Why does a partition-aware client reduce p99.9 latency so much?

It removes a network hop — client to random node, then forwarded to the coordinator — and the queueing at that intermediate node. Tail latency is very sensitive to extra hops because each one adds its own tail. The paper measured p99.9 read latency dropping from 68.9 ms to 30.4 ms.

9. Design question — a global "like" counter for posts must accept increments in every Region even during inter-Region partitions. Would you use Dynamo-style replication? How do you avoid lost increments?

Yes, leaderless or multi-leader replication fits, because increments commute. Don't store the count as a single LWW value — concurrent increments would overwrite each other. Use a G-Counter or PN-Counter CRDT: each replica keeps its own count and the merge takes the per-replica maximum, with the total being the sum. Accept writes locally with a small W, replicate asynchronously, and use anti-entropy for convergence. Mention that reads are approximate until convergence.

10. Why did AWS build DynamoDB on Multi-Paxos per partition instead of Dynamo's leaderless design?

Customers wanted strongly consistent reads, conditional writes and transactions, which need a single order of writes per key — easy with a leader, very hard with siblings. A managed multi-tenant service also needs predictable per-partition throughput control, which a leader makes simple. And cloud networks across Availability Zones are reliable enough that a consensus group with fast leader failover gives the availability the business needs. Dynamo's goals stayed; the mechanism changed.

11. Why does Dynamo let an administrator, not the failure detector, change ring membership?

Most outages are short. If a failure detector removed nodes automatically, every brief network blip would trigger expensive rebalancing and data movement, which itself hurts latency and can cascade. Short failures are covered by sloppy quorums and hints. Permanent changes are rare and important enough to need a human decision.

12. What would you change about Dynamo to run it with 20,000 nodes in one ring?

Full membership gossip on every node becomes expensive and slow to converge. Options: hierarchical membership (gossip within groups, summaries between them); a coordination service holding the partition map (ZooKeeper or a Raft-based metadata service) that clients and nodes cache; or split into many independent clusters (cells) behind a routing layer. Also use fixed partitions so map updates are small, and keep zero-hop routing via cached maps.


Further Reading

  • G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, W. Vogels. Dynamo: Amazon's Highly Available Key-value Store. SOSP 2007. — the primary source for every number on this page.
  • M. Elhemali et al. Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service. USENIX ATC 2022.
  • A. Lakshman, P. Malik. Cassandra — A Decentralized Structured Storage System. LADIS 2009.
  • N. Preguiça, C. Baquero, P. S. Almeida, V. Fonte, R. Gonçalves. Dotted Version Vectors: Logical Clocks for Optimistic Replication. 2010.
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski. Conflict-free Replicated Data Types. SSS 2011.
  • W. Vogels. Eventually Consistent. ACM Queue, 2008.

Related Archon pages: Consistent Hashing · Gossip Protocols · Vector Clocks · CRDT Fundamentals · Replication · Cassandra Internals · DynamoDB Internals