08 · CAP Theorem — Consistency, Availability, Partition Tolerance¶
Scaling Writes · Topic 8 of 10
The Theorem¶
During a network partition, a distributed read/write service cannot guarantee both linearizable consistency and availability for every request to a non-failing node. "Pick any two" is a misleading shortcut: partition behavior is the condition under which the trade-off arises.
| 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) | Not a distributed CAP example | Replication and failover configuration determine distributed behavior |
| Google Spanner | Consistency-oriented | Strong operations may be unavailable without a voting quorum |
| DynamoDB | Operation/mode dependent | Local strong reads and MREC/MRSC global-table modes have different contracts |
| Cassandra | Consistency-level dependent | Higher quorums reduce availability; ALL is not a consensus protocol |
| MongoDB | Concern/topology dependent | Majority writes, read concerns and elections determine guarantees |
| BigQuery | Analyze the specific API | OLAP does not make a distributed service automatically "CA" |
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) |
A Concrete Partition¶
Two regions can no longer communicate. A seat is available in both copies. If both regions must keep confirming reservations, they can sell the same seat. To preserve a single authoritative decision, at least one side must refuse or delay some reservations. Returning an error is not CAP availability, even if the HTTP server is healthy.
Specify the operation before labeling the system: browsing a stale seat map may remain available while confirming a reservation requires coordination. CAP says nothing about your normal-operation latency SLO or how fast replicas converge after healing. The PACELC table above is only a rough intuition; product modes and request settings matter.
Check Your Understanding¶
Source: Spanner, TrueTime and CAP.