Cap Theorem

The CAP theorem broadly states that it is impossible to provide all three of the following properties:

  1. Consistency - All nodes in the system returns the same data and regardless of where the data is read from, it always has the latest write. In the event that's not possible, it returns an error.
  2. Availability - The system is accessible even in the event of node failures.
  3. Partition tolerance - In the event the nodes are up but the network connecting the nodes is not, the nodes have sufficient replicated data to respond. Another way to look at this is if an arbitrary number of messages are dropped between nodes, the nodes are still functional.

Meaning of the CAP theorem

In the event of a network partition, there's really two options left:

  1. If we want to ensure consistency, we need to cancel write operations at the cost of availability.
  2. If availability is important, we need to sacrifice consistency meaning a write on one node may not reflect on another one because of the network partition.

When there is no network partition though, both consistency and availability can be satisfied.

CAP theorem and NOSQL databases

When drawing analogies with NoSQL databases (following BASE principles), we often argue that it's impossible to guarantee scalability and availability at the same time. However, CAP theorem doesn't really talk about scalability, only availability.

There are 3 kinds of NoSQL databases following CAP theorem:

  1. CP database - Delivers consistency and partition tolerance at the expense of availability. When a network partition occurs, the system shuts down the node to avoid drop in consistency.
  2. AP database - Deliver availability and parition tolerance at the expense of consistency. When a network partition occurs, the nodes at the wrong end of the network partition may return stale data.
  3. CA database - Delivers consistency ana availability and cannot tolerate network partitions. And hence, fault tolerance. The databases are hard to exist because network partitions are unavoidable.

Return to Index