CAP Theorem – What does it mean to you?

The CAP Theorem – Yes, No or… Maybe

If you haven’t yet met the CAP theorem, it goes like this. A distributed computer system cannot simultaneously guarantee all of the following:

1. Consistency. All parts of the computer system see the same data at the same time
2. Availability. Every request made to the system receives a response, whether positive or negative
3. Partition tolerance. The system still functions even if with message loss or partial failure

As you’ve probably spotted, the first letters of the three criteria form the word CAP – hence the name of the theorem. Eric Brewer who first came up with the CAP theorem in 2000 suggested the result was that design choices would have to be made around two out of the three CAP properties, meaning CA, AP or CA.

Using the CAP Theorem to Classify Database Technology

As an example, we can position conventional relational database management systems and some of the new generation NoSQL data stores according to these CAP property pairs as follows:

• CA (Consistency and Availability): relational database management systems (RDBMS)
• CP (Consistency and Partition Tolerance): MongoDB document store and Redis key-value store
• AP (Availability and Partition Tolerance): CouchDB document store and Riak key-value store

A quick comparison of replication capabilities between MongoDB and CouchDB illustrates the positioning. MongoDB offers master-slave replication with a single master for improved consistency. CouchDB offers multi-master replication which is designed for increased availability and faster server response time.

ACID for Relational Databases

In the CA category with relational database systems, transactions have ACID properties with ACID standing for atomic, consistent, isolated and durable. In other words, each transaction is ‘all or nothing’, the system can only move from one valid state to another, transactions executed concurrently or sequentially give the same end result and once a transaction has been accomplished, it remains accomplished. These properties guarantee that database transactions in an RDBMS can be processed reliably.

BASE for Cloud Systems

In contrast, in an elastic or cloud computing environment corresponding more to AP, ACID properties may not be available or even relevant. Services running in this context are often required to be responsive even if inner systems are inaccessible. Brewer and his students came up with BASE acronym to describe this new paradigm. BASE means Basically Available, Soft-State and Eventually Consistent. This translates as availability according to the CAP definition, a system state that may change in time even without input, and consistency ‘sooner or later’ after a transaction, unless the system receives further input.  In other words, it’s acceptable to use stale data and it’s OK to give guesstimates as answers.

The CAP Continuum

12 years after Brewer formulated the CAP theorem, he felt it necessary to make a few additional remarks to clarify things. In particular, if partition tolerance is to be a goal, this does not necessarily mean a rigid division between consistency (C) and availability (A). Choices between C and A can be made within a system, within subsystems, and according to the operation or data involved. The three properties are continuous rather than binary. Likewise, ACID and BASE are not necessarily two distinct states, but rather two directions on a continuum along which a system becomes less ACID and more BASE or vice versa.

Design and Operational Choices

The effects of the CAP theorem also become more noticeable as an application scales upwards. At low volumes of transactions, distributed databases can recover consistency with little latency and no noticeable effect on overall performance or user perception. Even if in absolute terms C, A and P remain unachievable together for distributed systems, smart design choices can limit the negative and accentuate the positive to ensure critical transactions are guaranteed while optimizing the user experience elsewhere.