CAP Theorem

Chapter 01 · Foundations

CAP theorem says that in a distributed system you can pick at most two of consistency, availability, and partition tolerance. In real life partitions are unavoidable, so you are really choosing between consistency and availability.

The most quoted, most misunderstood theorem in distributed systems

You have probably heard "CAP theorem" thrown around in design discussions. Half the time the speaker is using it correctly. The other half they are wielding it like a magic spell to dismiss an idea. Let's actually understand it.

CAP stands for Consistency, Availability, and Partition tolerance. The theorem says you can pick at most two. The classic mistake is to think you get to choose freely. You do not. Network partitions happen whether you like them or not, so partition tolerance is forced on you. The real choice is between consistency and availability when a partition occurs.

What each letter means (precisely)

Consistency (the C). Every read returns the most recent write, or an error. All nodes see the same data at the same time. This is "linearizability", a strict definition. It is not the same as the C in ACID, which is a different (database-level) concept. Confusing.

Availability (the A). Every request gets a non-error response. The system is responsive. It does not guarantee the response has the latest data, only that there is a response.

Partition tolerance (the P). The system continues to operate despite network failures between nodes. Some messages are dropped or delayed.

When the network splits, each node has to choose: respond with possibly stale data (AP) or refuse to respond (CP).

Try it: partition the network, choose your side

Toggle the partition. Pick CP or AP. Send writes and reads. Watch what each strategy does when the network splits.

Mode:

Why partition tolerance is not optional

This is the part most articles get wrong. People talk about "CA" databases. There is no such thing in a real distributed system. The moment you have multiple machines connected by a network, partitions can happen. They will happen. Not might, will. Networks are unreliable.

So the realistic framing is: when (not if) a partition occurs, do you choose consistency (refuse to serve until you can talk to your peers) or availability (keep serving but maybe with stale data)?

CP systems: consistency over availability

A CP system says: if I cannot guarantee you the latest data, I will return an error rather than risk lying. This is what banks do. If two servers in a bank cannot communicate to verify your balance, they would rather refuse the transaction than risk letting you withdraw twice.

Examples: traditional relational databases in single-leader mode (Postgres, MySQL with strict replication), MongoDB with strong read concern, HBase, etcd, Zookeeper.

You pick CP when correctness matters more than uptime: payments, inventory, leader election.

AP systems: availability over consistency

An AP system says: I'll always answer, even if my answer is a few seconds out of date. The reasoning is: a slightly stale answer is better than no answer, especially for the user experience. We will eventually reconcile.

Examples: DynamoDB (in default mode), Cassandra, CouchDB, most DNS systems, most CDNs.

You pick AP when staleness is tolerable but downtime is not: social feeds, product catalogs, analytics, shopping cart counts.

The trade-off in real life

Real systems are not uniformly CP or AP. They make different choices per operation. A bank's account balance read might be CP. The bank's "recent transactions" list might be AP. Same database, different consistency requirement per query.

Modern databases like CockroachDB and Spanner offer strong consistency at the cost of higher latency and slightly reduced availability during partitions. Cassandra lets you tune consistency per query (QUORUM reads vs ONE reads). The line is not bright; it's a knob.

PACELC: the underrated extension

CAP only describes behavior under partition. PACELC adds: even when there is no partition (the Else case), there is a trade-off between Latency and Consistency. To get strong consistency you need to coordinate among replicas, which adds latency. Even on a healthy network you are choosing.

So the full picture for any distributed database is two letters:

If a partition (P), do you choose A or C?
Else (E), do you choose L or C?

Cassandra is PA/EL: under partition it picks availability; on healthy network it picks low latency. Spanner is PC/EC: it picks consistency in both cases (and pays in latency). DynamoDB is PA/EL by default but can be tuned.

Common misuse "We can't guarantee strong consistency because of CAP" is sometimes said about a single-region single-database setup. That is not what CAP says. CAP applies once you have replicas across a network. A single Postgres instance is not subject to CAP, it just has its own (different) consistency model.

How a senior architect thinks about CAP in design

The trick is to not pick a single C/A/P answer for the whole system. You break the system into operations and ask, per operation:

If a partition occurs and the user attempts this operation, what is the right behavior?
What is the cost of staleness here? Seconds? Minutes? Catastrophic?
What is the cost of unavailability here? User impatience? Lost revenue? Lawsuit?

For a chat app: showing old messages during a partition is fine (AP). Sending a new message that gets ack'd to the user but lost is not fine. So reads are AP, writes are CP-ish (require ack from the leader before returning).

For a shopping cart: adding items can be AP (eventually merged). Checkout (charging the card) must be CP.

What to remember

CAP is a constraint, not a recipe. It tells you that in a distributed system, when the network breaks, you have to choose between two flavors of bad. Naming the choice consciously is the value. The number of incidents I have seen caused by engineers assuming "we get all three" is humbling. You do not. Pick.

← Previous

Back-of-the-Envelope Estimation

ACID vs BASE