Dissection · DeCandia et al., 2007

Anatomy of Dynamo

Amazon's Highly Available Key-value Store, dissected: a ring of seven nodes laid out in 3D, the paper's Figure 3 lived through by a seeded cluster, and a research desk that tests the model of how stale its reads are.

PaperDeCandia et al., SOSP 2007

Modelseven nodes, a seeded run, live

Reading43 min · 29 steps

Published2026-10-18

01Overview

How do you build a store that never says no to a write?

Dynamo set out to show that an eventually consistent storage system can run demanding production applications [1]. Its flagship user in the paper is the shopping cart, and a cart has one unforgivable failure: a customer must be able to view and add items even if disks are failing, network routes are flapping, or data centres are being destroyed. The design that follows is a set of answers to one question: what do you give up so that a write is always accepted? The paper's own summary of the method is that data is partitioned and replicated using consistent hashing, and consistency is facilitated by object versioning, with quorum-like replication, replica synchronisation and gossip around them.

What is on the table is that design, built out of numbers. Seven nodes stand in a circle. Each is a card showing what the node holds for six carts: up to three versions of each, coloured by which version it is, and the hinted replicas it keeps for others. Inside the circle are two rings: the one drawn in the paper's Figure 2, seven tokens named A to G, and the ring this cluster really uses, with four tokens for each node. The glowing links are messages, coloured by type. Further up the table are Figure 3's vector clocks, one stale read drawn replica by replica, two Merkle trees, gossip round by round, the three ways §6.2 partitions the ring, and the results of the research desk.

Nothing here is a drawing of data. The cluster is a seeded simulation of the protocol the paper describes, computed in this page, and test.mjs checks it against the paper's own figure, against a theorem about quorums on four latency models, against the invariants of the protocol under random crashes and partitions, and against the numbers a later paper published about how stale its reads are. The visual grammar, values as blocks of cells you can hover, follows Brendan Bycroft's LLM Visualization.

How to use this page

Scroll the article, or use ← →. Drag the stage to orbit, scroll on it to zoom; O shows the whole machine and R replays a step. Change the seed and a different ring, different latencies and a different run are computed. On the cards, an amber block is a version, a blue one a version that conflicts with it; a pink block marks a hint; a flat red card is a node that is down. Blocks on the rings are coloured by the node that owns them.

Go deeper: Dynamo: always writeable · Eventual consistency · Quorum

02Overview

One run on the table, a hundred thousand in the research desk

The paper describes a system, not an execution, so the only things in it to transcribe are its figures; those get their own steps. The seed in the input chooses an execution: . Scrolling this step plays the whole of it. It is the story the paper tells around its Figure 3, with the cluster of this page living it out: five writes to one cart, one node going down in the middle, a neighbour keeping its writes for it, two clients who cannot see each other's changes, and a read that finds both.

Go deeper: Seeds and the limits of determinism · Monte Carlo methods

03Why Dynamo

What would you drop from a database to keep a shopping cart up?

Amazon's platform serves tens of millions of customers at peak using tens of thousands of servers, and the authors' premise is that dealing with failures in an infrastructure of millions of components is the standard mode of operation. A shopping cart service therefore needs a store it can always write to and read from, and it is a heavy user: tens of millions of requests resulted in well over 3 million checkouts in a single day. Most services only need that store to do very little: reads and writes of one item by its key, no operation spanning items, no relational schema, of objects usually under 1 MB. A relational database offers far more than these services use, and the paper's complaint is that its replication typically chooses consistency over availability [1]; Dynamo removes the extras. It offers no isolation, and only single-key updates, and assumes a non-hostile environment, with no authentication or authorisation. Each service runs its own instance, so the initial design targets up to hundreds of storage hosts.

The requirement that shapes everything else is a latency one. Each service in the call chain must meet a contract, because a single page request typically needs responses from over 150 services. The contract is stated in the tail: a response within 300 ms for 99.9% of requests at a peak of 500 requests a second, because at Amazon, service level agreements are expressed and measured at the 99.9th percentile and not at the mean. That is why a put in the paper never waits for every replica, and why the research desk, which is about how stale a read can be when you do not wait, is the right question to ask of it.

On the stage each of the six carts is stored on three of the seven nodes. . Scrolling plays the first two writes to cart:alice.

Go deeper: SLI, SLO and SLA · Percentile latency · Tail latency

04Why Dynamo

Who resolves a conflict, and when?

If replicas accept writes independently, two replicas can end up with different answers, and a store must decide when to reconcile them and who does it. The paper's choices are the heart of the design. On when: traditional stores resolve at write time and reject a write they cannot make safe, but Dynamo targets an "always writeable" data store, so the complexity of conflict resolution is pushed to the reads, to ensure that writes are never rejected. On who: the store can only apply a simple policy such as last write wins [2], while the application knows its own data, so that the cart service can choose to merge the conflicting versions and return a single unified cart. The model is eventual consistency: all updates reach all replicas eventually, and the paper places itself with systems such as Bayou, where "Bayou allows application level resolution" [3]. The case against strong consistency is made by "strong consistency" systems being limited in scalability and availability [4].

Four principles are listed beside these. Incremental scalability: add one node at a time. Symmetry: no node has special duties. Decentralisation: peer-to-peer techniques over central control. Heterogeneity: work in proportion to each server's capacity. The next five steps are how each is achieved, and the stage already shows the price of the second choice: the blue cells of Figure 3's second table mark two versions of the same cart that neither supersedes.

Go deeper: Last writer wins · Sync conflict resolution · Strong against eventual consistency · Consistency models

05Partitioning

Where does a key live?

Dynamo spreads keys with consistent hashing [5]. A key is hashed with MD5 to a 128-bit identifier, and the output range of the hash is treated as a fixed circular space, a ring. Each node is given a random position on the ring; a key is assigned to a node by hashing it to a position and walking the ring clockwise to the first node with a larger position. A node is therefore responsible for the arc between its predecessor and itself, written $(A, B]$ in the paper, and a node joining or leaving affects only its immediate neighbours.

The inner ring on the stage is the paper's Figure 2: seven nodes, one token each, and a key $K$ hashed between A and B. B is its coordinator, and, as the next step explains, B, C and D store it. The miniature's ring is 32 bits wide, the first four bytes of the MD5, where the paper's is 128; test.mjs checks the hash against Node's own MD5 on twelve strings and checks that the key in Figure 2 lands on B, C and D. Hover any token for where it sits.

Live from the ring: .

Go deeper: Consistent hashing · Partitioning and sharding · Shard key

06Partitioning

Why give a node four places on the ring?

One random point per node has two weaknesses, which the paper names: random positions leave the data and load unevenly distributed, and the scheme ignores that servers differ in power. The fix is to give each node several points on the ring, so that a node is responsible for more than one virtual node, the points being tokens. A failed node's load is then dispersed evenly across the remaining nodes, and a node with more capacity can be given more tokens.

The outer ring on the stage is the one this cluster uses: seven nodes, four tokens each, coloured by owner, so the owner of an arc is the colour of the token that closes it. The figure below sweeps the number of tokens. On this page's keys the busiest of thirty nodes carries about twice the mean load with one token per node, and about a tenth more than the mean with a hundred (efficiencies of 0.49 and 0.89). And when a node joins a ring, the keys that move all move to the new node, about $1/ (S + 1)$ of them: both are checked in test.mjs.

Go deeper: Consistent hashing · Hot key · Sharding patterns

07Partitioning

Who else holds a copy?

Durability comes from copies. Each item is replicated at N hosts, N being set per instance; the node a key hashes to is its coordinator, and it replicates the key at the N-1 clockwise successors. The list of nodes responsible for storing a key is called the preference list, and it contains more than N nodes, to account for failures. With virtual nodes the next tokens round the ring can belong to a node already on the list, so the list is built by skipping positions to contain only distinct physical nodes.

The stage shows the walk for cart:alice. From the key the link runs to the first token at or after it, then on round the ring; an amber link reaches a new node, a red one passes a token whose node is already on the list. The run's own preference lists: . The first node on a list is the usual coordinator, the fourth and later ones are where writes go when a replica is down (the third failure-handling step).

Go deeper: Replication · Replication · Durability against availability

08Partitioning

Why did Dynamo stop giving nodes random tokens?

The paper's §6.2 is a rare thing: an account of a design that was changed after production taught its authors what was wrong. Strategy 1, the original, gave T random tokens per node and cut the ring at the tokens. In busy seasons bootstrapping a node has taken almost a day, because the nodes handing off keys must scan their local stores at the lowest priority; the Merkle trees of every changed range must be recomputed; and archiving the key space needs a visit to every node. The root cause was that partitioning and placement were intertwined. Strategy 2 divides the hash space into Q equal partitions and keeps T random tokens per node, and Strategy 3 gives each node Q/S tokens, with equal-sized partitions (this page models it as each token ending one partition), with Q much larger than N and than S·T.

The paper compares them by load-balancing efficiency, the mean number of requests a node serves over the maximum, at S = 30 and N = 3 and at equal metadata per node. Its reading is that Strategy 3 balances best and Strategy 2 worst, and that Strategy 3 reduces the membership information each node keeps by three orders of magnitude. The price is that changing the membership requires coordination to preserve the properties of the assignment. On the stage each strip is thirty nodes, a block's height and colour showing its share above or below the mean: .

