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

The main content of this article is to explain "what is zookeeper paxos". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn what zookeeper paxos is.

Let's start with a story.

Once upon a time, under the rule of King Leslie Lamport, there was a dark Greek city-state called paxos. There are three kinds of people in the polis.

Decision maker

Proposer

The masses

Although this is a dark city-state, it is very democratic. Laws are formulated in accordance with the political model of parliamentary democracy, and the masses can write proposals and opinions to the proponents, who will hand over the proposals to decision-makers. Why should there be an odd number of decision-makers? It is very simple because the way of decision-making is very mindless, and the minority is subordinate to the majority.

Finally, the decision maker announced the new decision to the world, and the masses were informed of the result of the decision.

Wait a minute, where's the darkness? The problem is that "the proponent will hand over the proposal to the decision maker." so many proposal decision makers decide who will decide first? Whoever gives more money will make a decision.

Then there will be several problems, with so many decision makers, how to ensure that the final decision is the same proposal, and how to ensure that they get the highest offer of all the proponents.

The smart and greedy decision maker came up with an idea: offer in two stages.

The first stage

The decision maker accepts all quotations that are higher than the quotation he currently holds and will not notify those who have made the previous offer.

The proponent gives quotations to all decision makers, and if someone offers more than their own price, they will increase the price, and more than half of the decision makers will stop the offer if they accept their own offer.

The state of the end of the first phase.

Every proponent feels that more than half of the bosses have accepted their own proposal and are very happy. At the moment, the status of the decision maker group is consistent, with more than half of the proposals agreed to only one, which is the highest offer (because the high can always cover the low), specific who proposed the who care, consistent on the line.

The second stage

The proponent goes to the boss who has received his own money to sign the contract. Here are three situations:

The bosses all charged others a higher price, went back to get the money and continued to bribe, went back to the first stage and upgraded again.

The highest quotation received by the boss is his own, Meizi, more than half of them successfully signed the contract, and the proposal was successful.

When the proponent went back to get the money to continue the bribe, he found that the contract had been signed and more than half of them had signed the proposal. Quit, quickly replace his proposal with the one already signed, and then submit it to all the bosses. See if you can get a piece of the pie and meet the boss who hasn't signed yet.

The state of the end of the second phase.

All proponents have the same proposal because there is the step of "quickly replacing your proposal with a signed proposal"; all members of the decision maker group end up accepting the same proposal.

The good goal has been achieved. Make this proposal known to the world and let all the masses know about it.

At the end of the story, use the correct posture to briefly introduce paxos.

What is paxos?

Paxos is a distributed consistency algorithm, which is used to solve the consistency problem in distributed systems. It can be said to be the cornerstone of distributed consistency. Almost all consistency algorithms are modified based on it.

As for the content of paxos, the above story is actually very clear. I'll use the professional word "explain" again.

There are two models of node communication in distributed systems: shared memory (Shared memory) and message passing (Messages passing).

As a distributed system based on message passing communication model, the following errors will inevitably occur in paxos: processes may be slow, killed or restarted, messages may be delayed, lost, and duplicated. In the basic Paxos scenario, the possibility of message tampering, that is, Byzantine errors, is ignored.

The problem solved by Paxos algorithm is how to agree on a certain value in a distributed system where the above exceptions may occur, so as to ensure that no matter any of the above exceptions occur, it will not break the consistency of the resolution. A typical scenario is that in a distributed database system, if the initial state of each node is the same and each node performs the same sequence of operations, then they can finally get a consistent state.

In order to ensure that each node executes the same sequence of commands, a "consistency algorithm" needs to be executed on each instruction to ensure that the instructions seen by each node are consistent. A general consistency algorithm can be applied in many scenarios and is an important problem in distributed computing.

In the paxos algorithm, there are four roles:

Acceptor: decision maker

Proposer: proponent

Client: the person who created the topic (the masses)

Learner: final decision-making Learner (Mass)

Phase one:

Proposer sends a Prepare request to more than half of the Acceptor with the number N.

If Acceptor receives a Prepare request numbered N, and N is greater than the number of all Prepare requests that the Acceptor has responded to, then it will respond with the highest numbered proposal (if any) it has accepted to Proposer, and the Acceptor promises not to accept any proposal with a number less than N.

If the Proposer does not get a response from more than half of the Acceptor, the number + 1 continues to initiate the request.

Stage 2:

If Proposer receives more than half of the Acceptor's response to its Prepare request numbered N, it sends a [N, proposal] Accept request to more than half of the Acceptor.

If Acceptor receives an Accept request for a proposal numbered N, as long as the Acceptor does not respond to a Prepare request with a number greater than N, it accepts the proposal

It is also mentioned that only one value is approved in a Paxos process, and only the value of the prepare and accepted by most Acceptor can be approved, and the approved value can be learner.

I don't know if you have any questions when reading the story, but I do.

Why should there be more Acceptor for decision makers?

If there is only one acceptor and multiple proposer,acceptor can choose any proposal, it is beautiful, but there is a single point of problem.

Why should we use the method of "passing by more than half" to make decisions?

It is impossible for a set to have more than two half subsets at the same time, and more than half of the ideas ensure that the submitted value is unique and consistent in the distributed system at the same time.

In this way, no matter whose proposal proposer has accepted, it only ensures that there is more than half of the proposal. Then confirm the more than half-way proposal in the second stage and let all nodes know about it. Therefore, if the algorithm can guarantee that the value is accepted by half of the acceptor, it means that the identified value is unique at this time.

Why did acceptor accept multiple proposals?

If acceptor can only accept one proposal, it may happen that all the proposals put forward by proposer cannot reach the majority, and the decision maker will end by accepting one proposal, and the status will not be consistent.

What is the problem when there are many Proposer?

It is difficult for a proposer to receive more than half of the responses, and then continue to implement the first phase of the agreement, the decision convergence rate is slow, can not make a decision for a long time.

Why should the proposal be numbered (that is, the money used to bribe in the story)?

It is numbered so that decision makers can make the only final decision in the comparison of the proposals they have received.

Imagine if you compare proposals according to their arrival time, not to mention receiving only one proposal that arrives first, and it may be cool because each decision maker receives proposals in a different order because of the network.

Following the above question, what if all the proposals received by decision makers are gathered together to select the earliest one?

To put the proposals together, we definitely need a master to judge. Have you noticed that this master seems to have become a propser? it gets the earliest proposal and hands it to the decision maker.

In fact, this has evolved into a variant of paxos.

At this point, I believe you have a deeper understanding of "what zookeeper paxos is", might as well come to the actual operation of it! 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.