What is CAP Theorem?
Tags: computerscience, 100daysofcode, programming
Published: 2021-04-16 08:14:38


CAP Theorem describes the decisions we have to make when building a distributed data store. 

Let's take a look at CAP Theorem, in under 5 minutes...

(my [newsletter](https://www.baseclass.io/newsletter/cap-theorem?utm_source=devto&utm_medium=top-link&utm_campaign=cap-theorem) subscribers received this first)

---

## Why should I care?

Have you ever wanted to know:

- How distributed databases handle network failures?
- What tradeoffs we must make when designing distributed data stores?

---

## In 5 minutes or less

Eric Brewer's **CAP Theorem** tells us that a distributed data store must choose no more than two of the following:

- **C**onsistency
- **A**vailability 
- **P**artition Tolerance.

What do those definitions mean, and why can't we have all three?


Let's imagine we're designing a distributed database. 

For simplicity our database will have just two interconnected instances, or 'nodes':

![Node returning no when disconnected](https://www.baseclass.io//newsletter/cap-theorem/connected.png)

---

### Partition Tolerance

Partition Tolerance means that one or more nodes in our distributed system can be split up and unable to communicate with each other (_partitioned_), and the system can still function.

Only a complete network failure is allowed to cause the system to respond incorrectly, anything else must be tolerated.

If we have a single node then there can be no partitions. But, in a distributed system, faults are inevitable given enough time. Therefore **we cannot sacrifice  Partition Tolerance**. 

With that in mind, we can actually re-state the problem like this:

> In the event of a Partition, should we choose either Consistency or Availability?


Imagine there's a fault in our system, and the connection to one of the nodes is broken. Our distributed database is now _partitioned_. 

![Node returning no when disconnected](https://www.baseclass.io//newsletter/cap-theorem/disconnected.png)

Somebody tries to update a record on one of the nodes.. What do we do now?

---

### Choosing Consistency

'Consistency' in CAP Theorem means that I can update a record on one node, and somebody reading from another node will _immediately_ see the 
effect of my update.

(Note: this is specifically called 'linearizable consistency').

Obviously, _instant_ communication isn't realistic in a distributed environment, so in practice, the goal is to reduce this to a level where we don't notice it.

This is a really useful property if you are a banking system. It would be a big problem if I could withdraw money from one ATM, then walk down the road to another ATM and withdraw the same amount again, because the database was not consistent across all nodes.

The nodes in our example database can no longer communicate, so we cannot reflect a change across all nodes 'instantly'. 

So, if we want to make sure both nodes stay 'consistent', there are a few ways to handle this.  We could shut down entirely, or refuse all updates and only allow reads, for example.

![Node returning no when disconnected](https://www.baseclass.io//newsletter/cap-theorem/nope.png)

Because we can't accept the update request though, we are sacrificing availability...

---

### Choosing Availability

'Availability' means that if we make a request to any working node, we _must_ get a non-error response, regardless of any partitions in the system.

**The data is allowed to be out of date, or 'stale', but it must be available.**

Twitter is a good example of a system where we might choose **A**vailability. If I 'like' a tweet, but the other nodes don't reflect that 'like' immediately, it's really not the end of the world.

In this case, it's more important for the system to be 'available' and accept the update than to be 'consistent'.

In our example scenario, we could continue to allow clients to read and write to nodes on _both sides of the partition_:

![Node returning no when disconnected](https://www.baseclass.io//newsletter/cap-theorem/likes.png)


That would give us a system that is **A**vailable, but because there's no way for those nodes to keep their information in sync while partitioned, it's impossible for this to be (immediately) **C**onsistent too.

This problem is the root of CAP Theorem. **We cannot have both Consistency and Availability in the event of a partition (a loss of communication between nodes).. we must choose between the two**.

---

## Want to know more?

Check out these links:

- [You Can’t Sacrifice Partition Tolerance](https://codahale.com/you-cant-sacrifice-partition-tolerance/)
- [CAP Twelve Years Later: How the "Rules" Have Changed](https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/)
- [Please stop calling databases CP or AP](https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html)