CAP Theorem Simplified 2023 | System Design Fundamentals | Distributed Systems | Scaler

Understanding CAP theorem is essential for anyone working with distributed systems.

Hi, my name is Anchorman, and I'm one of the co-founders of Scalar Academy. If you're in tech, chances are you would have heard about CAP theory. Today, we will talk about what C, A, and P in CAP theorem stand for, why it works the way it does, and what CAP theorem means in the modern ecosystem. I was fortunate to see tech at scale at Facebook and was able to design products that served millions of queries per second and billions of users. I'm here to share a few of those learnings with you. If you like the content, please like the video and subscribe to the channel.

Alright, so let's first look at why we even need to learn CAP theorem. CAP theorem is one of the most basic principles of distributed storage. So, if you think about building or working on distributed systems in the future, CAP theorem is a must-have, must-know. That's why you need to learn CAP theorem.

Now, before I get into explaining CAP theorem, I would try to do that using the simplest example possible. I want to give credit to Kaushik, whose blog I have borrowed a few ideas from. Thank you, Kaushik, for coming up with a very innovative example.

To elaborate on CAP theorem, I'll take a real-world example. Let's say you imagine I am an entrepreneur looking for ideas, and I feel people need reminders. Let's build a service that just stores reminders. Imagine I named my company ABCD and got a very premium number, 1234-1234. People could just call me on 1234-1234, tell me what they want to remember, and when they call me back, I tell them what they wanted to remember.

This seems like a great idea, so I set up this line and sit in the office. Imagine this is me (forgive my drawing). Every time somebody calls, let's say I got a call from X, and X says, "Hey, please remember that I have a flight tomorrow at 9 PM." I say, "Great." Next time they call and ask me, "Tell me what I wanted you to remember," I tell them, "You have a flight tomorrow at 9 PM." This seems great. I charge people a very nominal amount of money to store this information, and the service takes off. Everybody needs this; there's a big market, and everybody starts using it.

Then, I start to hit a problem. Most systems start to hit problems when they scale. I realize that I'm getting a lot of calls, and I'm not enough to address all of those calls myself. So, I start to think, "Let me get my wife involved." Now, this number actually has me and my wife. Both of us sit with our diaries, and the call gets routed to either one of us, whoever is free. When I get a call, if the person is asking me to take a reminder, I just take down that reminder. When the person calls back, I respond with the reminder. Great, I have suddenly doubled my capacity. If I was able to take 1000 requests in a day before, now I can take 2000 requests because I have my wife to help me as well.

Very soon, I got my first unhappy customer. Mr. X calls me one day and says, "Hey, can you please remind me when my flight is?" I look through my diary and realize I don't have an entry corresponding to Mr. X. I tell Mr. X, "Hey, look, I don't have an entry corresponding to you." Mr. X seems very disappointed and angry and then disconnects the call. Now, I start to think about what might have happened. Either Mr. X was delusional, or maybe there was a fault at my end.

Then, I see that there might have been a problem. It is possible when Mr. X wanted to store their reminder, they might have called my wife, and my wife would have stored this entry that X wants a reminder for a flight at 7 PM tomorrow. However, that entry is not with me because that call never came to me. When X wanted to understand when their flight was, they ended up calling me instead of my wife because they only know this number, 1234-1234, and I don't have that entry.

=> 00:06:19

When your data isn't consistent, your business suffers—solve it by ensuring all entries are mirrored across systems.

Corresponding to you, Mr. X seems very disappointed, very angry, and then disconnects the call. Now, I start to think about what might have happened. Either Mr. X was delusional, or maybe there was a fault at my end. Then I see that there might have been a problem. It is possible when Mr. X wanted to store their reminder, they might have called my wife, and my wife would have stored this entry that "Hey, X wants a reminder for a flight at 7:00 PM tomorrow." However, that entry is not with me because that call never came to me. When X wanted to understand when their flight was, they ended up calling me instead of my wife because they only know this number 1234-1234, and I don't have that entry. This is why X is very unhappy.

This is what is called a consistency problem or data consistency problem, which means an end consumer might have stored some data with me, and when they ask me back, there is no guarantee that they will get the data back. It depends on where the request comes to. If the request comes to my wife, they'll get their data back; if the request comes to me, they won't get the data back if my wife's diary has that entry. This is a big problem. If not solved, my company will die. So I start to think and come up with a solution. I say, "Hey, look, here is what we could do. When X calls me to say, 'Please note down that I have a flight tomorrow at, imagine, 6 PM,' I'll note it down in my diary. I'll also tell my wife to note down this entry, which is also that tomorrow 6 PM flight."

