Everything you did not know about the CAP theorem

During my first experience with distributed systems, I constantly came across a certain CAP-theorem, I had to dig a fair amount to study and understand it from all sides. I am not a database wizard, but I hope that my little exploration of the world of distributed systems will be useful for ordinary developers. In this article I will talk about what CAP is, its problems and alternatives, and also consider some popular database systems through a CAP prism.

CAP Theorem

This theorem was presented at a symposium on distributed computing principles in 2000 by Eric Brewer. In 2002, Seth Gilbert and Nancy Lynch of MIT published a formal proof of Brewer's hypothesis, making it a theorem.

According to Brewer, he wanted the community to start a discussion about compromises in distributed systems and after a number of years began to make amendments and reservations to it.

What is behind CAP

CAP says that in a distributed system it is possible to select only 2 of 3 properties:

• C (consistency) - consistency. Each reading will give you the most recent entry.
• A (availability) - availability. Each node (not falling) always successfully executes requests (for reading and writing).
• P (partition tolerance) - distribution tolerance. Even if there is no connection between the nodes, they continue to work independently of each other.

There is already enough clear evidence of this theorem, so I will give links to Bauman University and the proof in the form of the service “Call, I will remind!” .

Basically it's all a triangle

Many articles come down to such a simple triangle.

Put into practice

To apply the CAP theorem in practice, I chose the 3 most suitable and quite popular database systems, in my opinion: Postgresql, MongoDB, Cassandra.

Take a look at Postgresql

The following items relate to the abstract distributed Postgresql database.

• Master-Slave replication is one common solution.
• Synchronization with Master in asynchronous / synchronous mode
• The transaction system uses a two-phase commit to ensure consistency.
• If partition arises, you cannot interact with the system (in the main case)

Thus, the system cannot continue to work in the case of partition, but provides strong consistency and availability. This is a CA system!

Let's look at MongoDB

The following items relate to the MongoDB abstract distributed database.

• MongoDB provides strong consistency because it is a system with one Master node, and all entries go by default to it.
• Automatic change of the master, in case of separation from the other nodes.
• In the event of a network separation, the system will stop accepting records until it is satisfied that it can safely complete them.

Thus, the system can continue to work in case of network separation, but the CAP-availability of all nodes is lost. This is a CP system!

Take a look at Cassandra

Cassandra uses a master-master replication scheme, which in fact means an AP system in which network sharing leads to the self-sufficient functioning of all nodes.

It would seem simple ... But it is not.

CAP Issues

A lot of detailed and interesting articles have been written on the topic of problems in the CAP theorem here on Habré, so I will leave a link to the CAP no longer relevant and myths about the CAP theorem . Be sure to read them, but treat each article as a kind of new look and do not take it too close to your heart, because some scold, others praise. I myself will not go too deep, but try to give out some necessary compilation.

So, the problems of the CAP theorem are:

• Definitions far from the real world
• As part of the development, the choice is mainly between CP and AP
• Many systems are just P
• Pure AP and CP systems may not be what you expect

What is wrong with the definitions?

