I decided to try writing once in a while a post on some of the classical papers and topics that had major effect on our big data technologies, and there is no better place to start that than the CAP Theorem.
The CAP Theorem by Eric Brewer was a philosophical fuel behind the so-called NoSQL movement, the battle cry that for a while united them all (at least in 2010). CAP stands for Consistency, Availability, (network) Partition tolerance and the theorem claims that in a distributed system, when there is an inevitable network partition (and the cluster breaks into two or more “islands”), you can’t guarantee both availability (for updates) and consistency. However, it was sometimes dumbed down to to a “Consistency, Availablity, Partition Tolerance – pick any two” slogan to explain why an eventual consistency model for a NoSQL database is legit. The discussion usually classified relational databases as “CA” and typically NoSQL databases as “AP”. Here is one example, and another representative one as an image:
The theorem itself was claimed by Eric Brewer in 2000 as a conjecture (a claim). It was formalized and proven (became a theorem) by Seth Gilbert and Nancy Lynch in 2002 in the paper “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services“. The proof itself not long and is quite readable for my taste. It also discusses a potential weaker consistency guarantee based on timeouts.
Criticism and discussion. One of the most useful criticism on CAP theorem comes from the famous Daniel Abadi, who suggested to enhance CAP by calling it PACELC – hey, he is just a database genius, not a marketing genius 🙂 What he means is that there are two engineering tradeoffs in distributed databases – when there is a network Partition, a tradeoff between Availability and Consistency, Else a tradeoff between Latency and Consistency. I found a nice presentation by Arinto Murdopo on slideshare that visualizes this point:
Another aspect is that consistency and availability are not binary. Each can be bounded in various ways, and many databases actually offer user-adjustable tradeoffs between the two. Eric Brewer itself recently revisited the topic of his theorem in an article titled CAP Twelve Years Later: How the “Rules” Have Changed, where he discussed and clarified these points and moves forward to real system design tradeoffs – an highly recommended read (for example, the ATM example). A last link for readers – Abadi had another fine post several months ago where he reviewed the “IEEE Computer CAP Retrospective”, with additional pointers and insights.
It seems to me that the CAP theroem is mostly relevant today when designing distributed databases across data centers, where the tradeoff between latency, consistency and availability are most profound. Anyway, it is a powerful tool in order to understand the challenges of distributed systems and the designed behavior of specific systems.