PaxOS algorithm: Message transfer consistency

There are many excellent articles about Paxos algorithm on the Internet, I will organize and collect them below:

Paxos algorithm details Detailed explanation (1)–Describe the algorithm through the real world

Recently studied the paxos algorithm and read many related articles. The concept is still very vague, and I feel that I still have not grasped the essence of the paxos algorithm, so it took 3 days Analyzed all the code of libpaxos3, this code can be downloaded from https://bitbucket.org/sciascid/libpaxos. After you have a preliminary understanding of the paxos algorithm, it will be better to read this article; if you also want to analyze libpaxos3, this article should be of great help to you; there is not much introduction about the history of paxos, about describing paxos The best article written by the algorithm should be Wikipedia, the address is here: http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95

In the paxos algorithm, there are 4 roles:

Proposer: Proposer

Acceptor: Decision maker

Client: the person who generates the issue

Learner: the final decision-making learner

Among the above 4 roles, the proposer and the decision maker are very important, and the other 2 roles are in the entire algorithm It should be counted as soy sauce. Proposer is like the messenger of the Client. The messenger of Proposer takes the issue of the Client to propose to the Acceptor, and the Acceptor makes the decision. Here comes a new term: final decision. Now let’s systematically introduce all the behaviors in the paxos algorithm:

1. Proposer proposes an issue
2. Acceptor initially accepts or Acceptor initially does not accept
3. If you do If Acceptor initially accepts one step, Proposer again confirms to Acceptor whether it is finally accepted
4. Acceptor finally accepts or Acceptor finally does not accept

The final learning goal of Learner above is that Acceptors finally accept What is the issue? Note that this is learning from all Acceptors. If a majority of Acceptors finally accept a proposal, then the final result is obtained and the purpose of the algorithm is achieved. Draw a picture to make it more intuitive:

Why do we need 3 Acceptors? Because the Acceptor must be at least 3 or more, and it must be an odd number, because the majority must be formed. If it is an even number, such as 4, 2 accepts and 2 does not accept it. Each sticks to its own opinions and cannot continue.

Why are there 3 Proposers? In fact, it doesn’t matter how many, 1~n are all right; if it is a proposal, there is no competitive pressure, the two-stage submission is completed smoothly, and the Acceptors finally approved the matter. If there are multiple proposers, it is more complicated, please continue to read.

There are many nodes in the figure above. Does each node need a machine? The answer is not needed. The above figure is a logical diagram. In physics, you can put Acceptor, Proposer and Client on one machine, but use different port numbers. Acceptors start TCP monitoring on different ports, and Proposer comes Actively connect; it is completely possible to merge Client, Proposer, Acceptor, and Learner into one program; here is an example: For example, if a JOB program is developed, and the JOB program is deployed on multiple servers (odd number), these JOBs are possible To handle a task at the same time, now use the paxos algorithm to let these JOBs discuss who (which machine) will handle the task, so that the JOB program needs to include the 4 major functions of Client, Proposer, Acceptor, and Learner, and need Configure the IP addresses of other JOB servers.

Another example, zookeeper is often used as a distributed transaction lock. The zad protocol used by Zookeeper is similar to the paxos protocol. All distributed self-negotiation consensus algorithms are simplifications or variants of the paxos algorithm. Client is a machine that uses zookeeper service. Zookeeper itself includes Acceptor, Proposer, and Learner. Zookeeper leader election is the paxos process, and when Client writes Znode to Zookeeper, Paxos process is also required, because different Clients may connect to different Zookeeper servers to write Znode. Which Client can write successfully? It is necessary to rely on Zookeeper’s paxos to ensure consistency. The client who successfully writes the Znode is naturally accepted. The Znode contains the IP and port written to the Client, and other clients can also read this Znode for Learner. That is to say, the Learner is included in Zookeeper itself (because Zookeeper will conduct leader election in order to ensure its own consistency, so it needs to have Learner’s internal mechanism, and multiple Zookeeper servers need to know who is the leader now), and the client side also You can learner, and learner is generalized.

