CAP Theorem and PACELC
The CAP theorem explained correctly: what partitions force you to choose, CP vs AP systems, and PACELC's latency vs consistency trade-off.
The CAP theorem says that when a network partition splits a replicated data system, it must give up either consistency (every read sees the latest write) or availability (every request gets a non-error answer). It cannot keep both. It is often misquoted as "pick two of three"; the precise version is about what you do during a partition.
The three properties, precisely
- Consistency (C): here this means linearizability: every read returns the most recent completed write, as if there were one copy of the data. This is stronger than the C in ACID. See consistency models.
- Availability (A): every request to a non-failed node receives a response (not an error or a timeout), though it may not be the latest data.
- Partition tolerance (P): the system keeps working when messages between nodes are lost or delayed indefinitely.
In any system spread over a network, partitions will happen: a switch fails, a cable is cut, a cloud zone loses connectivity, or a long GC pause looks like a partition. So P is not optional, and the real choice is C or A when a partition occurs.
What a partition forces
- CP choice: node 2 can't confirm it has the latest value, so it returns an error or waits. The system stays correct but part of it is unavailable. Typically the side holding a majority of replicas keeps serving.
- AP choice: node 2 answers with x = 1. Everyone gets an answer, but some answers are stale, and if both sides accept writes, the conflicting writes must be reconciled when the partition heals.
Worked example: a leader, a replica and a partition
A leader takes writes and a replica copies them with a lag of 2 versions. Writes keep arriving (v1, v2, v3…). Then the network between them is cut while the leader reaches v5 and the replica is stuck at v3. A client next to the replica reads:
| Mode | Before the partition | During the partition | What the user sees |
|---|---|---|---|
| AP (read the replica, allow stale) | v3 while the leader has v5 (normal lag) | Still v3: the replica keeps answering | A slightly old value, but never an error |
| CP (require the leader) | v5 | Error or timeout: the cut-off side refuses to answer | Correct data, or no data |
Since partitions will happen across machines, P isn't optional; the real choice is CP (stay correct by refusing requests on the cut-off side) or AP (stay up by serving possibly stale data). A "CA" system only exists on a single node that never partitions. Most consumer features choose AP (a slightly stale feed beats an error page); money chooses CP (a wrong balance is worse than a spinner).
CP and AP systems in practice
| Leaning | Behaviour in a partition | Examples | Good for |
|---|---|---|---|
| CP | Minority side rejects requests; no stale or conflicting data | etcd, ZooKeeper, Consul, Spanner, HBase, MongoDB with majority writes | Config, leader election, locks, money, inventory counts |
| AP | All sides keep serving; reconcile later | Cassandra, DynamoDB (eventually consistent reads), Riak, CouchDB, DNS | Shopping carts, feeds, likes, sessions, telemetry |
Many databases let you choose per request. Cassandra and DynamoDB use tunable quorums: reading and writing at QUORUM behaves more like CP, ONE behaves like AP. See replication.
PACELC: the trade-off you face every day
Partitions are rare, but replication has a cost all the time. PACELC extends CAP: if there is a Partition, choose A or C; Else, in normal operation, choose Latency or Consistency.
- Waiting for a write to reach a majority of replicas, possibly in another region, makes it consistent but slower.
- Acknowledging after one replica and replicating in the background is fast but briefly inconsistent.
| System | PACELC class | Meaning |
|---|---|---|
| DynamoDB, Cassandra (defaults) | PA/EL | Favour availability in partitions and low latency otherwise |
| Spanner, etcd, ZooKeeper | PC/EC | Pay latency for consistency, always |
| MongoDB (typical config) | PA/EC-ish | Consistent reads from the primary; tunable |
Common misconceptions
- "Pick any two." You can't choose CA for a distributed system; partitions happen whether you like it or not. A single-node database is "CA" only because there's nothing to partition.
- "AP means no consistency." AP systems are usually eventually consistent and often offer stronger guarantees like read-your-writes per session.
- "CP means always unavailable." CP systems are unavailable only on the minority side of a partition, and only for strongly consistent operations.
- The C in CAP is not the C in ACID. ACID consistency means invariants hold after a transaction; CAP consistency is about replicas agreeing. See ACID vs BASE.
Where it’s used
Chose availability: the cart always accepts "add to cart", and conflicting versions are merged, because a lost sale costs more than a duplicated item.
Cluster state lives in etcd, a CP store using Raft: a minority partition can't change cluster state, which prevents split-brain decisions.
Chooses consistency and uses synchronized clocks (TrueTime) and Paxos to keep latency acceptable for global strongly consistent transactions.
A classic AP system: updates propagate slowly through caches, but lookups keep working through outages.
In an interview
- Don't recite "pick two"; say "partitions happen, so for this data we choose consistency (or availability) during a partition, because…".
- Make the choice per piece of data: payments and inventory CP, likes and feeds AP.
- Bring up PACELC when discussing multi-region writes: synchronous cross-region replication costs latency on every write.
- Explain what users see in each mode: errors and retries for CP, stale or conflicting data for AP, and how conflicts are resolved.