The problem: the cable between regions is cut
A fibre fault cuts the link between Snip's Frankfurt and Virginia regions for twenty minutes. Both regions are up, and
users on each side can reach their own. An owner in Berlin edits x7Kp; Frankfurt can't tell Virginia. Snip has to
choose, right now:
- Accept the edit in Frankfurt. Virginia keeps redirecting to the old destination until the link heals: available, but not consistent.
- Refuse the edit until Virginia can be told. Everyone sees the same thing, but Berlin owners get errors for twenty minutes: consistent, but not available.
That forced choice is the CAP theorem.
What CAP says, precisely
The everyday version, "consistency, availability, partition tolerance: pick two", causes most of the confusion. Martin Kleppmann's reading of the formal version is the useful one:
- C means linearizable (08.02 Consistency models), not "consistent" in any looser sense.
- A means every request to a non-failing node gets a non-error response, eventually.
- P isn't really a choice. Networks partition whether you like it or not.
So CAP says: when the network is partitioned, a system can't be both linearizable and fully available. That's it. Eric Brewer, who stated the conjecture, wrote twelve years later that the "2 of 3" formulation "was always misleading", and that since partitions are rare there's little reason to give up C or A when the system isn't partitioned.
Three consequences people miss:
- The choice is per operation, not per database. Snip can stay available for redirects and refuse code claims in the same partition.
- Most systems are neither "CP" nor "AP". A single-leader database with async replicas isn't linearizable (replicas lag) and isn't available on the minority side of a split. Kleppmann's point is that these labels describe almost nothing real; describe the actual guarantees instead.
- It says nothing about the 99.9% of the time with no partition. That's where PACELC comes in.
PACELC: the trade-off you pay every day
Daniel Abadi's extension adds the case that matters most often:
If there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.
Even with a healthy network, keeping replicas consistent means waiting for them. A linearizable write in Snip waits for the other region to confirm, about 100 ms across the Atlantic. Answering from the local replica is fast but may be stale. Every replicated system makes this trade on every request, which is why it shapes designs far more than partitions do.
| System (default settings) | During a partition | Normally | PACELC |
|---|---|---|---|
| Dynamo, Cassandra, Riak | Availability | Latency | PA/EL |
| VoltDB/H-Store, Megastore | Consistency | Consistency | PC/EC |
| BigTable, HBase | Consistency | Consistency | PC/EC |
Systems with tunable settings move along this: raising read and write quorums in Cassandra buys consistency with latency (08.04 Replication and quorums).
Snip, operation by operation
| Operation | Partition (PA or PC) | Normally (EL or EC) | Why |
|---|---|---|---|
| Redirect | A: answer from the local region | L: local cache and replica | A redirect to a minutes-old destination beats an error |
| Edit a destination | A: accept locally, reconcile later | L: async copy to the other region | Edits are rare and per-owner; last edit wins, with versions (05.06 Clocks, skew and ordering IDs) |
| Claim a custom code | C: refuse in the minority region | C: route to the code's home region | Two owners must never both get summer |
| Charge for Pro | C | C | Money |
Seen in production
Eric Brewer
2012CAP, revisited
Brewer writes that the "2 of 3" formulation was always misleading because it oversimplified the tensions between the properties, and that CAP prohibits only a small part of the design space: perfect availability and consistency in the presence of partitions, which are rare. Designers still choose between consistency and availability when partitions are present, and the choice can happen many times within one system, at very fine granularity.
What we foundThe author of CAP calls 'two of three' misleading: the C-or-A choice is about partitions, and can be made at fine granularity.
CAP Twelve Years Later: How the 'Rules' Have Changed (IEEE Computer, republished by InfoQ)infoq.com ↗Daniel Abadi
2012PACELC
Abadi rewrites CAP as PACELC: if there is a partition, how does the system trade off availability and consistency; else, in normal operation, how does it trade off latency and consistency. The default versions of Dynamo, Cassandra and Riak are PA/EL, giving up consistency both for availability and for lower latency, though their settings let users change the trade by raising R + W. Fully ACID systems such as VoltDB/H-Store and Megastore are PC/EC, as are BigTable and HBase.
What we foundThe latency-versus-consistency trade-off applies all the time, not just during partitions.
Consistency Tradeoffs in Modern Distributed Database System Design (IEEE Computer, February 2012)cs.umd.edu ↗Martin Kleppmann
2015CAP definitions
Kleppmann points out that consistency in CAP actually means linearizability, and availability means every request received by a non-failing node must get a non-error response. By those definitions many systems are neither consistent nor available under CAP, so the labels say little; he argues for describing the actual guarantees instead.
What we foundCAP's C is linearizability and its A is strict; many real systems are neither CP nor AP.
Please stop calling databases CP or APmartin.kleppmann.com ↗An interviewer asks: 'Is your Postgres primary with two async read replicas CP or AP?' What's the best answer?
Recap
Interview questions
Explain the CAP theorem. What's commonly misunderstood about it?