Explain distributed raft with dynamic diagram

This is Wukong's first 77  Original articles

author | Wukong chat structure

source |  Wukong chat structure （ID：PassJava666）

Please contact authorization for reprint （ WeChat ID：PassJava）

use Dynamic diagram Solution distribution type Raft

One 、Raft summary

Raft Algorithm It is the first choice for distributed system development Consensus algorithm . For example, it's popular now Etcd、Consul.

If master I've got this algorithm , You can easily handle most of the scenes Fault tolerance and Uniformity demand . Such as distributed configuration system 、 Distributed NoSQL Storage and so on , Easily break through the single machine limit of the system .

Raft The algorithm is all about leaders , Realize the consensus of a series of values and the consistency of each node log .

Two 、Raft role

2.1 role

follower （Follower）： Ordinary people , Silently receiving and receiving messages from leaders , When the leader's heartbeat message times out , I'll take the initiative to stand up , Recommend yourself as a candidate .

The candidate （Candidate）： The candidate Will ask other nodes to vote RPC news , Inform other nodes to vote , If you win a majority of the votes , Just be promoted to be a leader .

The leader （Leader）： Bullying, , Everything is up to me . Handle write requests 、 Manage log replication and constantly send heartbeat information , Notify other nodes “ I'm a leader , I'm still alive , You don't want it ” Launch a new election , No need to replace me with a new leader .

As shown in the figure below , Three graphs are used to represent followers 、 Candidates and leaders .

role

3、 ... and 、 Single node system

3.1 database server

Now let's imagine , There's a single node system , This node acts as a database server , And stored a value of X.

database server

3.2 client

The solid green circle on the left is the client , The blue solid circle on the right is the node a（Node a）.Term The term of office of the representative , I'll talk about it later .

client

3.3 The client sends data to the server

The client sends an update operation to the single node server , Set the value stored in the database to 8. In a stand-alone environment （ Single server node ）, The value the client gets from the server is also 8. Consistency is very easy to guarantee .

The client sends data to the server

3.4 How to ensure the consistency of multiple nodes ？

But if there are multiple server nodes , How to ensure consistency ？ For example, there are three nodes ：a,b,c. As shown in the figure below . These three nodes form a database cluster . The client updates the three nodes , How to ensure that the values stored in three nodes are consistent ？ This is the problem of distributed consistency .Raft Algorithm is to solve this problem . Of course, there are other agreements that can guarantee , This article is only for Raft Algorithm .

In a multi node cluster , Failure at node 、 Partition error and other abnormal situations ,Raft How does the algorithm guarantee that at the same time , There is only one leader in the cluster ？ Let's start with Raft The process of electing leaders .

Four 、 The election leadership process

4.1 The initial state

In the initial state , All nodes in the cluster are followers .

As shown in the figure below , There are three nodes (Node) a、b、c, term （Term） All for 0.

The initial state

4.2 Be a candidate

Raft The algorithm realizes the characteristic of random time-out , The timeout interval of each node waiting for the heartbeat information of the leader node is random . such as A The time interval that the node waits to time out 150 ms,B node 200 ms,C node 300 ms. that a Time out first , First of all, because I didn't wait for the leader's heartbeat information , Timeout occurred . As shown in the figure below , The timeout timer for three nodes starts running .

Timeout time

When A When the timeout of the node is up ,A The node becomes candidates , And add your own term number ,Term Value from 0 Updated to 1, And voted for myself .

• Node A：Term = 1, Vote Count = 1.
• Node B：Term = 0.
• Node C：Term = 0.

Be a candidate

4.3 vote

Let's look at how candidates become leaders .

Leader The election

