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

This article mainly explains "the introduction of Paxos algorithm in Zookeeper". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "introduction to Paxos algorithm in Zookeeper".

Brief introduction of algorithm

Paxos algorithm is a consistent algorithm based on message passing and high fault tolerance proposed by Leslie Lambert (Leslie Lamport) in 1990. Mike Burrows, author of Google Chubby, said that there is only one consistency algorithm in the world, and that is Paxos, and all other consistency algorithms are incomplete versions of the Paxos algorithm. Paxos algorithm is recognized as an obscure algorithm, and it is also very difficult to implement in engineering. The more famous Paxos engineering implementations include Google Chubby, ZAB, Wechat's PhxPaxos, etc.

What problem is the Paxos algorithm used to solve? The problem that the Paxos algorithm solves is how to agree on a resolution in a distributed system.

Paxos and the problem of Byzantine generals

The Byzantine general problem is a basic problem in peer-to-peer communication proposed by Leslie Lambert, author of the Paxos algorithm. The implication of this problem is that it is impossible to try to achieve consistency through message delivery on unreliable channels. Therefore, the premise of Paxos algorithm is that there is no Byzantine general problem, that is, the channel is secure and reliable, and the messages transmitted between cluster nodes will not be tampered with.

In general, there are two communication models between nodes in a distributed system: shared memory (Shared Memory) and message passing (Messages Passing). Paxos is based on the message passing communication model.

The algorithm describes three roles

There are three roles in the Paxos algorithm, each with three different behaviors. But in many cases, a process may play multiple roles at the same time.

Proposer: sponsor, put forward a proposal (Proposal)

Acceptor: voter

Learner: learner (synchronizer, that is, Proposer resolution formation, sends all formed resolutions to Learners)

Consistency of Paxos algorithm

The consistency of Paxos algorithm is mainly reflected in the following points:

When submitting a proposal, each sponsor will first get a globally unique and incremental proposal number N, that is, the unique number N in the whole cluster, and then assign the number to the proposal to be submitted.

After each voter accept a proposal, the number N of the proposal is recorded locally, so that among the proposals that have been accept saved by each voter, there will be a proposal with the highest number, which is assumed to be maxN. Each voter will only have a proposal whose accept number is greater than his or her local maxN.

In the end, only one of the many proposals was selected.

Once a proposal is selected, other servers will actively synchronize (Learn) the proposal locally.

If no proposal is put forward, no proposal will be selected.

Paxos algorithm flow

The execution process of Paxos algorithm is divided into two stages: preparation phase prepare and acceptance phase accept. A decision has been made before the Ps:Learn phase.

As the Paxos algorithm is obscure, here I will do the whole description with my own understanding, although the rigor may not be satisfactory, but the readability will be improved, hoping to give you an easier reading experience.

A, Prepare stage

The sponsor (Proposer) is ready to submit a proposal numbered N, so it first sends a prepare (N) request to all voters (Acceptor) to test whether the cluster supports the numbered proposal. If it is difficult to understand here, we can try to understand that the proponent bribes the "Accept" with banknotes.

Each voter (Acceptor) keeps the current maximum amount of bribes, that is, (maxN). When each voter receives an offer to bribe himself, he or she compares the bribe amount with the value of maxN. There are the following situations:

If N is less than maxN, the proposal is outdated (less money is not accepted), and the current voter rejects the prepare request by not responding or responding to Error.

If N is greater than maxN, the proposal is acceptable (after all, who gives more money and listens to whom), and the current voter will first record the N (current bribe amount) and feedback the proposal Proposal (myid,maxN,value), which was once the largest number of accept, to the sponsor to show the sponsor his willingness to support the proposal. The first parameter myid represents the identity id of the voter Acceptor, the second parameter indicates the largest number of the proposal he has accepted (the amount of bribes from the former leader), and the third parameter indicates the real content of the proposal value (the content proposed by the former leader). Of course, if the current voter has not made any accept proposal, the Proposal (myid,null,null) will be fed back to the sponsor.

