CAP Theorem: The Fundamental Trade-off
In a distributed system facing a network partition, you cannot simultaneously guarantee both consistency and availability. You must choose. The CAP theorem defines the hard limits of what's possible when nodes can't talk to each other — and forces every distributed database to pick a side.
Consistency, Availability, Partition Tolerance
The CAP theorem, formulated by Eric Brewer, states that a distributed system can satisfy at most two of three guarantees simultaneously. Here's what each property actually means:
Consistency (linearizability)
Every read sees the most recent write. After a write completes, all subsequent reads return that value or a newer one. It's the illusion of a single, up-to-date copy.
Availability
Every request to a non-failing node receives a response, without guarantee that it's the most recent write. The system never refuses to answer.
Partition Tolerance
The system continues operating despite arbitrary network partitions (nodes can't communicate). In practice, partitions are inevitable — you can't opt out.
The Real Statement
Since network partitions are not optional in real-world distributed systems, CAP is really a choice between CP (consistency + partition tolerance) and AP (availability + partition tolerance). When the network splits, do you refuse requests to stay consistent, or do you keep answering with potentially stale data?
CP vs AP: The Choice
When a partition occurs, a CP system sacrifices availability to preserve consistency. An AP system sacrifices consistency to stay available.
CP Systems: Consistency First
When partitioned from the majority, nodes stop accepting writes (or reads) to avoid returning stale data. They return errors until the partition heals.
Network partition detected. Node A (majority side) → still serves reads & writes ✓ Node B (minority side) → rejects requests: "unavailable" When the partition heals: Node B catches up, then resumes serving traffic.
AP Systems: Availability First
All nodes continue serving requests, even when partitioned. They return whatever data they have, which may be stale. When the partition heals, conflicts are reconciled.
Network partition detected. Node A → serves local data (may be stale) Node B → serves local data (may be stale) Client reads from A and B can return different values! When partition heals: Conflict resolution (last-write-wins, vector clocks, etc.)
What About CA (No Partition Tolerance)?
A system that's consistent and available but not partition-tolerant only works when the network is perfect. Since network failures are inevitable in any real distributed system, CA isn't achievable. A single-node database can be CA — but it's not distributed.
PACELC: The Full Picture
CAP only describes behavior during a partition. But what about normal operation, when there's no partition? PACELC extends the theorem:
PACELC Statement
if (Partition):
choose Availability or Consistency
else (no partition):
choose Latency or Consistency
In normal operation, you trade consistency for speed.PA/EL (Cassandra, DynamoDB)
During partition: choose availability. No partition: choose low latency (eventual consistency). Fast writes, stale reads.
PC/EC (HBase, MongoDB default)
During partition: choose consistency. No partition: choose strong consistency (slower). Every read is correct, but writes wait for acknowledgment.
PA/EC (Riak with tuning)
During partition: choose availability. No partition: choose consistency. Rare in practice — most systems pick a consistent position.
Common Misconceptions
Misconception: "CAP means pick two"
Reality: Partitions are not optional. You must be partition-tolerant. The real choice is CP vs AP when a partition occurs.
Misconception: "Consistency means ACID transactions"
Reality: CAP's "consistency" is linearizability — every read sees the most recent write. ACID's "consistency" is about application invariants (constraints, triggers). Different concepts.
Misconception: "AP systems are always inconsistent"
Reality: AP systems are eventually consistent. During normal operation, they converge quickly. Inconsistency is temporary and only guaranteed during partitions.
Misconception: "MongoDB is CP, so it's always consistent"
Reality: Default configuration is CP, but you can tune read/write concerns to trade consistency for availability or latency.
Live CAP Simulation
CAP Pitfalls to Avoid
- →Assuming your network is reliable: Partitions happen. Cloud networks fail, switches die, cables get unplugged. Design for partition tolerance.
- →Ignoring PACELC: CAP only covers partition behavior. You also trade latency vs consistency during normal operation.
- →Picking CP for everything: Strong consistency is expensive. If stale data is acceptable (analytics, feeds, caches), AP is often better.
- →Picking AP without conflict resolution: AP systems require application logic to handle divergent writes when partitions heal.
- →Confusing consistency models: CAP's consistency is linearizability, not ACID's integrity constraints or eventual consistency.
- →Forgetting tunable consistency: Many systems (Cassandra, DynamoDB) let you dial consistency per-request. Use strong reads when critical, weak reads when speed matters.
- →Treating CAP as absolute: Real systems often use hybrid approaches — CP for critical metadata, AP for user data.
Key Takeaways
- →CAP theorem: in a distributed system facing a partition, you must choose between consistency and availability.
- →Partition tolerance is not optional. Network failures are inevitable. The real choice is CP vs AP.
- →CP systems (HBase, MongoDB, ZooKeeper) sacrifice availability during partitions to stay consistent.
- →AP systems (Cassandra, DynamoDB, Riak) sacrifice consistency to remain available, then reconcile conflicts later.
- →CA systems don't exist in real distributed environments. Single-node databases can be CA, but they're not distributed.
- →PACELC extends CAP: during normal operation (no partition), you also trade latency vs consistency.
- →Many modern systems are tunable: you choose consistency level per operation (strong read vs eventual read).
- →CAP is a fundamental constraint, not a product feature. Understanding it helps you pick the right database for your use case.
Quick Reference: CP vs AP Systems
CP: HBase, MongoDB (default), ZooKeeper, etcd
Strong consistency. Minority nodes become unavailable during partitions. Use when correctness is critical: financial transactions, inventory counts, configuration stores.
AP: Cassandra, DynamoDB, Riak, CouchDB
Eventual consistency. Always available, may return stale data. Use when availability matters more than correctness: social feeds, recommendations, analytics, caches.
Tunable: Cassandra, DynamoDB (with tuning)
Let you choose consistency per-request. QUORUM reads give strong consistency; ONE reads give low latency. Best of both worlds, but requires understanding the trade-offs.
Special: Google Spanner
Globally consistent using synchronized atomic clocks (TrueTime). Appears to violate CAP, but actually sacrifices availability (waits for clock uncertainty) to guarantee consistency.