# DDIA Ch. 6: quorums overlap by w + r > n — and still read stale ## Concept In leaderless (Dynamo-style) replication with `n` replicas, a write goes to `w` nodes and a read queries `r` nodes. Pick `w + r > n` and the two sets are forced to share at least one node — pigeonhole — so a read is guaranteed to touch a node carrying the latest write. That is the quorum condition, and it feels airtight. The book is careful to call it a *general* guarantee, then lists the cases where `w + r > n` **still returns stale data**. You will run a tiny quorum store, watch `w + r > n` overlap in **all 9** write/read combinations, and then watch a **sloppy quorum** with `w + r = 4 > 3 = n` hand back a stale read anyway — because the count was pigeonholing nodes from the wrong pool. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 6 — *Replication*, §"Understanding the limitations of quorum consistency": > w + r > n ... you can generally expect every read to return the most recent value The weight is on *generally*. The same section enumerates the edge cases; here you build the store, confirm the overlap guarantee by brute force, then reproduce one documented case where it fails. ## Prerequisites The surprise is that a set-overlap guarantee can be true by count and false in fact. These help; each line notes where it shows up. 1. **Leaderless / quorum reads and writes** — there is no single leader; a write is sent to `w` replicas and a read to `r`, in parallel. Shows up in every step as the `write set` / `read set`. 2. **The quorum condition `w + r > n`** — the pigeonhole argument that a write set of size `w` and a read set of size `r` drawn from `n` nodes must intersect. Step 2 verifies it exhaustively; Step 3 breaks its precondition. 3. **Version numbers / recency** — each write carries a monotonically increasing version so a read can pick the newest value it saw. Appears as `version 1` (old) vs `version 2` (new) throughout. 4. **Sloppy quorums and hinted handoff** — when a write can't reach its `w` *home* replicas, it may be accepted on *fallback* nodes instead, to be handed back later. This is the mechanism that breaks the guarantee in Step 3. ### Where to learn the prerequisites - **Quorums and `w + r > n` (#1–#3):** DDIA §"Quorums for reading and writing" and §"Understanding the limitations of quorum consistency"; the Dynamo paper (§4.5) for the original formulation. - **Sloppy quorums (#4):** DDIA §"Sloppy Quorums and Hinted Handoff" — the two paragraphs that explain why a sloppy quorum "is not a quorum at all in the traditional sense." If only one is new, make it #2 — the whole exercise is that `w + r > n` is a claim about a *fixed* set of `n` nodes, and Step 3 is what happens when that assumption quietly stops holding. ## Environment Deterministic — every write set and read set is chosen explicitly, no randomness, so the transcript reproduces exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only (`itertools.combinations`) — no `pip`, no Docker - One key, `n = 3` home replicas, versions as plain increasing integers ## Mental model A `QuorumStore` of `n` replicas, each holding one `(value, version)` for a single key: - **write(nodes, value, version)** — set exactly those `w` nodes to the new `(value, version)`. That is the write set. - **read(nodes)** — query those `r` nodes and return the one with the highest version. That is the read set; highest version = most recent write it saw. - **overlap** — `write set ∩ read set`. If it is non-empty, the read touched a node holding the latest write, so it cannot be stale. `w + r > n` is supposed to force this. Three steps: `w + r ≤ n` (can miss), `w + r > n` (all pairs overlap, by enumeration), and a sloppy quorum where `w + r > n` by count yet the sets are disjoint. The whole exercise is one script, `code/quorum_limits.py`. ## Setup ``` cd study/ddia/ch06/code python3 quorum_limits.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — predict an undersized quorum **Predict.** `n = 3`, `w = 1`, `r = 1`, so `w + r = 2 ≤ n`. All replicas start at `('v1', version 1)`. You write `'v2'` to node `0` and read from node `1`. What version does the read return — the new `v2`, or the old `v1`? **Observe.** ``` ====================================================================== STEP 1 -- w + r <= n is NOT safe (w=1, r=1, n=3) ====================================================================== start: all 3 replicas hold ('v1', version 1) w + r = 1 + 1 = 2 n = 3 -> w + r <= n write ('v2', version 2) to w=1 node: write set = [0] read from r=1 node: read set = [1] read returned: ('v1', version 1) write set [0] INTERSECT read set [1] = (empty) -> the read never touched the node that got 'v2', so it saw STALE 'v1'. ``` With `w + r ≤ n` the write set `{0}` and read set `{1}` can be disjoint, and here they are — the read returns the **stale** `v1`. Nothing forces the two sets to meet. ### Step 2 — predict the overlap guarantee **Predict.** Now `w = 2`, `r = 2`, so `w + r = 4 > 3 = n`. The script enumerates **every** way to pick a write set of 2 and a read set of 2 from `{0, 1, 2}` — 3 × 3 = 9 combinations. In how many does the write set overlap the read set? In how many does the read return the latest `v2`? **Observe.** ``` ====================================================================== STEP 2 -- w + r > n GUARANTEES overlap (w=2, r=2, n=3) ====================================================================== w + r = 2 + 2 = 4 n = 3 -> w + r > n enumerate EVERY way to pick a write set of 2 and a read set of 2: write set read set overlap read sees ------------------------------------------------- [0, 1] [0, 1] [0, 1] ('v2', v2) [0, 1] [0, 2] [0] ('v2', v2) [0, 1] [1, 2] [1] ('v2', v2) [0, 2] [0, 1] [0] ('v2', v2) [0, 2] [0, 2] [0, 2] ('v2', v2) [0, 2] [1, 2] [2] ('v2', v2) [1, 2] [0, 1] [1] ('v2', v2) [1, 2] [0, 2] [2] ('v2', v2) [1, 2] [1, 2] [1, 2] ('v2', v2) ------------------------------------------------- 9 combinations: every one overlaps in >= 1 node = True reads returning the latest ('v2', version 2): 9/9 -> with w + r > n, no write set and read set can be disjoint (pigeonhole). ``` **9/9.** Every single write/read pair overlaps in at least one node, and every read returns the latest `v2`. Two sets of size 2 out of 3 nodes cannot avoid each other — that is the pigeonhole. The guarantee looks absolute. ### Step 3 — predict the sloppy quorum **Predict.** Same `w = 2`, `r = 2`, still `w + r = 4 > 3 = n`. But a network partition cuts the writer off from home nodes `1` and `2`; a **sloppy quorum** accepts the write on home node `0` plus a **fallback** node `3` (hinted handoff) to reach `w = 2`. The reader, on the other side, reads home nodes `1` and `2`. The count still says `w + r > n`. Does the read see `v2`, or stale `v1`? **Observe.** ``` ====================================================================== STEP 3 -- the limitation: a SLOPPY QUORUM (w=2, r=2) still reads STALE ====================================================================== n = 3 HOME replicas for this key: {0, 1, 2} w + r = 2 + 2 = 4 > 3 = n -> the count says 'guaranteed overlap' a network partition cuts the WRITER off from home nodes 1 and 2; only home node 0 is reachable. A sloppy quorum accepts the write anyway, storing it on node 0 plus a FALLBACK node (hinted handoff) to reach w=2. write ('v2', version 2): write set = [0, 3] (node 3 is a fallback, not a home replica) read from r=2 home nodes: read set = [1, 2] read returned: ('v1', version 1) write set [0, 3] INTERSECT read set [1, 2] = (empty) -> w + r = 4 > n = 3, yet the sets are DISJOINT, so the read is STALE 'v1'. ``` `w + r = 4 > 3`, and the read is **still stale**. The write set `{0, 3}` and read set `{1, 2}` are disjoint — the pigeonhole never applied, because the write escaped the home set onto fallback node `3`. ## What you should see - **Step 1:** `w + r = 2 ≤ n` — write `{0}`, read `{1}`, disjoint, read returns stale `v1`. - **Step 2:** `w + r = 4 > n` — **all 9** write/read pairs overlap; **9/9** reads return the latest `v2`. - **Step 3:** `w + r = 4 > n` by count, yet write `{0, 3}` and read `{1, 2}` are disjoint under a sloppy quorum, so the read is **stale `v1`** anyway. ## Why The quorum condition is a pigeonhole argument, nothing more. If you must pick `w` nodes for a write and `r` nodes for a read out of the *same* `n` nodes, and `w + r > n`, then the two selections have more slots between them than there are nodes, so at least one node is in both — the read is guaranteed to see the write. Step 2 confirms it the honest way: enumerate all `C(3,2) × C(3,2) = 9` pairs and check every intersection. There is no pair to be found where they miss, because there cannot be. That is why the guarantee feels absolute — as pure combinatorics, it is. The catch is the precondition: *the same `n` nodes*. A sloppy quorum quietly violates it. When a write cannot reach enough of its home replicas — a partition, a few down nodes — the system faces a choice: fail the write, or accept it on whatever nodes it *can* reach, including **fallback** nodes that are not home replicas for this key. Taking the write (with hinted handoff to return it later) buys availability, but now the `w` nodes that acknowledged the write include nodes *outside* the home set. Meanwhile the reader queries `r` home nodes. The `w + r > n` count is now adding up nodes drawn from a *larger* pool than `n`, so it no longer implies overlap: in Step 3 the write lives on `{0, 3}` and the read sampled `{1, 2}`, disjoint, and the reader has no way to know a newer value exists on a node it never asked. The version number is honest — node `1` really does still hold `v1` — the read is just looking in the wrong place. **The boundary — `w + r > n` is a guarantee about a fixed set of `n` nodes, not a law of nature.** The overlap is real whenever the write and read quorums are drawn from the same `n` replicas and there is a clear recency ordering. Break either assumption and stale reads return even with `w + r > n`: a **sloppy quorum** (Step 3) puts writes on fallback nodes outside the home set; **concurrent writes** give two values with no version ordering, so a reader that overlaps both can't tell which is newer; a **write that succeeds on fewer than `w` nodes** but isn't rolled back leaves the promised overlap unmet. This is why quorums give you strong *eventual* consistency, not linearizability — DDIA reaches for read-repair, anti-entropy, and (in later chapters) real consensus precisely because the arithmetic alone is only a general expectation. ### Go deeper 1. **Concurrent writes.** Extend the store to let two writers stamp the *same* version onto overlapping quorums (a tie). Predict what a read that overlaps both should return, and why "highest version" stops being well-defined — motivating version vectors and sibling values. 2. **Probabilistic staleness.** Instead of `w + r > n`, run `w = r = 1` many times with randomly chosen sets over `n` replicas and measure the fraction of stale reads. Predict how it falls as you raise `w + r` toward `n + 1`, matching the Dynamo "probability of staleness" analysis. 3. **Read repair.** After a stale read, have the read path push the newest version back to the lagging nodes it queried. Predict how many reads it takes for a partitioned replica to converge once the partition heals.