What you'll learn: By the end of this lesson you will be able to choose N, R and W for a leaderless store and explain what each choice costs, prove with a counting argument why R + W > N makes every read set overlap every write set, say precisely what that overlap does and does not promise, explain how a sloppy quorum and hinted handoff keep writes available and why they remove the overlap, and describe how read repair and anti-entropy bring stale replicas back, using a Java lab that runs all of it.
Picture a school with five noticeboards. A notice counts as published once it is pinned on any three boards. A parent who wants to know the latest notice reads any three boards and trusts the newest date. Pick any three boards for the writer and any three for the reader: with only five boards, the two groups must share at least one board. So the reader always meets a board that carries the latest notice, even though no board was ever checked twice and two boards may have been locked all week.
That is a quorum. The overview lessons CAP, PACELC and consistency models and replication introduce it in a paragraph each. This lesson is the dedicated treatment: the arithmetic, the settings, and the three mechanisms that decide what happens when boards are locked (sloppy quorums, hinted handoff and read repair). The lab in CAP and PACELC shows the strict-versus-sloppy choice; the new lab here is about the repairs.
Verified with Java 25, the Dynamo paper (SOSP 2007), Apache Cassandra documentation 5.0 and the Riak KV documentation, on 2026-11-08.
The core idea
A quorum system keeps N copies of each item, accepts a write once W copies have it, answers a read from R copies, and takes the newest answer. When R + W > N, the read set and the write set must share a replica, so a read that succeeds meets at least one copy of the latest acknowledged write. Everything else in the lesson is about what breaks that sentence: stand-in nodes, concurrent writers, replicas that missed a write, and repairs that never ran.
Three illustrations run through it, each labelled:
- Minimal example: five replicas and a counting argument, then the Java lab.
- Realistic example: ShopStream's cart store during a zone outage, in "In practice".
- Failure example: a hint that expires before the replica returns, so the missing write is never delivered.
N, R and W
| Parameter | Meaning (Dynamo paper, sections 4.3 and 4.5) | What raising it does |
|---|---|---|
| N | The number of replicas of each item; set per instance | More durability and read capacity, more storage and write traffic |
| W | The minimum number of nodes that must take part in a successful write | Stronger durability and overlap, fewer failures tolerated, slower writes |
| R | The minimum number of nodes that must take part in a successful read | Stronger overlap, fewer failures tolerated, slower reads |
The paper adds the cost rule: the latency of a get or put is dictated by the slowest of the R or W replicas that must answer, so R and W are usually configured below N. It also reports that the common (N, R, W) configuration of several Dynamo instances was (3, 2, 2). Apache Cassandra expresses the same thing with consistency levels: ONE, QUORUM (a majority, n/2 + 1 of the replicas) and ALL, and its documentation writes the overlap rule as W + R > RF, with RF the replication factor.
Why R + W > N overlaps
Take a write set of W replicas and a read set of R replicas, both drawn from the same N. Together they name R + W replicas, and only N exist, so at least R + W - N of them are named twice. If R + W > N that number is at least 1.
Figure 1. A write set and a read set on five replicas meet at replica 3. How to read this: the writer's three arrows are the write set, the reader's three arrows are the read set. Replicas 4 and 5 know nothing about the write, yet the read still reaches replica 3, so taking the newest version among the three answers returns the written value.
The "take the newest" rule matters as much as the overlap. The overlap guarantees a fresh copy is among the answers; a version number or vector clock lets the coordinator pick it out. Logical and Vector Clocks covers how versions are compared.
The same arithmetic as a table
| (N, W, R) | R + W > N? | Writes survive down replicas | Reads survive down replicas | Character |
|---|---|---|---|---|
| (3, 2, 2) | yes | 1 | 1 | The common Dynamo configuration |
| (3, 3, 1) | yes | 0 | 2 | Fast reads, writes fail if any replica is down |
| (3, 1, 3) | yes | 2 | 0 | Writes always accepted, reads need every replica |
| (3, 1, 1) | no | 2 | 2 | Fastest and most available, reads can be stale |
| (5, 3, 3) | yes | 2 | 2 | Majority quorum on five replicas |
"Survive" is N - W for writes and N - R for reads under strict quorums. The numbers are teaching examples, not product defaults.
What the overlap does not promise
The guarantee is narrow: a read that succeeds meets a replica that holds the latest acknowledged write, in a history where one operation finishes before the next starts. It does not give linearizability under concurrency. The sentence stops holding when:
- Writers overlap. Two writes in flight can land on different replicas; the read sees both and must decide. Detecting that two writes were concurrent, instead of silently keeping one, is the subject of Logical and Vector Clocks.
- A write fails halfway. If fewer than W replicas answer, the client sees a failure, but the protocol described in the paper has no step that removes the copies that were written, so a later read may return a value the client was told had failed.
- The quorum is sloppy. The next section.
- A replica missed a write and nothing repaired it. The section after.
Sloppy quorums and hinted handoff
A strict quorum insists that the W (or R) replicas be among the key's N home replicas, the first N entries of its preference list. If too many are down, the operation fails. Dynamo chose availability: "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" (section 4.6). The preference list holds more than N nodes so that stand-ins exist.
When home replica A is down, the write that would have gone to A goes to the next healthy node, D. The copy carries a hint naming A as its intended owner. D keeps hinted copies "in a separate local database that is scanned periodically"; once D detects that A has recovered, it delivers the copy and may delete it. That delivery is hinted handoff.
Figure 2. A hinted write with node A down. How to read this: the client reaches B, C and D, which is three healthy nodes, so W = 2 is met and the write is acknowledged. D holds the copy only for A. The dashed green arrow is the delayed delivery that makes A current again.
The price is the overlap. A sloppy read asks the first R of the first N healthy nodes. After A returns but before handoff, a read can ask A and a node that never saw the write, and find nothing, although R + W > N. The write exists, and the overlap proof does not apply because the write set included a stand-in outside the read set's home replicas. This is the trade the Dynamo paper accepts: the write is never refused for a transient failure, and in exchange the guarantee becomes "eventually, after handoff".
What happens to a hint
Handoff can fail, which is why hints are only part of the repair story.
Figure 3. The ways a hint ends. How to read this: the top path is the happy ending. The two lower paths leave the home replica stale, and the only exits from there are read repair (for keys that are read) and anti-entropy (for the rest).
Cassandra's documentation agrees. The coordinator stores the hint in a flat file on its own disk (the stand-in is the coordinator, not another ring node), replays hints "quickly after unavailable replica nodes return to the ring", and keeps new hints only for a bounded window (max_hint_window, 3h in the 5.0 documentation). Hints are "best effort" and "do not guarantee eventual consistency" the way anti-entropy repair does. In its consistency-level table only ANY ("a single replica may respond, or the coordinator may store a hint") mentions a hint as a way to finish a write. Riak's documentation uses other words for the paper's idea: preferred partitions for a key, with the rest "retained as fallbacks" for when a target is unavailable.
Read repair and anti-entropy
Read repair fixes replicas during reads. In the Dynamo paper, after the read response has gone back to the caller, the coordinator waits a short time for outstanding replies; if any returned a stale version, it writes the latest version to those nodes (section 5). Cassandra's 5.0 documentation calls it "the process of repairing data replicas during a read request", makes the blocking variant the default, and says it is not performed at consistency level ONE because the first replica read already satisfies the level.
Figure 4. A quorum read that repairs a stale replica. How to read this: the client gets the newest value of the answers; the stale replica is fixed as a side effect. Repair only reaches replicas the read contacted, so keys nobody reads are not repaired this way.
Anti-entropy is the repair that does not wait for a read. Dynamo's replicas compare Merkle trees, hash trees whose leaves are hashes of key values, descending only into the branches whose hashes differ, so they transfer only the keys that are out of sync (section 4.7). The paper says hinted handoff "works best if the system membership churn is low", and that anti-entropy covers the cases where hinted replicas become unavailable before they can be returned. Cassandra's architecture page lists replica read repair and hinted handoff as best-effort techniques and anti-entropy repair as the way to guarantee eventual consistency.
Build it: sloppy quorums, hinted handoff and read repair in Java
This is the minimal example, a model you can run. The quorum register lab in CAP and PACELC covers overlap and the strict-versus-sloppy choice; this lab covers hints and repairs.
Goal. See a stale read with R + W > N under a sloppy quorum, hinted handoff close it, a hint expire or vanish with its node, and read repair and anti-entropy finish the job.
Setup. From the repository's examples/backend folder:
cd examples/backend && ./gradlew :labs:quorum-sloppy-and-hinted-handoff:test
./gradlew -q :labs:quorum-sloppy-and-hinted-handoff:runThe first command runs 22 tests. The second prints the scenario table below. The code is in examples/backend/labs/quorum-sloppy-and-hinted-handoff/src/main/java/buildingai/labs/hintedquorum/HintedQuorum.java.
How the model works. One key lives on a ring A B C D E; A B C are the home replicas (N = 3) and D, E are stand-ins. Strict mode needs W home replicas up. Sloppy mode writes to the first N healthy nodes, and a stand-in keeps its copy as a hint, apart from its data. handoff() delivers a hint once its owner is up (never over a newer value) and drops hints older than the lifetime, 3 ticks in the demo, a parameter of the model and not a product default. Read repair writes the newest value to the contacted home replicas that were behind; antiEntropy() gives every live home replica the newest value any of them holds. The core of handoff is one condition:
if (now - hint.storedAt() > config.hintLifetime()) {
it.remove();
expired++;
} else if (!down.contains(hint.owner())) {
data.put(hint.owner(), data.get(hint.owner()).newest(hint.value()));
it.remove();
delivered++;
}Steps. Run the tests, then the demo. The tests check, for every N from 1 to 5, every W and R with R + W > N and every pattern of down nodes, that a successful strict read sees the acknowledged write; that a sloppy read can be stale with R + W > N; that a late hint never overwrites a newer value; and, over random 300-step histories, that replicas never move backwards and converge after handoff and anti-entropy when no disk is lost.
Expected output, captured from a real run (Java 25.0.3, 2026-11-08):
Sloppy quorum and hinted handoff: one key on ring A B C D E, home replicas A B C (N=3), W=2, R=2 unless a row says otherwise.
'homes after' is the value each home replica holds after the step; 'hints' lists the copies held on stand-ins for a home replica.
# mode homes after hints step -> outcome
-----------------------------------------------------------------------------------------------------------------------------
1 strict A=v1@1 B=v1@1 C=v1@1 none write v1 -> taken by [A, B, C]
1 strict A=v1@1 B=v1@1 C=v1@1 none read -> v1 from [A, B]
2 strict A=- B=- C=- none A and B unreachable; write v1 -> UNAVAILABLE
3 sloppy A=- B=- C=v1@1 D:[A<-v1@1] E:[B<-v1@1] A and B unreachable; write v1 -> taken by [C, D, E], hints [D(for A), E(for B)]
3 sloppy A=- B=- C=v1@1 D:[A<-v1@1] E:[B<-v1@1] A and B are back, no handoff yet; read -> (nothing) from [A, B] (R+W=4 > N=3, yet STALE)
3 sloppy A=v1@1 B=v1@1 C=v1@1 none handoff -> delivered 2, expired 0, waiting 0
3 sloppy A=v1@1 B=v1@1 C=v1@1 none read -> v1 from [A, B]
4 sloppy A=- B=- C=v1@1 D:[A<-v1@1] E:[B<-v1@1] A and B unreachable; write v1 -> taken by [C, D, E], hints [D(for A), E(for B)]
4 sloppy A=- B=- C=v1@1 none 4 ticks pass (hint lifetime 3), A and B return; handoff -> delivered 0, expired 2, waiting 0
4 sloppy A=- B=- C=v1@1 none read -> (nothing) from [A, B] (stale for good: no hint left)
4 sloppy A=v1@1 B=v1@1 C=v1@1 none anti-entropy -> replicas changed: 2
4 sloppy A=v1@1 B=v1@1 C=v1@1 none read -> v1 from [A, B]
5 sloppy A=- B=- C=v1@1 D:[A<-v1@1] E:[B<-v1@1] R=3, read repair on; A and B unreachable; write v1 -> taken by [C, D, E], hints [D(for A), E(for B)]
5 sloppy A=- B=- C=v1@1 none 4 ticks pass, A and B return; handoff -> delivered 0, expired 2, waiting 0
5 sloppy A=v1@1 B=v1@1 C=v1@1 none read -> v1 from [A, B, C], repaired [A, B]
6 sloppy A=- B=v1@1 C=v1@1 D:[A<-v1@1] A unreachable; write v1 -> taken by [B, C, D], hints [D(for A)]
6 sloppy A=v2@2 B=v2@2 C=v2@2 D:[A<-v1@1] A returns; write v2 -> taken by [A, B, C]
6 sloppy A=v2@2 B=v2@2 C=v2@2 none handoff -> delivered 1, expired 0, waiting 0 (A keeps v2)
7 sloppy A=- B=- C=v1@1 D:[A<-v1@1] E:[B<-v1@1] A and B unreachable; write v1 -> taken by [C, D, E], hints [D(for A), E(for B)]
7 sloppy A=- B=- C=- E:[B<-v1@1] C and D lose their disks (the hint for A goes with D); A and B return
7 sloppy A=- B=v1@1 C=- none handoff -> delivered 1, expired 0, waiting 0
7 sloppy A=- B=v1@1 C=- none read -> v1 from [A, B] (R=2 met by B)
7 sloppy A=v1@1 B=v1@1 C=v1@1 none anti-entropy -> replicas changed: 2
8 sloppy A=- B=- C=- D:[A<-v1@1] E:[B<-v1@1] A, B and C unreachable; write v1 -> taken by [D, E], hints [D(for A), E(for B)]
8 sloppy A=- B=- C=- D:[A<-v1@1] E:[B<-v1@1] A, B and C return; read -> (nothing) from [A, B] (the write exists only as hints)
8 sloppy A=v1@1 B=v1@1 C=- none handoff -> delivered 2, expired 0, waiting 0
8 sloppy A=v1@1 B=v1@1 C=- none read -> v1 from [A, B] (C never got a hint: only 2 stand-ins)
8 sloppy A=v1@1 B=v1@1 C=v1@1 none anti-entropy -> replicas changed: 1
9a strict A=- B=v1@1 C=v1@1 none A unreachable; write v1 -> taken by [B, C]
9a strict A=- B=v1@1 C=v1@1 none A returns; read -> v1 from [A, B] (read repair off: A stays behind)
9a strict A=- B=v1@1 C=v1@1 none read again -> v1 from [A, B] (still behind)
9b strict A=- B=v1@1 C=v1@1 none A unreachable; write v1 -> taken by [B, C]
9b strict A=v1@1 B=v1@1 C=v1@1 none A returns; read -> v1 from [A, B], repaired [A] (read repair on: A is fixed by the read)
10 strict A=- B=v1@1 C=v1@1 none R=1, read repair on; A unreachable; write v1 -> taken by [B, C]
10 strict A=- B=v1@1 C=v1@1 none A returns; read -> (nothing) from [A] (R+W=3 <= N: the one replica asked is the stale one, nothing to repair from)| Row | What it shows |
|---|---|
| 2 | Strict mode, A and B down: the write is refused. |
| 3 | Sloppy mode takes the same write on C, D and E with hints for A and B. After A and B return, a read of A and B finds nothing although R + W = 4 > N = 3; after handoff it is fresh. |
| 4 | The hints expire (4 ticks, lifetime 3) before A and B return: handoff delivers nothing and the read stays stale until anti-entropy. |
| 5 | The same expiry with R = 3 and read repair on: the read reaches C and repairs A and B. |
| 6 | A late hint reaches A, which already holds a newer value, and is ignored. |
| 7 | C and D lose their disks, and the hint for A goes with D. Anti-entropy repairs A and C from B. |
| 8 | A, B and C all down: D and E alone accept the write, and C, with no stand-in, stays empty until anti-entropy. |
| 9a, 9b | A missed a write in strict mode: it stays behind across reads with repair off, and the first read fixes it with repair on. |
| 10 | With R = 1 the read asks only A, the stale one, so there is nothing to repair from. |
Break it. In HintedQuorum.handoff, replace newest(hint.value()) with a plain overwrite: aLateHintNeverOverwritesANewerValue and the random-history test fail. Delete the owner-is-up check and handoffWaitsForTheOwnerThenDeliversAndDeletesTheHint fails.
Stretch. Let a sloppy read serve hints and see whether row 3 turns fresh. Add a bounded hint store. Replace the single counter with the vector clocks of the next lesson.
What the model leaves out. Concurrent clients, conflict resolution, asynchronous delivery of a write to later replicas (every target takes the write at once), several keys, membership changes, Merkle trees (anti-entropy is reduced to its effect) and every product default.
Choosing N, R and W: the trade-offs
The first question is whether stale reads are acceptable at all. If not, choose R + W > N, then pick the hot side: high W for read-heavy data, high R for write-heavy data, a majority on both for a balanced one. Separately, decide whether stand-ins may take writes during an outage; that choice is independent of (N, W, R) and sets what the guarantee is while nodes are down.
| Option | Gain | Cost | Wrong when |
|---|---|---|---|
| Strict quorum, R + W > N | Reads meet the latest acknowledged write | Operations refuse when too many home replicas are down | Writes must always be accepted |
| Sloppy quorum plus hinted handoff | Writes accepted through outages | Reads can be stale during and after an outage; hints can expire or be lost | A read after an acknowledged write must see it |
| R = 1, W = 1 | Lowest latency, most available | Stale reads, lost updates on failure | Anything that is money or uniqueness |
| Read repair only | Free, runs on the hot path | Heals only keys that are read, adds writes to reads | Cold keys must also converge |
| Scheduled anti-entropy | Heals everything, including cold keys | Background I/O and network | Nobody owns the schedule |
In practice: ShopStream's cart store during a zone outage
This is the realistic example, an educational scenario on the course's running example ShopStream; nothing in it describes a real company. Every number is illustrative.
This is a realistic scenario, not a case history.
The situation
ShopStream's cart has to accept "add to cart" even during a partial outage (the CAP lesson put carts on the available side). The team has a leaderless cart store with N = 3 replicas, one per zone, and wants to know what shoppers see when a zone goes away for a few hours.
Starting architecture
Figure 5. The cart path with zone 1 unreachable. How to read this: the cart service writes to the two healthy home replicas and to a stand-in that stores a hint for zone 1. W = 2 is met by zone 2 and zone 3, so shoppers see no error.
Options considered
| Option | Outage behaviour | Risk |
|---|---|---|
| A. Strict (3, 2, 2) | Works while any two zones are up, refuses if two are down | Simple and predictable; a second failure blocks carts |
| B. Sloppy (3, 2, 2) with hints | Accepts writes even with two zones down | Reads can miss a cart update until handoff; hints can expire |
| C. (3, 1, 1) | Always answers | Stale carts as the normal case |
The decision
Option A for normal operation and option B as the outage behaviour, with a repair schedule. The team accepts that for a few minutes after a zone returns a read may be a little behind and records two rules: hint delivery must finish within a bounded window, and a scheduled repair covers whatever hints miss. Carts are merged on read, as in the CAP lesson, so a stale read costs a missing item, not a wrong total.
Rollout and verification
A rollout would first run a test cluster in the lab's shape: take one node down, write, bring it back, and compare replicas before and after handoff. In production the checks are counts and ages: hints stored and delivered per node, the age of the oldest undelivered hint, replicas that disagree in a sampled digest comparison, and read repairs per minute. Verification is "the oldest hint is always younger than the hint window, and a repair run finds few differences".
The 2 a.m. failure
The page reads: shoppers say items vanished from carts after yesterday's zone outage. The outage outlasted the hint window, so the hints expired before zone 1 returned and handoff delivered nothing (row 4 of the lab). Carts that shoppers reopen are repaired by read repair, which is why complaints are mixed; carts nobody has opened since are still behind.
The checks: compare the hint backlog age with the window, run a digest comparison on a sample of carts across zones, and look for a missing scheduled repair. The mitigation is a full repair of the affected ranges, which is what anti-entropy is for. The lasting fix is a repair schedule with an owner, an alert on hint age approaching the window, and a decision on whether the window should exceed the longest outage the team plans for.
Architect's notes
- Name the guarantee in words. "A successful read meets the latest acknowledged write while the quorum is strict and no write is in flight" is a guarantee; "we use quorums" is not.
- Treat sloppy mode as a separate setting. It changes what R + W > N means, so document it beside the numbers.
- Plan for repair, not just for failure. Hints are best effort, so someone owns the hint window and the anti-entropy schedule.
- Read repair heals hot keys only. Cold data needs scheduled anti-entropy.
- Check the version. Defaults such as
max_hint_windowand the read repair options are documented per release.
Common mistakes
- Reading R + W > N as linearizability. It is overlap in a sequential history.
- Forgetting that sloppy mode removes the overlap. The settings can say (3, 2, 2) while reads miss acknowledged writes.
- Assuming a hint is delivered. It can expire or vanish with its stand-in.
- Counting on read repair for everything. It reaches only keys that are read.
- Setting W = N for safety. One down replica then blocks every write.
- Copying numbers from a paper. (3, 2, 2) was one team's choice, not a universal default.
Key takeaways
- N copies, W to acknowledge a write, R to answer a read; R + W > N forces the two sets to share a replica, and the newest version among the answers wins.
- The guarantee is narrow: the latest acknowledged write, a sequential history, a strict quorum.
- A sloppy quorum uses the first N healthy nodes, accepts writes through outages and gives up the overlap until hinted handoff delivers.
- Hints are best effort: they can expire, vanish with a node or have nowhere to go.
- Read repair fixes the replicas a read touched; anti-entropy fixes the rest.
- Decide the numbers, whether stand-ins take writes, the hint window and the repair schedule together.
Practice exercises
Exercise 1 (20 min). For N = 5, list every (W, R) pair with R + W > N and how many replicas may be down before strict writes and strict reads refuse.
Exercise 2 (45 min). Run the lab. For rows 3, 4, 7 and 8, write what a shopper would see and which mechanism finally repairs it.
Exercise 3 (1 hour). Run "Break it". Then, in row 3 of the demo, set the hint lifetime to 0 and add q.tick(1) before A and B return; say what changes and why a longer lifetime is not free.
Exercise 4 (2 hours). For ShopStream's cart, stock count and courier location, choose strict or sloppy, N, W and R, the hint window and the repair schedule, and write what each choice costs.
Related reading
- CAP, PACELC and Consistency Models: where quorums sit among the consistency models.
- CAP Theorem and PACELC: the quorum register lab and why R + W > N is not linearizability.
- Replication: leaders, followers, lag and leaderless replication.
- IDs, Clocks and Ordering: the ordering tools behind the "newest version".
- Consensus and Leader Election: the alternative when you need one agreed order.
Official documentation
- DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007): sections 4.5 to 4.7 and 5.
- Apache Cassandra documentation (5.0): Dynamo architecture, hints, read repair.
- Riak KV documentation: replication.