CAP Theorem

Pradeep P

Aug 31

3 min read

Series: Modern System Design · Layer 3 — Reliability

Layer 3 · Post 13 of 14

← Previous: Quorum → Next: Consistency Models

Layer 3 — Reliability · Post 38 of 88

CAP says that during a network split, a distributed system must choose: stay available, or stay consistent. You cannot fully have both.

What you'll learn

What C, A, and P actually mean — and that P is not optional on a real network
The only honest question in a partition: refuse writes, or risk divergence
Why "we are CA" is a wrong interview answer, and what to say instead

The idea in one minute

CAP (Brewer / Gilbert–Lynch): on a network partition, you cannot have both linearizable consistency and availability for every request.

C (consistency here): every read sees the latest write (more precisely: the system behaves like one copy).
A (availability): every request to a non-crashed node gets a (non-error) response.
P (partition tolerance): the network can split; you still have to pick a behavior.

{ Node A } ~~~~ cut ~~~~ { Node B } User hits A: A can answer with old/divergent data (AP) or A can error / refuse writes (CP)

You already met this as quorum: the minority stops (CP-ish). Dynamo-style "write to whoever I can see" is AP-ish.

Why it matters

Interviews love CAP because it is a forced product choice during failure, which is Layer 3's theme. "Our system is consistent and available" is true until the cable is cut. Then you are lying about one of them.

It is also overused. CAP does not say you cannot have a good database. It says when the network splits, pick: wrong/split data, or some users get errors. After the split heals, you still have latency vs consistency (PACELC) — but first get the partition story right.

How it works

P is given. You do not "choose CA" once you replicate over a network. Single-node Postgres has no replica partition to tolerate.

CP: require quorum / a leader. No majority, no write. etcd, ZooKeeper, Patroni, MongoDB majority write concern. The minority gets errors. Data does not fork.

AP: write to the nodes you can reach. Cassandra W=1, classic Dynamo, DNS, caches. Stay up; reconcile later (LWW, CRDTs). Readers may see stale or conflicting values.

A bank transfer is CP. A "like" counter can be AP. Do not put the whole product in one costume.

When there is no partition, extra replica waits are still latency (PACELC). That is Post 34's sync replication, not a CAP loophole.

A simple example

Two-region shopping cart.

CP: cart writes go to a global primary (or Spanner-style majority). If the regions cannot talk, one region rejects add-to-cart. Angry users, one cart.

AP: each region writes locally. Split lasts 10 minutes. User adds items on both phones via different regions. Merge: duplicate items, or last-write-wins drops a line. You stayed available and bought a merge policy.

Say that trade out loud. That is the interview.

Common mistakes

"We're CA." You either are not partitioned (single node) or you have not failed yet.

Treating CAP as three checkboxes you pick two of in normal operation. C and A are in tension under P.

Calling every NoSQL "AP" and every SQL "CP." Mongo can be majority (CP-ish). Cassandra can be QUORUM. Postgres with async replicas is not magically consistent on failover (Post 34).

Using CAP to avoid SLOs. "We're AP" does not make silent data loss fine. Define repair. The user who got 503 (CP) vs a stale 200 (AP) are both reliability stories.

How this shows up in real systems

etcd, ZooKeeper, Consul, Raft, Spanner, Cockroach: CP-leaning; minority stalls.
Cassandra, DynamoDB, Riak, DNS: AP-leaning knobs; conflicts or eventual consistency.
Redis Cluster: slots and majority of masters; partitions are messy — know the docs before you claim HA.
Kafka: availability vs acks=all + ISR — a quorum of in-sync replicas, not "always take the produce."

Recap

Under a partition, choose consistency (refuse) or availability (risk divergence).
P is not optional once you replicate over a network.
Next: the menu of consistency models — what "C" means when you are not in a textbook partition.