Notesdistributed🌱 seedling
CAP Theorem
Also: CAP · Brewer's Theorem · Brewer's Conjecture
When a network partition happens, a replicated system must give up either linearizability or availability (every request to a non-failing node gets a response). It says nothing about the system when there is no partition.
Why it exists
Large replicated services kept relaxing consistency, and CAP names the one choice they can't avoid: when replicas can't talk, a request must be refused or answered from possibly stale state.
How it works
- A partition separates replicas. A request reaches one side.
- Choose C: refuse or block until the partition heals. Never wrong, not available.
- Choose A: answer from local state. Always answers, possibly stale.
- A partition is, in practice, a timeout. At that moment the node decides between failing the request and proceeding without its peers. Good designs detect partitions, run a restricted partition mode, then reconcile.
Trade-offs
| CP behaviour | AP behaviour |
|---|---|
| minority side errors or blocks | every node answers |
| no anomalies | stale reads, conflicting writes to merge |
| simpler application logic | needs conflict resolution and recovery code |
In practice
- The choice can be per operation: browse a catalogue AP, run checkout CP.
- NATS JetStream (Jepsen, 2025): docs claimed both linearizability and "always available"; Jepsen noted that's impossible in an asynchronous network.
Pitfalls
- "Pick two of three." Partitions aren't optional, so "CA" just means "breaks when the network does". The slogan hides that C and A are only traded during a partition.
- Labelling databases CP or AP. C means only linearizability and A means only total availability; most real systems are neither in the theorem's sense.
- Ignoring latency, which CAP doesn't cover: see PACELC.
Connections
- Part of
- Distributed Systems
- Learn first
- LinearizabilityNetwork Partition
Recall
These cards are also in your review deck, scheduled with spaced repetition.