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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.