CAP Theorem

CAP Theorem

The CAP theorem is one of the most quoted, and most misquoted, ideas in distributed systems. Its popular slogan, "pick two of three", is misleading. What it actually says is narrower and more useful:

Understanding why, and what it means for real databases, lets you justify storage choices properly in design discussions.

The three properties, defined precisely

• Consistency (C): here it means linearizability. The system behaves as if there were a single copy of the data. Once a write completes, every subsequent read, from any node, returns that write or a later one.
• Availability (A): every request to a non-failed node gets a (non-error) response, without waiting indefinitely.
• Partition tolerance (P): the system keeps operating even when the network drops or delays messages between nodes, splitting them into groups that can't communicate.

CAP's "C" is not ACID's "C". ACID consistency means transactions preserve integrity rules, such as constraints and invariants. Mixing up the two is a common interview mistake.

Why "pick two" is the wrong framing

Networks do partition: switches fail, cables get cut, cloud zones lose connectivity, and long GC pauses make nodes look unreachable. A distributed system can't opt out of partitions. So P isn't a choice. The real question is what the system does when a partition happens:

            partition
  Node A  ─────╳─────  Node B
  (client writes x=2)   (still has x=1; a client reads from B)

Node B has two options:

• Choose consistency (CP): refuse to answer, or return an error or a timeout, because it can't confirm it has the latest value. Correct, but unavailable for that request.
• Choose availability (AP): answer with x = 1. It stays available, but the answer is stale, and it's not linearizable.

There's no third option. B can't know about a write it can't hear about. That's the whole theorem. And when there's no partition, a system can be both consistent and available. "CA" only describes a system that isn't distributed, or that simply fails entirely during a partition.

CP and AP in practice

CP-leaning behaviour: during a partition, the side without a majority stops accepting writes, and sometimes reads.

• Consensus systems: etcd, ZooKeeper, Consul. They're used for leader election, locks and configuration, exactly where two conflicting answers would be disastrous.
• MongoDB with majority write and read concerns: a primary that loses contact with the majority steps down.
• Spanner, CockroachDB: consensus per data range.
• Good for: balances, inventory counts that mustn't oversell, unique usernames, leader election.

AP-leaning behaviour: every reachable node keeps serving. Replicas may diverge and are reconciled later (eventual consistency).

• Cassandra, DynamoDB (default reads), Riak, CouchDB, and DNS.
• Good for: shopping carts, social feeds, likes and view counts, session data, product catalogues. A briefly stale answer beats an error.

Many systems are tunable per operation. Cassandra's consistency levels (ONE, QUORUM, ALL), DynamoDB's optional strongly consistent reads, and MongoDB's read and write concerns let you choose CP-like or AP-like behaviour per query. So "Cassandra is AP" really means "Cassandra is usually configured for availability".

PACELC: the everyday trade-off

Partitions are rare. Replication's costs are constant. PACELC extends CAP to cover normal operation:

Keeping replicas strongly consistent means waiting for coordination (a quorum or consensus round trip, possibly across regions) on every write, and sometimes on reads. That's a latency cost paid all the time, not just during failures.

Using CAP in a design discussion

Don't label the whole system CP or AP. Decide per data type and operation:

• "Payment and inventory decrements need linearizable writes. I'll use a consensus-backed or single-leader store with majority acknowledgement, and accept that some requests fail during a partition."
• "The activity feed and like counts can be eventually consistent. I'll prefer availability and low latency, and reconcile later."
• "User sessions: availability matters more. A stale session read is harmless."

It also helps to name the consistency model you need between the extremes: read-your-writes for a user's own profile, causal consistency for comment threads. See Replication & Consistency.

Follow-up questions this topic invites — and their answers

Q: Can a distributed system be CA? A: Not in a meaningful sense. Partitions can't be prevented, so a system that claims CA simply hasn't defined its partition behaviour, which in practice means it becomes unavailable or inconsistent when one occurs. A single-node database is "CA" only because it isn't distributed.

Q: Is CAP consistency the same as ACID consistency? A: No. CAP consistency is linearizability: all nodes act like one up-to-date copy. ACID consistency means a transaction moves the database from one valid state to another, preserving constraints and invariants.

Q: Is MongoDB CP or AP? A: It depends on configuration. With a single primary and majority write and read concerns, it behaves as CP: a primary without a majority steps down, and writes fail until a new primary is elected. Reading from secondaries with weaker concerns trades consistency for availability and latency.

Q: Why does PACELC matter more day to day than CAP? A: Because partitions are rare, but the latency cost of strong consistency is paid on every request in normal operation. Choosing between low latency and strong consistency is the decision you actually live with.

Q: How would you apply CAP to an e-commerce system? A: Inventory reservation, payments and order creation need strong consistency, so accept brief unavailability during partitions. Catalogue browsing, recommendations, reviews and carts favour availability, since stale data is acceptable and reconcilable. Different components use different stores or settings.