How does the leader election in Raft work?

Raft is a consensus protocol designed for its easy understandability. A consensus is defined as the agreement of shared states among multiple servers in distributed systems. The shared states typically involve some data structures supported by replicated logs.

Election algorithms choose a server from a group of servers to coordinate various tasks in a distributed system. In case of failure of a coordinator, a new coordinator is chosen by the algorithm.

Server states in Raft

Each server in the system exists in the following states:

1. Leader: A leader is responsible for accepting client requests and log replication at other servers. In normal circumstances, there is only a leader in the system.

2. Candidate: During the event of an election, servers can ask other servers for votes. When servers request votes, they are called candidates.

3. Follower: A follower is a passive entity. It does not issue requests on its own; rather, it only responds to requests made by the leader and candidates. The Follower syncs up its data with the leader and, in case of leader failure, it can contest an election.

The figure above shows the functionality of the system in normal circumstances.

In case of a leader’s failure, an election is called and the followers transition themselves to candidates.

The Raft algorithm divides time into smaller terms of arbitrary lengths. With each term, an election is initiated, and a leader is chosen by majority vote. In case of no majority, the term terminates without any leader. The term number increases monotonically and is exchanged in every communication.

The protocol uses these two types of Remote Procedure Calls (RPCs) to perform its basic functions:

1. RequestVotes is sent by candidates to gather votes during elections.

2. AppendEntries is used by leaders for replicating log entries and as a heartbeat. Heartbeats are exchanged to ensure the availability of servers.

Leader election

The leader sends periodic heartbeats to all other servers to maintain its leadership. An election is initiated when a follower times out while expecting a heartbeat from the leader. At this point, the timed out follower changes its state to Candidate and increments its term number. Then, it votes for itself and sends the RequestVotes RPC to all other servers.

These are the three possible configurations as a result of the election call:

1. The candidate wins the elections by receiving the majority of votes. It transitions itself to Leader and sends heartbeats to notify other servers of the new Leader.

2. When other candidates receive the AppendEntries RPC, they check the term number. If the term number is greater than what they have stored, they transition to Followers. Otherwise, they reject the RPC and maintain their Candidate state.

3. The candidate fails to receive the majority of votes or enters a split vote state. If more than one server becomes a candidate simultaneously, the votes can split with no clear majority. In this situation, a fresh election is called after one of the candidates times out.