• First step ： node A After being a candidate , Send request voting to other nodes RPC Information , Ask them to elect themselves leaders .
• The second step ： node B and node C Received node A After sending the request to vote information , At No 1 In this term of office , There has not been a vote yet , Vote for the node A, And add your own term number .
• The third step ： node A received 3 Votes , Got the majority of the nodes voting , From the candidate to the president of this term New leaders .
• Step four ： node A As a leader , Fixed time intervals for node B And nodes C Send heartbeat message , Tell node B and C, I'm a leader , Organize other followers to launch new elections .
• Step five ： node B And nodes C Send the response information to the node A, Tell node A I'm normal .

4.4 term

The English word is term, Leaders have tenure .

• Automatically add ： After the follower has timed out waiting for the leader's heartbeat information , Recommend yourself as a candidate , Will increase their tenure number , As shown in the figure above , node A The term of office is 0, When you put yourself as a candidate , The term number is added to 1.
• Update to a larger value ： When a node finds that its tenure number is smaller than other nodes , Will be updated to a larger number value . Such as node A For a term of 1, Request to vote , The voting message contains nodes A The tenure number of , And the number is 1, node B After receiving the message , I will update my tenure number to 1.
• Return to follower ： If a candidate or leader , Find that your tenure number is smaller than other nodes , Then it will immediately return to the follower state . This scenario occurs after partition error recovery , The term of office is 3 The leader of is subject to a term number of 4 The heartbeats of , Then the former will immediately return to the follower state .
• Reject the message ： If a node receives a request for a smaller term number value , Then it will directly reject the request , For example, the term of office number is 6 The node of A, Received term number 5 The node of B To ask for a vote RPC news , Then the node A Will reject the news .

4.5 Election rules

• In one term , Leaders will always be leaders , Until something goes wrong （ Such as downtime ）, Or network problems （ Delay ）, Other nodes launch a new round of elections .
• In an election , Each server node will cast at most one vote for a term number , After casting, it's gone .

4.6 majority

Suppose a cluster consists of N The nodes make up , So most of them are at least N/2+1. for example ：3 Cluster of nodes , Most of them are 2.

4.7 The heartbeat timeout

To prevent multiple nodes from voting at the same time , Each node is assigned a random election timeout . In this time , Nodes cannot be candidates , We have to wait until the timeout . For example, the above example , node A Time out first , I became a candidate first . This ingenious design , In most cases, only one server node initiates the election first , Instead of voting at the same time , It reduces the number of electoral failures caused by the division of votes .

Be a candidate

5、 ... and 、 Leader failure

If the leader node fails , It will trigger a new round of elections . As shown in the figure below , Leader nodes B failure , node A and node B Will be re elected Leader.

Leader failure

• First step ： node A happen fault , node B And nodes C No leader nodes received A Heartbeat information of , Waiting for timeout .
• The second step ： node C Timeout occurs first , node C Become The candidate .
• The third step ： node C To the node A And nodes B Initiate a request for voting information .
• Step four ： node C In response to the vote , Voted for C, And node A Because something went wrong , Unable to respond C To ask for a vote .
• Step five ： node C Got two tickets （ Most of the votes ）, Become The leader .
• Step six ： node C To the node A and B Send heartbeat message , node A Respond to heartbeat information , node B Does not respond to heartbeat information .

summary

Raft The algorithm conducts leadership election in the following ways , To ensure that there is only one leader for a term of office , Greatly reduced the number of election failures .

• term
• Leader heartbeat information
• Random election overtime
• First come, first served voting principle
• The majority vote principle

In this article, we will explain it by moving pictures Raft How the algorithm elects leaders , Easier to understand and digest .

- END -

Previous recommendation

Zhugeliang VS Pang Tong , Take the distributed Paxos 

Use Taijiquan to teach distributed theory , It is really comfortable ！

Talk about distributed algorithms in Three Kingdoms , Comfortable, right ？

I'm Wukong , Try to be strong , Become a super Saiya ！

This article is from WeChat official account. - Wukong chat structure （PassJava666）.
If there is any infringement , Please contact the [email protected] Delete .
Participation of this paper “OSC Source creation plan ”, You are welcome to join us , share .