Now through a story to learn the process of paxos algorithm (two-stage submission), there are 2 Clients (bosses, there is a competitive relationship between the bosses) and 3 Acceptors (Government officials):

1. Now we need to do the paxos process on a topic, the topic is “Project A, I want to win the bid!”, here “I” refers to each secretary with him Client owner of Proposer.
2. Of course, Proposer listened to the boss, and quickly went to the Acceptor government official with the issue and cash.
3. As a government official, of course you want to give the project to whoever gives more money.
4. Miss Proposer-1 brought cash and found officials Acceptor-1~Acceptor-3 at the same time. Officials No. 1 and No. 2 collected 10 bitcoins respectively. When they found No. 3 official, she did not expect to be attacked. Official No. 3 despised her. Official No. 3 told her that Proposer-2 gave 11 bitcoins. But it’s okay. Proposer-1 has been recognized by two officials, 1,2 and formed a majority (if there is no majority, Proposer-1 will go to the bank to withdraw money and ask the officials to give each person 20 bitcoins. This The process was repeated every time +10 bitcoins, until the majority formed), and returned to the boss with satisfaction, but at this time the Proposer-2 bodyguard found officials No. 1 and No. 2 and gave them 11 bitcoins, 1, and 1, respectively. Official No. 2’s attitude immediately changed, saying that Proposer-2’s boss was sensible. Now Proposer-2 was relieved. He had secured three officials and returned to the boss. Of course, this process is the first stage of submission, but the officials are just preliminary. Just accept bribes. The Bitcoin in the story is the number, and the topic is the value.

　　　　This process ensures that at a certain moment, a certain proposal’s issue will form a majority for preliminary support;

========= ====== Gorgeous dividing line, the end of the first stage ================

　　5.　 now enter the second stage of submission, now the proposer- Miss 1 used the doppling technique (multi-threaded concurrency) to divide three of them to find three officials. The first to find official No. 1 to sign the contract, was despised by official No. 1, and official No. 1 told him that Mr. Proposer-2 gave him Because of the nature of the previous rule, Miss Proposer-1 knew that the first stage of Proposer-2 had formed a majority after her (at least two officials’ stolen money was updated); at this time, she hurried to mention it. The money is ready to bribe the three officials again (re-entering the first stage), each with 20 bitcoins. I just gave No. 1 official 20 bitcoins, and No. 1 official was very pleased to initially accept the issue. Before he had time to meet No. 2 and No. 3 officials

At this time, Mr. Proposer-2 also used the clone technique to find out separately. 3 officials (note that this is the second stage of Proposer-2), was rejected by the first official and told him that he had received 20 bitcoins, and the second and third officials successfully signed the contract. At this time, the second and third officials recorded The client-2 boss used 11 bitcoins to win the bid. Because of the formation of a majority, he finally accepted the subject of the Client2 boss winning the bid. Mr. Proposer-2 has already done an excellent job;

At this time, the proposer- Miss 1 found official No. 2, and the official told her that the contract had been signed, and showed her the contract. Miss Proposer-1 is a smart person with no professional ethics. She felt that she had no future with the boss of Client1, so she changed her issue. He won the bid for “Client2 boss” and gave 20 bitcoins to official No. 2, thus forming a majority. Smoothly enter the second stage again. Since there was no competition at this time, we successfully found three officials to sign the contract. The three officials saw that the issue was consistent with the previous contract, so they finally accepted and formed a majority. Miss Proposer-1 moved to Client2. The boss’s company is gone.

===============Gorgeous dividing line, the end of the second stage===============

　　Paxos process is over. In this way, consistency is guaranteed. At the end of the algorithm operation, all proposers vote for “client2 winning bid.” All acceptors accept this issue, which means that in the first second stage, the issue is preconceived. Yes, whoever has the first opportunity will learn about this topic in the first stage and modify its own topic, because in this way, there is no professional ethics, so that the consistency can be guaranteed. This is a process of the paxos algorithm. It turns out that the roles in the paxos algorithm are all such unreliable, but it doesn’t matter, the result is reliable. The algorithm is to pursue the consistency of results.

Resources come from the Internet, keep updated.