08 · CAP Theorem — Consistency, Availability, Partition Tolerance
Scaling Writes · Topic 8 of 10
The Theorem
In a distributed system, you can only guarantee two of three properties simultaneously:
| Property | Meaning |
|---|---|
| Consistency | Every read receives the most recent write or an error |
| Availability | Every request receives a response (no errors), though it may be stale |
| Partition Tolerance | System continues operating despite network partitions |
Network partitions are inevitable in distributed systems. You must choose between C and A when a partition occurs.
The Real Choice: CP vs AP
graph TD
P[Partition occurs] --> CP[CP: Return error or block\nto ensure consistency]
P --> AP[AP: Return stale data\nto ensure availability]
CP systems: sacrifice availability — may return errors or block during partition AP systems: sacrifice consistency — return potentially stale data
Where Each DB Falls
| DB | CAP Trade-off | Notes |
|---|---|---|
| PostgreSQL (single node) | CA | Not distributed — partition tolerance N/A |
| Google Spanner | CP | Strong consistency globally; may sacrifice availability |
| DynamoDB (default) | AP | Eventually consistent; strong consistency optional |
| Cassandra | AP | Tunable consistency — can lean CP with ALL quorum |
| MongoDB (default) | CP | Primary-election during partition reduces availability |
| BigQuery | CA | Not a transactional system; OLAP |
PACELC Extension
CAP only applies during partitions. PACELC extends the model to normal operation:
- If Partition: choose between Availability and Consistency
- Else: choose between Latency and Consistency
| DB | P: A or C | E: L or C |
|---|---|---|
| DynamoDB | A | L (eventually consistent reads are faster) |
| Spanner | C | C (serializable, higher latency) |
| Cassandra | A | L (tunable) |