Go deeper: Partition assignment · Logical shard · Partitioning and sharding

09Reading and writing

What does a client actually call?

Two operations, and no others: get() and put(). get(key) locates the replicas of the object and returns a single object, or a list of objects with conflicting versions, along with a context. put(key, context, object) decides where the replicas go from the key and writes them to disk. The context is the interesting argument: it is opaque to the caller and carries system metadata such as the version, and it is what ties a write to the read that preceded it. In this page the context is the join of the vector clocks of the versions the read returned (two steps on); test.mjs checks the context for the read before D5 in Figure 3 is exactly the clock the paper prints.

Any node can receive a call: any storage node is eligible to receive client get and put operations for any key. A client either goes through a load balancer that picks a node by load, or uses a partition-aware library that routes directly to the coordinator. The second saves a forwarding hop; §6.4 measures how much (the coordination step). On the stage the six small pink blocks at the edge of the ring are the carts hashed onto it: .

Go deeper: Consistent hashing · Read your writes

10Reading and writing

Who runs an operation, and how many replies are enough?

The node that handles a read or write is the coordinator, typically the first of the top N nodes of the preference list. If a request arrives at a node outside that set, that node forwards it to the first of the top N. The coordinator contacts the first N healthy nodes of the list, skipping those that are down or unreachable, and the consistency protocol has two knobs: R is the minimum number of nodes that must take part in a successful read and W the minimum for a write. Setting R + W > N yields a quorum-like system, and the latency of an operation is the slowest of the R (or W) replicas it waits for. For that reason the usual settings keep R and W below N.

In the run: . The figure below lets you set N, R and W and read off what they buy. The probability that a read's R replicas miss a write's W replicas has a closed form that the research desk uses again, $p_{s} = (R N - W) / (R N)$ , and is zero exactly when $R + W > N$ .

Go deeper: Quorum · Tail latency · Consistency choices

11Reading and writing

What does it take for a write to count?

The paper's own account of a put is short. On receiving a put(), the coordinator generates the vector clock for the new version and writes it locally; it then sends the new version, with its clock, to the N highest-ranked reachable nodes; if at least W-1 nodes respond, the write is considered successful. The coordinator is itself one of the N, which is why W-1 replies are enough. On the stage the coordinator's card changes first; blue links carry the write to the other two cards, teal ones carry the acknowledgements back, and the put commits when the second copy exists. The third copy usually arrives a moment later, and in the meantime it is missing: .

Setting W controls how much the client is told. At W = 1, a write is accepted as long as one node has durably written it, the highest availability; but low values of W and R increase the risk of inconsistency and open a window in which a returned write sits on only a few nodes, and in practice most production services set a higher W. Each put also produces a new and immutable version of the data, never an in-place update; this is what the stage's cards show, a version added to a row rather than a cell overwritten.

The part of a put you cannot see

A put that has returned is not finished: the replicas that have not yet answered are still receiving it. That gap, between a write being acknowledged and being everywhere, is the whole subject of the research desk.

Go deeper: Replication lag · Durability against availability

12Reading and writing

What does a read return when the replicas disagree?

For a get(), the coordinator requests all existing versions from the N highest-ranked reachable nodes and waits for R responses before returning, and if it gathers several versions it returns all those it deems causally unrelated. Asking all N and waiting for R is what makes the latency the R-th fastest reply, not the slowest. In the run: .

The replicas that answer late, or answer with an old version, are not forgotten. The coordinator waits a little for the remaining responses and, when some are stale, writes them the latest version: read repair repairs replicas that have missed a recent update at an opportunistic time, and relieves anti-entropy of having to do it. . The research desk's second relaxation measures how much staleness read repair removes when a key is read often.

Go deeper: Read your writes · Eventual consistency

13Versions

How does the store know that two versions are unrelated?

A vector clock is a list of (node, counter) pairs, one clock per version of every object, after Lamport's logical clocks [7]. Two versions are compared by their counters: if the counters of the first clock are all less than or equal to the second's, the first is an ancestor and can be forgotten. In symbols, version $a$ is an ancestor of $b$ when $a_{n} \leq b_{n}$ for every node $n$ , and the two are in conflict when neither is an ancestor of the other. A write names the version it updates: the client passes the context it obtained from an earlier read.

Figure 3 of the paper is a story in five versions, and the stage's first table is that story, run through the engine's stamping and comparison code, not drawn. D1 carries the clock [(Sx, 1)]; D2, written through the same node, carries [(Sx, 2)] and supersedes D1. A different node writes the next update: D3 carries [(Sx, 2), (Sy, 1)]. A client who read D2 writes through a third node: D4 carries [(Sx, 2), (Sz, 1)]. D3 and D4 each have a counter the other lacks, so neither is an ancestor: they are in conflict, the blue cells of the second table. A client who then reads both receives the context [(Sx, 2), (Sy, 1), (Sz, 1)] and, writing through Sx, produces D5, with the clock [(Sx, 3), (Sy, 1), (Sz, 1)], which descends from all four. test.mjs asserts all five clocks, the verdict on every pair, and the context.

Go deeper: Version vector · Clock and ordering · Causal consistency · CRDT

14Versions

What happens when two clients write at once?

Most of the time a new version subsumes the previous ones, and the system itself determines the authoritative version: syntactic reconciliation. When failures combine with concurrent updates the history branches, and then the client must reconcile, collapsing the branches back into one: semantic reconciliation. Both happen in the run. . .

The stage plays it from immediately before D3 to immediately before the merge. D3 and D4 are different colours, because they are different versions that neither supersedes; the node that holds both has them side by side in two slots of the same row. A cart is a set of items, and the client's reconciliation here is the union. The paper is candid about the cost of that choice: an "add to cart" operation is never lost by this mechanism, but deleted items can resurface. The next step shows the resurfacing in the run, and the research desk tests the first half of that sentence.

Go deeper: Sync conflict resolution · Last writer wins · Conflict copy

15Versions

What does the client do with two versions?

. D5 supersedes all four earlier versions, as Figure 3 says, so once it has reached the replicas the conflict is gone and the next read returns one version.

: that is the second half of the paper's sentence, and it follows directly from merging by union. A union cannot tell an item that was never in one branch from an item that was deleted from it. Applications that care need tombstones or a richer merge, and the paper puts the burden on the application deliberately: the application knows its data, so it can pick the reconciliation that suits its customers. The last research step tests the first half of the paper's sentence against a later critique of its clocks [8].

Go deeper: Tombstone accumulation · CRDTs · Sync and conflict resolution

16Failures

What if one of the three nodes is down?

A strict quorum on the preference list would make the key unavailable for writes as soon as too many of its nodes were out. Dynamo's answer is to not enforce strict quorum membership: operations run on the first N healthy nodes of the preference list, which may not be the first N met walking the ring, a "sloppy quorum". How does a coordinator know a node is down? Locally, and only locally: node A may consider B failed if B does not respond to A's messages, even if B responds to C's, and A periodically retries B to check for its recovery. There is no global verdict.

The run does exactly this. . . The write that would have gone to the crashed node goes to the stand-in with a mark on it: the replica carries a hint in its metadata naming the intended recipient, and a node that receives hinted replicas keeps them in a separate local database, scanned periodically. On the stage the stand-in's hint column fills (pink) while the crashed node's card stays flat and red.

The preference list is also built so that its nodes are spread across several data centres, so a whole data centre can be lost without losing the key.

Go deeper: Quorum · Partition tolerance · CAP theorem · CAP and PACELC

17Failures

How does a stand-in give the data back?

When the stand-in detects that the node has recovered, it delivers the replica, and once the transfer succeeds it may delete its copy without reducing the number of replicas in the system. . On the stage the pink cell empties as the node's own cell fills, and a magenta link carries the transfer between the two cards.

Handoff only works if the stand-in is still alive when the node returns. The paper says so: hinted handoff works best if membership churn is low and node failures are transient. When a stand-in fails first, the hinted copy is gone and the intended recipient never received the write; that is the case the next step exists for. The research desk's failure experiment includes the version of it in which no coordinator has noticed the failure, so no hint is ever written.

Go deeper: Durability against availability · Replication

18Failures

How do two replicas find the one key they disagree on?

For failures hinting cannot cover, Dynamo implements anti-entropy to keep the replicas synchronised, using Merkle trees [9]. A Merkle tree is a hash tree whose leaves are hashes of the values of individual keys and whose parents are hashes of their children, and its use rests on one property: if the roots of two trees are equal the leaves are equal and nothing needs synchronising; if not, the nodes exchange children and descend, so they find the keys that differ without sending the data they agree on. Each node keeps a separate tree for each key range, the keys of one virtual node.

The stage has two replicas of one key range: . Highlighted blocks are the nodes whose hashes differ, the path the comparison follows. The figure below varies the number of differing keys and shows the comparisons, against comparing every key.

Go deeper: Replication · Replication lag

19Failures

Who is in the ring, and who tells the others?

A permanent departure and a crash look the same from a distance, and the paper chooses not to guess: joining and leaving the ring is an explicit action, issued by an administrator. The node that serves the request records the change and its time, and then each node contacts a random peer every second, and the two reconcile their persisted histories of membership change. Tokens spread the same way, so each node learns the ranges of its peers and can forward a request directly. To prevent a logical partition, seeds, nodes discovered by an external mechanism and known to all, take part.

