Lesson 05 · Quorums & the availability trade

The Dial

Every system so far has made one choice about consistency and lived with it. Dynamo's contribution was to stop choosing — and expose the trade as three numbers you turn, per application, at configuration time.

The win in this lesson: given N, R and W, you will be able to say what a system guarantees, what it costs, and — the part most people get wrong — what it still does not guarantee even when the arithmetic looks safe.

1. The requirement

Dynamo exists because of one product sentence: adding an item to a shopping cart must never fail. Not "should rarely fail" — never. A rejected write there is a lost sale, and Amazon had the numbers to prove what that was worth.

"Dynamo is targeted mainly at applications that need an 'always writeable' data store where no updates are rejected due to failures or concurrent writes."

Dynamo: Amazon's Highly Available Key-value Store, DeCandia et al., SOSP '07 · §2.3

Read "or concurrent writes" carefully. Most databases reject a concurrent write, or make one wait. Dynamo accepts both — which means it has to have an answer for what happens next, and that answer is the price of the whole design.

2. The constraint you cannot design around

"when dealing with the possibility of network failures, strong consistency and high data availability cannot be achieved simultaneously"

§2, Dynamo

This is not an engineering preference, it is a result — and the paper's framing of the usual choice is worth reading twice: "rather than dealing with the uncertainty of the correctness of an answer, the data is made unavailable until it is absolutely certain that it is correct."

That is what a conventional database does when a replica is unreachable. It stops. Refusing to answer is the safe behaviour, and for a shopping cart it is also the wrong one. Dynamo takes the other branch and accepts the uncertainty — then spends the rest of the paper dealing with it.

3. Three numbers

• N — how many nodes hold a copy of each key.
• R — "the minimum number of nodes that must participate in a successful read".
• W — "the minimum number of nodes that must participate in a successful write".

"Setting R and W such that R + W > N yields a quorum-like system."

§4.2, Dynamo

The arithmetic has one job: force the read set and the write set to overlap. If a write touched W nodes and a read asks R nodes, and R + W is greater than N, then at least one node must appear in both — so at least one of the answers the reader receives has seen the write.

4. Why nobody sets R = N

Because of a sentence that should sound familiar by now:

"the latency of a get (or put) operation is dictated by the slowest of the R (or W) replicas. For this reason, R and W are usually configured to be less than N, to provide better latency."

§4.2, Dynamo

Wait for more replicas and you wait for the worst of them. Every additional node you require is another chance to draw a slow one — so R and W are, quite literally, a dial between certainty and tail latency.

And Dynamo's targets are stated in the now-familiar currency:

"An example of a simple SLA is a service guaranteeing that it will provide a response within 300ms for 99.9% of its requests for a peak client load of 500 requests per second."

§2.2, Dynamo

5. The quorum that bends

A strict quorum has a fatal property for an always-writeable store: if the N nodes responsible for a key are not all reachable, the write fails. So Dynamo does not use one:

"If Dynamo used a traditional quorum approach it would be unavailable during server failures and network partitions… To remedy this 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."

§4.6, Dynamo

If node A is down, the copy that belonged on A goes to node D instead, carrying "a hint in its metadata that suggests which node was the intended recipient" — hinted handoff. When A returns, D delivers it and deletes its copy. The write never failed; it was simply held by a stranger for a while.

Notice what this costs, because it is easy to miss: once writes can land on nodes outside the intended N, R + W > N no longer guarantees overlap. The arithmetic assumed a fixed set of N nodes. A sloppy quorum breaks that assumption deliberately, in exchange for staying up.

6. The bill: conflicts

"No updates are rejected due to… concurrent writes" means two clients can both succeed in writing different values. Neither is wrong. Somebody has to reconcile them, and the paper is clear that the choice of who is the real design decision:

"If conflict resolution is done by the data store, its choices are rather limited. In such cases, the data store can only use simple policies, such as 'last write wins'… On the other hand, since the application is aware of the data schema it can decide on the conflict resolution method that is best suited for its client's experience. For instance, the application that maintains customer shopping carts can choose to 'merge' the conflicting versions and return a single unified shopping cart."

§2.3, Dynamo

"Last write wins" is the default and it is a data-loss policy wearing a neutral name: one customer's addition is silently discarded, and across machines "last" means "whichever clock said so". The cart instead merges — union the items, and nothing is lost.

7. The misconception worth killing

8. You have already used this dial

Dynamo's real legacy is not the system — it is that this dial is now everywhere, usually under a different name.

So when Discord writes at QUORUM across a replication factor of three, they are setting W = 2 on N = 3 — this paper's arithmetic, twelve years later, in a config file.

And the outcome Amazon reported after two years: applications "received successful responses (without timing out) for 99.9995% of its requests and no data loss event has occurred to date." The paper's own summary of why: Dynamo "provides the necessary knobs using the three parameters of (N,R,W) to tune their instance based on their needs."

9. Check yourself

10. Back to your world

You are unlikely to configure a Dynamo cluster. You are very likely to choose a consistency level in a client library, tick "synchronous replication" in a managed-database console, or accept a default that someone chose for you. Those are all this dial. The questions that make the choice real:

• What does a rejected write cost here? A lost sale, or an error message the user shrugs at? Dynamo exists because of the first answer.
• If two writes conflict, who merges them — and can they? If nobody, your default is last-write-wins, which means silent data loss.
• What is the slowest replica going to do to my p99? Because that is who you are waiting for.