Only when both of us have written the entry in our own diaries will I return success and tell Mr. X, "I have noted down your entry." That way, there is a guarantee that both of our diaries, my diary and my wife's diary, will have the exact same entries, ensuring consistency of data. Now, when X calls either one of us, we can respond back with the right data points. Things were going great. One day, I again start to face a problem. One day, my wife calls in sick; she's not keeping well, so she's not in the office. What that means is that my wife, for the time being, is gone for a day. At that very moment, another gentleman, Y, calls me and tells me to note down an entry. I say, "Okay, sure, what's your entry?" They tell me, "You know what, I have a flight tomorrow at 3 PM." I said, "Great, let me note it down. Let me, by the way, also go and tell my wife to note it down. Oh, by the way, my wife is not here; she can't note it down." Therefore, I'll have to tell Y that, "Hey, I can't note down your request; your request actually has failed," which means for the entire day, I can't take in any new requests.

That is an availability problem, which means my system is not available to take all kinds of write requests. In the case of software systems, for example, like Facebook, you could think of Facebook saying that for an entire day or for an hour or for a few minutes, you can't make any new posts or you can't post any new photos. That is an availability problem. So again, I'm very stressed. What do I do? I don't want my business to fail. So I think and think and come up with another solution. I say, "You know what, when my wife is not here, I have my diary, and imagine my wife is not here, so I have written a bunch of entries. This new day comes, whatever entries I get, Mr. X says to note down something, I'll note it down here. Mr. Y says to put down something, I'll note it down."

When my wife returns, because I want both of our diaries to be identical, I tell her, "Look, you'll not take up any phone calls till you have noted down all of the additional entries that I made in the previous day, or if she was gone for the last two days, then in the previous two days. So you first note down all of the additional entries and then you start taking calls." Then my problem is solved. Now, if X calls me and says, "Please note down that I have a flight tomorrow at 8 PM," even if my wife is not in the office, I can still note down the entry, and therefore, I am still available. Since my wife will come back and she will actually catch up with whatever new entries are there in my diaries before answering any phone calls.

=> 00:11:26

When systems can't communicate, you must choose between being consistent or available, but you can't have both.

Because I want both of our diaries to be identical, I tell her, "Look, you'll not take up any phone calls till you have noted down all of the additional entries that I made the previous day." If she was gone for the last two days, then she should note down the entries from the previous two days first. After noting down all of the additional entries, she can start taking calls. This way, my problem is solved. If X calls me and says, "Please note down that I have a flight tomorrow at 8 PM," even if my wife is not in the office, I can still note down the entry. Therefore, I am still available since my wife will come back and catch up with whatever new entries are there in my diaries before answering any phone call. This consistency is great, and things are going super well.

Then comes another problem. One day, my wife and I have a fight and stop talking to each other. Imagine I get a phone call from X who says, "Please note down I have a flight tomorrow at 9 PM." I can't note it down because I'm not able to talk to my wife. If I note it down and tell X, "Hey, I've noted down your entry," my system becomes inconsistent. My diary now has different entries from my wife's, and she's still taking calls. When this network partition happens, where I'm not able to talk to my wife or other systems, I have to make a choice: do I want to stay consistent or do I want to stay available?

If I want to stay consistent, then if Mr. X calls me and says, "Please note down the entry," I will have to say, "Sorry, I can't. My system is down; it's not accepting any new write requests." If I want to stay available, then I can take down the entry, but then I become inconsistent. So, if I choose consistency, I become unavailable. If I choose availability, I become inconsistent. This is exactly the CAP theorem. The CAP theorem states that if you have consistency, availability, and partition tolerance, you can only guarantee two out of these three at any time. You can't promise all three simultaneously. When this network partition happens, I would have to choose between consistency and availability; I can't have both.

Now, I have two bonuses to add here. Most systems that are available and partition tolerant (AP) can still ensure they become eventually consistent. What does that mean? It means eventually my and my wife's diary will have the same entries. How do I ensure that? Whenever we start talking again, we can exchange notes. Imagine there is a clerk here that I've hired who takes up all of the new entries in the last hour, tells me what those entries were, and I take those down. The clerk also asks me what entries I made in the last hour, goes back to my wife, and tells her, "Here are the new entries that were made in the last hour." There might be periods in between when I was inconsistent, but eventually, we become consistent. That is eventual consistency.

There is one more extension to the CAP theorem that was done about 10 years back, called the PACELC theorem. This theorem states that when a network partition happens and my systems can't talk to each other, I have to choose between availability or consistency; I can't have both. However, there are cases when my systems can talk to each other, meaning there is no network partition, which is "else." In such cases, I have to choose between latency or consistency; I can't have both. If I decide to stay consistent, I will ensure that on every single call, my wife also notes down the entry, and only then do I return success. This means I'm waiting for my wife to note down that entry, which could take time if she is busy. Hence, the latency could become high because I want consistency. However, if I was willing to let go of consistency and just note it down, assuming my wife would catch up later, then latency could stay really low. This balance between latency and consistency is what the LC theorem addresses, which is an extension to the CAP theorem because CAP does not talk about latency.

I hope that made sense to you and was helpful. The CAP theorem is one of the most basic and useful theorems you'll come across when designing distributed systems. I'll keep doing more videos like this. If you liked this video, please like the current video and subscribe to the channel. Thank you so much. If you liked the video, please like this video and subscribe to the channel. Leave a comment if you want me to do a video on a topic that you find interesting. Thank you so much.