preface

Distribution is indeed an interesting topic, as it is everywhere in life if you pay attention.

Brother Wukong began to learn distribution from a technical essay written with great care, and this article won the first prize in the essay contest. Thanks to the platform provided by the Nuggets community. If you want to learn, you can click on the link to this article: “The last three years have been miserable by distributed pits, exposed ten pits”.

The first two lectures are focused on the theory of distribution, covering the four major theories of distribution.

Byzantine general question: “with the Killing of The Three Kingdoms on distributed algorithms, comfortable?”

BASE, CAP, ACID: “Using Tai Chi to teach distributed theory, comfortable!”

Starting with this article, eight distributed protocols/algorithms will be explained. This article mainly explains Paxos consensus algorithm.

The main contents of this paper are as follows:

Paxos algorithm

Paxos is the big brother in distributed algorithms, and it can be said that Paxos is synonymous with distributed consensus. The most commonly used distributed consensus algorithms are based on it. Consider the Raft algorithm (also covered later). Therefore, learning distributed algorithm must first learn Paxos algorithm.

Paxos algorithm mainly consists of two parts:

  • Basic Paxos algorithm: How multiple nodes agree on a value. (This value is calledMeasure the Value)
  • Multi-paxos algorithm: Execute multiple instances of Basic Paxos to agree on a set of values.

The Basic Paxos algorithm is at the heart of the idea of Multi-PaxOS. Multi means multiple times, which means executing Basic Paxos several times. So Basic Paxos is the most important algorithm.

Paxos of the three

In the Liu Bei Group of The Three Kingdoms, there were two great strategists: Zhuge Liang and Pang Tong. They were both very powerful figures. How could they reach an agreement when they had different battle plans for several generals?

role

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

Let’s look at the Paxos algorithm in a more general way. Let’s go back to the late Eastern Han Dynasty and learn how Paxos algorithm attacked Cao Cao in the camp of Liu Bei group.

Introduction to liu Bei’s Camp:

  • One principal: Liu Bei, as the requester or client.

  • Two advisers: Zhuge Liang, Pang Tong, as the proposer.

  • Three generals: Guan Yu, Zhang Fei, Zhao Yun, as the receiver.

  • Two scholars: Fa Zheng and Ma Liang, as learners.

(a) Proposer

  • Propose a value for voting.
  • Access and coordination: After receiving a request from a client, the client can initiate a two-phase submission for consensus negotiation.
  • mappingIn the story above,strategistIt’s used to plan battles.

Acceptor

  • Each proposed value is voted and the accepted value is stored.

  • Vote negotiates and stores data, votes on proposed values, and accepts agreed values for storage and preservation.

  • In the above story, the general is used to receive the strategist’s battle plan.

  • In fact, all nodes in the cluster play the role of receiver, participating in consensus negotiation, and receiving and storing data.

Learner

  • Being told the results of the vote, accepting the agreed values, storing data,

  • Not participating in the voting process means not participating in consensus consultation.

  • Mapped to the above story, it is the two civil servants as a backup to record the battle plan.

Receiver or proposer

Why can a node play the role of receiver as well as proposer?

Last time I explained the BASE protocol, I talked about the two-phase commit protocol. Among them is the identity of a coordinator, who can be either a receiver or a proposer.

  • As recipientTo receive messages from the client. Such asThe various ge is brightNeed to receiveLiu beiOperational requirements.
  • As proposerTo initiate a phase 2 commit. This node then negotiates consensus with other nodes as recipients. Such asThe various ge is brightPut together the final battle planLiu bei.

As shown in the figure below, node 1 serves as the proposer and receiver, and nodes 2 and 3 serve as the receiver.

Zhuge Liang VS Pang Tong

Among them were Liu Bei Group (occupying western Shu), Cao Cao Group (occupying the north) and Sun Quan Group (occupying the South of the Yangtze River).

Zhuge Liang and Pang Tong, as the proposers, presented the proposal of the battle plan to the three recipients. There are two attributes in the proposal:

  • Bill numberEach time the consigliere makes a proposal, it has a number, denoted by n.
  • Offer valueThat’s the battle plan, which is represented by v. So the proposal is [n, v].

Zhuge Liang’s battle plan was to attack Cao Cao from the north, pang Tong’s battle plan was to attack Cao Cao from the south, guan Yu, Zhang Fei and Zhao Yun received their battle plans successively, who should listen to? This is a matter of consensus. The Paxos algorithm reached consensus in two stages. The Prepare stage and the Accept stage.

Preparation stage

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

Send prepare request

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

  • The recipient, Guan Yu (node X), received the battle plan preparation request from Zhuge Liang at 8 o ‘clock, and the battle plan preparation request from Pang Tong at 10 o ‘clock.

  • The receiver, Zhang Fei (node Y), received the battle plan preparation request from Zhuge Liang at 9 o ‘clock, and the battle plan preparation request from Pang Tong at 11 o ‘clock.

  • The recipient, Zhao Yun (node Z), received the battle plan preparation request from Pang Tong at 12 o ‘clock, and received the battle plan preparation request from Zhuge Liang at 13 o ‘clock.

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

