Understanding CAP Theorem | What is CAP Theorem

CAP theorem is also called Brewer’s theorem, named after the computer scientist, Eric Brewer. We will try to answer the following questions to better understand CAP theorem:

Contributed by: Ramalingam

• What is the CAP theorem?
• Where can the CAP theorem be used as an example?
• How is CAP theorem used in the field of distributed system databases? 

Before we deep dive into the concepts, let us try to understand the distribution system. A distributed system is any network structure that consists of autonomous systems that are connected using a distribution node. Distributed systems help in sharing different resources and capabilities to provide users with a single, integrated coherent network. Why do you build a distributed system? This is because we are trying to build something more reliable than a centralized system.

With the understanding of the distribution system, now we can relate to the CAP theorem. CAP theorem stands for:

• Consistency
• Availability
• Partition tolerance

The theorem talks about the trade-offs between consistency and availability that you have to make if your system ever suffers from partitions. 

Bank example to understand CAP theorem

Let us consider a bank which has two branches and one account. Bank branches can support 

three different operations:

1. Money withdrawal
2. Money deposit
3. Check Account balance

Now the account holder walks up to a bank branch. If everything is working, then the system is relatively simple. If the account holder deposits or withdraw money, banks need to update the balance on both branch systems and then complete the track. This involves a consistent view of the account balance as it’s always the same on every branch system. As an account holder, he will like to operate the account with whatever operations he wants and also whenever he wants. Bank branch system needs to be available for him. We will consider the following negative scenario.

• A customer walks up to a Branch, and the branch system does not work. In that case, the bank branch needs to put a sign on the Bank branch saying: Today, our bank branch is not operational, please visit the nearest branch.

• Now customers walk up to a branch that’s working, but there is another branch which is not working. Now the problem is both the branch systems cannot network with each other, or their communication is too slow for the system to work. The distributed system has suffered a partition in this case. So, what does the bank branch do next when this partition happens? This is the design decision that the CAP theorem talks about. The system can make a choice either to be consistent or available, but it can’t do both.

Bank with Consistency design

If the bank has chosen a consistent design, then the branch will inform: I can’t accept deposits or withdrawals right now, because I can’t update the balance in the other bank branch. As a customer, you might get a warm fuzzy feeling, oh cool, the bank is doing everything at hand to keep my money in account balance safe. Also, you will be annoyed because you can’t use any banking services. 

Bank with availability design

In availability design, when you walk up to the branch offices and say, I can’t talk to the other branch system. But I will allow you to make the positive withdrawals and will keep track of what happened and then later when the partition heals with the other branch, the account transaction will be updated in another bank branch. So, with this design, it’s more available, even though bank branches are inconsistent in the storage of the bank balance. In a nutshell, this is the cap theorem when you design your system for availability.

Bank with degree of consistency and availability design

In the real world, we can also consider degrees of consistency and degrees of availability. Also make trade-offs.

 For example, when a partition happens, we can have bank branches:

• Accept partial deposits & withdrawal 
• Not provide balance information service.

Banks can also provide balance information but only provide tentative balance information. Which means, we are not sure if this is the correct balance, but it is probably right if you haven’t been running between ATMs.

Banks can allow withdrawals, but only allow customers to do a limited number of transactions and amount. That way, the account balance does not become negative, and the customer is not hit with a huge fee. In turn, banks can also be sued. 

In short, the bank decides to make. How much complexity do you want to add to your system, to get higher availability to the account holders? Because consistent designs tend to be simpler to build and understand. Complicated availability design can bring conflicts and can become harder or even impossible to resolve.

Above mentioned are not the only ways we could increase availability in the branch system. Banks can add power backups to branches. So, those systems are less likely to fail due to a power outage. Banks can test the software better so that we’re not going to have failures due to bugs as often. Banks might need to decide quite frankly the network doesn’t fail very often to have better customer experience.

Just a thought. Try to apply a bank example with an e-commerce portal for supply chain management. Think about amazon prime day sales where the order in your checkout becomes unavailable. What amazon should choose to be consistent in the product listing or always have the inventory to be available?

CAP theorem in distributed databases

Just a recap, before applying to the distributed databases.

Consistency means all the users can see the same data at same time.

Partition tolerance means the system continues to operate in spite of network failures.

Availability means the system continues to operate even in the presence of node failure.

Now a question arrives which databases to use for the following scenarios CA, AP and CP.

Consistency and Availability:

Relational databases are the best databases for this scenario. For better understanding, we can have below equation:

Same Data / Some Data   > Isolated Data

Example – IBM DB2, MYSQL, Microsoft SQL Server and Oracle

Consistency and Partition tolerance:

Isolated data which are always consistent. For better understanding, we can have below equation:

Same Data / Isolated Data > Some Data   

Example – Mongodb, Redis, Couchbase and Apache HBASE

Availability and Partition tolerance:

Isolated data which are always available. For better understanding, we can have below equation:

Some Data / Isolated Data > Same Data   

Example – Cassandra, CouchDB & Amazon DynamoDB

Just a reminder, though the database examples for each scenario are provided, we can also make the databases behave differently. For example, by setting up the database properties, we can also make Cassandra more consistent.

Extension to CAP theorem

PACELC Theorem:

This was developed to give a complete description of the space of potential tradeoffs for a distributed system. For a high level of understanding, it adds an else ‘E’. While you need to choose between availability and consistency if communication between partitions has failed in a distributed system, even if things are running well and there are no network issues, there is still going to be a trade-off between consistency and latency (the ‘LC’).

Amazon PIE Theorem:

Similar to the CAP theorem, here you can choose two features out of three in a data system. Features involve pattern flexibility, efficiency and infinite scale.

Conclusion

The CAP theorem is useful for establishing priorities in database server infrastructure and configuration. In such a scenario, it is still possible to achieve both consistency and availability within acceptable parameters.

I like to conclude with a quote from Napoleon Bonaparte.

“Nothing is more difficult, and therefore more precious than to be able to decide.”

Hope you were able to gain knowledge from this blog post on the CAP Theorem. I hope you make the right decision with the distribution databases. Happy Learning! To learn more such concepts, enrol with Great Learning Academy’s free online courses.