Leader Election (And a bit of refreshing)

#

Base on all the question from the previous post, it seems that Raft single handedly powered a majority of modern cloud technology since its invention.

So, lets learn about dig deep down

Question Chain

#

Who made it?

Raft algorithm was introduced by Diego Ongaro and John Oustershout around 2013 with an extended paper published in 2014[^6] (that I’ll be using as the source of truth for my code later). The focus on Raft is to create an “understadable” consensus algorithm, pushing others to improve on its building blocks.

What is Consensus?

To put it simply, consensus is an agreement surrounding a state between fault tolerant distributed systems. Reaching an agreement meant that the decision on a state value is final, creating a cluster of server with a replicated state. To reach that goal these server need a protocol to do so.[^7]

How Raft works?

Raft work with a single leader approach and decompose the consensus problem to multiple subproblem. Each server talk to each other via two Remote Procedure Call (RPC), AppendEntries and RequestVote, we’ll talk about it later on.[^6]

Leader? What’s that?

Leader is one of the three state of a server in Raft. A Leader is responsible of handling these things:

• Client requests (If a client connect to a server with a state other than a Leader they will redirect it to the Leader)
• Log replication

The other two state are Candidate and Follower. The name is self explanatory, a Follower follow what Leader ask it to do, while Candidate ask for vote to be elected to a new Leader. [^6]

What about the multiple subproblem?

The subproblem to create a working consensus is listed below:

• Leader election
• Log replication
• Safety
• Cluster membership changes
• Log compaction

How do Raft deal with Leader election?

We need to start with what trigger the election. The election is triggered when a Follower failed to receive a “heartbeat” (AppendEntries Remote Procedure Call (RPC) with no new log data) from the current elected Leader within a period of time called “election timeout” that is choosen randomly from a fixed interval.

Once the timeout has passed, a Follower would change it’s state to Candidate and increase it’s term count by 1. A term signify an arbitrary division of time in Raft, just like what you see in real world Democracy leader election.

The new Candidate then ask for vote to other server by sending a RequestVote RPC and vote for itself. Other server can only vote for 1 server and vote on first-come-first-served basis. The election can end in three way:

• The Candidate win
  • It receives a majority of vote (Not detailed in Paper, I assume it as (N/2) + 1 where N is the amount of servers)
  • It become Leader and send heartbeat to other server
• The Candidate lost
  • It receive an AppendEntries RPC from another server claiming to be leader with a term as big as itself (if not it’ll reject the RPC and continue to be a Candidate)
• The Candidate neither win or lose
  • There has been multiple Candidate that split vote to themselves causing no majority wins by the Candidate
  • The Candidate will timeout and rerun the election with an increased term
  • To prevent another tie in the next term, the election timeout is re-randomized

To sum it up, it’s a bunch of simple “if-else” logic that if followed correctly would create an simple yet complex behaviour in the system.

With the Leader elected, can it start to do it’s job?

Yes, in this case we can go to the next subproblem Log Replication, we’ll discuss it in the next post.

TL;DR

#

Raft Leader Election Overview:

• Created By: Diego Ongaro and John Ousterhout (2013-2014) to develop an understandable consensus algorithm.¹
• Consensus: Agreement on a state among distributed systems, requiring a protocol.²
• How Raft Works: Utilizes a single leader to handle client requests and log replication, with servers operating as Leaders, Followers, or Candidates.[^6]
• Leader Election Process:
  • Triggered when a Follower misses a heartbeat from the Leader.
  • The Follower becomes a Candidate, requests votes, and if it secures a majority, it becomes the Leader.
  • If the Candidate fails to win, it either receives a vote from another Leader or faces a tie, prompting a new election with re-randomized timeouts.
• Outcome: The elected Leader then manages client requests and log replication.

Next Up: Details on Log Replication in the following post.