CAP Theorem
The CAP theorem states that a distributed data store can provide at most two of three guarantees: Consistency, Availability, and Partition Tolerance — and since network partitions are inevitable, the real choice is between consistency and availability during a partition.
Proposed by Eric Brewer in 2000 and proven by Gilbert and Lynch in 2002, CAP says a distributed system can guarantee at most two of: Consistency (every read gets the most recent write), Availability (every request gets a response), and Partition Tolerance (the system works despite network failures between nodes). Since network partitions will happen in any distributed system, the practical choice is CP (consistent but may reject requests during partitions — e.g., HBase, MongoDB with majority reads) or AP (available but may return stale data — e.g., Cassandra, DynamoDB). Most real systems are tunable rather than strictly CP or AP.
Tradeoffs
Strengths of CP Systems
- Data correctness guaranteed — critical for financial, inventory, and coordination systems
- Easier to reason about — no stale reads or conflicting writes
- Supports strong transactions (serializable isolation)
Weaknesses of CP Systems
- Higher latency (consensus rounds between replicas)
- Reduced availability during partitions (some requests are rejected)
- More complex failure handling
Strengths of AP Systems
- Always responsive — better user experience during failures
- Lower latency (no cross-node coordination for reads)
- Better throughput at scale
Weaknesses of AP Systems
- Stale reads are possible and must be handled by the application
- Conflict resolution required (last-writer-wins, vector clocks, CRDTs)
- Harder to reason about correctness
Likely Follow-Up Questions
- Can you give an example of when you'd choose AP over CP?
- What's the difference between CAP consistency and ACID consistency?
- How does Google Spanner appear to violate CAP?
- What is eventual consistency and when is it acceptable?
- How does PACELC extend the CAP theorem?
- How would you handle a network partition in a payment system?
Source: editorial — Synthesized from Brewer's conjecture, Gilbert-Lynch proof, PACELC paper, and Spanner paper