Distributed Systems Core · lesson 1 of 11 · about 32 min
What CAP really says and what it hides: what a partition forces a replica to choose, what “consistent” precisely means (with a checker you can run), why normal days trade latency for consistency, how R and W tune availability per request, how replicas merge after a split, and what happens when you choose availability for money. Tap any for a plain-language card.
The partition
That is the : when a partition happens you can have Consistency or Availability, not both. (It says nothing about the times when there is no partition: that is the next-but-two scene.) The simulation runs 60 ticks with a split from tick 20 to 40, three clients (two on the A/B side, one on C) incrementing and reading a counter, and tallies what each choice costs.
Run CP, then AP with last-write-wins: AP answers everyone, and then loses some acknowledged increments on the heal.
CP: the lone replica refused 20 requests during the split (11% unavailable), and in return no read ever missed an acknowledged write and nothing was lost: 106 increments acknowledged, 106 counted.
Seeded 60-tick simulation: 3 clients, 60% increments / 40% reads, partition ticks 20 to 39. Stale = a read that does not include every acknowledged increment so far.
What does “consistent” mean?
This page contains a real checker. Each trial generates a small history of 3 writes and 3 reads against three replicas with random replication lag, then searches for any single order of the operations that respects real time and in which every read returns the last write. If none exists, the history was not linearizable. Run 400 histories per configuration: how often does each design behave like one copy?
Compare “read any replica” with “read the leader”, and see what acknowledging at a majority changes.
Ack at leader + read any replica: only 13% of histories behave like one copy. In the rest, a read returned a value that no single real-time ordering allows, for example an older write after a newer one had finished. Example: write 1 [2.2–3.0], write 2 [7.5–8.4], write 3 [14.1–15.4], read 0 [3.1–5.5], read 2 [10.2–11.2], read 2 [17.7–20.3].
Brute-force linearizability check (depth-first over valid orders with memoisation) on 400 seeded histories per row: 3 writes of values 1 to 3, 3 reads, random timings. Lag is log-normal around your setting.
PACELC
Three replicas sit in New York, London and Tokyo; you choose the leader and where the user is (real great-circle distances, 200 km/ms fibre, 1.5× route inflation, as in the CDN lesson). A user in Sydney reading “eventually” talks to Tokyo; reading “strongly” may cross an ocean twice. Writes that need a majority add the leader's trip to its nearest peer.
Put the leader in New York and the user in Sydney: the consistent read is more than twice as slow as the nearest-replica read.
From Sydney with the leader in New York: the nearest replica answers in 122 ms but may be about 44 ms behind; the leader answers in 245 ms with the latest value (2× slower). A write that waits for a majority takes 333 ms.
Round-trip times computed from great-circle distance, fibre speed, 1.5× route inflation (illustrative) and 5 ms of equipment. Staleness window ≈ one-way delay from the leader to the nearest follower.
Tunable quorums
Choose the cluster size, R, W, and how the partition splits the replicas. The table tells you who can still work. Notice that no choice makes both sides fully available and consistent: that is the theorem, shown as arithmetic. And note that “CP” and “AP” are really properties of a request, which is why Martin Kleppmann argued against labelling whole databases.
Try N=5, R=3, W=3 and a 3/2 split: the 3-side works, the 2-side is read- and write-dead. Then R=1, W=1.
| Side | Replicas | Can read? | Can write? |
|---|---|---|---|
| Side 1 | 3 | yes | yes |
| Side 2 | 2 | no | no |
R + W = 6 > 5: reads always overlap the latest write. Only the larger side can write, and the smaller side is blocked: consistency bought with availability.
Pure arithmetic: a side with s replicas serves a read if s ≥ R and a write if s ≥ W.
Merging
Two classic examples. A counter keeps a separate count per replica and sums them: increments made on both sides all survive. A set (a shopping cart) merges by union, so an item added on either side survives. The cost is that you must design the operations to fit (a counter that also decrements, or a set with removals, needs more careful CRDTs).
Give side A 40 increments and side B 25, and compare what last-write-wins keeps with what the counter CRDT keeps.
Side A counted 40 and side B 25. Last-write-wins keeps the larger side (40) and throws away 25 acknowledged increments. The counter CRDT keeps a count per side and sums them: 65, exactly what happened.
Counter merge: per-replica counts, summed (a G-counter). Last-write-wins keeps the side with the most recent write (assumed to be the larger one). Cart: set union vs one side's copy.
CP, AP or bounded?
For each system, decide what should happen during a partition, and why. Each answer is worth 20 XP.
Ask: what is the worst thing a stale or duplicated answer can do?
A bank account balance that must never go below zero.
Tip: press 1 to 3 to answer, Enter for the next one.
Who lives by this
Four sources on how real systems and their designers talk about CAP.
PODC 2000 keynote → proof in 2002
Eric Brewer stated the CAP conjecture in a 2000 keynote, and Seth Gilbert and Nancy Lynch proved a formal version in 2002: in an asynchronous network, a system cannot guarantee both consistency (linearizability) and availability (every request to a live node gets a response) when messages can be lost.
GetItem → eventually consistent by default; ConsistentRead optional
DynamoDB's documentation says reads are eventually consistent by default and that you can request a strongly consistent read, which costs more and can fail when a partition makes the leader unreachable. It is a published example of choosing consistency per request.
TrueTime timestamps → Paxos groups → global ACID
Google Spanner offers strongly consistent transactions across continents using Paxos replication and TrueTime (GPS and atomic clocks bounding clock uncertainty). Eric Brewer's 2017 article argues it is technically a CP system that is available enough in practice, because Google's private network makes partitions very rare.
"Please stop calling databases CP or AP" (2015)
Kleppmann's essay argues the CAP labels are too coarse: real systems offer different guarantees for different operations, "availability" in the theorem is stricter than users' meaning, and linearizability, not a vague "consistency", is the property actually lost. He urges describing the specific consistency model and failure behaviour instead.
Interview angle
Six questions, each worth 20 XP. CAP is the most quoted and most misquoted fundamentals topic in design interviews.
Say what the partition does, what each side may answer, and what the system does when the network heals.
What does the CAP theorem say?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Three designs. AP: both sides answer from their copy (overdraft). CP: only the side with a majority serves, so the other side's customers are refused (safe, less available). Bounded allowance (escrow): before the split, give each side a share of the balance it can spend alone, 50 each, so both stay available and the total can never exceed 100. Real systems often accept small overdrafts and reconcile later, because refusing a customer also costs money. The choice is a business one, made on purpose.
Start on AP with 2 sides and 5 withdrawals each, then try the other two.
Every side approved against its own balance of 100: 195 paid out, overdrawn by 95. Money that does not exist is now owed.
Seeded: each request withdraws 10 to 39 from a balance of 100; a side approves a request if its own limit allows it.