CAP Theorem

In a Nutshell

The CAP theorem states that a distributed data store can provide at most two out of three guarantees simultaneously: Consistency (every read returns the most recent write), Availability (every request receives a response), and Partition Tolerance (the system continues operating despite network failures between nodes). Since network partitions are inevitable in any distributed system, the real-world choice is between CP (consistent but may reject requests during a partition) and AP (available but may return stale data). CAP doesn't tell you what to build — it tells you what you can't have, forcing you to choose your trade-off consciously.

How It Actually Works

The Three Properties

Property	Meaning	Example
Consistency	Every read returns the most recent successful write. All nodes see the same data at the same time.	After writing balance = $50, every subsequent read returns $50 — never the old value.
Availability	Every request (read or write) receives a non-error response, even if some nodes are down.	The system always responds — never returns a timeout or error due to node failure.
Partition Tolerance	The system continues to operate despite arbitrary message loss between nodes.	If the network link between Node A and Node B breaks, the system still serves requests.

Why You Can't Have All Three

Imagine two database nodes, A and B, replicating data. A network partition splits them:

  Node A                    Node B
  ┌──────┐    ✂ partition   ┌──────┐
  │ data │ ───── X ──────── │ data │
  │  v1  │                  │  v1  │
  └──────┘                  └──────┘

  Client writes to Node A: data = v2

  Node A                    Node B
  ┌──────┐                  ┌──────┐
  │ data │                  │ data │
  │  v2  │                  │  v1  │  ← stale!
  └──────┘                  └──────┘

  Now a client reads from Node B. You have two choices:
  1. Return v1 (stale) → Available but NOT Consistent (AP)
  2. Reject the read → Consistent but NOT Available (CP)

There is no third option. This is why CAP is a theorem, not a design guideline.

CP vs AP Systems

Choice	Behavior During Partition	Examples	Best For
CP	Rejects requests if it can't guarantee consistency	CockroachDB, Google Spanner, HBase, ZooKeeper, etcd	Financial transactions, inventory, leader election — where stale data is unacceptable
AP	Serves requests with potentially stale data	Cassandra, DynamoDB, CouchDB, Riak	Social media feeds, analytics, shopping carts — where availability matters more than freshness

Common Misconceptions

1. "You choose 2 out of 3" — Misleading. Since partitions are inevitable, you're really choosing between C and A during a partition. When there's no partition, you can have both C and A.

2. "CAP applies to every system" — CAP applies only to distributed systems. A single-node PostgreSQL is not subject to CAP — it provides both C and A because there are no partitions to tolerate.

3. "AP means no consistency ever" — AP means during a partition, reads might be stale. Once the partition heals, data converges (eventual consistency). Under normal operation, AP systems often provide strong consistency.

4. "You must choose one for the entire system" — Different parts of the same system can make different CAP choices. Payments: CP. Social feed: AP. This is polyglot consistency.

Beyond CAP: PACELC

CAP only describes behavior during partitions. PACELC extends it: if there's a Partition, choose between Availability and Consistency. Else (normal operation), choose between Latency and Consistency.

System	During Partition	Normal Operation	PACELC
PostgreSQL (single node)	N/A	Low latency, consistent	— (not distributed)
CockroachDB	Chooses Consistency	Higher latency (consensus)	PC/EC
Cassandra	Chooses Availability	Low latency (local read)	PA/EL
DynamoDB	Chooses Availability	Tunable (eventual or strong)	PA/EL or PA/EC

Seeing It in Action

Scenario: Designing a global e-commerce platform

Payment Service (CP):
  - CockroachDB with Serializable isolation
  - During partition: rejects payment writes → user sees "try again later"
  - Rationale: A double-charge or lost payment is worse than a brief outage

Product Catalog (AP):
  - Cassandra with eventual consistency
  - During partition: serves potentially stale prices or stock counts
  - Rationale: Showing a slightly outdated price for 30 seconds is acceptable
  - Reconciliation: Fix inconsistencies after partition heals

Shopping Cart (AP):
  - DynamoDB with eventual consistency
  - During partition: both regions can accept cart updates
  - Conflict resolution: "last writer wins" or merge strategy
  - Rationale: Cart is per-user, temporary — minor inconsistency is tolerable

Key insight: The system doesn't make one CAP choice — it makes different choices for different components based on their correctness requirements.

Interview Questions

1. Q: Explain CAP theorem with a real-world example. Hint: Two-node database with a network partition. A write to Node A can't replicate to Node B. Choice: reject reads from Node B (CP — consistent but unavailable at Node B) or serve stale data from Node B (AP — available but inconsistent). Example: a bank (CP) vs a social media feed (AP).

2. Q: Is a single-node PostgreSQL a CP or AP system? Hint: Neither — CAP applies only to distributed systems. A single-node PostgreSQL provides both consistency and availability because there are no network partitions to tolerate. CAP becomes relevant only when you add replicas or shard the database.

3. Q: How does Cassandra handle the CAP trade-off? Hint: Cassandra is AP by default — it prioritizes availability. During a partition, both sides accept writes. After healing, it reconciles using timestamps (last write wins) or custom conflict resolution. You can tune toward CP per query using QUORUM consistency level, but at the cost of availability during partitions.

4. Q: What is PACELC, and why is it more useful than CAP alone? Hint: CAP only tells you what happens during a partition. PACELC adds: when there's no partition (normal operation), you still trade off between latency and consistency. This explains why CockroachDB is slower than Cassandra even when the network is healthy — it's paying for consistency with latency.

5. Q: You're designing a distributed system that needs strong consistency for payments and high availability for product listings. How do you architect this? Hint: Polyglot consistency. Use a CP database (CockroachDB, Spanner) for payments — it guarantees consistency at the cost of availability during partitions. Use an AP database (Cassandra, DynamoDB) for product catalog — it guarantees availability with eventual consistency. The systems communicate via events/messages, not shared state.

References

• Designing Data-Intensive Applications by Martin Kleppmann — Chapter 9: Consistency and Consensus
• Brewer's CAP Theorem (Original Paper) — Gilbert & Lynch formalization
• CAP Twelve Years Later: How the "Rules" Have Changed — Eric Brewer's updated perspective

Dive Deeper

• PACELC — Daniel Abadi — the original PACELC paper
• Jepsen — Kyle Kingsbury's rigorous testing of CAP/consistency claims
• Martin Kleppmann — Please stop calling databases CP or AP — nuanced critique of simplistic CAP labeling