CAP Theorem & Trade-offs
You've built your distributed system with replication and sharding. Everything looks great in testing. Then production happens: a network cable gets cut, a data center loses power, a router misconfigures. Suddenly your nodes can't talk to each other.
What happens now?The CAP Theorem
In 2000, Eric Brewer proposed what became one of the most important theorems in distributed systems:
In a distributed system, when a network partition occurs, you must choose between:
The Three Properties
Consistency (C)
Every read receives the most recent write or an error. All nodes see the same data at the same time.
Availability (A)
Every request receives a response (not an error), without guarantee that it contains the most recent write.
Partition Tolerance (P)
The system continues to operate despite network partitions (messages being dropped between nodes).
Why Not All Three?
Here's the key insight: network partitions will happen. Cables get cut. Data centers have outages. This isn't theoretical - it's reality.
When a partition happens, you have two choices:
Choose Consistency (CP): Refuse to respond until nodes can sync. The user might see "Service unavailable" but will never see incorrect data. Choose Availability (AP): Respond from whichever node is reachable. The user gets a response, but it might be stale or lead to conflicts.CP vs AP Systems
| System Type | Behavior During Partition | Use Cases |
|---|---|---|
| CP | Returns error or waits | Banking, inventory, bookings |
| AP | Returns potentially stale data | Social feeds, analytics, caching |
Real-World Examples
If you transfer $1000, it's better for the system to reject the transaction than to risk double-spending. "Transaction failed, try again" is acceptable. "$1000 disappeared" is not.
If a post shows 1,523 likes instead of 1,524, nobody cares. It's better to show something than to show an error. The count will eventually converge.
Eventual Consistency
Most AP systems don't give up on consistency entirely - they use eventual consistency:
Eventual Consistency: If no new updates are made, eventually all replicas will converge to the same value.
The Timeline
Time 0: User writes "balance = $50" to Node A
Time 1: Node A has $50, Node B still has $100 (inconsistent!)
Time 2: Node A replicates to Node B
Time 3: Both nodes have $50 (consistent again)The system was inconsistent for a window of time, but eventually became consistent.
Conflict Resolution
What if both nodes receive writes during a partition?
Last Write Wins (LWW)
Timestamp-based. Simple but can lose data.
Merge/CRDT
Mathematically merge conflicts. No data loss.
Application-Level
Let the app decide how to resolve.
Real-World: Amazon Dynamo
Amazon's Dynamo paper (2007) heavily influenced NoSQL databases. It explicitly chose availability:
"Customers should be able to view and add items to their shopping cart even if disks are failing, network routes are flapping, or data centers are being destroyed by tornados."
Dynamo influenced: DynamoDB, Cassandra, Riak, Voldemort.
Real-World: Google Spanner
Google went the other direction with Spanner - a globally distributed database with strong consistency:
Uses GPS and atomic clocks (TrueTime) to achieve globally consistent transactions. If clocks could be perfectly synchronized, you could have consistency without sacrificing much availability.
Beyond CAP: PACELC
CAP only describes behavior during partitions. But what about normal operation?
PACELC extends CAP:if (Partition) {
choose Availability or Consistency
} else {
choose Latency or Consistency
}| System | During Partition | Normal Operation |
|---|---|---|
| Cassandra | Availability (AP) | Latency (EL) |
| MongoDB | Consistency (CP) | Consistency (EC) |
| DynamoDB | Availability (AP) | Latency (EL) |
Practical Guidelines
Choose CP When...
- Money or inventory is involved
- Data loss is unacceptable
- Regulations require accuracy
- Users expect correctness
Choose AP When...
- Stale data is acceptable
- Uptime is critical
- Data can be merged later
- Users expect responsiveness
Key Takeaways
- CAP is about partitions - When network fails, choose C or A
- P is not optional - Network partitions will happen in distributed systems
- Eventual consistency is the most common AP strategy - trade immediate consistency for availability
- Choose based on business needs - Banking needs CP, social media can use AP
Next up: Message Queues - Decoupling services with asynchronous communication.