Consistency in CAP actually means linearizability (and it's really hard to achieve). To explain what linearizability is, let's look at the following picture:



In the described case, the referee finished the game, but not every client gets the same result. To make his system linearized, we need to instantly synchronize data between the referee and other data sources, so that when the referee finishes the game, each client receives the correct information.

Availability in CAP, by definition, has two serious problems. The first - there is no concept of partial availability, or some degree of it (percentages for example), but there is only full availability. The second problem is unlimited response time, i.e. even if the system answers for an hour, it is still available.

Resistance to distribution does not include fallen nodes, and here's why:

1. By definition. In availability, it says "... every node (if not failed) always ..."
2. Based on the evidence. The proofs of the CAP theorem state that some code must be executed on the nodes.
3. Well, some of my (and not only) conjectures. In the event of a node crash, the system can recover, communicate with other nodes and continue to work as if nothing had happened. In case of network separation, you will have to wait for the connection to be restored.

Therefore, you need to remember about the ability of the system to recover, but beyond the scope of the CAP theorem.

AP / CP selection

Communication between nodes usually occurs through an asynchronous network, which can delay or delete messages. The Internet and all our data centers have this property, and these are not unlikely incidents, so CA systems are rarely considered in the development framework.

Many systems are just P

Imagine a system in which two nodes (Master, Slave) and a client. If you suddenly lost contact with Master, the client can read from Slave, but cannot write - there is no CAP-availability.

Ok, like a CP system, but if Master and Slave synchronize asynchronously, then the client may request data from Slave before successful synchronization - we lose CAP-consistency.

Pure AP and CP systems

Pure AP systems can simply include 2 number generators. Pure CP systems may not be available at all, as I will try to come to an agreed state and will not answer us. We go further, CP systems give us not expected strong consistency, but eventual consistency. We will talk about him a little later.

How to live with it

After all, this is just an attempt to classify something abstract, so you don't need to reinvent the wheel. I recommend using the following approach when trying to work with distributed databases:

• Be aware of CAP definitions and their limitations.
• Use the PACELC theorem instead of CAP, it allows you to look at the system from another angle.
• Remember the ACID / BASE principles and how they apply to your system.
• Any body movements should be done, given the project you are working on.

Pacelc

The PACELC theorem was first described and formalized by Daniel J. Abadi of Yale University in 2012. Since the PACELC theorem is based on CAP, it also uses its definitions.

The whole theorem reduces to IF P -> (C or A), ELSE (C or L).

Latency is the time for which the client will receive a response and which is regulated by some level of consistency. Latency (latency), in a sense, represents the degree of availability.

A bit about BASE

BASE is a peculiar contrast of ACID, which tells us that true consistency cannot be achieved in the real world and cannot be modeled on highly scalable systems.

What is behind BASE:

• Basic Availability. The system responds to any request, but this response may contain an error or inconsistent data.
• Soft state The state of the system may change over time due to changes in the final consistency.
• Eventual consistency. The system will eventually become consistent. She will continue to accept data and will not check every transaction for consistency.

I was asked several times about which is better ACID or BASE - it depends on your project. For example, if your data is not critical and the user really cares about the speed of interaction, BASE would be the best option. If the opposite is true, ACID will help you make the system as reliable as possible in terms of data.

A fresh look

Now that we know about most of the pitfalls, let's try to look at the same popular database systems through the prism of knowledge gained.

Postgresql

Postgresql does allow many different system configurations, so it’s very difficult to describe them. Let's just take the classic Master-Slave replication with implementation through Slony.

• The system works in accordance with ACID (there are a couple of problems with two-phase commit, but this is outside the scope of the article).
• In the event of a disconnection, Slony will try to switch to the new Master, and we have a new master with its consistency.
• When the system is operating normally, Slony does everything to achieve strong consistency. In fact, ACID is the reason for the big delay in this system.
• System classification - PC / EC (A).

Mongodb

Let's find out something new about MongoDB:

• This is ACID in a limited sense at the document level.
• In the case of a distributed system - it's all about that BASE.
• In the absence of network partitions, the system ensures that reading and writing are consistent.
• If the Master node falls or loses contact with the rest of the system, some data will not be replicated. The system will select a new wizard to remain available for reading and writing. (The new master and the old master are inconsistent).
• The system is regarded as PA / EC (A), since most nodes remain CAP-available in the event of a break. Remember that in CAP MongoDB is usually considered as CP. The creator of PACELC, Daniel J. Abadi, says there are far more problems with consistency than with accessibility, so PA.

Cassandra

• Designed for "high-speed" interaction (low-latency interactions).
• ACID at the record level.
• In the case of a distributed system - it's all about that BASE.
• If a disconnection occurs, the remaining nodes continue to function.
• In the case of normal operation, the system uses levels of consistency to reduce latency.
• The system is regarded as PA / EL (A).

conclusions

• The trade-offs of distributed systems are where to start the design process.
• It is difficult enough to classify an abstract system, it is much better to first formulate the requirements based on the technical specifications, and only then correctly configure the desired database system.
• Don’t bother, we are just curious developers, if you have any doubts, contact an expert.

Thanks for attention!