Nabid In Motion Nabid In Motion

Study interactive :: Progress tools open in the Study Hub reader.

17. CAP Theorem

Once you have data spread across multiple machines, you bump into a fact of life that no engineering can avoid. It's called the CAP theorem. It's small. It's important. People get it wrong constantly.

The three letters

In a distributed system, you have three properties:

What's a partition

A network partition is when some nodes can't talk to others, even though both are up. Maybe a cable failed. Maybe a region lost connectivity. Maybe the load balancer dropped them. From inside, each side sees the other as "down".

Node ANode B

In a real distributed system, partitions happen. Not "if". "When". They're rare on a single-data-center network. They're common across continents. So P is forced once you accept partitions as inevitable.

The useful statement (see Brewer's later clarifications): during a partition, choose C or A. You do not freely pick "any two of three" as a lifestyle; you face a C-vs-A decision while P is already on.

CP: prefer consistency

If the network is partitioned, refuse to serve queries that might return stale data. Better to return an error than the wrong answer.

error cannot reach peersUserNode A

Used by: banking systems, etcd, ZooKeeper, Spanner (Google's globally-consistent DB).

When this is right: money. Inventory. Locks. Anything where a wrong answer costs you.

AP: prefer availability

If the network is partitioned, keep serving. Some users might see stale data, but the system stays up.

best guess maybe staleUserNode A

Used by: DNS, Cassandra, DynamoDB (default mode), most CDNs, most social media products.

When this is right: a "like" count being briefly wrong is fine. A web page being unreachable is not.

The CAP triangle (a famous picture)

ConsistencyAvailabilityPartition toleranceCP systemsAP systems

The "CA" corner is what single-machine systems give you. As soon as you go distributed, P is forced on you. The corner becomes a choice between CP and AP.

A real example

Two database nodes, replicated. User updates their profile photo on Node A. Network breaks before Node B sees it.

Node BNode AUserNode BNode AUsernetwork breaksAP returns old or CP refusesset photo to Xconfirmedread photo

Both are reasonable engineering decisions for different systems.

PACELC: the more accurate version

CAP only talks about partitions. The Yale CS professor Daniel Abadi pointed out: even when the network is fine, there's still a trade-off. It's called PACELC.

If Partition, then Availability or Consistency. Else, Latency or Consistency.

In other words: even with a healthy network, getting strong consistency costs latency (more nodes to talk to, more rounds of coordination). And to get low latency, you might serve a slightly stale read.

System P → E →
DynamoDB (default) AP EL (favor latency over consistency in normal times)
Cassandra AP EL
Spanner CP EC
MongoDB CP-ish EC
Postgres replica reads CP (with primary) or AP (with replica) depends on config

PACELC is the better mental model. CAP is what people memorize.

What "eventually consistent" really means

This phrase shows up everywhere. It means: if no new writes happen, every replica will eventually agree. "Eventually" is unbounded. In practice it's milliseconds, sometimes seconds.

  Write to Node A: photo = X     (everyone else still says photo = old)
  10 ms later:    Node B has it.
  50 ms later:    Node C has it.
  200 ms later:   Everyone in the cluster agrees.

This is fine for likes, view counts, follower counts. Not fine for bank balances.

Some systems offer read-your-own-writes consistency, after you write, your own subsequent reads see the new value, even if other users haven't yet. A useful middle ground.

Strong consistency models

If you want CP, there's a hierarchy of how strict:

The stronger you go, the slower the system. Linearizable is what etcd and ZooKeeper sell. Causal is what some social networks use to make sure "Alice posted, Bob replied" is never seen in the wrong order.

How real systems actually work

Most systems are tunable. Cassandra lets you choose, per query, how many replicas have to agree:

   QUORUM   = strict, slower
    weak consistency
   ALL      = strongest, slowest, fragile to failures

A typical write/read combo:

   write to QUORUM, read from QUORUM

QUORUM means a majority of replicas (e.g. 2 out of 3). If both writes and reads use QUORUM, you're guaranteed to read your own writes. This is the practical compromise most apps land on.

A practical mental model

When you're picking a database or designing a system:

  1. Will partitions happen? Yes. So you choose C or A.
  2. What does wrong data cost? If it's money, pick C. If it's a like count, pick A.
  3. What does downtime cost? If the product can't be down at all, pick A.
  4. Even without partitions, do you care more about latency or strict ordering? That's the PACELC half.

You almost never have to pick "the world's most consistent database". You usually have to pick "what should this part of the system do under this kind of failure?". A typical app uses Postgres (CP) for the orders table, Redis (AP-ish, cache) for sessions, and an object store (AP) for blobs.

Things to remember

Going deeper