RAFT Consensus

RAFT uses a strong leader model where one server acts as the leader, managing the replicated log. A leader election is triggered using a heartbeat mechanism and randomized election timeouts.

• A candidate requests votes from peers to become leader.
• Each server votes for at most one candidate per term.
• The candidate that receives a majority of votes becomes the leader for that term.
• If no candidate wins, the term increments and a new election begins with randomized timeouts to prevent split votes.

The leader accepts client commands, appends them to its log, and replicates them to followers via AppendEntries remote procedure calls. Consistency is maintained by ensuring logs are identical across a majority.

• The leader appends the command to its log and sends it to all followers.
• Once a majority of followers have written the entry, it is considered committed.
• The leader then applies the committed entry to its state machine and returns the result to the client.
• Followers that crash or lag behind are eventually repaired by the leader's consistency check.

RAFT divides time into arbitrary periods called terms, which act as a logical clock. Each term begins with an election and is identified by a monotonically increasing integer.

• A term number is included in all communication between servers.
• If a server receives a message with a higher term, it updates its current term and reverts to a follower state.
• If a candidate or leader discovers its term is outdated, it immediately steps down.
• Terms ensure that stale leaders cannot corrupt the log with outdated commands.

RAFT ensures that once a command is applied to a state machine at a specific log index, no other server will ever apply a different command for that same index. This is enforced by an election restriction.

• A candidate's log must be at least as up-to-date as the logs of a majority of the cluster to win an election.
• The RequestVote RPC includes the candidate's last log index and term.
• Voters deny their vote if their own log is more complete.
• This prevents a leader from overwriting committed entries from a previous term.

RAFT supports dynamic cluster membership changes using joint consensus. This allows the cluster to transition from an old configuration to a new one without creating a window where two leaders could be elected.

• A joint consensus phase requires agreement from both the old and new configurations.
• Log entries are replicated to servers in both configurations during the transition.
• Once the joint configuration is committed, the system transitions to the new configuration.
• This ensures safety during server additions, removals, and replacements.

To prevent unbounded log growth, RAFT uses snapshotting for log compaction. The state machine writes its entire state to a snapshot, and all log entries up to that point can be discarded.

• Each server independently creates snapshots of its applied state.
• The leader can send a snapshot to a follower that is far behind via the InstallSnapshot RPC.
• This is more efficient than replaying millions of log entries.
• Snapshots also accelerate the recovery of a new server joining the cluster.