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 **C**onsistency, **A**vailability, (network) **P**artition 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 **P**artition, a tradeoff between **A**vailability and **C**onsistency, **E**lse a tradeoff between **L**atency and **C**onsistency. 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.

Pingback: NipTech Podcast » NipDev 3 – Data et NoSQL

Pingback: Informix goes NoSQL? | Informix on my mind

Reblogged this on TERA ONE (1T).