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

This article mainly explains "how to master distributed Paxos". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's ideas to study and learn "how to master distributed Paxos".

Paxos algorithm

Paxos is the big brother of distributed algorithms, and Paxos can be said to be synonymous with distributed consensus. The most commonly used distributed consensus algorithms are improved based on it. For example, the Raft algorithm (which will be described later). Therefore, to learn distributed algorithms, we must first learn the Paxos algorithm.

The Paxos algorithm mainly consists of two parts:

Basic Paxos algorithm: how to agree on a value among multiple nodes. (this value is what we call proposal Value)

Multi-Paxos algorithm: executes multiple Basic Paxos instances and agrees on a series of values.

Basic Paxos algorithm is the core of Multi-Paxos thought. Multi means many times, that is to say, execute Basic Paxos algorithm several times. So the Basic Paxos algorithm is the top priority.

Paxos in the three Kingdoms

The Liu Bei Group in the three Kingdoms has two major military advisors, Zhuge Liang and Pang Tong, who are both very powerful figures. How can they reach an agreement when they have different battle plans for multiple generals?

Role

There are three roles in Paxos: proponent, receiver, and learner.

Let's explain the Paxos algorithm in a more popular way. Let's go back to the end of the Eastern Han Dynasty, Liu Bei Group's camp to learn how the Paxos algorithm attacked Cao Cao.

Introduction to the characters in Liu Bei's camp:

A master: Liu Bei, as the requester or client.

Two military advisors: Zhuge Liang and Pang Tong, as proponents.

Three generals: Guan Yu, Zhang Fei and Zhao Yun, as recipients.

Wen Chen two: Fazheng, Ma Liang, as learners.

Liu Bei Group

Proponent (Proposer)

Propose a value for voting.

Access and coordination, after receiving the request from the client, you can initiate a two-stage submission for consensus negotiation.

Mapped to the above story, the Advisor is used to deploy battle plans.

Recipient (Acceptor)

Vote for each proposed value and store the accepted value.

Vote to negotiate and store data, vote on proposed values, accept agreed values, store and save.

Reflected in the above story, the general is used to accept the battle plan of the military advisor.

In fact, all the nodes in the cluster are acting as receivers, participating in consensus negotiation, and receiving and storing data.

Learner (Learner)

Be informed of the results of the vote, accept agreed values, and store data

Do not participate in the voting process, that is, do not participate in consensus negotiations.

Mapped to the above story, there are two courtiers as the backup to record the battle plan.

Recipient or proposer

Why can a node act as a receiver or a proponent?

In the previous article, when I explained the BASE protocol, I talked about the two-phase commit agreement. There is the identity of a coordinator, who can be either the recipient or the proposer.

As a recipient, it receives messages from the client. For example, Zhuge Liang needs to accept Liu Bei's operational requirements.

As the proponent, initiate a two-phase submission. This node then negotiates with other nodes as recipients. For example, Zhuge Liang wants to summarize the final battle plan to Liu Bei.

As shown in the following figure, node 1 serves as the proponent and recipient, and node 2 and node 3 serve as the recipient.

The node is both the proposer and the receiver.

Zhuge Liang VS Pang Tong

Among the three Kingdoms are Liu Bei Group (occupying Xishu), Cao Cao Group (occupying the north) and Sun Quan Group (occupying Jiangnan).

Zhuge Liang and Pang Tong, as proponents, put forward the battle plan proposal to the three recipients. There are two attributes in the proposal:

Proposal number, every time a military advisor makes a proposal, there will be a number, which is represented by n here.

The proposed value, that is, the battle plan, is expressed here as v. So the proposal is [n, v].

Zhuge Liang's battle plan is to attack Cao Cao from the north, Pang Tong's battle plan is to attack Cao Cao from the south, and Guan Yu, Zhang Fei and Zhao Yun have received their battle plans one after another. who should listen to? This is a consensus issue. The consensus of Paxos algorithm is divided into two stages. The Prepare phase and the Accept phase.

Preparation stage

Zhuge Liang and Pang Tong, as proponents, sent preparation requests containing the battle plan number (proposal number) to all recipients (Guan Yu, Zhang Fei, Zhao Yun), but did not include the battle plan (proposal value).

Send a preparation request

Zhuge Liang, the proponent, first sent a request for preparation of the battle plan numbered 1, and Pang Tong sent a request for preparation of the battle plan numbered 2.

Recipient Guan Yu (Node X) received a battle plan preparation request from Zhuge Liang at 8 o'clock and a battle plan preparation request from Pang Tong at 10:00.

