CAP Theorem in a simple, accessible language
- Transfer
This text is a free translation of the wonderful post by Kaushik Sathupadi on the topic of distributed systems and the existing restrictions on their creation.
When developing distributed systems, you will probably often hear references to the CAP theorem. Let's try to understand it through a situation that could arise in real life.
Yesterday, when your spouse once again appreciated the fact that you remembered her birthday and gave a gorgeous gift, a funny idea came up in my head. "Hm, but people always forget everything." And you just have a brilliant memory! Why not make a new service that will fully reveal your talent? With each thought of this idea, you like it more and more. You have already come up with an advertisement that could be printed in a newspaper:
A typical call to your service would look like this:
Several months passed ...
Hooray, it’s off! Your idea is as simple as effective. The service shoots, you get hundreds of orders every day.
Everything would be fine, but there was a problem: more and more customers are waiting in line to talk with you. Some do not stand up and just hang up. Moreover: when you fell ill and could not work, the whole day of business and all the revenue disappeared. And this is not to mention unsatisfied customers who have lost the opportunity to receive information. Resolved - it's time to expand! Take a spouse to help.
So the plan is simple:
You are very excited about this idea, because:
Great! This is a distributed system! And why are all these guys making software so noisy about distributed systems, it's still so simple!
Everything goes according to plan, before ...
Two days after the introduction of the new system, you receive a call from your regular client, Ivan Andreevich:
A day later, Ivan Andreevich calls you again:
How could this even happen? Maybe Ivan Andreevich just lied? You think about what happened, and a thought strikes your head. Maybe Ivan Andreevich called your wife? You find her notebook, and, oh yes, as you expected, on the page of Ivan Andreevich indicated that he was supposed to leave for New York yesterday.
What a terrible flaw in your seemingly beautiful scheme! Your distributed system is not consistent! There is always a chance that the client will tell something to you or your wife, and the next call he will get to another person who will not be aware of the latest changes.
Your competitors could safely ignore poor service, but you, of course, care about your customers and reputation. While your wife was sleeping, the problem did not bother you; you spent the whole night thinking and trying to find a way out and situations. Bingo! When the wife woke up, at the same moment you talk to her about new plans:
You notice the only problem - you cannot work in parallel. Every time a colleague calls you for synchronization, you cannot answer customer calls - you will be busy. But this is not so scary, because most calls come with a request to remind something (search), and not to remember something (update).
The main thing is to answer the client correctly at all costs.
“Excellent,” your spouse tells you, “However, there is another gap you did not think about. What if one day someone cannot go to work? Then we won’t be able to accept a single request to remember, because the other person will not be able to write down the changes in his notebook. This brotherwe get an accessibility problem, because, for example, if an update request comes to me, I won’t be able to complete the client’s call: even if I wrote the changes to my notebook, I won’t be able to write them to yours. Thus, I can’t say goodbye to the client! ”
You have already realized why distributed systems are not as simple as you thought. Is it difficult to come up with a solution that would be both “accessible and agreed upon” ? Someone may have given up, but not you! Your competitors did not dream about what you came up with. And again you will eagerly awaken your wife ...
“Look, this is what we need for accessibility and consistency.” The plan is almost the same as last time, but with important changes:
Ingenious! You cannot find a single flaw in the resulting solution. Now “Call, let me remind you” is simultaneously available and consistent service.
Everything seems to be fine already that day. Your system is consistent. Everything works, even if one of you cannot go to work. But what happens if you both come to work, but one of you cannot update the information of the other? Remember how you woke up your wife with another brilliant delirium? What if your wife decides to receive calls, but is too offended by you and decides not to talk with you all day? Your whole business will turn into a pumpkin again! Your idea is still good for its consistency and accessibility, but it is very sensitive to the separation of communications! Of course, you can not accept a single call while you are in a quarrel, but then your system will be unavailable all this time ...
So, let's now take a look at the CAP theorem. It is argued that when developing a distributed system, you cannot achieve three properties at the same time: accessibility, consistency, and tolerance for network sharing. You can choose only two of:
Here is one more reason to think about it. You can hire a courier. He will update your spouse’s or notebook at a time when the information in another book has changed. The biggest benefit of this approach is that it can work in the background and someone’s update does not block another person in order to update. Thus, many NoSQL solutions work, one node locally updates itself and the background process synchronizes the other nodes, respectively. The only problem is that consistency is lost for a while. For example, a client calls your wife and until the courier reaches you, he calls back and gets on the line to you. As you can see, he will get an uncoordinated answer. But still, it remains a great idea if such cases are limited. For instance,
I tried to explain the CAP theorem and Eventually Consistency to you in a simple, accessible language. I will gladly accept your questions, comments and comments.
When developing distributed systems, you will probably often hear references to the CAP theorem. Let's try to understand it through a situation that could arise in real life.
Part number 1: The idea of a new service - "Call, I remind!"
Yesterday, when your spouse once again appreciated the fact that you remembered her birthday and gave a gorgeous gift, a funny idea came up in my head. "Hm, but people always forget everything." And you just have a brilliant memory! Why not make a new service that will fully reveal your talent? With each thought of this idea, you like it more and more. You have already come up with an advertisement that could be printed in a newspaper:
“Call, let me remind you” - Never forget, even if you don’t remember what you forgot!
Feeling bad because you forgot something? Do not worry. Help just a phone call away!
If you need to remember something, just call and let us know! Let's call us and tell your boss the phone number. Forget about him. When you need to remember him, call back and we will definitely remind you.
Only 3 rubles per call.
A typical call to your service would look like this:
- Client: - Hello, could you remember my neighbor’s birthday?
- You: - Of course, what number?
- Client: - The second of January.
- You: - (Write the date in the notebook) That's it, write it down. Call us anytime you need something.
- Client: - By the way, the idea came to me here that he should give a radio-controlled helicopter, he loves such things!
- You: - A great gift idea, we will definitely remind you of it.
- Client: - Thank you!
- You: - Always please, 3 rubles have been withdrawn from your account.
Several months passed ...
- Client: - Hi, I think I forgot something ...
- You: - Good afternoon, of course, a couple of seconds ... (We are looking for the client’s page in the notebook)
- You: - Thank you for waiting. A week later, your neighbor’s birthday, do not forget to congratulate him and give a radio-controlled model of a helicopter.
- Client: - Exactly, thanks a lot! And the gift is super, you guessed it?
- You: We are always happy to help, 3 rubles have been withdrawn from your account.
Part 2: Business is growing
Hooray, it’s off! Your idea is as simple as effective. The service shoots, you get hundreds of orders every day.
Everything would be fine, but there was a problem: more and more customers are waiting in line to talk with you. Some do not stand up and just hang up. Moreover: when you fell ill and could not work, the whole day of business and all the revenue disappeared. And this is not to mention unsatisfied customers who have lost the opportunity to receive information. Resolved - it's time to expand! Take a spouse to help.
So the plan is simple:
- We hand you and his wife by an additional telephone.
- Customers continue to call the same number: there is no need to remember several numbers.
- The PBX redirects customer calls to someone who is currently free.
You are very excited about this idea, because:
- You can serve twice as many customers.
- Even if someone gets sick and cannot work, the service does not stop and continues to function.
Great! This is a distributed system! And why are all these guys making software so noisy about distributed systems, it's still so simple!
Everything goes according to plan, before ...
Part 3: First Failure
Two days after the introduction of the new system, you receive a call from your regular client, Ivan Andreevich:
- Ivan: - Good afternoon.
- You: - Hello, “Call, let me remind you!”, How can we help you?
- Ivan: - Remind me, please, I didn’t forget anything there?
- You: - For a second ... (look in the notebook, but on the page of Ivan Andreevich there is nothing worth recalling)
- You: - No, everything is fine, you have not forgotten about anything, Ivan Andreevich!
- Ivan: - Great, thanks a lot.
A day later, Ivan Andreevich calls you again:
- Ivan: - You let me down a lot, you have a terrible service. I had a business trip to New York on important matters, and I missed the plane. And most importantly, I asked you to remind, but no, you lied. I am very angry. (beeps)
- You: - But how ...
How could this even happen? Maybe Ivan Andreevich just lied? You think about what happened, and a thought strikes your head. Maybe Ivan Andreevich called your wife? You find her notebook, and, oh yes, as you expected, on the page of Ivan Andreevich indicated that he was supposed to leave for New York yesterday.
What a terrible flaw in your seemingly beautiful scheme! Your distributed system is not consistent! There is always a chance that the client will tell something to you or your wife, and the next call he will get to another person who will not be aware of the latest changes.
Part 4: Solving the Consistency Problem
Your competitors could safely ignore poor service, but you, of course, care about your customers and reputation. While your wife was sleeping, the problem did not bother you; you spent the whole night thinking and trying to find a way out and situations. Bingo! When the wife woke up, at the same moment you talk to her about new plans:
- When a customer calls one of you and wants to remember something, before saying “Thank you, we wrote everything down”, you call another person and report the changes.
- Thus, both of you have recorded all the latest updates.
- When a client calls in order to remind himself of something, you do not need to call your spouse - you always have all the right and relevant information with you.
You notice the only problem - you cannot work in parallel. Every time a colleague calls you for synchronization, you cannot answer customer calls - you will be busy. But this is not so scary, because most calls come with a request to remind something (search), and not to remember something (update).
The main thing is to answer the client correctly at all costs.
“Excellent,” your spouse tells you, “However, there is another gap you did not think about. What if one day someone cannot go to work? Then we won’t be able to accept a single request to remember, because the other person will not be able to write down the changes in his notebook. This brotherwe get an accessibility problem, because, for example, if an update request comes to me, I won’t be able to complete the client’s call: even if I wrote the changes to my notebook, I won’t be able to write them to yours. Thus, I can’t say goodbye to the client! ”
Part 5: The Brilliant Idea Comes to You
You have already realized why distributed systems are not as simple as you thought. Is it difficult to come up with a solution that would be both “accessible and agreed upon” ? Someone may have given up, but not you! Your competitors did not dream about what you came up with. And again you will eagerly awaken your wife ...
“Look, this is what we need for accessibility and consistency.” The plan is almost the same as last time, but with important changes:
- When a client calls one of you and wants to remember something, before saying “Thank you, we wrote everything down”, you check to see if a colleague is available and, if available , call another person and report the changes.
- If a colleague is not available, then you write an e-mail with information about new updates.
- First of all, after your absence from work, you or your spouse check your mail and write down the changes before receiving calls.
Ingenious! You cannot find a single flaw in the resulting solution. Now “Call, let me remind you” is simultaneously available and consistent service.
Part 6: Spouses quarrel sometimes
Everything seems to be fine already that day. Your system is consistent. Everything works, even if one of you cannot go to work. But what happens if you both come to work, but one of you cannot update the information of the other? Remember how you woke up your wife with another brilliant delirium? What if your wife decides to receive calls, but is too offended by you and decides not to talk with you all day? Your whole business will turn into a pumpkin again! Your idea is still good for its consistency and accessibility, but it is very sensitive to the separation of communications! Of course, you can not accept a single call while you are in a quarrel, but then your system will be unavailable all this time ...
Part 7: Conclusions
So, let's now take a look at the CAP theorem. It is argued that when developing a distributed system, you cannot achieve three properties at the same time: accessibility, consistency, and tolerance for network sharing. You can choose only two of:
- Consistency ( the Consistency ) - your customers once to update the information can always get the most current data when a subsequent request. And no matter how quickly they call you back.
- Availability ( Availability ) - «Call me remind you" is always available for calls at a time when at least one of the staff came to work.
- Tolerance to network sharing. ( Partition Tolerance ) “Call, I remind you” always works correctly, even if you have lost contact with your wife.
Bonus: we reach availability over time with the help of a courier.
Here is one more reason to think about it. You can hire a courier. He will update your spouse’s or notebook at a time when the information in another book has changed. The biggest benefit of this approach is that it can work in the background and someone’s update does not block another person in order to update. Thus, many NoSQL solutions work, one node locally updates itself and the background process synchronizes the other nodes, respectively. The only problem is that consistency is lost for a while. For example, a client calls your wife and until the courier reaches you, he calls back and gets on the line to you. As you can see, he will get an uncoordinated answer. But still, it remains a great idea if such cases are limited. For instance,
I tried to explain the CAP theorem and Eventually Consistency to you in a simple, accessible language. I will gladly accept your questions, comments and comments.