CAP Theorem
CAP falls out of one physical fact: when a network partition splits your replicas into groups that cannot talk, a write accepted on one side is invisible to the other side until the link heals — so the instant a client reads from the far side, the system must either hand back possibly-stale data (stay Available) or refuse to answer until it can confirm it is current (stay Consistent). The theorem is not a menu of three things you casually pick two of; it is a statement about that one forced choice during a partition.
The three properties, stated precisely
The loose "pick 2" slogan hides how narrowly each word is defined in the Gilbert–Lynch formalization (the 2002 proof of Brewer's conjecture). Get these definitions wrong and every later argument goes wrong.
- Consistency (C) here means linearizability: there is a single, up-to-date logical copy, and every read returns the most recent committed write (or an error). This is not the C in ACID — ACID's C is about invariants, CAP's C is about a global order of reads and writes.
- Availability (A) means every request that reaches a non-failing node returns a non-error response in finite time. It is a binary, theoretical property — distinct from the ops sense of "99.9% uptime." A CP system can be down for a request and still be "highly available" in the ops sense the rest of the time.
- Partition tolerance (P) means the system keeps functioning despite arbitrary messages being dropped or delayed between nodes. On any real network — where a GC pause, a saturated NIC, or a cross-AZ blip all look identical to a partition — P is not optional. It is a fact of the environment, not a design choice.
Because P is forced on you, the real theorem reads: during a partition, a distributed system must sacrifice either Consistency or Availability. CA is incoherent as a distributed choice — a system that assumes partitions never happen has simply not decided what it does when one occurs, and it will then drop C or A anyway. A single-node database is "CA" only in the trivial sense that it is not distributed.
A worked partition trace
Three replicas N1, N2, N3 hold one key, stock:sku42, with replication factor N=3. Initially all three agree the value is 5. A partition then isolates N3 from the majority side {N1, N2}. Follow the same events under a CP configuration (quorum: W=2, R=2, so R+W>N guarantees read/write overlap) and an AP configuration (W=1, R=1).
| t | Event | CP system (W=2, R=2) | AP system (W=1, R=1) |
|---|---|---|---|
| t0 | Steady state | N1=N2=N3=5 | N1=N2=N3=5 |
| t1 | Partition: {N1,N2} | {N3} | link to N3 down | link to N3 down |
| t2 | Client A writes stock=4 (an order is placed) | Majority acks (N1,N2 = 2 ≥ W). Commit succeeds. N3 still 5. | Nearest replica acks locally. Succeeds. N3 still 5. |
| t3 | Client B reads via the stranded N3 | N3 cannot assemble R=2 (it is alone). Returns error/timeout — refuses to serve. C preserved, A sacrificed on this side. | N3 answers from its local copy: returns 5 (stale). A preserved, C sacrificed — the store just oversold the item. |
| t4 | Partition heals | N3 rejoins, replays the log, converges to 4. No data was ever wrong. | Anti-entropy / read-repair pushes 4 to N3. If both sides had taken conflicting writes, version vectors or last-write-wins must reconcile them. |
The fork is entirely at t3. Notice the majority side {N1,N2} keeps serving consistent reads in both configurations — the sacrifice is localized to the minority partition. That is why "CP means unavailable" is too coarse: it is unavailable only where it cannot prove freshness.
Real CP and AP datastores
The choice is baked into products (and, in tunable stores, into each request):
- CP — sacrifice availability on the minority side to never return stale data: etcd and ZooKeeper (Raft/ZAB — only the majority partition keeps a leader; the minority stops serving), HBase, MongoDB with majority write/read concern, Google Spanner (linearizable via Paxos + TrueTime, engineered to keep partitions rare so it feels always-up). These back config stores, leader election, locks, and unique-constraint systems.
- AP — keep serving on every reachable node and reconcile later: Cassandra, Amazon DynamoDB, Riak, CouchDB, and DNS. They accept writes on both sides of a partition and resolve divergence afterward with hinted handoff, read-repair, last-write-wins, or version vectors/CRDTs.
- Tunable: Cassandra and Dynamo are AP by default but let you dial per query. Set R+W>N (e.g. R=2, W=2, N=3) and you buy overlap-guaranteed strong reads — at the cost of unavailability on the minority side during a partition. The CAP position is per-operation, not a fixed brand.
Pitfalls
- Treating "pick 2" as a free trade in normal operation. When there is no partition, you get C and A together. The trade only bites during a partition, so the honest question is "what do we do when a partition hits," not "which two do we want."
- Claiming "CA" for a replicated system. Any product marketed as CA is really CP or AP with the partition behavior unspecified — it will still drop C or A when the network splits, you just won't have chosen how.
- Confusing CAP-C with ACID-C. They share a letter and nothing else. A store can be ACID-consistent (enforces invariants locally) yet not linearizable across replicas.
- Reading "Availability" as uptime. CAP availability is the all-or-nothing property that every non-failing node answers. A CP system that occasionally refuses the minority side can still hit 99.99% ops availability.
- Assuming partitions are exotic. Long GC pauses, overloaded links, misconfigured firewalls, and rolling deploys all present as partitions. Jepsen has repeatedly shown "consistent" stores losing data under partitions they claimed to handle — the failure mode is common, not rare.
- Forgetting the normal-case latency cost. CAP is silent about the partition-free case, but strong consistency still costs you quorum round-trips every day. That is exactly what PACELC adds: Else (no partition), you still trade Latency vs Consistency.
When to choose CP vs AP
Signals that point to CP (consistency-first): a stale read causes real, hard-to-undo harm — double-spending a balance, overselling inventory, two clients both winning a lock or a leader election, violating a uniqueness constraint. You gain correctness by construction. You pay with unavailability on the isolated side during a partition and higher write latency every day (quorum round-trips). Reach for etcd/ZooKeeper, MongoDB majority, or R+W>N in a tunable store.
Signals that point to AP (availability-first): serving something beats serving nothing and staleness is either tolerable or mergeable — shopping carts, social feeds, session and preference stores, product catalogs, metrics, DNS. You gain uptime and low latency on every replica. You pay with conflict-resolution machinery (LWW, version vectors, CRDTs) and application code that must tolerate reading slightly old or divergent data. Reach for Cassandra, DynamoDB, or Riak.
The decision rule: choose CP when a wrong answer is worse than no answer; prefer AP when no answer is worse than a slightly wrong answer. And because most real systems are mixed, apply it per data domain, not per company — the same shop can run inventory-decrement on CP and the browse feed on AP. The moment you also care about the everyday, partition-free latency-vs-consistency trade, graduate to PACELC.
Takeaways
- P is forced by the network, so CAP reduces to one honest question: during a partition, do we return stale (AP) or refuse (CP)?
- The sacrifice is local — only the side that cannot prove freshness gives up C or A; the majority keeps serving.
- CAP-C is linearizability and CAP-A is "every non-failing node answers" — neither means what the ACID/uptime words suggest.
- Decide per data domain: CP where a wrong answer is dangerous, AP where unavailability is; tunable stores let you set it per request via R+W vs N.
Sources: Eric Brewer's PODC 2000 keynote (the CAP conjecture) and his 2012 retrospective "CAP Twelve Years Later: How the Rules Have Changed" (IEEE Computer); Seth Gilbert & Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" (2002, the formal proof); Martin Kleppmann, Designing Data-Intensive Applications, ch. 5 & 9; the Amazon Dynamo (2007) and Google Spanner (2012) papers; and Kyle Kingsbury's Jepsen analyses for the real-world failure modes. Re-authored/Deepened for this guide.
🤖 Don't fully get this? Learn it with Claude
Stuck on CAP Theorem? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **CAP Theorem** (System Design) and want to truly understand it. Explain CAP Theorem from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **CAP Theorem** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **CAP Theorem** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **CAP Theorem** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.