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

This article mainly explains "SOFAJRaft election mechanism analysis | what is the principle of SOFAJRaft implementation". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "SOFAJRaft election mechanism analysis | what is the implementation principle of SOFAJRaft"!

Preface

In the Raft algorithm, election is a very important part, the so-called election is to select a Leader node among multiple nodes, and he will provide writing services (and default reading services).

In the analysis of the source code, the understanding of the election mechanism will often encounter polarization. For students who understand the basic principles of the Raft algorithm, reading the source code is an ingenious process of taste and realization, while the students who experience it for the first time will fall into the dilemma of the second monk, as if in a fog.

In order to improve the readability of the article, I still hope to spend part of my time explaining the basic principles of the election mechanism so that I can focus on the code implementation later. The following is a picture and text analogy, which helps to understand and keeps the whole article from getting into the details too early.

Question 1: what is the election to solve?

A distributed cluster can be regarded as a fleet composed of multiple warships, which communicate with each other through flags. In such a fleet, ships will not be completely isolated from each other, but they can not maintain very close contact as on land. Weather, sea conditions, ship distance, and ship war damage lead to the existence of contact between ships, but it is not reliable.

As a unified combat cluster, the fleet needs a unified consensus and orders in step, all of which depend on the flagship command. Each ship has to obey the instructions issued by the flagship, and when the flagship can no longer work, another warship needs to take over the role of the flagship.

Cdn.nlark.com/yuque/0/2019/png/307286/1562208003160-14473ea8-f451-4c07-97f2-d79927b4f6f7.png ">

Figure 1-it is the responsibility of all ships to be ready to take over the flagship

How to select a flagship recognized by everyone in the fleet is the problem to be solved in the election in SOFAJRaft.

Question 2: when can an election be launched

When can an election be held? In other words, what are the criteria that trigger the election? This standard must be consistent with all warships so that all ships can participate in the election fairly when the standards are met. In SOFAJRaft, the trigger standard is communication timeout. When the flagship does not communicate with the Follower ship within a specified period of time, Follower can think that the flagship can no longer perform the duties of the flagship, then Follower can try to take over the role of the flagship. This communication timeout is called Election Timeout (ET for short), and Follower's attempt to take over the flagship is to initiate an election request.

Figure 2-ET triggers other ships to run for flagship

Question 3: when will the election really be launched?

In an election, only when more than half of the ships in the fleet agree, the ship that initiates the election can become the flagship, otherwise it will have to start a new round of elections. So if Follower adopts the strategy of launching elections as soon as possible and tries to select available flagships for the fleet as soon as possible, it may lead to a potential risk: multiple ships may launch elections almost at the same time, and none of them will win more than half of the votes, resulting in the failure of this round of elections, and then the defeated Follower will once again launch the election at the same time, lose again, re-elect again, and then fail again.

Figure 3-an election is launched at the same time, and the votes are divided

To avoid this, we use random election trigger time. When Follower discovers that the flagship is missing, it will choose to wait for a random period of time Random (0, ET). If no flagship is selected during the waiting period, Follower will launch the election again.

Figure 4-Random waiting time

Question 4: which candidates deserve to vote?

The election of SOFAJRaft includes the judgment of two attributes: LogIndex and Term, which is the core of the whole election algorithm and is easy to be confusing, so let's explain:

Term

We will number the history of the flagships in the fleet, such as the first flagship and the second flagship of the fleet, which we will use Term to represent. Since there can only be one flagship in the fleet at the same time, each Term belongs to only one ship, and obviously the Term is monotonously increasing.

LogIndex

During each flagship's term of office, some instructions are issued (called "flagship order", analogous to "presidential decree"). Of course, these flagship orders are also numbered and archived. This number is identified by the two dimensions of Term and LogIndex, which means "the LogIndex flagship order issued by the first Term flagship". Unlike the real presidential decree, the LogIndex in our flagship order is always increasing and will not be calculated from scratch because of the change of flagships.

Figure 5-Presidential decree Vs flagship order, LogIndex slightly different

All ships try their best to preserve the flagship orders they have received from the flagship in the past, so the criterion for our election is that the ship that keeps the most complete flagship order is the most qualified to take over the flagship. Specifically, the voting boat V will not vote for the following two candidates C: one is lastTermC

LastLogIndexC).

To explain briefly, the first situation shows that the flagship of candidate C's last communication is no longer the latest flagship, at least lagging behind V, so the flagship order it knows cannot be more complete than V. The second case shows that although both C and V have communicated with the same flagship, candidate C's flagship from the flagship is not as complete as V (lastLogIndexV > lastLogIndexC), so V will not vote for it.

