Zero, problem,

1. What granularity does CAP theory focus on?

2. Does memcache cluster conform to CAP theory? Mysql? Kafka?

A brief introduction

It was proposed as a conjecture in 2000 by Eric Brewer, a computer scientist at the University of California, Berkeley.

It was proved in 2002 by Seth Gilbert and Nancy Lynch of THE Massachusetts Institute of Technology, making it an accepted theorem in distributed computing.

When Brewer put forward CAP conjecture, he did not define clearly the definitions of Consistency, Availability and Partition Tolerance in detail. Therefore, we would feel confused when inquiring the definition of CAP. The detailed definition of CAP varies slightly from one source to another.

Such as:

! [image-20200703192859861](/Users/lipengpeng/Library/Application Support/typora-user-images/image-20200703192859861.png)

Second, CAP theory

See Robert Greiner (robertgreiner.com/about/)

! [image-20200707124323279](/Users/lipengpeng/Library/Application Support/typora-user-images/image-20200707124323279.png)

Robert Greiner also experienced a process of understanding CAP. He wrote two articles to expound CAP theory, and the first one was labeled “outdated” (some Chinese translations just refer to the first one). We will compare the differences between the two explanations to have a deeper understanding of CAP theory.

concept

First edition Explanation:

For a distributed computing system, it is impossible to satisfy three design constraints of Consistence, Availability and Partition Tolerance at the same time.

Second Edition Explanation:

In a distributed system (a collection of nodes connected to each other and sharing data), when it comes to read and write operations, only two of Consistence, Availability, and Partition Tolerance can be guaranteed, and the other must be sacrificed.

Contrast:

There are several key differences: The second edition defines what distributed systems are in CAP theory, with an emphasis on two things: interconnection and sharing of data.

Distributed systems do not necessarily connect and share data. The simplest cluster, such as Memcache cluster, does not connect and share data with each other. Therefore, Memcache cluster and other distributed systems do not conform to the object discussed by CAP theory. MySQL cluster is interconnected and data replication, so it is the object of CAP theory. The second edition’s emphasis on “read and write operations” is a continuation of the previous difference. That is, CAP focuses on reading and writing data rather than all the functionality of a distributed system. For example, ZooKeeper’s election mechanism is not the subject of CAP. The second version is more precise.

consistency

All nodes see the same data at the same time.

For a given client, a read operation is guaranteed to return the latest write result

Contrast:

1) The first version is described from the perspective of node, and the second version is described from the perspective of client. In contrast, version 2 is more consistent with the way we view and evaluate systems, which is to observe the behavior and characteristics of the system from the perspective of the client.

2) The first edition emphasized the same time + same data, while the second edition did not. According to? The transaction! Although the data of each node in the transaction is inconsistent, the data read by the client is consistent.

availability

Every request can receive a success or failure response.

The second version explains: non-failed nodes return reasonable responses (not error and timeout responses) in a reasonable amount of time.

Contrast:

1) Is a request still usable if it receives a failed response? 2) Even a successful response may not be correct, such as a successful response that should return 100 but actually returns 90, but does not get the correct result. Does this work? (Some time ago, Java qconf was changed, but the data was wrong, and a lot of people reported the problem offline and online)

By contrast, the second version of the explanation makes it clear that 1) nodes cannot fail and 2) responses cannot time out or fail, but can be reasonable without saying “correct” results. For example, if you should have returned 100 but you actually returned 90, this is definitely not the correct result, but it could be a reasonable result. (Database synchronization delay)

Zonal tolerance

The first version explains: The system can continue running when a message is lost or a partition error occurs.

The second version explains: After a network partition occurs, the system can continue to “perform its duties.”

Contrast:

1) Work was used in the first edition, and function was used in the second edition. Work emphasizes “running”. As long as the system does not break down, we can all say that the system is working. Returning errors is also work, and refusing service is also work. Function emphasizes “playing a role” and “performing its duties”, which is in line with usability. That is, a function is only one that returns a reasonable response. The second edition, by contrast, is more explicit.

2) The first version describes the partition with the message loss or partition error, the second version directly uses the network partition, no matter what the reason, may be packet loss, may also be the connection interruption, may also be congestion, as long as the network partition caused, it is counted in the inside.

