Part 6 of 8 · 4 min read
Quorums
Choosing how many replicas must confirm a write and answer a read.
Think of a bank with five branches that all hold the record of your balance. If a deposit must be recorded at 3 branches and a balance check must ask 3 branches, then any check will meet at least one branch that saw the deposit, because 3 and 3 add up to more than 5.
Quorum (n, w, r)
With n replicas for each item, a write must be confirmed by w of them and a read must ask r of them. If w + r > n, then every read set overlaps every write set in at least one node, so a read should see the latest successful write.
Example: n = 5, w = 3, r = 3. Since 3 + 3 = 6 > 5, a read of 3 replicas includes at least one that has the latest write.
The writes are always sent to all n replicas in parallel. The numbers w and r decide only how many answers the client waits for.
A common choice from the book: make n odd (3 or 5) and set w = r = (n + 1) ÷ 2, rounded up. Reads and writes need a majority. Other choices are possible. A workload with few writes and many reads might set w = n and r = 1. Reads are fast, but one failed node makes every write fail.
What the numbers tolerate:
| n | w | r | w + r > n | Failed nodes tolerated for writes | Failed nodes tolerated for reads |
|---|---|---|---|---|---|
| 3 | 2 | 2 | yes (4 > 3) | 1 | 1 |
| 5 | 3 | 3 | yes (6 > 5) | 2 | 2 |
| 5 | 5 | 1 | yes (6 > 5) | 0 | 4 |
| 5 | 1 | 5 | yes (6 > 5) | 4 | 0 |
| 5 | 2 | 2 | no (4 ≤ 5) | 3 | 3 |
With w + r ≤ n, reads and writes still go to n nodes but need fewer answers. The result is lower latency and higher availability, but a higher chance of reading stale values. There can be more than n nodes in the cluster, since each value lives on only n of them. That allows partitioning (module 4).
Limits of quorums. Even with w + r > n, the book lists cases where stale values can be returned:
- A sloppy quorum (next section) may put the writes on different nodes from the reads.
- Two writes at the same moment: the only safe solution is to merge them. If LWW picks a winner by timestamp, clock skew can lose writes.
- A write at the same time as a read may reach only some replicas, so it is not clear whether the read returns the old or the new value.
- A write that succeeded on some replicas but fewer than w is reported as failed, but is not rolled back. A later read may or may not return it.
- A node with a new value fails and is restored from a replica with an old value, so the count of nodes holding the new value falls below w.
- Timing edge cases even when everything works.
The book's advice is not to take n, w and r as absolute guarantees. They adjust the probability of stale reads. Dynamo-style databases suit uses that tolerate eventual consistency. In particular, you usually do not get read-your-writes, monotonic reads or consistent prefix reads (module 2). Stronger guarantees need transactions or consensus.
Monitoring. For a leader-based database, lag is the difference between positions in the log. In a leaderless database there is no fixed order of writes, so lag is harder to measure. With read repair only, an item rarely read can be very old on a stale replica. The book would like staleness measures in the standard metrics, since it is important to be able to quantify "eventual".
A worked example. n = 5, w = 3, r = 3. A write succeeds on nodes 1, 2, 3. A read asks nodes 3, 4, 5. Node 3 has the new value; nodes 4 and 5 have the old one. The client sees one new and two old values with different versions, takes the highest version, and does read repair on 4 and 5. Now suppose two nodes fail: nodes 1 and 2. Writes still need 3 of the 3 remaining (3, 4, 5): possible. A third failure makes writes impossible (only 2 left).
Check yourself:
- With n = 7 and w = 4, what is the smallest r that satisfies w + r > n?
- Why can quorum reads still return old values?