Last time we explained four kinds of cluster distributed control algorithm, so, next to introduce you to the common algorithms in distributed control. But to help you understand the RAFT algorithm better, let’s start with a simple example.
If a class (composed of: At the beginning, no one volunteers. After A certain period of time, three members offer themselves as candidates (A,B,C), but they are all good at it. So who should be the leader? A,B, and C each carry A countdown timer with A random time. Once the countdown is over, this person (suppose A) will collect and ask others for their opinions on him, namely, can he be elected class president? If he gets enough votes, he will automatically be promoted to monitor. If later, A is removed from the position of monitor for violation of law and discipline, other followers and previous candidates can still apply for the position and continue to compete for the position of leader. As for the log replication mentioned later, in this example, it can be understood as: the math teacher (client) asks the monitor to count his opinions and suggestions on the math class. The monitor receives the teacher’s information and sends it to others. After a period of time, some others give feedback, and the monitor counts it into his own information statistics. This opinion is transmitted to other followers. If the majority of the followers give feedback after a certain period of time, the leader makes a thorough count of the opinions of the math class and reports them to the math teacher (client).
Raft consistency algorithm is also known as distributed consensus algorithm. Consistency is the consistency of data across a distributed system, which can also be understood as the consistency of data values across multiple nodes. Its predecessor is Paxos algorithm, Paxos algorithm is distributed election algorithm: that is, in a pile of messages through continuous election so that the receiver or executor of each message can achieve data consistency, according to the same message order to execute. Paxos algorithm allows each client (client) each other send instruction to the server, and according to the election the way make data agree, its characteristic is that the algorithm is based on serial number higher win for the standard, and to attempt to when information if rejected, will once again with a new serial number to take part in the election, repeat, the purpose of the selected sequence recognized. It’s efficient, but it’s still a fly in the wall, and Raft is a much more optimized and understandable algorithm based on his work.
Raft algorithm, as a whole, can be understood as a democratic election, which elects a leader from voters. The core work of Raft algorithm is to decompose the problems generated by such a leader into two sub-problems of election and state replication process for processing. The election process is easy to understand, but what is state replication? In short, status replication is log replication. Its purpose is to ensure that the entire system can still ensure the normal operation of existing data when a node fails after primary selection. Each node has three states: leader, candidate and follower, which can be exchanged. The Leader is responsible for issuing proposals and the president node; Candidate as a candidate, in charge of competing for the leader; Followers are responsible for unifying the proposals issued by the leader. The following will do a simple exposition of the two sub-problems.
(1) Election Process:At server startup, all nodes start as followers, and each follower has a timer. Within a certain period of time, if there is no leader in the cluster, the followers will declare themselves as candidate to join the leader election. If no response is received within a period of time, a new election will be held. Other nodes will vote according to the received message. The candidate who receives votes from most nodes will be promoted to leader. If the leader fails during the working process of the system and the relevant nodes fail to receive the message sent by the leader within a certain period of time, other followers will re-join the election process of the leader to compete for the next leader. It is worth noting that if the two candidates for the position of leader elect at the same time and obtain the same number of votes, the voting information will be re-sent to conduct a new round of election. Such operation ensures that there will be no conflict after the re-sending of voting requests. The specific process can be seen in the following two figures to facilitate understanding.
(2) Replication process: After the leader is elected in the above election process, the specific steps of the log replication process are as follows: (1) The leader receives the proposal request from the client and writes the data in the local log. (2) The proposal content is included in the request sent by the leader. (3) The Follower replies to the Leader after receiving the request; (4) After receiving the response from the majority of followers, the Leader confirms the proposal, writes it into its own storage space and replies to the Client; (5) If a problem occurs, the leader is lost and the client cannot receive its information. After a certain period of time, a new leader will be elected to control and lead the whole cluster.
This is a brief introduction to the distributed control algorithm Raft consistency algorithm, which I hope you will understand in depth.
- End –
With the rapid development of technology, AMu Lab will keep up with the pace of technology and constantly recommend the latest technology and hardware in the robot industry to everyone. The greatest value of our training is to see our trainees make rapid progress in technology. If you are in the robotics industry, please follow our official account, we will continue to publish the most valuable information and technology in the robotics industry.
Amu Lab is committed to cutting-edge IT technology education and intelligent equipment, so that robot research and development more efficient!