Prepare request received (first time)

According to the chronological order of receiving requests, Guan Yu and Zhang Fei received zhuge Liang’s request [1, empty], and Zhao Yun received Pang Tong’s request [2, empty].

Because Guan Yu and Zhang Fei did not receive the proposal before, they returned a response with no proposal. In other words, he told Zhuge Liang that he would not respond to any preparation request whose number was less than or equal to 1, nor would he approve any proposal whose number was less than 1. The response time points are 14 and 15.

Zhao Yun had not received the proposal before, so he returned a response with no proposal. In other words, pang Tong was told that he would not respond to any more preparation requests with numbers less than or equal to 2, and would not approve any proposals with numbers less than 2. The response time is 16 o ‘clock.

Request for preparation received (second)

As for Pang Tong’s preparation request, Guan Yu and Zhang Fei received a preparation request numbered 2, but the number 2 was larger than the number 1 they had received before. Moreover, Guan Yu and Zhang Fei did not pass any proposal, so they still returned pang Tong a response with no proposal. That is, it tells Pontoon that it will no longer respond to requests for preparation numbered less than or equal to 2, nor will it approve proposals numbered less than 2. The response time points are 14 and 15.

When Zhao Yun finally received zhuge Liang’s preparation request no. 1, the preparation request no. 1 was smaller than the proposal No. 2 of the previous preparation request, so he directly discarded the preparation request and did not respond, as shown in ❌ in the figure above.

acceptance

Send accept request

After receiving the prepared response, Zhuge Liang and Pang Tong would send the acceptance request respectively, as shown in the figure below:

After receiving the prepared response from the majority of the recipients (Guan Yu and Zhang Fei), Zhuge Liang set the value in the acceptance request according to the value of the proposal with the largest proposal number in the response. Since guan Yu and Zhang Fei returned no proposal yet, they still sent the acceptance request with proposal number 1 and proposal value as North. The north representative attacked Cao Cao from the north. The time of transmission is one minute past 15 and 16 o ‘clock.

Why is it one past fifteen? As long as most of the recipients’ prepare requests are satisfied, the accept request can be sent. The response time of Guan Yu and Zhang Fei is 14:00 and 15:00, so it 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 largest proposal number in the response. Since guan Yu, Zhang Fei and Zhao Yun returned no proposal yet, they still sent the request with proposal number 2 and proposal value as South, and The south representative attacked Cao Cao from the south. The time of delivery is 1800, 19:00, 20:00.

Receive acceptance request

When Guan Yu, Zhang Fei and Zhao Yun received zhuge Liang and Pang Tong’s acceptance request, they would deal with it as follows, as shown in the picture below:

When Guan Yu, Zhang Fei and Zhao Yun received zhuge Liang’s proposal [1, North], zhuge Liang’s proposal was rejected because the proposal number 1 was smaller than the minimum proposal number 2 that they promised to pass.

When they received pang Tong’s proposal [2, South], they approved Pang Tong’s proposal [2, South] because no. 2 was no less than the promised number 2. Therefore, Guan Yu, Zhang Fei and Zhao Yun planned to attack Cao Cao from the south. A consensus was reached.

Come on learner

When the recipient approves a proposal, all learners are notified. When the learner finds that most of the recipients have approved a proposal, the learner will also approve the proposal and accept the value of the proposal.

That is to say, after Guan Yu, Zhang Fei and Zhao Yun reached an agreement, learners Fa Zheng and Ma Liang also agreed to attack from the south.

conclusion

  • Basic Paxos was also agreed upon through a two-phase submission agreement. Preparation stage, acceptance stage. If you are not aware of the two-phase commit protocol, check out my previous article. Taijiquan distributed theory, comfortable!

  • Basic Paxos not only implements consensus, it also implements fault tolerance. The cluster can function properly when fewer than half of the nodes fail. The article also emphasizes the principle that most nodes agree on, which gives Basic Paxos its fault tolerance.

  • Proposal numbers represent priorities and guarantee three commitments:

    • ifPrepare the requestProposal no.,Less than or equal toThe recipient has respondedPrepare the requestThen the recipient will promise not to respond to thisPrepare the request.
    • ifAccept the requestThe proposal number of the proposal in,Less thanThe recipient has respondedPrepare the request“And the recipient will promise not to pass it.
    • If the recipient has previously approved the proposal, then the recipient will commit to itPrepare the requestContains the maximum number of proposals that have been passed.

bonus

If Guan Yu and Zhang Fei had already approved a proposal [2, south], but Zhao Yun had not yet approved any proposals, what would guan Yu, Zhang Fei, and Zhao Yun finally do when jian Yong, the third military adviser, presented a proposal, no. 8, with the battle plan of attacking Cao Cao from the east [8, east]? Leave a comment in the comments section.

I am Wukong, strive to become stronger, become super Saiya people! I have written a set of Spring Cloud advanced tutorial and PMP brush small procedures. Welcome to our public account: Wukong chat structure