The stage plays one change spreading: . Failure detection is deliberately not part of this: early designs kept a globally consistent view of failure state, but the explicit join and leave methods made that unnecessary. When a node does join, it is given tokens at random; for the paper's example, a node X added between A and B takes over three ranges, (F, G], (G, A] and (A, X], and the nodes that held them offer the keys and, on X's confirmation, transfer them.

Go deeper: Partition tolerance · Distributed systems

20In production

What runs on one node?

Each storage node has three main components: request coordination, membership and failure detection, and a local persistence engine, all implemented in Java. Coordination is built on an event-driven messaging substrate whose pipeline is split into stages, like SEDA [10], and each client request creates a state machine on the node that received it. A read's machine is the paper's own list of five steps: send read requests, wait for the required responses, fail if too few arrive in time, otherwise gather the versions and decide which to return, and, if versioning is enabled, reconcile syntactically and generate the write context. The engine's get is that machine, and its put the corresponding one.

Writes have a refinement the stage does not need but the research desk does. A put's coordinator need not be the first of the list. The paper chooses the node that replied fastest to the previous read, recorded in the request's context, because that node holds the data the preceding read returned, which raises the chance of read-your-writes consistency. Background work, replica synchronisation and handoff, competes with foreground gets and puts, so each background task reserves runtime slices of the resource through a shared admission controller. Storage is pluggable: BDB Transactional Data Store, BDB Java Edition, MySQL and an in-memory buffer with persistent backing store, and most production instances use BDB Transactional Data Store. This page's nodes keep versions in memory, and take no time to do it; the paper's write latencies include a disk.

Go deeper: Read your writes · Replication

21In production

What did Amazon report, and what did it keep back?

The measurements of §6 were taken on a live system running (N, R, W) = (3, 2, 2) on a couple of hundred nodes; that was the configuration several instances commonly used, with N usually 3. Services chose differently according to what they needed: a read-heavy catalogue ran R = 1 and W = N. The authors did not publish absolute numbers: they reduced some detail to protect Amazon's business interests, so latencies, request rates and outage lengths are aggregate measures.

Four results stand out. On the tail: a typical SLA is 99.9% of reads and writes within 300 ms, and the 99.9th percentile is around 200 ms, an order of magnitude above the mean. A buffer of a thousand writes in memory lowered the 99.9th percentile by a factor of 5 at peak, and at the cost of a durability risk it mitigates by having the coordinator pick one of the N replicas to make a durable write. On availability: 99.9995% of requests succeeded without timing out, and no data loss event has occurred. On inconsistency, the figure that matters most to this page: in 24 hours the cart service saw one version in 99.94% of requests, two in 0.00057%, three in 0.00047% and four in 0.00009%, which the authors trace to concurrent writers, mostly automated clients, and not to failures.

Go deeper: Percentile latency · Tail latency · Hedged request · Tail latency

22In production

What did moving the coordinator into the client buy?

The state machine need not live on a server. In client-driven coordination, clients poll a random node for the membership view every 10 seconds and coordinate their own reads, avoiding the load balancer and the forwarding hop. The result, in the paper's Table 2: the 99.9th percentile falls by at least 30 ms and the average by 3 to 4 ms. The paper's explanation is that the load balancer and the network add variability, which weighs more at the high percentile.

For this page the choice matters for a different reason. In the PBS paper's model, which the research desk tests, the coordinator is outside the replicas: every message to and from a replica takes time. In Dynamo's server-driven mode the coordinator is a replica, and a message to oneself takes none. The PBS authors know it: a read or write to R or W nodes in that case behaves like a read or write to R-1 or W-1 nodes [11]. How much that matters is the first thing the research desk relaxes. .

Go deeper: Tail latency · Read your writes · Hedged request

23Research desk

E1 · How stale is a read, and does the model of it hold?

Dynamo's configurations with R + W ≤ N, which the paper's own (3, 2, 2) is not but many of its descendants are (Cassandra defaults to N = 3, R = W = 1, Voldemort at LinkedIn runs N = 3, R = W = 1 for applications needing very low latency), give up the intersection guarantee, and the Dynamo paper does not quantify what they give instead. Bailis and colleagues do [11]. A strict quorum is one in which any two quorums overlap, which is why Riak's default of N = 3, R = W = 2 reads the latest committed write. They call a configuration with R + W ≤ N a partial quorum and ask the probability that a read started t seconds after a write commits sees the latest value, t-visibility. Dynamo-style systems keep writing after the put returns: the write quorum grows even after the operation returns, since coordinators send every request to all replicas but consider only the first R (W) responses. And they are inconsistent as a result of read and write message reordering, a product of message delays. Their model is WARS, named for four message delays: W from the coordinator to a replica carrying the write, A the acknowledgement back, R the read request out, S the response back.

The rule is local to one replica. A read is stale when all of the first R responses arrived at their replicas before the last committed write; for one replica, its response is stale if $r_{0} + w_{t} + t < w_{0}$ , where $w_{t}$ is the commit time and $w_{0}$ the delay of the write to it. The commit time is the W-th smallest of the sums of write and acknowledgement delay. The stage's lowest table is one such trial laid out replica by replica: . A write that is acknowledged by a fast replica leaves the slow ones behind, and a read that is fast can overtake the write on a slow one: that is all of the mechanism.

Claim

Dynamo is straightforward to reason about but difficult to analyse in a simple closed form, so PBS use a Monte Carlo, which takes only a few lines of code, and validate it on Cassandra: an average prediction RMSE of 0.28% over each t from 1 to 199 ms, with read repair disabled and only the first R responses considered, injecting exponentially distributed delays across 50,000 writes. They then predict the stale-read behaviour of production systems from fitted latencies. Three things are left open: whether their prediction holds on the protocol the Dynamo paper describes, whether the model is conservative where it says it is, and what failures do.

Hypotheses

E1a: a cluster configured to the model's assumptions agrees with the model in every cell. E1b: the model, as we read it, reproduces the numbers they published. E1c: each of three relaxations (the coordinator is a replica, read repair, a failed replica) moves the result as PBS say, or not. Verdict rules, written before any run, are in research/README.md.

Design

The cluster of this page, 7 nodes, N = 3, one key per trial, a put and reads at t ms after commit, and the model warsMonteCarlo, written from §5.1. The latencies are PBS's own fits: LNKD-SSD: 91.22% Pareto(0.235, 10), 8.78% exponential(1.66), LNKD-DISK writes: 38% Pareto(1.05, 1.51), 62% exponential(0.183), YMMR writes: 93.9% Pareto(3, 3.35), 6.1% exponential(0.0028) with 98.2% Pareto(1.5, 3.8), 1.8% exponential(0.0217) for the other three, and WAN, with 75 ms on remote messages. All independent and identically distributed, their assumption. Three seeds per arm.

Go deeper: Replication lag · Read your writes · Monte Carlo methods

24Research desk

E1a and E1b · Does the cluster match the model, and does the model match the paper?

E1a. Four latency models, three configurations (R, W) = (1,1), (1,2), (2,1), eleven times from 0 to 1000 ms: 132 cells, each with , against the model's one million samples. The tolerance is the larger of half a point and four standard errors of the difference.

The strict configurations, R + W > N, are a theorem and not an experiment: test.mjs runs 3,000 trials of each on each latency model and finds no stale read. The two simulations are, however, independent code. The model draws four numbers per replica; the cluster sends messages, applies versions with vector clocks, reconciles at the coordinator and counts the first R replies. That they agree to a fraction of a point across four very different latency shapes, including the 75 ms bimodal WAN, is the check that matters.

E1b. The model is only worth testing against if it is the PBS model. We compare it with four sets of published numbers: the probabilities right after commit, 97.4% for LNKD-SSD, 43.9% for LNKD-DISK, 89.3% for YMMR and 33% for WAN; the 24 t-visibilities at 99.9% of their Table 4; and the N sweep, 57.5% at N = 2 and 21.1% at N = 10 right after commit with 45.3 and 53.7 ms for 99.9%. All of it comes from the model with .

With exponential delays their Figure 4 gives 94% consistent right after the write and 99.9% after 1 ms when writes are fast and 41% and 65 ms when they are slow; the model reproduces both, and test.mjs checks it. Their headline trade-offs follow: 1.85 ms against 45.5 ms for 99.9% consistent reads, SSD against disk, and an 81.1% combined read and write latency improvement at the 99.9th percentile for a 202 ms window of inconsistency on YMMR, where setting R = 2 and W = 1 brings t-visibility to 202 ms from 1364 ms, and on LNKD-DISK a 99.9% t-visibility of 13.6 ms. In the model, as in the paper, the long tail of the write delay W, not the mean, sets how long a read can be stale.

Go deeper: Multi-seed reporting and run-to-run variance · Monte Carlo methods · Percentile latency

25Research desk

E1c · Where does the model stop being conservative?

The model's assumptions are stated with their direction. With WARS, data may be fresher than predicted, because overlapping writes lower the probability of inconsistency; a conservative assumption for read repair and Merkle tree exchange is that they never occur; and failures are left to the tail, since unless failures are common-case, they affect tail staleness probabilities a replica set with some failed nodes behaves like a smaller one, and modelling hinted handoff would be useful. Three relaxations, one at a time, each against the same model (research/README.md has the designs and verdict rules):

