Understanding Raft Leader Election by building from scratch | Sushant Dhiman

Let’s say you are building distributed software that supports replication (such as a database). There will be multiple nodes running in a distributed environment for that same application. In order to support replication, all the data from one node needs to be copied to other nodes in the network as well. So you came up with an idea of a leader/follower-based system. But now there is a different problem. There are 5 nodes in a distributed system. How will you elect 1 node as leader? Raft is the solution for that.

Consensus Algorithms

Before diving into the Raft algorithm, we must understand what consensus algorithms are. A consensus algorithm is a set of rules that must be obeyed by multiple computers in a distributed environment to agree and a single state of data or decision. Let’s say you are using PayPal or Google Pay as your digital payment wallet. Behind the scenes, PayPal or GPay isn’t storing your transaction history in a single database. Instead, they are storing a copy of the same data in several databases (as a replica).

But if there is no coordination between all the databases, you might see inconsistency in your transaction history. What if a database shows 10 transactions and another shows only 7? Which will you trust? This can happen due to network partition, where one node keeps working and another node falls behind due to the partitioned network. Consensus algorithms make sure that data is correct and synced to all the nodes.

Raft Consensus

The Raft Consensus Algorithm is the PhD work of Diego Ongaro. He made this algorithm because other algorithms at that time were hard to understand and implement. For example, a very popular algorithm, Paxos, was created in 1989 and was used in almost every distributed system before the introduction of Raft. Paxos is extremely hard to understand and implement. So Raft is a simple and easy-to-understand alternative to Paxos.

Note: In order to keep this post beginner-friendly, we are going to discuss only the leader election part of Raft.

In Raft there are 3 types of nodes.

Leader — Accept and write requests and instruct followers.

Followers — Receive requests from the leader and execute them.

Candidates — When a leader dies, any follower can become a candidate and take part in the election.

This is a distributed database cluster where the leader node accepts write requests, processes them, and sends instructions to follower nodes to process the exact same request. This keeps data consistent between all nodes.

How communication is done in Raft?

Before discussing the actual leader election system, we need to discuss how nodes in the Raft consensus algorithm communicate with each other. There is no fixed communication protocol specified in the Raft research paper, but most of the Raft implementations are done using Remote Procedure Call protocols. You can also use other protocols like HTTP, Raw TCP, and even WebSockets, but RPCs are considered more reliable and fast for these kinds of workflows.

There are 2 types of network requests that are made in Raft.

AppendEntries - Used by leader to send instructions to client.

RequestVote - Used by candidates to request vote from other nodes.

Leader Election

In order to make things more understandable, let’s say there is already an existing leader in the raft cluster. In a regular interval, the leader will send the AppendEntries request to followers. Followers will process this request and return a response to the leader. In case the system is idle and the leader does not get any requests from the client, it will simply send heartbeats to followers in the form of empty AppendEntries requests. These heartbeats are the way in which a leader tells followers that I’m still active.

But what if the leader dies? In that case, followers won’t receive any heartbeat from the leader. Every follower has a random timeout between 150 ms and 300 ms that tells the follower how long to wait before the leader heartbeats before considering the leader as dead.

Once followers escalate the timeout and do not receive any communication from the leader, it will consider the leader as dead and promote itself to the candidate. Once a follower enters the candidate state, it will send a RequestVote request to other nodes in the cluster and ask for a vote. If other nodes give a vote to a candidate and the candidate gets a majority, it will promote itself as a leader.

All nodes have different waiting timeouts, and there is a reason for that. If every node has the same timeout, then each node will know that the leader is dead at the same time. This will cause all follower nodes to start the election at the same time, and none of the nodes will get a majority because everyone is standing in the election at the same time.

Complexities in Election

Although the Raft election system looks easy at first, it is not that...