Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "what is the concept of Raft algorithm". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Background

Recently, in the process of using K8S, I have been using a Key-Value database Etcd. Whenever I see a tutorial that introduces Etcd, there is not much introduction. Most of them are independent of the K8S cluster and save state data. After going deep into Baidu, it is found that Etcd is a reliable, distributed Key Value storage system, which is used to store key data in distributed systems. An Etcd cluster is usually composed of 3 or 5 nodes. Among multiple nodes, distributed consistency collaboration is completed through a way called Raft consistency algorithm. The algorithm selects a master node as leader, and leader is responsible for data synchronization and data distribution. When the leader fails, the system will automatically select another node to become leader, and re-complete the synchronization and distribution of the data.

Seeing here, you probably know that Etcd is reliable because of the support of the Raft algorithm behind it. Think carefully, what is the Raft protocol? How does it conduct the election? if the leader node is dead, how to ensure that the data of each node is consistent? Will the change of member nodes lead to the problem of brain fissure? With these questions, let's unveil the truth of Raft.

Raft algorithm concept

Easy to understand, the Raft algorithm is a way based on the leader to achieve the consistency of communication and data of each node; if the leader node is down, the new leader is re-elected through specific rules.

This is just like an election in the village. first of all, there will be a village head in the village, and the village head is the bearer of the village, and everything has to be obeyed by him. Later, because of the lack of resistance to the epidemic, the village has been killed, and the village cannot be long for a day. Re-elect a candidate, how to elect the village head? First nominate the candidate, and then vote. So there are three roles in the whole raft algorithm: follower, candidate and leader.

Followers: ordinary people, silently follow orders, if you can not find a leader, then recommend yourself as a candidate

Candidate: the candidate asks for a vote from other nodes, and if he gets a majority of votes, he will become the leader.

Leader: everything depends on me, and all nodes have to listen to me.

How to conduct the election?

1. In the initial state, all nodes are followers. Each follower will carry a term number and a random timeout. As shown in the following figure:

Countdown state (0) initial state (1)

2. If the NodeC timeout occurs first, then it will recommend itself as a candidate. As shown in the following figure:

Request for vote (2)

3. Other nodes find that the term number has not been voted yet and are called by RPC, then they will vote according to the rule of "one node, one vote". In the voting process, they will verify that the candidate's number is greater than themselves, verify the integrity of the log, and increase their term number.

4. After NodeC is elected as the leader node, it will periodically send messages to other nodes, telling other nodes that everything is up to me to prevent other nodes from initiating elections, while other nodes will not initiate elections if they can keep their heartbeats with leaders within the timeout period.

Leaders send heartbeats (4) how to ensure data consistency?

When it comes to the consistency of the raft algorithm, we have to talk about the concept of logging. When is the journal? The replica data of each node exists in the form of a log, the client sends a write request to the server, the leader receives the write request, and the process of dealing with the write request is the process of copying and submitting log entries. As shown in the following figure:

Log submission process

1. The client sends data to the leader node, and the leader node creates log entries based on the client data and adds them to the local log.

2. The leader copies the log information to other follower nodes through RPC.

3. After most nodes are successfully replicated, the leader node will submit the data to the state machine.

4. Return to the client.

5. Other nodes receive log replication RPC information and find that the leader has submitted the data, then other nodes will also follow the submitted data.

Of course, after watching this process, there is no problem with the wind and water, but in the distributed system, any node may go down at any time. To take a most common example, in the second step above, the leader happens to successfully copy the log to another node, and the master node is down. How does the raft algorithm deal with it? At this time, it can be divided into two cases: the leader node has been submitted and successfully returned to the client and not submitted, but the treatment is relatively similar, in which a new leader node is re-elected to continue data submission. You may have two questions.

The raft algorithm does not require all node data to be based on the leader node. What if the leader node data is not up-to-date?

"

First of all, the leader log that can be elected must be up-to-date, otherwise the election will not be successful; in addition, if there are more followers than the leader log data, then be forced to be consistent with the leader.

"

How to deal with the client without knowing whether the submission was successful?

"

You can try to repeat the submission to the master node, and the raft algorithm requires each node to achieve idempotency, that is, the de-duplication mechanism.

"

A few more words, log matching this part, raft does very interesting, if interested, you can reply in the official account [raft] to get the raft paper.

Member node change problem

Before understanding the change of member nodes, consider a question. If two nodes join the three-node cluster at the same time, will the problem of cluster splitting occur? As shown below, a stable raft cluster now needs to join two nodes.

At this time, the cluster split occurred between NodeC, NodeA and NodeB, because the number and log index of NodeC are the largest, and successfully become the leader, as shown below:

For the above problems, many distributed systems have this problem, how to solve the raft algorithm?

"

Quite simply, nodes join the cluster one by one in order, and there is never a two-majority problem.

"

The specific method for joining is as follows:

In the whole joining process, the main steps are as follows: first, the leader synchronizes the data to the NodeD; after the synchronization is completed, synchronize the joining information of the NodeD node to other follower nodes, and finally submit the log to complete the change. After this change is completed, the next node will follow the above steps again.

Through the node change in the above way, it is guaranteed that there will always be only one leader node, which ensures the data consistency of most nodes, from which we can see that Raft is not a strict consistency algorithm, but a consensus algorithm.

In addition, consider another extreme case. NodeA, NodeB, and NodeC are raft clusters, and a network connection error occurs between NodeA and NodeB and NodeC, that is, NodeA is isolated from NodeB and NodeC, as shown below:

Network partition (1)

NodeB elected leader (2) client request, which cannot be copied to most nodes and cannot be submitted successfully (3)

Client request, which can be copied to most nodes, submitted successfully (4)

Finally, if the network is restored and NodeA updates the term data and finds that there is a term update in the cluster, then NodeA will be downgraded to a follower to join the raft cluster and copy the leader node data.

This is the end of the content of "what is the concept of Raft algorithm". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.