introduce

Distributed consistency algorithms allow multiple machines to run services as a whole, even if some machines fail. Its origin is replicated State Machines, structured as follows

The core function of distributed consistency algorithm is to maintain the consistency of request logs. Each state machine executes exactly the same logs in the same order to maintain consistency.

Raft foundation

Raft is made up of multiple services and calls between services are made through RPCs.

state

Each service in a RAFT cluster can be in one of three states:

  1. leader
  2. follower
  3. candidate

In a normal case, only one of the cluster is the leader and the others are followers. Followers are passive and only accept and respond to requests. The leader accepts all client requests and distributes them to followers. Candidate is used to elect a new leader. The three state transitions are as follows

term

Raft divides time into terms, as shown in the figure below. Each RAFT starts with an election, during which time there is usually one or more candidates running for the leader, and if one candidate wins the election, it serves as the leader for the rest of the term. In some scenarios, the votes in the term are divided so that no candidate wins the election and becomes the leader. At this time, a new term will be opened and a new round of election will be held.

Term is used in raft much like a clock cycle, each service holds a current term. Calls between services are accompanied by term; If a service finds that it holds a smaller term, it will update it to a larger term. If the leader or candidate receives a request for a larger term, the term is updated and the state changes to follower. If a service receives a request for a smaller term, it will reject the request.

Leader election

Raft uses a heartbeat mechanism to trigger elections. The service stays in the follower state until it receives a valid request from the leader or candidate (term greater than or equal to its own term). The leader periodically sends requests to the followers to maintain their authority. If a follower does not receive the leader’s request within the election timeout period, it is considered that there is no effective leader and a new round of election is initiated.

When followers start the election, they add one to their term and change their status to candidate. Then vote for yourself and send a request to vote for other services. If a follower receives more votes than n/2 + 1(n is the number of services), it wins the election and becomes the leader.

The voting rules: each service can vote for no more than one candidate in one term, and followers will vote for the first eligible request that arrives. A candidate sends a vote request with two parameters, the index and term of its latest log. If the term parameter is greater than or equal to the term of the latest follower log, and the index parameter is greater than or equal to the index of the latest follower log, Would vote yes, or no.

There are three possible outcomes of the vote

  1. thiscandidateWin an election to becomeleader
  2. The rest of thecandidateWin an election asleaderDuring the voting process, receive greater than or equal to thistermWithin theleaderThe request sent to add logs is convertedcandidateThe status offollower)
  3. thistermnocandidateWin an election asleader

The third possibility is that multiple followers become candidates at the same time, and the votes are divided among multiple candidates. As a result, no candidate wins the majority of votes, that is, no candidate wins the election and becomes the leader. To avoid this persistent situation, raft uses a random election timeout (which reduces the likelihood of multiple followers becoming candidates).

Log copy

When a leader is established, requests sent by the client are accepted. Each request sent by the client contains an operation to be performed on the State Machine. Upon receiving the request, the leader adds the operation to the local log and synchronizes the log to other services. When the log is copied safely (described below), the operation corresponding to the log is applied to the state machine, a successful response is returned to the client, and finally sent to other services to indicate that the operation has been performed by the state machine (this step can be appended to the request to copy the log).

The log is organized as follows (the same colors are within a term) :

The leader decides to apply operation logs to the State machine when it is safe, and this state is called COMMITTED. Raft ensures that committed logs are persisted and executed by other valid services. Security means that logs are accepted by most services (n/2+1 or greater). This also means that the previous log is also safe (the leader log whose index is less than the current Commited log index is also safe)

conclusion

So far, I have briefly covered the basic concepts of RAFT, leader election, and log replication. Simple as it may seem, are these basic concepts enough to ensure security? This is still open to debate, and we’ll talk about safe behavior later.

reference

This article mainly refers to the following articles

  1. raft.github.io/raft.pdf