Summary of CAP Theorem
What is CAP Theorem? Here is the great intro. Please, refer to that post for basic terminology.
Originally, Eric Brewer said that you cannot have all of the three properties (Consistency, Availability and Partition Tolerance) in a distributed system. Then, it was proved formally. Let's look at the conclusion of this paper: "In this note, we have shown that it is impossible to reliably provide atomic, consistent data when there are partitions in the network. It is feasible, however, to achieve any two of the three properties: consistency, availability, and partition tolerance".
Only the first sentence is really useful in CAP Theorem: when the network partition happens, what do we prefer?
- Availability. Return stale data or error from the node a request came to. (Yes, returning an error counts as available if it is part of system's specification).
- Consistency. Redirect the request to the node with up to date data (probably, leader node). Any other speculations have little to do with reality. CAP Theorem is great because it is thought provocative and helps to understand distributed systems. However, when people try to apply it to real systems, it is rather confusing.
Let's take a look at some problems.
The research paper shows what happens in case of the network partition and how we can choose either PA or PC behavior. But what the hell is CA?
Coda Hale says, CA is impossible because network partitions are guaranteed to happen. Distributed systems somehow deal with them, therefore, they all are partitions tolerant.
Daniel Abadi thinks, CA is kinda the same as CP: "CA systems are “not tolerant of network partitions”. But what if there is a network partition? What does “not tolerant” mean? In practice, it means that they lose availability if there is a partition. Hence CP and CA are essentially identical."
The author of the theorem, Erec Brewer accepted both arguments: "Does choosing consistency and availability (CA) as the "2 of 3" make sense? As some researchers correctly point out, exactly what it means to forfeit P is unclear."
For other problems, I have to quote a lot from excellent Martin Kleppmann's blog post.
People who have not studied the CAP Theorem carefully, misunderstand its definitions.
- Consistency means linearizability, not ACID-like concistency.
- Availability by definition: "...every request received by a non-failing node in the system must result in the response". It has nothing to do with latency or high-availability. It allows very long processing. Even if a request is redirected to another node and successfully resolved, the system is still considered non available.
- Partition "is when the network fails to deliver some messages to one or more nodes by losing them (not by delaying them - eventual delivery is not a partition)." What partition tolerance is unclear, as we have seen earlier.
The CAP Theorem oversimplifies and does not cover the complexities of real-world systems, therefore it is not applicable to them.
The CAP theorem only concerns about network partition faults. "That kind of fault absolutely does happen, but it’s not the only kind of thing that can go wrong: nodes can crash or be rebooted, you can run out of disk space, you can hit a bug in the software, etc. In building distributed systems, you need to consider a much wider range of trade-offs, and focusing too much on the CAP theorem leads to ignoring other important issues."
CAP Theorem does not care about latency.
No real system can realistically guarantee 100% CAP Theorem consistency or availability. (Those narrow definitions are not very useful anyway.) As Martin showed, systems should not be labeled as CA/CP/AP. Systems have different characteristics and configurations. The same system may behave differently in different operations.