Raft Consensus Algorithm

The consensus algorithm is specifically designed to solve data consistency problems among multiple replicas in a distributed environment. It achieves multi-replica consistency by electing a Leader and having the Leader node responsible for managing log replication.

Flowchart

Roles

• Leader: Responsible for receiving client requests, replicating logs to other nodes, and informing other nodes when it’s safe to apply these logs
• Candidate: A role used for electing a Leader
• Follower: Responsible for responding to requests from Leader or Candidate

Each term begins with an election. If the election fails, there is no Leader within that term; if a Leader is elected, then there is a Leader responsible for cluster state management during that term.

Execution Rules

All nodes:

• If commitIndex > lastApplied, apply log lastApplied to the state machine and increment lastApplied
• If RPC request or response contains term T > currentTerm, set currentTerm to T and convert to Follower

Followers:

• Respond to RPC requests from Leader and Candidate
• If no AppendEntries request is received or vote is given to Candidate within the election timeout period, convert to Candidate role

Candidates:

• Convert to candidate role and start election:

  1. Increment currentTerm
  2. Vote for self
  3. Reset election timer
  4. Send RequestVote to all other nodes

• If majority votes are received, convert to Leader node

• If election times out, restart a new round of election

Leader:

• Once election is complete: send heartbeats to all nodes; continuously send heartbeats during idle periods to maintain Leader status
• If client request is received, append log to local log, then respond to client after log is applied to state machine
• If for a follower, the index of the last log entry is greater than or equal to nextIndex, then: send all log entries starting from nextIndex, and update commitIndex