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

How to use the Paxos algorithm, for this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

First of all, Paxos, which is a consistency algorithm based on message passing, was proposed by Leslie Lamport in 1990 and has been widely used in distributed computing in recent years. The Zookeeper of Google's Chubby,Apache is based on its theory. Paxos is considered to be the only distributed consistency algorithm so far, and other algorithms are all improvements or simplifications of Paxos. There is a question to mention. Paxos has a premise: there is no Byzantine general problem. That is to say, Paxos can only be established in a trusted computing environment, which will not be destroyed by intrusion.

A specific description of Paxos can be found in Wiki: http://zh.wikipedia.org/zh-cn/Paxos algorithm. There are also many articles about Paxos analysis on the Internet. Here we want to describe it in the simplest way and establish the corresponding relationship between Paxos and ZK Server.

Paxos describes a scene in which a group of residents live on an Island called Paxos. Everything on the island is decided by some special people, who are called Senator. The total number of members (Senator Count) is fixed and cannot be changed. Every change in environmental affairs on the island requires a proposal (Proposal), and each proposal has a number (PID), which is growing all the time and cannot be retrogressed. Each proposal requires the consent of more than half of the members ((Senator Count) / 2 + 1) before it can take effect. Each member will only agree to proposals that are larger than the current number, including those that are already in force and those that are not. If a member receives an offer that is less than or equal to the current number, he will reject it and inform the other party that your proposal has already been raised. The current number here is the number recorded by each member in his own notepad, which he constantly updates. The whole council cannot guarantee that the numbers on all members' notebooks will always be the same. Now parliament has a goal: to ensure that all members can agree on the proposal.

OK, now that the parliament is in operation, all members start with the number 0 on their notepad. A congressman made a proposal to set the electricity tariff at 1 yuan per kilowatt-hour. He first looked at the notepad, well, the current proposal number is 0, so the number of my proposal is 1, so he sent a message to all members: proposal 1, setting the electricity charge at 1 yuan per kilowatt-hour. After receiving the message, other members checked their notepad. Oh, the current proposal number is 0, and this proposal is acceptable, so he recorded the proposal and replied: I accept your proposal No. 1. At the same time, he wrote in the notepad: the current proposal number is 1. The member who made the proposal received more than half of the responses and immediately sent a notice to everyone: proposal 1 will take effect! The member who receives it will amend his notepad to change a good proposal from a record to a formal statute. When someone asks him what the electricity bill is, he will check the decree and tell the other party: 1 yuan per kilowatt-hour.

Now let's look at the resolution of the conflict: suppose a total of three MPs, S1 and S2, have launched a proposal at the same time: proposal No. 1 to set electricity charges. S1 wants to set it to 1 yuan / degree, S2 wants to set it to 2 yuan / degree. As a result, S3 first received a proposal from S1, so he did the same thing as before. Then he received the proposal from S2, and as a result, he checked the notepad. Hey, the number of this proposal was less than or equal to my current number 1, so he rejected the proposal: sorry, this proposal has been predetermined. As a result, S2's proposal was rejected, and S1 formally issued a proposal: proposal 1 takes effect. S2 asked S1 or S3 about and updated the contents of decree 1, and then he could choose to continue with proposal 2.

OK, that's all the essence of Paxos. Now let's take a look at how Paxos is implemented in ZK Server.

Island (Island)-ZK Server Cluster

Member (Senator)-ZK Server

Proposal (Proposal)-ZNode Change (Create/Delete/SetData...)

Proposal number (PID)-Zxid (ZooKeeper Transaction Id)

Official decree-all ZNode and its data

It seems that all the key concepts can be matched one by one, but wait a minute, the councillors on Paxos Island should be equal, while ZK Server seems to have a concept of Leader. Yes, in fact, the concept of Leader should also belong to the category of Paxos. If all members are equal, under certain circumstances, there will be a "live lock" as a result of the proposed conflict (my understanding of the so-called live lock is that everyone is not dead and is moving, but the conflict problem has not been resolved). Lamport, the author of Paxos, addresses the problem and gives a solution in his chapter "The Part-Time Parliament"-to set up a president among all lawmakers, only the president has the right to make proposals, and if lawmakers have their own proposals, they must be sent to the president and proposed by the president. Okay, we have another role: the president.

President-ZK Server Leader

Another question arises. How was the president elected?

Now that we assume that the president has been elected, let's take a look at how ZK Server is implemented.

Situation 1:

Client went to a congressman (ZK Server) to ask about a certain law (ZNode data). The congressman did not hesitate to take out his notepad (local storage), consult the decree and tell him the result, and declare that my data are not necessarily up-to-date. You want the latest data? No problem. Wait. I'll let you know when I talk to President Sync.

Case 2:

Client went to a congressman (ZK Server) to ask the government to return the ten thousand yuan owed to him, and the congressman told him to wait in the office, and he reflected the problem to the president. The president asked all the congressmen for their opinions, and most members said that the money owed to the people must be repaid, so the president issued a statement that ten thousand yuan was set aside from the national treasury to repay the debt, and the total assets of the national treasury changed from 1 million to 990000. Fart Man B got the money and went back (the Client function returned).

Situation 3:

The president suddenly hung up, and one after another, lawmakers found that they could not reach the president, so they issued statements to elect a new president, and the government closed down during the presidential election and refused the request of the people.

The answer to the question on how to use the Paxos algorithm is shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

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.