CAP & Consistency
Three copies of a shopping cart in two data centres: read and write quorums, what a network partition forces you to choose, and how diverged copies are put back together.
An interactive System Design lesson: 22 steps, about 32 minutes, on a live simulation in your browser.
A shop keeps Ada's cart, cart:ada, on three database replicas in two data centres: replica-1 and replica-2 in dc-a, replica-3 in dc-b. The cart holds one book. Then the link between the data centres fails.
Every machine is still running. dc-a works, dc-b works, each can talk to its own neighbours. They simply cannot reach each other. That is a network partition.
What you will learn
Copies in two places
- Nothing crashed: A partition is not a crash. Both sides are healthy, neither can reach the other, and neither can tell whether the other is dead or just unreachable.
- A write goes to all three copies: In leaderless replication the client sends every write to all N replicas and calls it done after W of them acknowledge. The rest catch up on their own time.
- Reading from the far side
Read and write quorums
- R + W > N: the read always overlaps: If R + W > N, any R replicas and any W replicas share at least one member, so a read always includes a copy of the latest successful write.
- R = 1, W = 1: With R + W ≤ N a read can land entirely on replicas that missed the latest write. It succeeds, quickly, with an old value.
- Drill: the quorum inequality
Partition: choose consistency
- Back to R = 2, W = 2, then the split
- Ada's phone is in dc-b: Choosing consistency means the side of a partition that cannot reach a quorum answers with errors, never with a wrong answer.
- Break it: the minority cannot read either
Partition: choose availability
- Same partition, R = 1 and W = 1
- Two carts, both answered with 200: Choosing availability means both sides of a partition keep answering and quietly disagree. Someone has to reconcile the copies when the partition heals.
Healing and conflicts
- The link returns: last write wins: Last-write-wins turns a conflict into a silent loss: one of two acknowledged writes is discarded, with no error for anyone.
- Read repair makes it permanent: Read repair converges copies as a side effect of reads. It fixes what is read; everything else needs background anti-entropy.
- Siblings: hand both to the reader: Siblings keep every concurrent version and give them to the reader. The database stops losing data by making the application decide.
- The application merges
What CAP says
- What CAP really says: CAP is one question: during a partition, does the side that cannot reach a quorum answer anyway, or refuse?
- PACELC: the cost with no partition: Even without a partition, every consistent read or write waits for replicas that are far away. PACELC names that trade: latency or consistency.
- Consistency models, in plain terms: Eventual, read-your-writes and linearizable are promises about what a reader may see. Stronger promises cost more waiting.
- Where you will meet each choice
- Drill: pick the consistency level
Recap & playground
- Cheat sheet
- Playground