R1. The coordinator is a replica, as in Dynamo's server-driven mode; a write goes through a random node of the top N, a read through a random node of the seven, and a replica talking to itself takes no time. Hypothesis: the cluster is fresher than the model.

R2. Read repair. Background reads of the key every 5 ms (200 a second), repair on, one probe read at 20, 50, 100 or 200 ms. Hypothesis: repair removes staleness the model counts.

F. A failed replica. With probability 0.05 per key, one replica is down when the put is issued and returns after up to 200 ms. In the unknown arm nobody suspects it; in the known arm every coordinator does, so the write goes to a stand-in with a hint, and handoff runs every 250 ms. Hypotheses: unknown failures break the model, known ones do not.

Go deeper: Read your writes · Partition tolerance · Durability against availability

26Research desk

E2 · Does a closed form for versions bound a real cluster?

PBS also ask how many versions a read can be behind. A read's R replicas and a write's W replicas, if chosen at random, miss each other with probability

p_{s} = (R N - W) / (R N),

and a read is more than $k$ versions behind with probability $p_{s}^{k}$ when the last $k$ writes used independent random quorums: k-staleness, with probability 1 − p_s^k a read has a value committed within k versions of the latest. It comes from expanding prior work on probabilistic quorums to account for multi-version staleness [12], the cousin of k-quorums, which give deterministic guarantees of being within k versions of the most recent write [13], and it says that for expanding quorums, which Dynamo's are, the solution is an upper bound. The bound is the part nobody has measured on a cluster. For N = 3 and R = W = 1, $p_{s} = 2/3$ ; with N = 100 and R = W = 30 it is 1.88 × 10^-6, and test.mjs computes both.

Claim

For non-expanding quorums the closed form is exact; for expanding quorums it is an upper bound. Neither is tested in the paper, whose

k

analysis is a derivation.

Hypotheses

H2a: in a cluster whose writes reach exactly W random replicas and whose reads ask exactly R, the probability of being

d

or more versions behind is

p_{s}^{d}

. H2b: in the normal, expanding cluster it is at most

p_{s}^{d}

. Verdict rules in research/README.md.

Design

Six serial writes to one key (each issued when the last commits), then a read at t = 0; the share of reads

d \geq 1

to 5 versions behind. Five (N, R, W): (3,1,1), (3,1,2), (5,1,1), (5,2,2), (5,2,3). 120,000 trials in all per cell (three seeds). Expanding arms on LNKD-DISK and YMMR.

Go deeper: Quorum · Read your writes · Multi-seed reporting and run-to-run variance

27Research desk

E3 · Is an "add to cart" never lost?

Back to the sentence in §4.4: "an add to cart operation is never lost". It rests on the clocks. Preguiça and colleagues, analysing Dynamo, Cassandra and Riak, point at a weakness in them [8]. Version vectors with an entry per server cannot track causality among updates submitted to the same server, and Dynamo's, with one entry per replica node, fall into that category. The consequence, in their words: a last-writer-wins policy is in effect for concurrent updates handled by the same node, and one of them is lost. Their proposal, the dotted version vector, keeps information growing only with the servers that register updates, bounded by the replication degree.

The mechanism is on the stage as test.mjs runs it. Two clients read the same version and write through the same coordinator: the coordinator stamps the first with its next counter, and the second with the next again, so that the second's clock descends from the first, and the store drops the first as superseded. Through two different coordinators the same two writes are kept as siblings; with dotted version vectors they are kept at one coordinator too.

Claim

"An add to cart operation is never lost." (§4.4). Whether it is, with Dynamo's own clocks and the reconciliation it describes, is not measured in the paper.

Hypotheses

H3a: with Dynamo's clocks and the preferred coordinator, at least 2% of acknowledged adds are missing from the final cart with four clients. H3b: the loss grows with the number of clients. H3c: dotted version vectors lose none, in any run.

Design

