Skip to content

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

#

Question 1

Does a majority-based system necessarily stop completely during a partition?

#

Question 2

Is ACID consistency the same as CAP consistency?

Source: Spanner, TrueTime and CAP.