Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "analyzing CAP and Paxos consensus algorithms". Many people will encounter this dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

What is CAP?

There has been a lot of background introduction about CAP theory, but there is no more introduction here. Let's talk about how to understand it.

Explain three nouns in easy-to-understand words:

Consistency

If you have just written to one node, then what is read from another node must be the data that has just been written, not the older data.

Usability

If a node is requested, the node must be able to reply, and if the node dies, there will be no availability.

Partition tolerance

Whether the network partition is tolerated, that is, nodes can not be allowed to communicate with other nodes.

What CAP means is that we can only guarantee that two of these conditions are true at the same time.

Let's see why.

As shown in the figure, if we satisfy the partition tolerance, that is, the dotted line indicates that two nodes are partitioned.

If consistency is to be met, we can only allow the operation requesting another node to hang temporarily and return the result of client failure or timeout. This often happens in situations such as the bank counter that require high data consistency, because it is more important to ensure the correctness of the number of user funds than to make it impossible for users to operate temporarily.

If you want to meet usability, because the network is isolated, there is no way to achieve consistency, which often happens in the Internet industry, such as news, where there is no high requirement for data consistency but high usability. After all, it is much more important for users not to see the news at all than not to see the timely news.

You can combine freely on your own, and it will eventually prove that the three conditions cannot be met at the same time. In fact, in most cases, we just choose between consistency and usability.

Consistency = Consensus?

Consistency is so badly used by the industry that when we talk about consistency, we are not sure whether each other's consistency is consistent with our own.

Consistency: consistency, Consensus: collaboration, these two concepts are easily confused.

What we often call Consistency in a distributed system means that for multiple copies of the same data, the external data consistency, such as linear consistency, causal consistency, final consistency, etc., are used to describe the consistency in the replica problem. Consensus (Consensus) is different. To put it simply, consensus problem is a process in which multiple nodes reach the same state through some algorithm. In my opinion, consistency emphasizes results and consensus emphasizes process.

Consensus? State machine?

The consensus has a more compelling title:

Consensus algorithm based on State Machine replication

So, what is the state machine?

State machine is the abbreviation of finite state automaton, and it is a mathematical model abstracted from the operation rules of real things.

Look at the picture below. The door has two states, open and closed. Therefore, in my opinion, the state is a static scenario, and the transition gives it a dynamic change.

For this analogy, if the current data of a node is X, and now you have the operation log of add+1, then the current state is X, OK, the state (X) is there, the change (operation log) is there, and this is the state machine.

Distributed consensus, simply put, is the whole process in which all nodes in the system agree on a state after one or more nodes have proposed what a state should be.

Consensus is the process and consistency is the result.

Consensus model

Master-slave synchronization:

We all know the master-slave synchronization (Master-Slave Replication) of MySQL and other common databases in the industry. Master-slave synchronization is divided into three stages:

Master accepts write request

Master replicates logs to Slave

Master waits until all are returned from the library.

It can be seen that there is a fatal problem in the master-slave synchronization model: as long as one node fails, the Master will block, resulting in the unavailability of the whole cluster, ensuring consistency and greatly reducing the lack of availability.

Majority:

Each write is greater than 2 nodes of Njump, and each read is guaranteed to be read from 2 nodes of Number. The majority model seems to perfectly solve the problem of multi-node consistency, which means poor performance, but not necessarily in the case of concurrency, as shown in the following figure:

In the concurrent environment, because the writing order of the operation log of each node can not be guaranteed to be consistent, the final consistency cannot be guaranteed. As shown in the picture, it is directed to three nodes.

Inc5, set0 two operations, but because the order is not the same, the final state of two is 0, one is 5. Therefore, we need to introduce a mechanism to number each operation log, which is generated from small to large, so that each node will not make a mistake. (do you think of subcontracting and reorganization in the network?) So, now the key question comes again, how to cooperate with this number? It seems that this is the problem of chickens laying eggs and laying eggs.

Paxos

The Paxos model attempts to explore a more general form of distributed consensus problems.

