3.3 Distributed Consensus Algorithm: Raft

1. What Is Raft?

• A distributed consensus algorithm invented by Diego Ongaro.

2. Why Is Raft Needed?

• To solve the complexity of implementing Paxos.

3. Raft Algorithm Process

3.1. Roles

• Leader
• Follower
• Candidate

3.2. Three Phases

3.2.1. Phase 1: Leader Election

• Rule: whoever has the larger term is elected leader; if the terms are the same, whoever has the larger index is elected leader.
  • Vote: (term, index)
  • term: which Leader term it is.
  • index: index of the latest log entry.

1. All Nodes are in the Follower state.
2. If a Follower does not receive a heartbeat from the Leader for a certain amount of time, it switches itself to the Candidate state and starts an election.
   1. If more than half of the Nodes return true, it is elected Leader.
   2. If no more than half of the Nodes return true, it waits for a while and starts another election.
   3. If, during the election, it receives a request from a Leader whose term > its own term, it gives up the election and becomes a Follower.
3. After the election ends, it becomes either a Leader or a Follower.

3.2.2. Phase 2: Normal Replication

1. The Leader receives a client write request.
2. The Leader makes RPC calls to replicate it to the other Followers.
   1. If more than half of the Followers return true, replication succeeds and the Leader commits the local log.
   2. If no more than half of the Followers return true, replication fails and the Leader does not commit the local log.
3. The Leader returns write success or failure to the client.

3.2.3. Phase 3: Crash Recovery

• The old Leader crashes, a new Leader takes office, and the other Followers switch to the new Leader and begin synchronizing data.
• Leader election is the same as Phase 1.

4. References

• Software Architecture Design: Integrating Large-Scale Website Technical Architecture and Business Architecture - Yu Chunlong - WeRead
• Raft Compared with the ZAB Protocol - pingpangkuangmo - OSCHINA