N cannot be equal to maxN in the prepare phase. This is determined by the generation mechanism of N. In order to obtain the value of N, it must be increased by one by synchronous lock on the basis of the original value.

It needs to be explained here why, when the voter (Acceptor) determines that the amount of the bribe is greater than the maximum amount currently saved, it returns the amount saved by the predecessor and the content of the proposal to the sponsor. This is because the sponsor (Proposer), after receiving the voter's reply, needs to determine who is the richest sponsor, and then elects it as the leader (to revise his own proposal).

B, Accept stage

When the sponsor (Proposer) sends out prepare (N) and receives feedback from more than half of the voter (Accepter), then the sponsor will send its real proposal Proposal (myid,N,value) to all the voter.

When the voter (Acceptor) receives the Proposal (myid,N,value) proposal sent by the sponsor, it will once again take out the largest number maxN of the proposal he has ever accept, or the largest number of the recorded prepare, and let N compare with them. If N is greater than or equal to these two numbers, the current voter accept the proposal and feed it back to the sponsor. If N is less than these two numbers, the voter rejects the proposal by not responding or responding to the Error.

If the sponsor does not receive accept feedback from more than half of the voters (someone else bribed it with more money), there are two possible outcomes. One is to abandon the proposal and not to put it forward again; the other is to re-enter the prepare stage, increase the number of proposals, and re-submit the prepare request.

If the sponsor receives more than half of the feedback, he or she will broadcast two types of information:

Send "executable data synchronization signals" to voters who have accept their proposals, that is, to ask them to implement the proposals they have received

Send "proposal + executable data synchronization signal" to voters who have not sent accept feedback to them, that is, they will implement the proposal as soon as they receive the proposal.

In the above process, if a proposal receives a response from a majority of the Acceptor (the N in the Proposal must be greater than the current maxN to respond), the proposal is adopted and synchronous data is sent to all voter and leaner to achieve data consistency.

Of course, the above is only a simple description, the real algorithm scenario is more complex, all proponents, decision makers identity information is cross, if the number of proponents and recipients is 4, 5. But if you follow the above idea, you will eventually find that the only proposal wins with a majority of votes, so that other proponents and decision makers synchronize the proposal.

Livelock problem

The above process may cause livelock problems, so what is a livelock?

Live lock refers to the process in which the task or executor is not blocked, and some conditions are not met, resulting in repeated attempts-failures-attempts-failures. The entity in the livelock is constantly changing its state, and the livelock may unlock itself.

So how did the above behavior cause a livelock? Next, let's analyze it together:

Throughout the election process, it is totally uncontrollable for everyone who comes first and who arrives later, and when the "recipient" can receive the message from the "proposer".

Suppose that the first sponsor, A (Proposal), has successfully passed the prepare stage and is ready to send Accept to the Acceptors broadcast. When a richer sponsor B also broadcasts the prepare request to the Acceptors and sends it to the decision maker before A's accept request arrives, there is no doubt that the decision maker will receive the request and record it. At this time, A's accept request arrives late, and the amount of bribes paid by the decider to this proposal is already less than the current record prepare maximum number, so if he does not respond to proponent A, the proponent A will receive more than half of the response and the proposal will be abandoned. At this time, it re-initiates the preapre broadcast request with a bribe amount greater than Proposer A, and then the accept request of Proponent B has not yet reached the Acceptors, so the Acceptor also accepts the prepare request and records it. After that, the accept request sent by Proponent B arrives, and the decider finds that the bribe amount is less than the maximum bribe amount of the current prepare, so he refuses to respond, which will lead to livelock problems.

Summary

The story of this article basically ends here. Let's sum it up. In fact, the Paxos algorithm mainly consists of two stages:

The prepare phase, which mainly prepares a proposal numbered N, first sends a prepare request to all Acceptor to test whether the numbered proposal is supported.

In the accept phase, when more than half of the responses to a proposal are received, the proposal content proposal will be formally distributed. If more than half of the proposal is submitted successfully, it will be broadcast to all learner.

At this point, I believe you have a deeper understanding of "the introduction of Paxos algorithm in Zookeeper". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.