# DDIA Ch. 10: CAP made countable — a partition costs you 12 refusals or 3 conflicts ## Concept You do not "pick 2 of 3." Two regions, R1 and R2, each a client and a replica, joined by one inter-region link. The link goes **down** — a partition, an event imposed on you, not a setting you toggled. Replay the **same** fixed workload against two deployments of the same two regions: **(a) CP** — single-leader, the leader in R1; and **(b) AP** — multi-leader, both regions write locally. While partitioned, the CP deployment keeps every replica consistent but R2 (the non-leader side) must **refuse** every write and linearizable read — **12 of 20** requests turned away, zero divergence. The AP deployment serves **every** request at both regions — **0** refusals — but the two states drift apart, and on heal **3 keys** conflict and need reconciliation. Same partition, same workload; you chose availability **XOR** consistency, and each choice cost something countable. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 10 — *Consistency and Consensus*, §"The Cost of Linearizability" / §"The CAP theorem" / §"The Unhelpful CAP Theorem". The claim under test, paraphrased: > When a network partition occurs, a system must choose between linearizability > and availability — it cannot have both while the partition lasts. The book is emphatic that CAP is *not* "pick two of Consistency, Availability, Partition tolerance." Partitions are a fault you cannot opt out of; the theorem only forces a choice — **consistent OR available** — *while a partition is happening*. Here you build the two regions, cut the link, and measure both costs. ## Prerequisites The surprise is that "partition tolerance" is not a thing you choose — the partition chooses you, and then you pay one of two measurable bills. Each line notes where it shows up. 1. **Linearizability** — the strong-consistency model where every read returns the most recent write, as if there were a single copy. A follower cut off from the leader cannot promise this, which is *why* R2 must refuse linearizable reads in the CP run. 2. **The CAP theorem's actual statement** — under a network **P**artition you get **C**onsistency **or** **A**vailability, not both; it says nothing about a partition-free system. It shows up as the two deployments giving up opposite things during the same outage. 3. **Single-leader vs multi-leader replication** — one writable copy (all writes funnel to the leader) versus many (every region writes locally). This *is* the CP/AP switch: single-leader ⇒ CP, multi-leader ⇒ AP. 4. **"CA" is not a real operating point** — you can't choose to not tolerate partitions; a partition still happens, and a "CA" system just fails when it does. There is no third column to pick, only C-or-A *once the partition is here*. ### Where to learn the prerequisites - **Linearizability & the CAP theorem (#1, #2, #4):** DDIA §"Linearizability", §"The Cost of Linearizability", §"The CAP theorem", and §"The Unhelpful CAP Theorem"; Gilbert & Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" (2002) for the formal proof; Brewer, "CAP Twelve Years Later" (2012) for why "2 of 3" misleads. - **Single- vs multi-leader (#3):** DDIA Ch. 6 §"Leaders and Followers" and §"Multi-Leader Replication". If only one idea carries the result, make it this: **the partition is not a choice.** Everything else follows — because you cannot decline the partition, the only decision left is which of consistency or availability to surrender while it lasts. ## Environment Deterministic, so the counts reproduce exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker, no deps - No real network: the two regions, the link, and the partition are simulated in one process, so the result is fixed every run - Fixed workload (23 requests: 3 at R1, 20 at R2), RNG seeded (`Random(1010)`) so R2's request interleaving reproduces byte-for-byte ## Mental model A partition is an **event imposed on you**, not an option. Once the link is down, the same two regions behave differently depending only on how writes are routed. - **CP — refuse service on the wrong side to stay consistent.** The leader is in R1. R2 is a follower; with the leader unreachable it *cannot* accept writes (no one to order them) and *cannot* serve linearizable reads (it can't confirm it holds the latest). So it refuses them. It may still answer **stale** reads from its own frozen copy. Consistency is preserved — only the leader ever wrote, so nothing diverges — at the cost of availability on R2. - **AP — serve everywhere and reconcile later.** Both regions are leaders; each answers every request from its local replica. Nothing is refused. But each side writes without the other seeing it, so their states diverge; on heal, any key written on **both** sides with different values is a conflict to reconcile. Both deployments face the **identical** partition and replay the **identical** workload. The whole thing is one script, `code/cap_partition_tradeoff.py`. ## Setup ``` cd study/ddia/ch10/code python3 cap_partition_tradeoff.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — the partition and the workload **Predict.** The link between R1 and R2 is cut, and 23 requests arrive during the outage: 3 at R1, 20 at R2. Is "partition tolerance" something either deployment gets to *decline* — can a well-designed system just avoid this situation? **Observe.** ``` ====================================================================== CAP, made countable -- two regions, one link, the SAME workload twice ====================================================================== R1 = {client, replica} R2 = {client, replica} link: DOWN (partition) workload: 23 requests during the partition (3 at R1, 20 at R2) The partition is NOT a setting we chose -- the link is cut. Both deployments below face the identical outage; they differ only in what they give up while it lasts. ``` The partition is not on the menu. It has already happened to *both* deployments. The only thing left to decide is what to give up while it lasts. ### Step 2 — CP: count the refusals **Predict.** Single-leader, leader in R1. Of R2's 20 requests during the partition, how many must be **refused**? (R2's stream is 7 writes, 5 linearizable reads, and 8 stale-tolerant reads.) And how many keys will have **diverged** when the link heals? **Observe.** ``` ---------------------------------------------------------------------- (a) CP -- single-leader, leader in R1 => choose CONSISTENCY ---------------------------------------------------------------------- R2 is a follower cut off from the leader. It CANNOT serve writes or linearizable reads, so it refuses them; it still serves stale reads. R2 requests refused (writes + linearizable reads): 12 of 20 R2 requests served (stale-tolerant reads only): 8 of 20 example stale read at R2: read('c') -> ('v0', v0) (leader has moved on; R2 is behind) keys diverged (need reconciliation on heal): 0 COST: 12 refused requests. availability sacrificed on the minority side; consistency intact. ``` **12 of 20 refused, 0 diverged.** The 7 writes and 5 linearizable reads all need the leader, which R2 can't reach, so they're turned away; only the 8 stale reads are served — and those come back **behind** (`c` still reads `v0` while the leader has moved on). Consistency is perfect precisely *because* R2 refused to write. ### Step 3 — AP: count the conflicts **Predict.** Same partition, same 23 requests, but now multi-leader — both regions write locally. How many requests are refused this time? And after the link heals, how many keys will have **diverged** and need reconciliation? (R1 wrote `x, y, z`; R2 wrote `x, y, z, w, a, b, c`.) **Observe.** ``` ---------------------------------------------------------------------- (b) AP -- multi-leader, both regions accept writes => choose AVAILABILITY ---------------------------------------------------------------------- Every request is served locally at whichever region issued it. Nothing is refused -- but the two replicas drift apart. requests refused: 0 of 23 requests served: 23 of 23 keys diverged (need reconciliation on heal): 3 -> ['x', 'y', 'z'] key 'x': R1 has ('r1', v1) R2 has ('r2', v1) <- conflict key 'y': R1 has ('r1', v1) R2 has ('r2', v1) <- conflict key 'z': R1 has ('r1', v1) R2 has ('r2', v1) <- conflict COST: 3 conflicting keys to reconcile. consistency sacrificed; availability intact. ``` **0 refused, 3 diverged.** Full availability — every request answered — but `x`, `y`, and `z` were each written on *both* sides during the partition, so both hold version 1 with different values (`r1` vs `r2`). The count of conflicts is exactly the keys the two regions touched in common. `w, a, b, c` were written only at R2, so they don't conflict. ### Step 4 — the takeaway **Predict.** Line the two costs up. Was there any deployment that paid *neither* cost — no refusals **and** no divergence — during the partition? **Observe.** ``` ====================================================================== TAKEAWAY ====================================================================== CP: refused = 12 diverged keys = 0 AP: refused = 0 diverged keys = 3 The partition happened to BOTH deployments -- it was never optional. You did not 'pick 2 of 3'. You chose, WHILE partitioned, between refusing service (CP) and diverging (AP), and each cost is countable. ``` **No free deployment exists.** CP paid 12 refusals to keep 0 divergence; AP paid 3 conflicts to keep 0 refusals. One of the two bills always comes due while the link is down — that is the whole content of CAP. ## What you should see - **Step 1:** the partition is imposed on both deployments — 23 requests arrive during an outage neither chose. - **Step 2 (CP):** **12 of 20** R2 requests refused (7 writes + 5 linearizable reads); 8 stale reads served (one returns `v0`, behind the leader); **0** keys diverged. - **Step 3 (AP):** **0** of 23 refused; **3** keys (`x, y, z`) diverged and need reconciliation. - **Step 4:** CP = {refused 12, diverged 0}; AP = {refused 0, diverged 3}. No deployment paid neither cost. ## Why From first principles: while the link is down, R2 is a node that has lost contact with the rest of the system. Ask it to honor a write or a linearizable read and it is trapped between two things it cannot both do — (i) **answer with the latest value**, which it may not have, since a newer write could exist on the far side of the partition it cannot see; and (ii) **answer at all**. It can guarantee at most one. If it insists on (i), correctness, it must sometimes refuse to answer — that is CP, and the refusals are the 12 requests R2 turned away. If it insists on (ii), always answering, it must sometimes answer with a value that another region has concurrently overwritten — that is AP, and the divergence is the 3 keys both sides wrote. There is no third door, because the node genuinely does not know what happened on the other side of the cut. Gilbert & Lynch's proof is exactly this impossibility formalized; the script just makes each horn of it countable. Notice the two costs are duals of the *same* fact. CP refuses R2's writes, so only the leader ever mutates state, so on heal there is nothing to reconcile — 0 divergence is *bought* with 12 refusals. AP accepts every write, so nothing is refused, so both sides advance `x`, `y`, `z` independently — 0 refusals is *bought* with 3 conflicts. Move the cost from one column and it reappears in the other; you never make it disappear, because the partition — the thing that severed R2 from the truth — was never yours to remove. **The boundary — bring the link UP and you get both.** CAP forces the choice *only during a partition*. With the link healthy, R2 reaches the leader on every request: the CP deployment serves all 20 of R2's requests linearizably (0 refusals) *and* keeps 0 divergence — consistency and availability at once. The trade-off is not a permanent property of the system; it is a property of the *failure mode*. And "available" here has a specific technical meaning: every **non-failing** node returns a non-error response. It does not mean "fast," and it does not promise the node that *is* partitioned away stays up — only that nodes still running keep answering. ### Go deeper 1. **PACELC — the else-case.** CAP only speaks about the partition. PACELC adds: **E**lse (no partition), you still trade **L**atency against **C**onsistency. Make R2's linearizable reads in the *healthy* case pay a round-trip to the leader and measure the added latency; that is the "EL vs EC" knob CAP is silent about, and it's the trade you actually pay 99.9% of the time. 2. **Reconcile the AP conflicts.** Add a merge step on heal — last-write-wins by region-stamped timestamp, then a version-vector sibling set — and watch LWW silently drop one region's write while the version vector preserves both as conflicts for the app to resolve (the Ch. 6 CRDT/sibling machinery). 3. **Shrink the minority.** Make R2 a 1-node minority of a 5-node CP cluster whose other 4 nodes are on R1's side. Predict which side keeps serving writes (the majority that can still form a quorum) and confirm the minority is the side that must refuse — CP availability follows the quorum, not the geography.