To sum up: CAP theorem is that only two of Consistence, Availability and Partition Tolerance can be guaranteed when read and write operations are involved in a distributed system (refers to a collection of nodes connected and sharing data). The other must be sacrificed. Consistency refers to the guarantee that a read operation can return the latest write operation result for a specified client. Availability means that non-failing nodes return reasonable responses in a reasonable amount of time (not error and timeout responses); Partition tolerance is the ability of the system to continue to “perform its duties” when network partitions occur.

3. CAP application

Although CAP theory defines that only two of the three elements can be selected, we will find that P (partition tolerance) must be selected in the distributed environment, because the network itself cannot be 100% reliable and may fail, so partition is an inevitable phenomenon. If we choose CA instead of P, then when partition occurs, in order to guarantee C, the system needs to forbid write. When there is A write request, the system returns error (for example, the current system does not allow write), which again conflicts with A, because A requires no error and no timeout. Therefore, it is theoretically impossible for a distributed system to choose CA architecture, only CP or AP architecture.

CP

As shown in the following figure, to ensure consistency, data on N1 node has been updated to Y after partition occurs, but data on N2 cannot be synchronized to N2 because the replication channel between N1 and N2 is interrupted, and data on N2 node is still X. In this case, when client C accesses N2, N2 needs to return Error to inform client C that “an Error has occurred in the system”, which violates the requirements of Availability. Therefore, CAP can only meet CP requirements.

AP

As shown in the following figure, to ensure availability, data on N1 node has been updated to Y after partition occurs, but data on N2 cannot be synchronized to N2 due to interruption of the replication channel between N1 and N2, and data on N2 node is still X. When client C accesses N2, N2 returns its own data X to client C, but in fact the latest data is Y, which does not meet the requirement of Consistency. Therefore, CAP can only meet AP. Note: the N2 node returns x, which is not a “correct” result, but a “reasonable” result because x is old, not a messed up value, just not the most recent.

Iv. Key details of CAP

CAP focuses on the granularity of the data, not the entire system

This sentence is a key point to understand and apply CAP theory. In the definition and interpretation of CAP theory, system-level concepts such as system and node are all used, which leads to great misdirection for many people, believing that the whole system should either choose CP or AP in the architectural design. However, in the actual design process, each system cannot only deal with one kind of data, but contains multiple types of data, some data must be selected CP, some data must be selected AP. However, if we choose CP or AP from the perspective of the whole system when designing, we will find that there are problems no matter what we do.

Take a simple user management system as an example, the user management system contains user account data (user ID, password), user information data (nickname, interests, hobbies, gender, self-introduction, etc.). Generally, user account data selects CP, while user information data selects AP. If the whole system is limited to CP, it does not meet the application scenarios of user information data. If the entire system is defined as an AP, the application scenario of user account data is not applicable. Therefore, when CAP theory is put into practice, we need to classify the data in the system according to different application scenarios and requirements, and choose different strategies (CP or AP) for each type of data, rather than directly defining all data in the whole system as the same strategy.

CAP ignores network latency

This is a very implicit assumption, and Brewer does not take delay into account when defining consistency. That is, when a transaction commits, the data can be copied to all nodes instantly. But in reality, copying data from node A to node B always takes some time. If it is the same machine room, the time may be a few milliseconds; If the equipment room is in a different region, for example, the synchronization from Beijing to Guangzhou may take tens of milliseconds. This means that C in CAP theory cannot be perfectly realized in practice. In the process of data replication, the data of node A and node B are inconsistent. (a review of consistency: consistency means that read operations are guaranteed to return the latest write results for a given client;)

In normal operation, CP and AP are not available and CA can be used at the same time.

CAP theory tells us that the distributed system can only choose CP or AP, but in fact, the premise here is that the system has “partition” phenomenon. If the system does not partition, that is to say, when P does not exist, there is no need to give up C or A, but both C and A can be guaranteed. This requires architectural design to consider CP or AP when partition occurs, and how to guarantee CA when partition does not occur. Also take the user management system as an example. Even when CA is implemented, different data implementation methods may be different. For example, the bike_last_order order_end_time in our system implements CA through Kafka. More often, the CA is implemented using master-slave synchronization of the database. There are also implementations of CA using interfaces. For example, after the user succeeds in payment, we can call back our reporting interface to tell us that the user succeeds in payment.

