CONCEPT SHEET · Concepts

CAP Theorem (and PACELC)

One-liner: Under a network partition a distributed store must choose consistency or availability; PACELC adds that without partitions you still trade latency vs consistency.

ArticleConcepts© Arthur Bernier Jr506 words1 code block

Say this#

How it works#

TEXT
   [A] <--X--> [B]         partition between A and BCP: minority side returns errors / blocks until healed    -> consistent, not availableAP: both sides accept writes, diverge, merge later       -> available, not consistent
  1. Partitions are not optional in a real network, so P is a given; the choice is C vs A during a partition.
  2. CP: leader needs majority acks; nodes that can't reach quorum stop serving writes (and often linearizable reads).
  3. AP: each side serves; conflicts resolved with last-write-wins, vector clocks, or CRDTs; anti-entropy repairs.
  4. PACELC in normal operation: synchronous replication = higher latency, lower lag (PC/EC, e.g. Spanner, VoltDB); async = lower latency, stale reads (PA/EL, e.g. Cassandra, DynamoDB default).

CAP "consistency" ≠ ACID consistency. CAP's A ≠ "high availability" in the SLA sense; a CP system can still be 99.99% available in practice.

Trade-offs#

ChoiceProCon
CP (etcd, Zookeeper, Spanner)No stale reads, safe for locks/leader election/configWrites unavailable in minority partition; higher write latency
AP (Cassandra, Dynamo)Always writable, low latency, geo-friendlyStale reads, conflict resolution burden on app
PC/EC (sync replication)Strong everywhereEvery write pays cross-node RTT
PA/EL (async replication)FastReplication lag, possible loss on failover
Tunable (Cassandra QUORUM)Pick per queryOperators must understand R+W>N

Numbers#

  • Quorum = ⌊N/2⌋+1: 3 nodes tolerate 1 failure, 5 tolerate 2.
  • Cross-AZ RTT ~1-2 ms; cross-region ~50-150 ms: the cost of synchronous C.
  • Spanner's TrueTime bounds clock uncertainty to a few ms to achieve external consistency.

In the interview#

See also