CAP Theorem
A distributed system can only provide two of three guarantees: Consistency, Availability, and Partition tolerance—and in practice, partition tolerance is required.
Detailed Explanation
The CAP theorem states that a distributed data store cannot simultaneously provide more than two of these three guarantees: Consistency (every read receives the most recent write), Availability (every request receives a response), and Partition tolerance (the system continues operating despite network failures).
Since network partitions are unavoidable in distributed systems, you must choose between CP (consistency + partition tolerance, e.g., PostgreSQL with replication) and AP (availability + partition tolerance, e.g., Cassandra, DynamoDB). CA systems (single-node databases) don't handle partitions. Understanding CAP helps you choose the right database for your consistency and availability requirements.
Why It Matters
CAP theorem guides database selection for distributed systems. It explains why different databases make different tradeoffs between consistency and availability.
Real-World Example
During a network partition between two data centers: a CP system (PostgreSQL) rejects writes to maintain consistency. An AP system (Cassandra) accepts writes on both sides, accepting temporary inconsistency for availability.
When to Use
When designing distributed systems, choosing databases for multi-region deployments, or understanding why different databases behave differently under failure conditions.
Advantages
- Framework for understanding distributed system tradeoffs
- Guides database selection
- Explains real-world behavior under failures
- Fundamental concept in distributed systems
- Helps set expectations for system behavior
Disadvantages
- Oversimplifies real-world tradeoffs
- PACELC extends CAP for normal operations
- Different databases interpret CAP differently
- Not all tradeoffs are binary
- Modern databases offer tunable consistency
Related Terms
Frequently Asked Questions
What is the PACELC theorem?
PACELC extends CAP: if Partition, choose Availability or Consistency; Else (normal operation), choose Latency or Consistency. It captures the tradeoff between latency and consistency even when there are no partitions.
What is eventual consistency?
Eventual consistency means that after a write, all replicas will eventually see the value. The "eventual" part can range from milliseconds to seconds. It trades strong consistency for higher availability and lower latency.
Can a system be both highly available and consistent?
In a single data center, yes (CA systems). In distributed systems across regions, you must choose. Most modern databases offer tunable consistency—you can choose the consistency level per operation.
Which database should I choose based on CAP?
For strong consistency: PostgreSQL, MySQL, MongoDB (with transactions). For high availability and partition tolerance: Cassandra, DynamoDB, CouchDB. Most applications choose CP for core data and AP for less critical data.
Is the CAP theorem still relevant?
Yes, but the PACELC extension provides a more complete picture. Modern databases offer tunable consistency, making the choice less binary. Understanding CAP helps you reason about distributed system behavior.