Giving up does not mean doing nothing, and you need to prepare for when the partition is restored.

CAP theory told us that only two of the three were left out and that the third had to be “searched for”, a term which was somewhat misleading because “searched” led many to understand that nothing had been done. In fact, the “sacrifice” of CAP theory is to say that we cannot guarantee C or A in the partitioning process, but it does not mean doing nothing. Since most of the time is normal during the entire operating cycle of the system, the partition phenomenon does not occur for a long time.

For example, a 99.99% available system (commonly known as four nines) runs for only 50 minutes a year; A 99.999% (commonly known as five nines) available system that runs for only five minutes a year. Abandoning C or A during partitioning does not mean abandoning C and A forever. We can do something during partitioning to restore the system to the CA state once the partition failure is resolved. Typically, some logs are recorded during partitioning. When a partition failure is resolved, the system uses the logs to restore data to the CA state. We adopted this method during the off-service period of transitioning table some time ago. At that time, we used AP for some internal interfaces, such as calling back to our interface after successful payment. At that time, we first recorded logs, and finally restored C through logs when the system was restored.

Five, the implied

What is the C in ACID?

The integrity of the database is not compromised before and after a transaction.

Both atomicity and consistency emphasize that the database changes (or doesn’t change) from one state to another. But the emphasis is different: atomic states of concern, either all success or all failure, no partial success. Consistency focuses on the visibility of data. Data in the intermediate state is not visible to the outside, and only data in the initial state and final state are visible to the outside

The BASE theory of

BASE is Basically Available, Soft State, and Eventual Consistency. The core idea is that even if it is impossible to achieve strong Consistency, However, applications can adopt appropriate methods to achieve final consistency.

1. A distributed system allows for a partial loss of availability in the event of a failure, i.e. the core is guaranteed to be Available. The key words here are “part” and “core.” It is a challenging task to choose which businesses can be lost and which businesses must be guaranteed. For example, for a user management system, “login” is a core function, and “registration” can be counted as a non-core function. Because the unregistered users have not used the system business, can not register is the loss of a part of the user, and this part of the user number is small. If the user is registered but cannot log in, it means that the user cannot use the system. For example, games with money can’t be played, cloud storage can’t be used… These will cause great loss to users, and the number of login users is far greater than the number of newly registered users, and the impact is larger.

2. Soft state refers to that data in the system is allowed to exist in an intermediate state, and the state is considered not to affect the overall availability of the system, that is, the system is allowed to have data delay in multiple data copies of different nodes. (The above table migration case is actually in a soft state until the final consistency is achieved with logging)

3. Eventual Consistency Indicates that all data copies in the system reach a consistent state after a certain period of time.

   The key words here are “certain time” and “eventually”. “certain time” is strongly correlated with the characteristics of data, and different data can tolerate different inconsistent times. For example, the synchronization delay of account data is required to be short, and the data delay of microblog Posting can be appropriately relaxed.

BASE theory is essentially an extension and supplement to CAP, and more specifically, a supplement to AP scheme in CAP. That is, when C cannot be guaranteed, we can make a record in a certain way, and finally realize C through certain means after the system is restored.

How does KAFKA talk about CAP in a message?

Kafka Producer has three ack mechanisms

0

Meaning that the producer does not wait for the broker to acknowledge that it has completed the synchronization and continues to send the next message

Provides minimal latency. But with the weakest persistence, data loss is likely to occur when the server fails. If P occurs then AP is satisfied and C is sacrificed.

1

This means that the producer waits for the leader to successfully receive and confirm the data before sending the next message. This option provides better persistence with low latency.

When the Partition Leader dies and Follwer has not replicated, data is lost. If P occurs then AP is satisfied and C is sacrificed.

– 1

That means the producer receives follwer’s confirmation before sending the next piece of data. If P happens then CP is satisfied and A is sacrificed.