CAP Theorem

We don't hear a lot about theorems when talking about computer science, but when we do, it is either in your examination hall or your system design interview and you can't afford to mess up either one of them.

Today we'll talk about one of the most important yet simple theorems in computer science. It is called the CAP Theorem.

So what is this CAP? Claude Answering Your Prayers? Sadly no, not in this scenario.

Rather than going with the full form of this abbreviation, we'll try to understand the situation with an example first and see how beautifully CAP theorem fits into real life.

The Business

Consider you and your partner (don't blush please) started a business to sell some stuff. You're that old-fashioned couple who likes to take orders on a call and write them down in a diary. You both sit at the same desk, one diary each, right next to each other.

From day one, you set a ground rule.

Note

Whoever receives an order updates both diaries before confirming the sale. Your own diary and your partner's diary. Both, every single time.

This means at any point in time, both diaries have the exact same count. And if you and your partner receive calls at the same time, one of you will be in the middle of writing in both diaries. The other can see that and knows the count is being updated, so they wait for the write to finish before confirming their sale.

No confusion. No overselling. The diaries are always in sync.

Let's say you start the day with 10 products in stock. Both diaries say 10.

• A customer calls you and orders 3 items. You update both diaries: 10 - 3 = 7. Sale confirmed.
• Your partner gets the next call, 2 items. They check both diaries, see 7, update both to 7 - 2 = 5. Sale confirmed.

Clean, consistent, no surprises. This is what a normal day looks like for you.

The Argument

Now one fine day, you and your partner get into a heated argument. No one's willing to back down and say sorry. So you show up to work not on speaking terms.

You start the day with 10 in your diary. Your partner starts with 10 in theirs.

Remember the ground rule? You can't reach over and write in your partner's diary anymore. So when an order comes in, you only update your own.

• A customer calls you, wants to buy all 10 items. Stock cleared. WOHOO! You update your diary to 0. Your partner's diary still says 10.
• Simultaneously, a different customer calls your partner, also wants all 10 items. Your partner's diary says 10. Stock cleared again. WOHOO??

You just oversold. 10 items, sold to 20 people. If this were concert tickets, you are in serious trouble.

Lack of communication always causes problems :)

The no-talking situation between you and your partner is what we call a network partition. A breakdown in communication between two parts of your system. And the mess it caused is exactly the problem that CAP Theorem is trying to help you reason about.

So What Do You Do?

When the argument happens and a call comes in, you have two choices.

Choice 1: Refuse to confirm any sale until you and your partner are back on talking terms. You pick up the phone, but you tell the customer you can't process their order right now. Some customers leave. But nobody gets oversold. The data is always correct.

Choice 2: Keep taking orders based on whatever your own diary says. Customers always get served. But during the no-talking period, you might oversell. Once you patch things up, you sort out the diaries and fix the count.

Neither choice is obviously wrong. It depends entirely on what you're selling.

• Concert tickets? Choice 1. Overselling 10 slots to 20 people is a disaster you cannot recover from gracefully.
• Coffee? Choice 2. You think you have 10 cups left but actually have 9. You can always apologize.

Now Let's Put Names to Things

What you just read is the entire intuition behind CAP Theorem. Now let's give the concepts their actual names.

C: Consistency

Both diaries always show the same number. Every node in your system has the same, latest data. Nobody is working off old information.

A: Availability

The system always picks up the phone. Even if the answer is a little outdated, you still get one.

P: Partition Tolerance

The system doesn't just die when a partition happens. It survives. The business still exists during the argument. What changes is how it behaves while the two of you aren't talking, and that is where C and A come in.

The CAP Theorem says that during a partition, you must choose between Consistency and Availability.

Since partitions in real systems are going to happen no matter what, partition tolerance is something you just have to build for. Hardware fails. Networks go down. So the real question is, when a partition happens, which one do you let go?

CP: Consistency over Availability

You stop taking requests if it means the data might be wrong. Think about your bank. When something looks off during a transaction, it just fails. You'd much rather see a failed payment than have your account balance be a complete mystery.

AP: Availability over Consistency

You keep responding even during a partition and sort the data out once things are back to normal. This is called eventual consistency: things will be correct eventually, just not right this second. Think about when @AskMaddyy posts something on X. If your friend in another country doesn't see the post for a few seconds, that is fine. It'll show up. (Though I would argue X should make this CP because everyone needs to see the post right away, it is that important.)

One More Thing

A lot of people think CAP is something you pick once for your whole system. It is not.

Different parts of the same system can make different choices. Take Amazon.

• Browsing products and reading reviews? AP. A slightly old review count is not a big deal.
• Placing an order and moving money? CP. Getting that wrong is not okay.

Same product, two different choices, depending on what is actually at stake.

The Takeaway

Every distributed system makes this tradeoff, whether the people building it knew about CAP Theorem or not. The theorem just gives you the words to talk about it properly.

Before you pick a database or design a system, ask yourself honestly, when things go wrong, what hurts more, wrong data or no data?

Answer that and you'll know exactly where you stand.