The inventor of Lesile Lamport,Latex, proposed the Paxos algorithm. He imagined a Greek city-state called Paxos, an island that made laws according to the political model of parliamentary democracy, but no one was willing to devote all his time and energy to it. Therefore, neither the congressman, the speaker nor the waiter who delivered the note can promise that others will show up when they need it, nor can they promise to approve the time for the latter to transmit the message. Because Paxos was so difficult to understand, Lamport felt that his peers could not understand his sense of humor, so he later republished a simple version of the algorithm description "Paxos Made Simple".

The consensus algorithm as a whole, there are two stages, such as the figure, the first stage is the proposal, the second stage is the decision.

If a distributed system wants to achieve fault tolorence, it needs a consensus model, and for nodes to reach a consensus, it not only needs the algorithm between nodes, but also depends on the behavior of client. For example, even if the replica system uses multi-paxos to synchronize log sequence numbers on all replica servers, if Client is allowed to write data from non-Leader nodes, the whole replica system is still not strongly consistent.

Next, here comes the highlight, introducing Paxos in detail.

Role introduction:

Client: external role of the system, request initiator. Such as the people.

Proposer: accepts the Client request and makes a propose to the cluster. And when the conflict occurs, it plays the role of conflict adjustment. For example, a congressman should propose a motion for the public.

Accpetor: proposed vote and recipient, the proposal will be accepted only when a quorum (Quorum, that is, the Majority majority) is formed. Such as Congress.

Learner: the recipient of the proposal, backup, backup, has no effect on cluster consistency. Such as a recorder.

Steps, stages:

1.Phase1a: Prepare

Proposer put forward a motion, numbered NMagi N must be greater than the previous proposal number of this proposer, and asked acceptor's quorum (most) to accept it.

2.Phase1b: Promise

If N is greater than any proposal number previously accepted by this acceptor, it will be accepted, otherwise rejected.

3.Phase2a: Accept

If a majority is reached, proposer issues an accept request containing the proposal number and content of the previous step.

4.Phase2b: Accepted

If this acceptor does not receive any proposal greater than N during this period, the proposal will be accepted, otherwise it will be ignored.

Recall that we mentioned above that synchronous numbering is a very important issue, and the green box is actually the process of synchronous numbering. Through this number, you can know the sequence of each operation log. To put it simply, the first stage, get the number, and the second stage, write to the log. As you can see, Paxos makes up for the consistency problem through two rounds of interaction at the expense of time and performance.

Now let's consider the scenario where some of the nodes' down are dropped.

Because it was the majority accptor that reached an agreement, the first phase was still numbered successfully, and all was successful in the end.

Consider the situation where proposer down is dropped.

It doesn't matter, although the first proposer failed, the next proposer has a larger proposal number, so the next proposer finally succeeds, still ensuring usability and consistency.

Potential problem: live lock

There is a livelock problem in Paxos. As shown in the figure, when the first proposer makes a request in the first stage, there is no time for the subsequent second stage request, and then the second proposer also sends the request in the first stage. If this is endless and the acceptor always stays in the process of determining the sequence number, then no one can succeed. If you encounter such a problem, it is actually very easy to solve. If you find that the sequence number has been updated by the new proposer. Then a random waiting timeout is introduced, which avoids the problem of multiple proposer conflicts.

Multi Paxos

Due to the problems of Paxos: difficult to implement, low efficiency (2 rounds of rpc), live lock.

Therefore, Multi Paxos,Multi Paxos is introduced to introduce Leader, the only proposer, through which all requests go.

Because only one node maintains the proposal number, the process of the proposal number in the first round of discussion is omitted.

And then further simplify the role.

The one on the left of the Servers is Proposer, and the other two and themselves act as acceptor, which is more like our real system. In fact, the Raft and ZAB protocols are basically the same, but the difference is very small, but the direction of the heartbeat is different.

Raft and ZAB

The Raft and ZAB protocols divide Multi Paxos into three sub-issues:

Leader Election

Log Replication

Safety

During the leader election process, roles are also redefined:

Leader

Follower

Candidate

This animation site vividly shows the process of leader election and log copying. I won't say much about it here.

In addition, the official raft website can simulate the election process on its own.

This is the end of "analyzing CAP and Paxos consensus algorithms". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.