Skip to content
LoopBitzBlog

System Design4 min read

CAP Theorem

What the CAP theorem means in distributed systems: consistency, availability and partition tolerance, with simple diagrams.

The CAP theorem is a concept in distributed computing. CAP stands for:

  1. Consistency
  2. Availability
  3. Partition tolerance

Why distributed systems?

In standalone applications, we set up our application on one computer. If that machine is down, our application won't work. We call this a single point of failure.

So what we do is deploy our application across a network of machines. We call these distributed computer systems.

Scaling

There are two ways of scaling:

  1. Vertical scaling
  2. Horizontal scaling

Vertical scaling makes one machine bigger, horizontal scaling adds more machines

Vertical scaling

Vertical scaling is an increase in processing power. We can increase the RAM, hard disk and CPU. We increase the specification of one machine.

Horizontal scaling

Horizontal scaling is an increase in the number of machines. If some machines fail, we still have other machines.

In MySQL, what we do is, if the primary machine fails, we maintain another secondary machine as a backup.

But NoSQL databases can be distributed across multiple machines. They're not like MySQL, because there are no relations. We don't join tables in NoSQL like we do in MySQL. So NoSQL databases can be distributed across multiple machines.

Primary and worker nodes

Normally, distributed systems have a master node computer and worker node computers.

What the master node does is, once it gets a job, it distributes it between the worker nodes, and they do the work.

What the secondary (or worker) node does is complete the task given by the primary (or master) node.

Some distributed networks have one primary machine and multiple worker nodes.

One primary machine distributing work to three worker nodes

Some distributed networks don't have one fixed primary machine. They have multiple worker nodes, and at a given time the network elects a primary machine. If that machine fails, the network uses an election algorithm to choose another machine and convert it from a worker to the primary machine.

Nodes connected to each other, with one elected as the primary

The problem

In distributed systems, there are multiple machines. At a given time, when multiple users are trying to read data, one user can be connected to one machine and another user can be connected to another machine.

In that kind of scenario, how can we make sure both users see the same data from both machines? That's why we use the CAP theorem.

What the CAP theorem says

The CAP theorem says that at a given time, a distributed system can have a maximum of 2 properties. This means at a given time, a distributed system can be CA, AP or CP.

CAP stands for consistency, availability and partition tolerance

  • Consistency: in our distributed computers, every node should have consistent data.
  • Availability: all the nodes of the distributed computers should be available every time.
  • Partition tolerance: a partition is when distributed databases are separated by a network.

Partition

Two databases that normally sync over the network, with the link broken by a partition

These databases are connected by networks. In distributed computers, when we update any record in one database, it should update in the other connected databases. This happens through the networks that connect the databases.

If the network breaks, an update in one database can't reach the other database. Tolerance means the system keeps working even when the network breaks. But then it has to make a choice:

  • CP (Consistency + Partition tolerance): stop answering some requests until the network is back, so no user sees old data.
  • AP (Availability + Partition tolerance): keep answering every request, even if some users see slightly old data for a while. The databases sync again once the network is back.

Maximum 2 properties

Most of the databases in the world have a maximum of 2 properties.

CAP Venn diagram: a distributed system can have at most two of consistency, availability and partition tolerance

  • Consistency: all clients see the same view of data, even right after an update or delete.
  • Availability: all clients can find a replica of the data, even in case of partial node failures.
  • Partition tolerance: the system continues to work as expected, even in the presence of partial network failure.

In real distributed systems, network failures will always happen at some point, so partition tolerance is a must. That means the real choice is between CP and AP. CA is only possible when everything runs on a single machine, which is not a distributed system.