Figure 6-Follower ship b rejected ship c and voted for ship a. The flagship order of ship a has a blank box indicating that "the first Term flagship" has not issued any flagship order.

Question 5: how to avoid "making trouble" by unqualified candidates

As mentioned in the previous section, SOFAJRaft uses LogIndex and Term as the selection criteria for the election, so when a ship launches an election, it will add Term and then fill it in the election request and send it to other ships (which may be a very complicated flag slogan) to indicate that it is running for the "first Term + 1 term" flagship.

First of all, I would like to explain a mechanism, which is used to ensure that the Term of each ship increases synchronously: when the voting Follower ship receives this voting request, if it finds that its Term is smaller than that in the voting request, it will consciously update its own Term to keep up with the candidates, so that it can easily synchronize the increasing Term information to the entire fleet.

Figure 7-Follower ship updates its Term based on voting request

But this mechanism also brings a problem. If a ship does not see the flag issued by the flagship for its own reasons, it will self-righteously try to campaign to become the new flagship. Although it continues to launch elections and has not been elected (because the flagship and other ships communicate normally), it actually raises the overall Term through its own voting request. This forces the flagship stepdown (retiring from the flagship position) in the SOFAJRaft algorithm.

Figure 8-self-righteous troublemaker, forcing flagship stepdown

So we need a mechanism to stop this kind of "trouble-making", which is called pre-vote. The candidate initiates pre-voting before initiating the vote. if he does not get feedback from more than half of the nodes, the candidate will wisely give up his candidacy and will not raise the overall Term.

Figure 9-Pre-vote advance Voting

Election analysis

In the above analogy, we can see that the main task of the whole election operation is:

Candidate is triggered by ET

Candidate started trying to launch pre-vote pre-voting.

Follower judges whether to approve the pre-vote request or not

Candidate decides whether to launch RequestVoteRequest or not according to pre-vote response.

Follower judges whether to approve the RequestVoteRequest or not

Candidate judges whether he is elected or not according to response.

This process can be shown in the following figure:

Figure 10-A successful election

At the code level, there are four main ways to handle this process:

Com.alipay.sofa.jraft.core.NodeImpl#preVote / / pre-voting com.alipay.sofa.jraft.core.NodeImpl#electSelf / / Voting com.alipay.sofa.jraft.core.NodeImpl#handlePreVoteRequest / / processing advance Voting request com.alipay.sofa.jraft.core.NodeImpl#handleRequestVoteRequest / / processing Voting request

The code logic is more intuitive, so we use a flowchart to describe the processing in each method.

Advance voting and voting

Figure 11-pre-voting Vs voting

As you can see in the figure, the process of pre-voting request preVote is basically similar to that of voting request electSelf, except that there are several differences:

PreVote is triggered by a timeout

PreVote assigns term to currTerm + 1 when assembling Request, while electSelf first assigns term + +

After preVote is successful, enter electSelf,electSelf and become Leader after success.

Process the request

The logic for processing pre-voting and voting requests is similar, also represented by a diagram.

Figure 12-processing a pre-voting request

Figure 13-processing Voting request

As you can see in the figure, the processes for handling the two requests are basically similar, except that when processing voting requests, there is a stepdown mechanism that forces Leader to fall back from its Leader status to Follower. In the specific implementation, Leader will use the lease mechanism to avoid some unnecessary stepdown, about the lease mechanism, you can see the previous series of articles "SOFAJRaft linear consistent read implementation analysis | SOFAJRaft implementation principle".

Summary

In this paper, we use analogy to analyze the source code, mainly to make it easier for readers to understand how to reach a consensus in a distributed environment, which is also the goal of the whole SOFAJRaft.

At this point, the author feels that the election has been made clear. If there is anything that has not been mentioned, or some branch tasks in the process, you are welcome to look for further answers from the source code. Finally, post the source code of the four methods mentioned above.

Figure 14-preVote advance Voting

Figure 15-electSelf Voting

Figure 16-handlePreVoteRequest processing pre-voting

Figure 17-handleRequestVoteRequest processes voting

Thank you for your reading. The above is the content of "Analysis of SOFAJRaft Election Mechanism | what is the principle of SOFAJRaft implementation". After the study of this article, I believe you have a deeper understanding of the analysis of SOFAJRaft election mechanism | what is the principle of SOFAJRaft implementation. 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.