Notes › System Design
CAP Theorem and Consistency
In a distributed system (data stored on several machines), the network between machines can fail. The CAP theorem says what you can and cannot promise when it does.
The three letters
- C — Consistency: every read gets the most recent write (or an error). All nodes look like one copy. (This is "linearizability" — not the C in ACID.)
- A — Availability: every request to a working node gets a non-error response (maybe not the latest data).
- P — Partition tolerance: the system keeps working even if messages between nodes are lost or delayed.
The theorem
During a network partition, a distributed system must choose between Consistency and Availability.
Partitions will happen in real networks, so P is not optional. The real choice is:
| Choice |
During a partition |
Example behaviour |
| CP |
refuse or wait on some requests to avoid wrong data |
"Service unavailable, try again" |
| AP |
answer every request, possibly with stale data; fix differences later |
shows an old like count |
| When there is no partition, a system can be both consistent and available. |
|
|
Picture it
Node A ──✂── (link broken) ── Node B
x = 1 x = 1
User writes x = 2 to A. Another user reads x from B.
CP: B refuses (or waits) — it can't confirm the latest value.
AP: B answers x = 1 — available but stale.
Examples
| System |
Usually classed |
Notes |
| Single-node PostgreSQL/MySQL |
CA (not distributed) |
no partition to worry about |
| MongoDB (default, majority writes) |
CP |
minority side can't elect a primary |
| HBase, ZooKeeper, etcd, Consul |
CP |
used for config, leader election, locks |
| Cassandra, DynamoDB, Riak |
AP (tunable) |
quorum settings move them toward C |
| CouchDB, DNS |
AP |
eventually consistent |
| Google Spanner |
CP |
uses atomic clocks; is practically highly available |
| Many databases are tunable — the label depends on configuration. |
|
|
Which to choose
| Prefer CP |
Prefer AP |
| bank balance, payments, stock/inventory reservation, seat booking |
social feed, likes, view counts, product catalogue, shopping cart, DNS |
| wrong data is worse than an error |
an error is worse than slightly old data |
PACELC — the fuller picture
If Partition → choose A or C; Else (normal operation) → choose Latency or Consistency.
Even without failures, waiting for replicas to agree costs time.
| System |
PACELC |
| Cassandra, DynamoDB |
PA/EL — available, low latency |
| MongoDB |
PC/EC (default) |
| Spanner, HBase |
PC/EC |
| PNUTS (Yahoo) |
PC/EL |
Consistency models (strongest → weakest)
| Model |
Guarantee |
Example |
| Strong / linearizable |
everyone sees the latest write immediately |
bank balance in a single-leader DB with sync reads |
| Sequential |
everyone sees operations in the same order |
— |
| Causal |
if B depends on A, everyone sees A before B |
a reply never appears before its comment |
| Read-your-writes |
you always see your own updates |
your edited profile |
| Monotonic reads |
you never see older data after newer |
refreshing a feed |
| Eventual |
if writes stop, all replicas eventually agree |
like counts, DNS |
| Stronger = simpler to reason about but slower and less available. |
|
|
How AP systems reconcile
- Last-write-wins (LWW) using timestamps — simple but can silently drop writes.
- Version vectors to detect concurrent writes, then merge (e.g. union of shopping-cart items).
- CRDTs — data types that always merge correctly (counters, sets; used in collaborative editors).
- Read repair and anti-entropy (Merkle trees) to sync replicas in the background.
Quorums
With N replicas: write to W, read from R. W + R > N → every read overlaps the latest write.
| N, W, R |
Result |
| 3, 2, 2 |
consistent reads, tolerates 1 failure |
| 3, 1, 1 |
fastest, eventually consistent |
| 3, 3, 1 |
fast reads, any failure blocks writes |
ACID vs BASE
| ACID (traditional SQL) |
BASE (many NoSQL) |
| Atomic, Consistent, Isolated, Durable |
Basically Available, Soft state, Eventually consistent |
| correctness first |
availability and scale first |
| See Transactions and ACID. |
|
Common interview mistakes
- Saying "pick any two of three" — you can't give up P in a distributed system.
- Mixing up CAP's C (latest value across nodes) with ACID's C (constraints hold).
- Calling a whole product "CP" or "AP" without saying which configuration.
Interview one-liners
- CAP: during a partition, choose consistency or availability.
- CP for money and inventory; AP for feeds and counters.
- PACELC adds the latency vs consistency trade-off in normal times.
- Eventual consistency: replicas agree once writes stop.
- W + R > N for strong reads with quorums.
- Related: Database Sharding and Replication.
More System Design notes