Skip to content

CAP Theorem

1. What is it? (2-3 lines)

The CAP Theorem (Brewer's Theorem) states that any distributed data store can simultaneously provide at most two of three guarantees: Consistency (Linearizability), Availability, and Partition Tolerance. In the presence of a network partition, a system MUST choose between Consistency (CP) or Availability (AP).

2. Why does it exist?

Network partitions (packet drops, severed fiber cables, hardware failures) are inevitable in distributed systems. CAP provides a formal mathematical boundary (proven by Seth Gilbert and Nancy Lynch) forcing system architects to explicitly design how a distributed store handles network partitions.

3. Where is it used?

  • CP Systems (Consistency over Availability): Google Spanner, CockroachDB, HBase, MongoDB, ZooKeeper, etcd.
  • AP Systems (Availability over Consistency): Apache Cassandra, Amazon DynamoDB (eventual consistency mode), Couchbase.

4. How does it work? (simple flow)

  1. Normal Operation (No Partition): System achieves both High Availability and Strong Consistency.
  2. Network Partition Occurs: Node A and Node B can no longer communicate over the network.
  3. Client Write Arrives at Node A:
  4. If CP Choice: Node A rejects the write or blocks waiting for Node B, returning an error / timeout to preserve Linearizability across nodes (Sacrifices Availability).
  5. If AP Choice: Node A accepts the write locally and returns success to the client, but Node B now holds stale data (Sacrifices Strong Consistency).

5. Advantages

  • Establishes a fundamental architectural trade-off framework for distributed database selection.
  • Prevents impossible engineering goals (e.g. attempting to build a 100% available + 100% strongly consistent system over unreliable networks).

6. Limitations

  • Binary Oversimplification: CAP treats Availability and Consistency as binary (0 or 1), ignoring latency spectrums and degrees of consistency (e.g., Causal Consistency, Read-Your-Writes).
  • Applies ONLY during Network Partitions: CAP says nothing about system behavior during normal non-partitioned operations (addressed by PACELC).

7. Common interview questions (10)

  1. What does Consistency mean in the CAP Theorem and how does it differ from ACID Consistency?
  2. Why is Partition Tolerance (P) mandatory in real-world distributed systems?
  3. Explain why a "CA System" cannot exist in a distributed network.
  4. How does Apache Cassandra operate as an AP system during network partitions?
  5. How does ZooKeeper / etcd operate as a CP system during network partitions?
  6. What happens to a CP system when a majority partition cannot be formed (Quorum loss)?
  7. How does the PACELC theorem extend the CAP Theorem?
  8. Can a database dynamically switch between CP and AP modes depending on the query configuration?
  9. How does Eventual Consistency fit into the CAP Theorem framework?
  10. How do multi-region deployments handle CAP Theorem trade-offs?

8. Common misconceptions

  • Misconception: You can choose "CA" and ignore Partition Tolerance. Fact: Network partitions are physical realities; you CANNOT opt out of P. You can only choose CP or AP when P occurs.
  • Misconception: AP systems mean zero consistency ever. Fact: AP systems trade immediate linearizable consistency for eventual consistency during a partition.

10. 30-second cheat sheet

  • C (Consistency): Linearizability \(\implies\) Every read receives the most recent write or an error.
  • A (Availability): Every non-failing node returns a non-error response (without guarantee of latest data).
  • P (Partition Tolerance): System continues operating despite dropped network messages between nodes.
  • Rule of Thumb: P is mandatory! Choose CP for money/ledgers; choose AP for high-availability feeds/shopping carts.