C clients (2, 4 or 8) each make 12 adds to one cart: a get, a merge of the returned versions by union, one new item, a put with the context; exponential think time of mean 20 ms; LNKD-DISK latencies; (N, R, W) = (3, 2, 2); read repair on; no failures. When the clients finish, anti-entropy runs until the replicas agree and the cart is read from all of them. Clock in {Dynamo's, dotted version vector, last-write-wins} × coordinator in {preferred, random of the top N}. Thirty runs per cell, all reported.

The dotted version vector's losses are the surprising part. A trace of one run showed the cause: coordinator C stamped two concurrent writes with dots 7 and 8; a third client read replicas that had the version with dot 8 but not yet the one with dot 7, and wrote with a context saying "I have seen C up to 8", which, in the compact form, also covers 7. The version with dot 7, never seen by that client, was dropped. The dotted version vector's compactness assumes that a replica never holds a dot without its past, and Dynamo's replication, which sends each replica only the new version, does not guarantee that. Sending every replica the coordinator's whole sibling set restores it: in the 180 runs of that exploratory arm nothing was lost. This is the cause as found in one trace and confirmed by the control, and it is a lead about one implementation, not a statement about the dotted version vector in general.

Go deeper: Version vector · Last writer wins · CRDT · Multi-seed reporting and run-to-run variance

28Research desk

What this leaves open

The coordinator as a replica, at W > 1. R1 found the cluster staler for W = 1 in the first few milliseconds, by up to 56 points on a latency fit in which 94% of write delays are at least 3 ms. How the effect varies with W and with how often the read coordinator is itself a replica (three nodes of seven here) is a grid, and PBS's remark about R-1 and W-1 gives the prediction to compare it with.
Failure detection that lags. The failure arm has two extremes, nobody knows and everybody does. Real coordinators learn at different times (the paper's detector is local and the suspicion period is not given). A mixture, with a share of coordinators aware, would give the staleness as a function of detection time, which is the number an operator could set.
Dotted version vectors with partial replication. The cart loss through coordinator C needs a replica to hold a dot without its past. Whether other repair paths (anti-entropy, read repair, handoff) create the same state, and whether the fix is cheaper than shipping whole sibling sets, can be tested with the engine.
The bound's looseness. E2 shows the closed form is an upper bound, not how far it is. A tighter bound that uses the write-delay distribution, which PBS's Monte Carlo already does in time, could be checked against the cluster.
Hot keys and overlapping writes. PBS say overlapping writes make data fresher than predicted; E1c did not test it, and the Dynamo paper says concurrent writers are what produce divergent versions. A writer rate on one key, with E3's carts, is the experiment that would join them.

29Research desk

What was read, what was not, and how to check it

The primary source [1] was read in full: every section, table and figure caption (the figures' curves were not readable from the extracted text). The sandbox could not reach allthingsdistributed.com, amazon.science, the ACM library or arxiv.org, so the paper was read from a copy in the public papers-we-love repository, fetched from raw.githubusercontent.com, and every quote in the fact ledger was checked against the text extracted from it (ignoring whitespace, case and the hyphens the extraction loses at line ends). The copy's footer reads "SOSP 2007, Oct., 2004", a template slip. The two papers the research desk stands on, [11] and [8], were read in full as arXiv v1 from the Cornell mirror on Google Cloud Storage, as PDF text and not LaTeX, which is why Table 4 was read from the page layout.

Cited here only for what the sources say of them, and not fetched: [7], [5], [9], [6], [4], [10], [13], [12], [3], [2]. Later literature on Dynamo-style stores that could not be reached is not cited, and nothing here describes the current behaviour of Cassandra, Riak or DynamoDB; where PBS describe their defaults, that is quoted from PBS, as of 2012. Dynamo's relation to the other canon topics on this site is by link, not by claim: the Lamport clocks dissection covers logical clocks and the Raft dissection covers the opposite design choice, a leader and a log.

Everything is reproducible from engine.js (the cluster and the model), test.mjs (the truth checks), research/README.md (the pre-registration, written before the experiments in research/run.mjs were run), research/summarise.mjs (which applies the verdict rules and writes the result paragraphs on this page) and research/LAB-NOTES.md, which records the engine bugs found and the one change made after a result. The visual grammar follows Bycroft's tensor visualisation.

Go deeper: Multi-seed reporting and run-to-run variance · Seeds and the limits of determinism · Replication · Dynamo: always writeable

References

DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P. and Vogels, W. (2007). Dynamo: Amazon's Highly Available Key-value Store. Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP '07), Stevenson, WA The subject of this page, read in full (16 pages, body, tables, figure captions and references) from the copy committed in papers-we-love/papers-we-love (datastores/dynamo-amazons-highly-available-key-value-store.pdf, fetched from raw.githubusercontent.com); allthingsdistributed.com, amazon.science and the ACM library could not be reached from the sandbox. Every quote in the fact ledger was checked against the extracted text of that file. This copy's footer reads 'SOSP 2007, Oct., 2004', a template slip.
Thomas, R. H. (1979). A majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems 4(2), 180-209 Cited by the Dynamo paper as [22], for the 'last write wins' policy. Not fetched.
Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J. and Hauser, C. H. (1995). Managing update conflicts in Bayou, a weakly connected replicated storage system. Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), 172-182 Cited by the Dynamo paper as [21], for application-level conflict resolution and eventual consistency. Not fetched.
Gray, J., Helland, P., O'Neil, P. and Shasha, D. (1996). The dangers of replication and a solution. Proceedings of the 1996 ACM SIGMOD Conference, 173-182 Cited by the Dynamo paper as [7], for the claim that strongly consistent replication limits scalability and availability. Not fetched.
Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M. and Lewin, D. (1997). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the 29th ACM Symposium on Theory of Computing (STOC '97), 654-663 Cited by the Dynamo paper as [10] for the partitioning scheme. Not fetched; the next canon entry of this section covers it. Nothing is claimed here about its content beyond what the Dynamo paper says of it.
Stoica, I., Morris, R., Karger, D., Kaashoek, M. F. and Balakrishnan, H. (2001). Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM 2001, 149-160 Cited by the Dynamo paper as [20], with Pastry, as the multi-hop designs Dynamo avoids. Not fetched.
Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM 21(7), 558-565 Cited by the Dynamo paper as [12] for object versioning and vector clocks. Not re-read for this page; the sibling dissection on this site, Anatomy of Lamport Clocks, covers it.
Preguiça, N., Baquero, C., Almeida, P. S., Fonte, V. and Gonçalves, R. (2010). Dotted Version Vectors: Logical Clocks for Optimistic Replication. arXiv:1011.5808v1 Read in full as arXiv v1 (12 pages) from the Cornell arXiv mirror. It analyses the causality tracking of Dynamo, Cassandra and Riak, and proposes the dotted version vector that the lost-add experiment (E3) compares against Dynamo's clocks.
Merkle, R. (1988). A digital signature based on a conventional encryption function. Proceedings of CRYPTO '87, Springer, 369-378 Cited by the Dynamo paper as [13] for the hash tree. Not fetched; the page uses the tree as Dynamo §4.7 describes it.
Welsh, M., Culler, D. and Brewer, E. (2001). SEDA: an architecture for well-conditioned, scalable internet services. Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), 230-243 Cited by the Dynamo paper as [24], for the staged event-driven structure of a node. Not fetched.
Bailis, P., Venkataraman, S., Franklin, M. J., Hellerstein, J. M. and Stoica, I. (2012). Probabilistically Bounded Staleness for Practical Partial Quorums. Proceedings of the VLDB Endowment 5(8), 776-787 (arXiv:1204.6082v1) Read in full as arXiv v1 (12 pages) from the Cornell arXiv mirror on Google Cloud Storage; arxiv.org itself could not be reached from the sandbox, so the quotes come from the PDF text, not the LaTeX. The model whose predictions the research desk tests. Its Table 3 fits and Table 4 are reproduced in E1b; its closed form is tested in E2.
Malkhi, D., Reiter, M. K., Wool, A. and Wright, R. N. (2001). Probabilistic quorum systems. Information and Computation 170(2), 184-206 The PBS paper's reference [49], the probabilistic quorum systems it extends. Not fetched; the PBS paper is the only source for what is said of it here.
Aiyer, A. S., Alvisi, L. and Bazzi, R. A. (2005). On the availability of non-strict quorum systems. DISC 2005, 48-62 Cited by the PBS paper as [10] for k-quorums and the bound it quotes for N = 100. Not fetched; the page uses it only as the PBS paper does.

Fact ledger

Every number from the literature on this page, with the sentence it comes from. Hover any underlined number in the text to see its entry.

Value	What	Source
an eventually consistent store can run demanding production applications	the paper's claimed contribution	[1] §1 It demonstrates that an eventually-consistent storage system can be used in production with demanding applications.
always readable and writable	the shopping cart requirement	[1] §1 customers should be able to view and add items to their shopping cart even if disks are failing, network routes are flapping, or data centers are being destroyed by tornados.
consistent hashing, object versioning, quorum-like, replica synchronisation, gossip	the techniques combined	[1] §1 Data is partitioned and replicated using consistent hashing [10], and consistency is facilitated by object versioning [12].
the first N healthy nodes	whom operations contact	[1] §4.5 Read and write operations involve the first N healthy nodes in the preference list, skipping over those that are down or inaccessible.
tens of millions of customers, tens of thousands of servers	platform scale	[1] §1 Amazon runs a world-wide e-commerce platform that serves tens of millions customers at peak times using tens of thousands of servers located in many data centers around the world.
the standard mode of operation	failure	[1] §1 Dealing with failures in an infrastructure comprised of millions of components is our standard mode of operation
well over 3 million	shopping cart checkouts in a day	[1] §1 served tens of millions requests that resulted in well over 3 million checkouts in a single day
get and put by key, no multi-item operations	the query model	[1] §2.1 No operations span multiple data items and there is no need for relational schema.
usually under 1 MB	object size	[1] §2.1 Dynamo targets applications that need to store objects that are relatively small (usually less than 1 MB).
none; single-key updates only	isolation	[1] §2.1 Dynamo does not provide any isolation guarantees and permits only single key updates.
none; the environment is assumed non-hostile	security	[1] §2.1 Its operation environment is assumed to be non-hostile and there are no security related requirements such as authentication and authorization.
up to hundreds of storage hosts	design scale	[1] §2.1 its initial design targets a scale of up to hundreds of storage hosts.
over 150	services behind one page	[1] §2.2 a page request to one of the e-commerce sites typically requires the rendering engine to construct its response by sending requests to over 150 services.
300 ms for 99.9% of requests at 500 requests per second	an example service level agreement	[1] §2.2 provide a response within 300ms for 99.9% of its requests for a peak client load of 500 requests per second.
the 99.9th percentile	where SLAs are measured	[1] §2.2 at Amazon, SLAs are expressed and measured at the 99.9th percentile of the distribution.
an "always writeable" data store	the design space	[1] §2.3 Dynamo targets the design space of an “always writeable” data store
at read time	where conflict resolution happens	[1] §2.3 This requirement forces us to push the complexity of conflict resolution to the reads in order to ensure that writes are never rejected.
the application, or last write wins	who resolves conflicts	[1] §2.3 the application that maintains customer shopping carts can choose to “merge” the conflicting versions and return a single unified shopping cart.
eventual consistency	the consistency model	[1] §2.3 Dynamo is designed to be an eventually consistent data store; that is all updates reach all replicas eventually.
application-level conflict resolution	Bayou	[1] §3.2 Bayou allows application level resolution.
limited in scalability and availability	strongly consistent replication	[1] §3.2 these systems are limited in scalability and availability [7].
incremental scalability	principle 1	[1] §2.3 Incremental scalability: Dynamo should be able to scale out one storage host (henceforth, referred to as “node”) at a time, with minimal impact on both operators of the system and the system itself.
symmetry	principle 2	[1] §2.3 Symmetry: Every node in Dynamo should have the same set of responsibilities as its peers; there should be no distinguished node or nodes that take special roles or extra set of responsibilities.
decentralization	principle 3	[1] §2.3 Decentralization: An extension of symmetry, the design should favor decentralized peer-to-peer techniques over centralized control.
heterogeneity	principle 4	[1] §2.3 Heterogeneity: The system needs to be able to exploit heterogeneity in the infrastructure it runs on.
MD5, 128 bits	the hash	[1] §4.1 It applies a MD5 hash on the key to generate a 128-bit identifier, which is used to determine the storage nodes that are responsible for serving the key.
the hash output range as a circle	the ring	[1] §4.2 the output range of a hash function is treated as a fixed circular space or “ring”
a random position on the ring	a node's place	[1] §4.2 Each node in the system is assigned a random value within this space which represents its “position” on the ring.
the first node clockwise	a key's node	[1] §4.2 Each data item identified by a key is assigned to a node by hashing the data item’s key to yield its position on the ring, and then walking the ring clockwise to find the first node with a position larger than the item’s position.
only the immediate neighbours	what a join affects	[1] §4.2 departure or arrival of a node only affects its immediate neighbors and other nodes remain unaffected.
stores three ranges	Figure 2's node D	[1] §4.3 Node D will store the keys that fall in the ranges (A, B], (B, C], and (C, D].
non-uniform load; ignores heterogeneity	problems with one point per node	[1] §4.2 the random position assignment of each node on the ring leads to non-uniform data and load distribution.
several points per node	virtual nodes	[1] §4.2 instead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring.
the positions a node is given	tokens	[1] §4.2 when a new node is added to the system, it is assigned multiple positions (henceforth, “tokens”) in the ring.
a failed node's load is dispersed	virtual node advantage 1	[1] §4.2 If a node becomes unavailable (due to failures or routine maintenance), the load handled by this node is evenly dispersed across the remaining available nodes.
N, set per instance	replication factor	[1] §4.3 Each data item is replicated at N hosts, where N is a parameter configured “per-instance”.
the N-1 clockwise successors	where replicas go	[1] §4.3 the coordinator replicates these keys at the N-1 clockwise successor nodes in the ring.
the nodes responsible for a key	the preference list	[1] §4.3 The list of nodes that is responsible for storing a particular key is called the preference list.
more than N	its length	[1] §4.3 To account for node failures, preference list contains more than N nodes.
skip positions so nodes are distinct	its construction	[1] §4.3 the preference list for a key is constructed by skipping positions in the ring to ensure that the list contains only distinct physical nodes.
T random tokens per node, partition by token value	Strategy 1	[1] §6.2 Strategy 1: T random tokens per node and partition by token value: This was the initial strategy deployed in production
slow bootstrapping, Merkle recomputation, no easy snapshot	what went wrong	[1] §6.2 during busy shopping season, when the nodes are handling millions of requests a day, the bootstrapping has taken almost a day to complete.
T random tokens per node, equal-sized partitions	Strategy 2	[1] §6.2 Strategy 2: T random tokens per node and equal sized partitions: In this strategy, the hash space is divided into Q equally sized partitions/ranges and each node is assigned T random tokens.
Q/S tokens per node, equal-sized partitions	Strategy 3	[1] §6.2 Strategy 3: Q/S tokens per node, equal-sized partitions: Similar to strategy 2, this strategy divides the hash space into Q equally sized partitions and the placement of partition is decoupled from the partitioning scheme.
much larger than N and S*T	Q	[1] §6.2 Q is usually set such that Q >> N and Q >> S*T, where S is the number of nodes in the system.
mean load over the hottest node's load	load-balancing efficiency	[1] §6.2 Load balancing efficiency is defined as the ratio of average number of requests served by each node to the maximum number of requests served by the hottest node.
S = 30, N = 3	the experiment	[1] §6.2 The efficiency of these three strategies is evaluated for a system with S=30 and N=3.
Strategy 3 best, Strategy 2 worst	the ranking	[1] §6.2 strategy 3 achieves the best load balancing efficiency and strategy 2 has the worst load balancing efficiency.
three orders of magnitude less membership data	Strategy 3 against 1	[1] §6.2 Strategy 3 achieves better efficiency and reduces the size of membership information maintained at each node by three orders of magnitude.
coordination on membership change	the price of Strategy 3	[1] §6.2 The disadvantage of strategy 3 is that changing the node membership requires coordination in order to preserve the properties required of the assignment.
get() and put()	the interface	[1] §4.1 it exposes two operations: get() and put().
one object, or a list of conflicting versions, with a context	what get returns	[1] §4.1 The get(key) operation locates the object replicas associated with the key in the storage system and returns a single object or a list of objects with conflicting versions along with a context.
the key, a context and the object	what put takes	[1] §4.1 The put(key, context, object) operation determines where the replicas of the object should be placed based on the associated key, and writes the replicas to disk.
opaque to the caller; carries the version	the context	[1] §4.1 The context encodes system metadata about the object that is opaque to the caller and includes information such as the version of the object.
any storage node	who accepts requests	[1] §4.5 Any storage node in Dynamo is eligible to receive client get and put operations for any key.
a load balancer, or a partition-aware client	routing a request	[1] §4.5 (1) route its request through a generic load balancer that will select a node based on load information, or (2) use a partition-aware client library that routes requests directly to the appropriate coordinator nodes.
typically the first of the top N	the coordinator	[1] §4.5 A node handling a read or write operation is known as the coordinator. Typically, this is the first among the top N nodes in the preference list.
forwarded to the first of the top N	a request at a non-replica	[1] §4.5 that node will forward the request to the first among the top N nodes in the preference list.
the minimum number of nodes for a read	R	[1] §4.5 R is the minimum number of nodes that must participate in a successful read operation.
the minimum number of nodes for a write	W	[1] §4.5 W is the minimum number of nodes that must participate in a successful write operation.
R + W > N	the quorum rule	[1] §4.5 Setting R and W such that R + W > N yields a quorum-like system.
the slowest of R (or W) replicas	latency of an operation	[1] §4.5 the latency of a get (or put) operation is dictated by the slowest of the R (or W) replicas.
any node	who coordinates a read (§6.4)	[1] §6.4 Any Dynamo node can act as a coordinator for a read request.
a node of the preference list	who coordinates a write (§6.4)	[1] §6.4 Write requests on the other hand will be coordinated by a node in the key’s current preference list.
zero-hop: every node can route directly	routing	[1] §3.3 Dynamo can be characterized as a zero-hop DHT, where each node maintains enough routing information locally to route a request to the appropriate node directly.
multi-hop routing raises tail latency	why not Chord or Pastry	[1] §3.3 multi-hop routing increases variability in response times, thereby increasing the latency at higher percentiles.
stamp, write locally, send to N, W-1 replies	a put	[1] §4.5 Upon receiving a put() request for a key, the coordinator generates the vector clock for the new version and writes the new version locally. The coordinator then sends the new version (along with the new vector clock) to the N highest-ranked reachable nodes. If at least W-1 nodes respond then the write is considered successful.
accepted if any one node has written it	W = 1	[1] §4.6 Applications that need the highest level of availability can set W to 1, which ensures that a write is accepted as long as a single node in the system has durably written the key it to its local store.
risk of inconsistency and a durability window	low W and R	[1] §6 low values of W and R can increase the risk of inconsistency as write requests are deemed successful and returned to the clients even if they are not processed by a majority of the replicas.
a higher W	what production uses	[1] §4.6 in practice, most Amazon services in production set a higher W to meet the desired level of durability.
a new, immutable version	a modification	[1] §4.4 Dynamo treats the result of each modification as a new and immutable version of the data.
ask the N, wait for R	a get	[1] §4.5 for a get() request, the coordinator requests all existing versions of data for that key from the N highest-ranked reachable nodes in the preference list for that key, and then waits for R responses before returning the result to the client.
all causally unrelated versions	what a get returns	[1] §4.5 If the coordinator ends up gathering multiple versions of the data, it returns all the versions it deems to be causally unrelated.
repair stale replicas opportunistically	read repair	[1] §5 This process is called read repair because it repairs replicas that have missed a recent update at an opportunistic time and relieves the anti-entropy protocol from having to do it.
a list of (node, counter) pairs	a vector clock	[1] §4.4 A vector clock is effectively a list of (node, counter) pairs.
counters less than or equal	the ancestor test	[1] §4.4 If the counters on the first object’s clock are less-than-or-equal to all of the nodes in the second clock, then the first is an ancestor of the second and can be forgotten.
the client passes the context from a read	updating	[1] §4.4 when a client wishes to update an object, it must specify which version it is updating. This is done by passing the context it obtained from an earlier read operation
[(Sx, 1)]	D1's clock	[1] §4.4 The system now has the object D1 and its associated clock [(Sx, 1)].
[(Sx, 2)]	D2's clock	[1] §4.4 The system now also has object D2 and its associated clock [(Sx, 2)].
[(Sx, 2), (Sy, 1)]	D3's clock	[1] §4.4 The system now has data D3 and its associated clock [(Sx, 2), (Sy, 1)].
[(Sx, 2), (Sz, 1)]	D4's clock	[1] §4.4 The system now has D4 (descendant of D2) whose version clock is [(Sx, 2), (Sz, 1)].
[(Sx, 2), (Sy, 1), (Sz, 1)]	the read context before D5	[1] §4.4 The read's context is a summary of the clocks of D3 and D4, namely [(Sx, 2), (Sy, 1), (Sz, 1)].
[(Sx, 3), (Sy, 1), (Sz, 1)]	D5's clock	[1] §4.4 The new data D5 will have the following clock: [(Sx, 3), (Sy, 1), (Sz, 1)].
at a threshold of, say, 10 pairs the oldest is dropped	clock truncation	[1] §4.4 When the number of (node, counter) pairs in the vector clock reaches a threshold (say 10), the oldest pair is removed from the clock.
"has not surfaced"	truncation in production	[1] §4.4 this problem has not surfaced in production and therefore this issue has not been thoroughly investigated.
the system picks the descendant	syntactic reconciliation	[1] §4.4 Most of the time, new versions subsume the previous version(s), and the system itself can determine the authoritative version (syntactic reconciliation).
the client merges branches	semantic reconciliation	[1] §4.4 the client must perform the reconciliation in order to collapse multiple branches of data evolution back into one (semantic reconciliation).
"an add to cart operation is never lost"	the cart guarantee	[1] §4.4 Using this reconciliation mechanism, an “add to cart” operation is never lost. However, deleted items can resurface.
sloppy	the quorum	[1] §4.6 it does not enforce strict quorum membership and instead it uses a “sloppy quorum”; all read and write operations are performed on the first N healthy nodes from the preference list, which may not always be the first N nodes encountered while walking the consistent hashing ring.
purely local	failure detection	[1] §4.8.3 node A may consider node B failed if node B does not respond to node A’s messages (even if B is responsive to node C's messages).
A periodically retries B	after a failure	[1] §4.8.3 A periodically retries B to check for the latter's recovery.
carries the intended recipient	a hinted replica	[1] §4.6 The replica sent to D will have a hint in its metadata that suggests which node was the intended recipient of the replica (in this case A).
a separate local database, scanned periodically	where hints live	[1] §4.6 Nodes that receive hinted replicas will keep them in a separate local database that is scanned periodically.
the preference list spans several	data centres	[1] §4.6 the preference list of a key is constructed such that the storage nodes are spread across multiple data centers.
on recovery; then delete	delivery	[1] §4.6 Upon detecting that A has recovered, D will attempt to deliver the replica to A. Once the transfer succeeds, D may delete the object from its local store without decreasing the total number of replicas in the system.
hinted replicas may vanish first	when hints fail	[1] §4.7 Hinted handoff works best if the system membership churn is low and node failures are transient.
anti-entropy	permanent failures	[1] §4.7 Dynamo implements an anti-entropy (replica synchronization) protocol to keep the replicas synchronized.
leaves hash keys; parents hash children	a Merkle tree	[1] §4.7 A Merkle tree is a hash tree where leaves are hashes of the values of individual keys. Parent nodes higher in the tree are hashes of their respective children.
nothing to synchronise	equal roots	[1] §4.7 if the hash values of the root of two trees are equal, then the values of the leaf nodes in the tree are equal and the nodes require no synchronization.
per virtual node	one tree per key range	[1] §4.7 Each node maintains a separate Merkle tree for each key range (the set of keys covered by a virtual node) it hosts.
trees are recomputed on membership change	the drawback	[1] §4.7 The disadvantage with this scheme is that many key ranges change when a node joins or leaves the system thereby requiring the tree(s) to be recalculated.
an explicit administrator action	joining and leaving	[1] §4.8.1 it was deemed appropriate to use an explicit mechanism to initiate the addition and removal of nodes from a Dynamo ring.
a random peer every second	membership gossip	[1] §4.8.1 Each node contacts a peer chosen at random every second and the two nodes efficiently reconcile their persisted membership change histories.
nodes known to all	seeds	[1] §4.8.2 Seeds are nodes that are discovered via an external mechanism and are known to all nodes.
dropped	a global view of failures	[1] §4.8.3 Later it was determined that the explicit node join and leave methods obviates the need for a global view of failure state.
random tokens	a new node	[1] §4.9 When a new node (say X) is added into the system, it gets assigned a number of tokens that are randomly scattered on the ring.
takes (F, G], (G, A] and (A, X]	X between A and B	[1] §4.9 When X is added to the system, it is in charge of storing keys in the ranges (F, G], (G, A] and (A, X].
the old holders offer, X confirms	a join's transfers	[1] §4.9 Therefore, nodes B, C, and D will offer to and upon confirmation from X transfer the appropriate set of keys.
full membership works for a couple of hundred nodes	the limit	[1] §6.6 This model works well for a system that contains couple of hundreds of nodes.
coordination, membership and failure detection, persistence	a node's software	[1] §5 each storage node has three main software components: request coordination, membership and failure detection, and a local persistence engine.
Java	language	[1] §5 All these components are implemented in Java.
event-driven, staged like SEDA	the substrate	[1] §5 The request coordination component is built on top of an event-driven messaging substrate where the message processing pipeline is split into multiple stages similar to the SEDA architecture [24].
one per client request	state machines	[1] §5 Each client request results in the creation of a state machine on the node that received the client request.
five states	the read state machine	[1] §5 (i) send read requests to the nodes, (ii) wait for minimum number of required responses, (iii) if too few replies were received within a given time bound, fail the request, (iv) otherwise gather all the data versions and determine the ones to be returned and (v) if versioning is enabled, perform syntactic reconciliation and generate an opaque write context that contains the vector clock that subsumes all the remaining versions.
the node that replied fastest to the previous read	who coordinates a write	[1] §5 the coordinator for a write is chosen to be the node that replied fastest to the previous read operation which is stored in the context information of the request.
read-your-writes, and a better tail	why	[1] §5 This optimization enables us to pick the node that has the data that was read by the preceding read operation thereby increasing the chances of getting “read-your-writes” consistency.
admission control by slices	background tasks	[1] §6.5 Each of the background tasks uses this controller to reserve runtime slices of the resource (e.g. database), shared across all background tasks.
BDB Transactional Data Store	storage engines (1)	[1] §5 Engines that are in use are Berkeley Database (BDB) Transactional Data Store
BDB Java Edition, MySQL, in-memory buffer	storage engines (2)	[1] §5 BDB Java Edition, MySQL, and an in-memory buffer with persistent backing store.
BDB Transactional Data Store	the usual engine	[1] §5 The majority of Dynamo’s production instances use BDB Transactional Data Store.
(3,2,2), a couple of hundred nodes	what the measurements ran on	[1] §6 All the measurements presented in this section were taken on a live system operating with a configuration of (3,2,2) and running a couple hundred nodes with homogenous hardware configurations.
(3, 2, 2)	the common configuration	[1] §6 The common (N,R,W) configuration used by several instances of Dynamo is (3,2,2).
3	typical N	[1] §6 A typical value of N used by Dynamo’s users is 3.
R = 1, W = N	a high-performance read engine	[1] §6 Typically, these services have a high read request rate and only a small number of updates. In this configuration, typically R is set to be 1 and W to be N.
absolute latencies, request rates, outage lengths	what the authors withhold	[1] §1 protecting Amazon’s business interests require us to reduce some level of detail
99.9% within 300 ms	the typical SLA	[1] §6.1 A typical SLA required of services that use Dynamo is that 99.9% of the read and write requests execute within 300ms.
around 200 ms, an order of magnitude higher	the 99.9th against the mean	[1] §6.1 the 99.9th percentile latencies are around 200 ms and are an order of magnitude higher than the averages.
99.9th percentile down 5x with 1,000 objects	write buffering	[1] §6.1 This optimization has resulted in lowering the 99.9th percentile latency by a factor of 5 during peak traffic even for a very small buffer of a thousand objects
one replica does a durable write	the durability patch	[1] §6.1 the write operation is refined to have the coordinator choose one out of the N replicas to perform a “durable write”.
99.9995% of requests, no data loss	delivered availability	[1] §6.6 applications have received successful responses (without timing out) for 99.9995% of its requests and no data loss event has occurred to date.
99.94% one; 0.00057% two; 0.00047% three; 0.00009% four	divergent versions seen by the cart service in 24 hours	[1] §6.3 99.94% of requests saw exactly one version; 0.00057% of requests saw 2 versions; 0.00047% of requests saw 3 versions and 0.00009% of requests saw 4 versions.
concurrent writers, mostly robots	what causes divergence	[1] §6.3 the increase in the number of divergent versions is contributed not by failures but due to the increase in number of concurrent writers.
30 days	Figure 4's period (text)	[1] §6.1 Figure 4 shows the average and 99.9th percentile latencies of Dynamo’s read and write operations during a period of 30 days.
the past year	how long in use (§1)	[1] §1 In the past year, Dynamo has been the underlying storage technology for a number of the core services in Amazon’s ecommerce platform.
the past two years	how long in use (§6.6)	[1] §6.6 Many Amazon internal services have used Dynamo for the past two years
within 15% of the average	"in balance"	[1] §6.2 a node is considered to be “in-balance”, if the node’s request load deviates from the average load by a value a less than a certain threshold (here 15%).
about 20% at low load, close to 10% at high	imbalance against load	[1] §6.2 during low loads the imbalance ratio is as high as 20% and during high loads it is close to 10%.
clients poll membership every 10 seconds	client-driven coordination	[1] §6.4 Currently clients poll a random Dynamo node every 10 seconds for membership updates.
30 ms at the 99.9th percentile; 3 to 4 ms on average	what it saves	[1] §6.4 the client-driven coordination approach reduces the latencies by at least 30 milliseconds for 99.9th percentile latencies and decreases the average by 3 to 4 milliseconds.
a read or write to R or W nodes behaves like R-1 or W-1	local replicas	[11] §4.2 a read or write to R or W nodes behaves like a read or write to R − 1 or W − 1 nodes.
up to 10 seconds	client-driven staleness	[1] §6.4 However, in the worst case the client can be exposed to stale membership for duration of 10 seconds.
immediate when the table looks stale	client refresh	[1] §6.4 if the client detects its membership table is stale (for instance, when some members are unreachable), it will immediately refresh its membership information.
N=3, R=W=1	Cassandra default	[11] §2.3 Cassandra defaults to N =3, R=W =1 [4].
N=3, R=W=1 for low latency	LinkedIn Voldemort	[11] §2.3 For applications requiring “very low latency and high availability,” LinkedIn deploys Voldemort with N =3, R=W =1.
any two quorums overlap	strict quorum	[11] §2.1 Informally, a strict quorum system is a quorum system with the property that any two quorums (sets) in the quorum system overlap (have non-empty intersection).
N=3, R=W=2	Riak default	[11] §2.3 Riak defaults to N =3, R=W =2 [14, 15].
R + W <= N	partial quorum	[11] §1.1 given N replicas and read and write quorum sizes R and W, partial quorums imply R+W ≤N .
a read t after commit sees the latest value	t-visibility	[11] §3.4 t-visibility is the probability that a read operation, starting t seconds after a write commits, will observe the latest value of a data item.
writes keep propagating after commit	Dynamo-style quorums expand	[11] §2.2 in Dynamo-style partial quorums, the write quorum size increases even after the operation returns, growing via anti-entropy [21].
the first R (W) responses	what a coordinator waits for	[11] §2.2 Coordinators send all requests to all replicas but consider only the first R (W) responses.
four message delays: W, A, R, S	WARS	[11] §4.1 Dynamo-style quorum systems are inconsistent as a result of read and write message reordering, a product of message delays.
all first R responses arrived before the write	when a read is stale	[11] §4.1 reads are stale when all of the first R responses to the read request arrived at their replicas before the last (committed) write request.
r0 + wt + t < w0	a replica's response is stale if	[11] §4.1 a single replica’s response is stale if r0 + wt + t < w0 for r0 drawn from R and w0 drawn from W.
the Wth smallest W+A	commit time	[11] §5.1 compute wt, the W th smallest value of {W[i] + A[i], i ∈ [0, N )}
hard to analyse	WARS and closed forms	[11] §4.1 Dynamo is straightforward to reason about and program but is difficult to analyze in a simple closed form.
a few lines of code	the Monte Carlo	[11] §5.1 This requires only a few lines of code.
Cassandra, 50,000 writes, RMSE 0.28%	the validation	[11] §5.2 Our average t-visibility prediction RMSE was 0.28% (std. dev. 0.05%, max. 0.53%) for each t ∈{1,. . . ,199} ms.
read repair disabled; first R responses only	how they validated	[11] §5.2 We modified Cassandra to profile WARS latencies, disabled read repair (as it is external to WARS), and, for reads, only considered the first R responses
exponential W: 20, 10, 5 ms; A=R=S: 10, 5, 2 ms	their injected latencies	[11] §5.2 We injected each combination of exponentially distributed W = λ ∈ {0.05, 0.1, 0.2} (means 20ms, 10ms and 5ms) and A=R=S = λ ∈ {0.1, 0.2, 0.5} (means 10ms, 5ms and 2ms) across 50,000 writes.
91.22% Pareto(0.235, 10); 8.78% Exponential(1.66)	LNKD-SSD	[11] Table 3 91.22%: Pareto, xm = .235, α = 10 8.78%: Exponential, λ = 1.66
38% Pareto(1.05, 1.51); 62% Exponential(0.183)	LNKD-DISK, W	[11] Table 3 38%: Pareto, xm = 1.05, α = 1.51 62%: Exponential, λ = .183
93.9% Pareto(3, 3.35); 6.1% Exponential(0.0028)	YMMR, W	[11] Table 3 93.9%: Pareto, xm = 3, α = 3.35 6.1%: Exponential, λ = .0028
98.2% Pareto(1.5, 3.8); 1.8% Exponential(0.0217)	YMMR, A = R = S	[11] Table 3 98.2%: Pareto, xm = 1.5, α = 3.8 1.8%: Exponential, λ = .0217
75 ms on remote messages, plus LNKD-DISK	WAN	[11] §5.5 We delay remote messages by 75ms and apply LNKD-DISK delays once the command reaches a remote data center
independent and identically distributed	the assumption behind their fits	[11] §5.5 we assume that each latency distribution is independently, identically distributed (IID).
97.4%	LNKD-SSD right after commit	[11] §5.6 Immediately after write commit, LNKD-SSD had a 97.4% probability of consistent reads
43.9%; 92.5% ten ms later	LNKD-DISK right after commit	[11] §5.6 immediately after write commit, LNKD-DISK had only a 43.9% probability of consistent reads and, ten ms later, only a 92.5% probability.
89.3%; 99.9% at 1364 ms	YMMR right after commit	[11] §5.6 Immediately after commit, YMMR had a 89.3% chance of consistency.
33%	WAN right after commit	[11] §5.6 (33% chance immediately after commit)
t-visibility at p_st = .001, N = 3	Table 4	[11] Table 4 t-visibility for pst = .001 (99.9% probability of consistency for 50, 000 reads and writes)
57.5% and 21.1% right after commit	LNKD-DISK, N = 2 and 10, R = W = 1	[11] §5.7 With 2 replicas, LNKD-DISK has a 57.5% probability of consistent reads immediately after commit but only a 21.1% probability with 10 replicas.
45.3 ms (N=2) to 53.7 ms (N=10)	LNKD-DISK, 99.9% t-visibility	[11] §5.7 the t-visibility at 99.9% probability of consistency ranges from 45.3ms for 2 replicas to 53.7ms for 10 replicas.
94% at once, 99.9% after 1 ms	Figure 4, fast writes	[11] §5.3 we observe a 94% chance of consistency immediately after the write and 99.9% chance after 1ms.
41% at once, 99.9% after 65 ms	Figure 4, slow writes	[11] §5.3 we observe a 41% chance of consistency immediately after write and a 99.9% chance of consistency only after 65ms.
1.85 ms against 45.5 ms for 99.9%	SSD against disk	[11] §1.2 1.85ms versus 45.5ms wait time for a 99.9% probability of consistent reads
81.1% lower latency for a 202 ms window	the trade	[11] §1.2 we observe an 81.1% combined read and write latency improvement at the 99.9th percentile (230 to 43.3ms) for a 202ms window of inconsistency (99.9% probability consistent reads).
202 ms	YMMR, R=2, W=1	[11] §5.6 setting R=2 and W =1 reduces t-visibility to 202ms
1364 ms after commit	YMMR's 99.9%	[11] §5.6 reached a 99.9% probability of consistency 1364 ms after commit.
13.6 ms	LNKD-DISK, R=2, W=1	[11] §5.6 A 99.9% consistent t-visibility of 13.6ms reduces LNKD-DISK read and write latencies by 16.5% (2.48ms).
1M reads and writes	Table 4, the sample size again	[11] Table 4 across R and W , N =3 (1M reads and writes).
data may be fresher than predicted	overlapping writes	[11] §4.2 with WARS, data may be fresher than predicted.
lower the probability of inconsistency	overlapping writes	[11] §4.2 If multiple writes overlap (that is, have overlapping periods where they are in-flight but are not committed) the probability of inconsistency decreases.
assumed never to occur	read repair and Merkle trees	[11] §4.2 A conservative assumption for read repair and Merkle tree exchange is that they never occur.
they appear as latency spikes	failures and the tail	[11] §6 Unless failures are common-case, they affect tail staleness probabilities (which appear as latency spikes in WARS).
a set with F failed nodes behaves like N - F	failures	[11] §6 If they are independent, a replica set of N nodes with F failed nodes behaves like an N − F replica set.
left for future work	hinted handoff	[11] §6 Modeling recovery semantics such as hinted handoff [20, Section 4.6] would also be useful.
at least one value within k versions of the latest committed	k-staleness	[11] §3.1 if, with probability 1 − psk , at least one value in any read quorum has been committed within k versions of the latest committed version when the read begins.
extended to multi-version staleness	probabilistic quorums	[11] §1.2 we answer these questions by expanding prior work on probabilistic quorums [49, 51] to account for multi-version staleness
deterministic guarantees of being within k versions	k-quorums	[11] §2.1 k-quorum systems provide deterministic guarantees that a partial quorum system will return values that are within k versions of the most recent write [10].
the closed form is an upper bound	expanding quorums	[11] §3.1 For expanding partial quorum systems, this solution is an upper bound on the probability of staleness.
1.88e-6 at N=100, R=W=30; "0.6" at N=3, R=W=1	non-intersection probability	[11] §2.1 With N = 100, R = W = 30, ps = 1.88 × 10−6 [10]. However, with N = 3, R = W = 1, ps = 0.6.
N=3, R=W=1: 0.5, 0.703, >0.868, >0.98; N=3, R=1, W=2: 0.6, 0.8, >0.995	their worked values	[11] §3.1 When N =3, R=W =1, this means that the probability of returning a version within 2 versions is 0.5, within 3 versions, 0.703, 5 versions, > 0.868, and 10 versions, > 0.98. When N =3, R=1, W =2 (or, equivalently, R=2, W =1), these probabilities increase: k=1 → 0.6, k=2 → 0.8, and k=5 →> 0.995.
cannot order updates at one server	per-server entries	[8] §3.2 However, this approach cannot track causality among updates submitted to the same server.
plausible clocks	where Dynamo falls	[8] §3.2 The Dynamo system uses one entry per replica node and thus falls into this category.
one concurrent update is lost	the consequence	[8] §3.2 In practice a last writer wins policy was enforced with respect to concurrent updates handled in the same replica node, and, in this case, one concurrent update was lost.
one entry per server holding a replica	what dotted version vectors need	[8] Abstract it maintains information that grows linearly only with the number of servers that register updates for a given data element, bounded by the degree of replication.

How this was made

The run is a seeded discrete-event simulation of the protocol the paper describes, computed in the page by engine.js. test.mjs checks MD5 against node's own, Figure 3 clock by clock, consistent hashing's defining property, the theorem that R + W > N never reads stale across four latency models, convergence of every replica after random crashes and partitions once hinted handoff and anti-entropy run, negative controls that must fail, the closed forms and arithmetic of the Bailis paper (including two of its numbers that its own equation contradicts), and the model against the numbers that paper published: the probabilities right after a commit, Figure 4's, Table 4's t-visibilities and the N sweep. Every paper number is a fact with a verbatim quote.

Built with the dissection skill. The visual grammar of values as blocks of cells owes much to Brendan Bycroft's LLM Visualization. Source, tests and experiments: anatomy/architecture/2026-10-18-dynamo/ in the site's repository.

Cite this page

@misc{sigmoid-dynamo,
  title  = {Anatomy of Dynamo},
  author = {Praveen T N},
  year   = {2026},
  note   = {Sigmoid Anatomy, interactive dissection},
  url    = {https://praveentn.live/anatomy/dynamo}
}