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

This article focuses on "how to understand distributed Raft". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand distributed Raft.

I. Overview of Raft

Raft algorithm is the preferred consensus algorithm for distributed system development. For example, Etcd and Consul are popular now.

If you master this algorithm, you can easily deal with the fault tolerance and consistency requirements of most scenarios. For example, distributed configuration system, distributed NoSQL storage and so on, easily break through the single machine limit of the system.

The Raft algorithm realizes the consensus of a series of values and the consistency of the log of each node through all the ways that take the leader as the standard.

II. Raft role

2.1 roles

Follower (Follower): ordinary people silently receive and receive messages from leaders. When the leader's heartbeat information times out, they come forward and recommend themselves as candidates.

Candidate (Candidate): the candidate will request a voting RPC message from other nodes, notify the other nodes to vote, and be promoted to leader if they win a majority of the votes.

Leader (Leader): overbearing president, everything is subject to me. Process write requests, manage log replication and constantly send heartbeat messages, telling other nodes that "I'm the leader, I'm alive, you don't" to launch a new election, and there's no need to find a new leader to replace me.

As shown in the following figure, three diagrams are used to represent followers, candidates, and leaders.

Role

III. Single-node system

3.1 Database Server

Now imagine a single-node system that acts as a database server and stores a value of X.

Database server

3.2 client

The green solid circle on the left is the client, and the blue solid circle on the right is node a (Node a). Term represents the term of office, which will be discussed later.

Client

3.3 the client sends data to the server

The client sends an update operation to the single-node server, setting the value stored in the database to 8. In a stand-alone environment (a single server node), the client gets a value of 8 from the server. Consistency is very easy to guarantee.

The client sends data to the server

3.4 how can consistency be ensured with multiple nodes?

But if there are multiple server nodes, how to ensure consistency? For example, there are three nodes: a _ r _ b _ r _ c. This is shown in the following figure. These three nodes form a database cluster. If the client updates these three nodes, how to ensure that the values stored in the three nodes are consistent? This is the distributed consistency problem. Raft algorithm is to solve this problem. Of course, there are other protocols that can also be guaranteed, this article is only for the Raft algorithm.

In a multi-node cluster, how can the Raft algorithm ensure that there is only one leader in the cluster at the same time in the case of node failure, partition error and other abnormal cases? Let's start with the process of electing leaders with the Raft algorithm.

IV. The process of electing leaders

4.1 initial state

In the initial state, all nodes in the cluster are in the state of followers.

As shown in the following figure, there are three nodes (Node) a, b, c, and the term of office (Term) is 0.

Initial state

4.2 be a candidate

The Raft algorithm realizes the characteristic of random timeout, and the timeout interval between each node waiting for the heartbeat information of the leader node is random. For example, the time interval between A nodes waiting for a timeout is 150 ms,B nodes 200 ms,C nodes 300 ms. Then a timed out first, and the timeout occurred first because it did not wait for the leader's heartbeat information. As shown in the following figure, the timeout timer for the three nodes starts to run.

Timeout time

When the timeout of node An expires, node A becomes a candidate and increases its term number, updates the Term value from 0 to 1, and votes for itself.

Node A:Term = 1, Vote Count = 1.

Node B:Term = 0.

Node C:Term = 0.

Be a candidate

4.3 Voting

Let's take a look at how candidates become leaders.

Leader election

Step 1: after node A becomes a candidate, send a request vote RPC message to other nodes, asking them to elect themselves as leaders.

The second step: after receiving the request voting information sent by node A, node B and node C will vote for node A without voting during the term of office numbered 1, and increase their own term number.

The third step: node A received three votes, got the majority of node votes, from the candidate to become the new leader in the current term.

Step 4: node A, as a leader, sends heartbeat messages to nodes B and C at fixed intervals, telling nodes B and C that I am the leader and organizing other followers to initiate new elections.

Step 5: node B and node C send response information to node A, telling node A that I am normal.

4.4 term of office

The English word is term, and leaders have tenure.

Automatic increment: followers recommend themselves as candidates after waiting for the leader's heartbeat message to time out, and will increase their own term number. As shown in the figure above, the term of office of Node An is 0, and when they are recommended as a candidate, the term number is increased to 1.

Update to larger value: when a node finds that its term number is smaller than other nodes, it will update to a larger numbering value. For example, the term of office of node An is 1 and requests to vote. The voting message contains the term number of node A, and the number is 1. After receiving the message, node B will update its term number to 1.

Return to follower: if a candidate or leader finds that his term number is smaller than that of other nodes, it will immediately return to the follower state. This scenario occurs after the partition error is restored, and the leader with term 3 receives a heartbeat message with term number 4, and the former will immediately return to the follower state.

Reject message: if a node receives a request for a smaller term number value, it will directly reject the request, such as Node A with term number 6, and Node B with term number 5 receiving a request to vote RPC message, then Node A will reject the message.

4.5 Election rules

During a term, leaders will lead until they have problems (such as downtime) or network problems (delays), and other nodes launch a new round of elections.

In an election, each server node will cast at most one vote for a term number, and then it will be gone.

4.6 most

Assuming that a cluster consists of N nodes, then most of them are at least Nmax 2 nodes 1. For example: a cluster of 3 nodes, most of them are 2.

4.7 heartbeat timeout to prevent multiple nodes from initiating voting at the same time, each node is assigned a random election timeout. During this time, the node cannot be a candidate and can only wait until the timeout. For example, in the above example, node A times out and becomes the candidate first. This ingenious design, in most cases, only one server node initiates the election first, rather than at the same time, reducing the loss of the election caused by the carve-up of votes.

Be a candidate

V. Leader failure

If the leader node fails, a new round of election will be triggered. As shown in the following figure, if leader node B fails, node An and node B will re-elect the Leader.

Leader failure

The first step: node A fails, node B and node C do not receive the heartbeat information of leader node A, waiting for timeout.

Step 2: node C times out first, and node C becomes a candidate.

Step 3: node C initiates a request for voting information to node An and node B.

Step 4: node C responded to the vote and voted for C, while Node A failed to respond to C's voting request.

Step 5: node C receives two votes (majority) and becomes the leader.

Step 6: node C sends heartbeat information to nodes An and B, node A responds to heartbeat information, node B does not respond to heartbeat information.

At this point, I believe you have a deeper understanding of "how to understand distributed Raft". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.