Recipient Zhang Fei (Node Y) received a battle plan preparation request from Zhuge Liang at 9: 00 and 11:00 from Pang Tong.

Recipient Zhao Yun (Node Z) received a battle plan preparation request from Pang Tong at 12:00 and a battle plan preparation request from Zhuge Liang at 13:00.

Preparation phase-send a preparation request

Note: the preparation phase does not need to carry a specific battle plan, so the battle plan can be empty, but the proposal number must be there.

Request for preparation received (first time)

According to the chronological order of accepting the request, Guan Yu and Zhang Fei received the request from Zhuge Liang [1, empty], and Zhao Yun received the request from Pang Tong [2, empty].

Preparation phase-request for preparation received (first time)

Because Guan Yu and Zhang Fei had not received the proposal before, they returned a response with no proposal yet. That is to tell Zhuge Liang that he will no longer respond to preparation requests with numbers less than or equal to 1, and will not pass proposals with numbers less than 1. The response time is 14:00 and 15:00.

Zhao Yun did not receive a proposal before, so he returned a response with no proposal yet. That is to tell Pang Tong that he will no longer respond to preparation requests with numbers less than or equal to 2, and will not pass proposals with numbers less than 2. The time for the response is 16:00.

Request for preparation received (second time)

Preparation phase-request for preparation received (second time)

As for Pang Tong's preparation request, Guan Yu and Zhang Fei received a preparation request numbered 2, while number 2 was larger than the number 1 previously received, and Guan Yu and Zhang Fei did not pass any proposals. so they will still return to Pang Tong a response that has not yet been proposed. That is to tell Pang Tong that he will no longer respond to preparation requests with numbers less than or equal to 2, nor will he pass proposals with numbers less than 2. The response time is 14:00 and 15:00.

After Zhao Yun finally received the preparation request numbered 1 by Zhuge Liang, because the number 1 was less than the proposal number 2 of the previous response, he directly discarded the preparation request and did not respond, as shown in the figure above. Illustration.

Acceptance stage

Send an acceptance request

After receiving the ready response, Zhuge Liang and Pang Tong will send acceptance requests respectively, as shown in the following figure:

Acceptance phase-send an acceptance request

After receiving the prepared response from most of the recipients (Guan Yu and Zhang Fei), Zhuge Liang sets the value in the acceptance request according to the value of the proposal with the highest proposal number in the response. Since the prepared response of Guan Yu and Zhang Fei was that there was no proposal yet, they still sent the request with proposal number 1 and proposal value of north, and the north representative attacked Cao Cao from the north. The sending time is one minute after 15: 00 and 16:00.

Why is it one minute after 15: 00? Because as long as the preparation request of most recipients is met, the accept request can be sent. The time points for Guan Yu and Zhang Fei to respond are 14:00 and 15:00, so they can be sent after 15:00.

After Pang Tong received the prepared response from most of the recipients (Guan Yu, Zhang Fei and Zhao Yun), he set the value in the acceptance request according to the value of the proposal with the highest proposal number in the response. Because Guan Yu, Zhang Fei, and Zhao Yun returned ready to respond that there was no proposal yet, they still sent an acceptance request with proposal number 2 and a proposal value of the south, and the south representative attacked Cao Cao from the south. The time to send is 18:00, 19:00, 20:00.

Receive a request to accept

When Guan Yu, Zhang Fei and Zhao Yun receive the acceptance request from Zhuge Liang and Pang Tong, they will do the following, as shown in the following figure:

Acceptance phase-request for acceptance received

When Guan Yu, Zhang Fei and Zhao Yun received the proposal [1, North] sent by Zhuge Liang, Zhuge Liang's proposal was rejected because proposal number 1 was less than the minimum proposal number 2 they promised to pass.

And when they received Pang Tong's proposal [2, Nan], because the number 2 was not less than the promised number 2, they adopted Pang Tong's proposal [2, Nan]. So Guan Yu, Zhang Fei, Zhao Yun, their battle plan is to attack Cao Cao from the south. A consensus has been reached.

Learners appear on the stage

When the recipient passes a proposal, it notifies all learners. When the learner finds that most of the recipients have passed a proposal, the learner will also adopt the proposal and accept the value of the proposal.

In other words, after Guan Yu, Zhang Fei and Zhao Yun reached a consensus, learner Fazheng and Ma Liang also adopted a battle plan to attack from the south.

Thank you for your reading, the above is the content of "how to master distributed Paxos", after the study of this article, I believe you have a deeper understanding of how to master distributed Paxos, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.