Deep Dive into Raft Leader Election: Building a Distributed Consensus Algorithm from Scratch

In the world of distributed systems, consensus is one of the most critical and challenging problems. When multiple nodes need to agree on a value, how do you ensure the entire system continues to operate correctly even when some nodes crash or network partitions occur? The Raft algorithm was born to solve exactly this problem. Compared to Paxos, which is notoriously difficult to understand, Raft's design philosophy prioritizes understandability. This article takes you through a ground-up exploration of the most critical component of Raft — Leader Election.

Why We Need the Raft Consensus Algorithm

In distributed systems, we frequently need to maintain a Replicated State Machine across multiple servers — for example, in distributed databases or configuration centers like etcd and Consul. The replicated state machine is the core abstraction for achieving fault tolerance in distributed systems. The fundamental idea is: if state machines on multiple servers start with the same initial state and execute the same sequence of commands in the same order, they will ultimately reach the same state. This seemingly simple idea faces enormous challenges in practice — network delays, message loss, and node crashes can all cause nodes to receive commands in inconsistent orders. The core task of a consensus algorithm is to ensure that all nodes' logs (i.e., command sequences) remain consistent. The fundamental requirement of these systems is that data replicas across all nodes must remain consistent, even in the face of machine failures.

etcd is the core data store for Kubernetes, using Raft to guarantee strong consistency of cluster configuration data. Every write operation to etcd goes through the Raft log replication process: the Leader receives the write request, replicates the log to a majority of Followers, and only returns success after confirming the commit. HashiCorp's Consul similarly uses Raft to achieve consistency in service discovery and configuration management. In these production systems, tuning election timeouts and heartbeat intervals directly affects the system's failure recovery time (typically ranging from hundreds of milliseconds to a few seconds). Additionally, TiKV (the storage engine of TiDB) uses a Multi-Raft architecture where each data shard (Region) runs an independent Raft group, achieving strong consistency with horizontal scalability.

While the traditional Paxos algorithm is theoretically complete, its complexity makes engineering implementation extremely difficult. Paxos was proposed by Leslie Lamport in 1989 and was the first consensus algorithm to be rigorously proven correct. However, the original Paxos paper was written as an allegory about a Greek parliament, and there is virtually no standardized guidance for engineering implementations of Multi-Paxos (handling consensus on consecutive values). Google's Chubby lock service team openly acknowledged that a huge gap exists between the Paxos paper and a usable implementation. This directly motivated Diego Ongaro to propose Raft in his 2014 doctoral dissertation, where user studies demonstrated that Raft is significantly easier to understand and teach than Paxos.

Raft's authors, Diego Ongaro and John Ousterhout, explicitly stated during the design process that algorithm understandability should be the primary goal. To achieve this, Raft decomposes the entire consensus problem into three relatively independent subproblems:

• Leader Election: How to elect a unique leader within the cluster.
• Log Replication: How the leader synchronizes logs to other nodes.
• Safety: How to ensure committed logs are never lost or overwritten.

This article focuses on the first subproblem, which is the foundation for understanding Raft. Only after a stable leader is elected does subsequent log replication become meaningful.

Three Node Roles in a Raft Cluster

In a Raft cluster, every node is in one of the following three states at any given moment:

Follower

This is the initial state of every node. Followers are passive — they never initiate requests on their own and only respond to messages from Leaders and Candidates. If a Follower does not receive a heartbeat from the Leader within a certain period, it considers the Leader to have failed.

Candidate

When a Follower's election timeout triggers, it transitions to the Candidate state and initiates a new election round, requesting votes from other nodes.

Leader

The sole node in the cluster responsible for handling client requests and managing log replication. The Leader periodically sends heartbeats (empty AppendEntries RPCs) to all Followers to maintain its authority.

These three roles can transition between each other, forming the dynamic equilibrium of the Raft state machine.

Term: The Core Concept of Raft's Logical Clock

Understanding leader election is impossible without grasping the concept of "term." Raft divides time into consecutive terms, each identified by a monotonically increasing integer. Terms serve as Raft's logical clock, helping nodes identify outdated information.

Every term begins with an election. If a candidate wins the election, it serves as Leader for the remainder of that term. If the election fails due to a split vote, that term will have no Leader, and the system will start a new term with a fresh election.

The critical role of terms is this: every node records its current term number and includes it in all communications. When a node discovers that another node's term number is greater than its own, it immediately updates its term and reverts to the Follower state. This mechanism ensures that two Leaders with the same term number can never coexist in the cluster, fundamentally preventing the "split brain" problem.

Split brain is one of the most dangerous failures in distributed systems: a network partition causes the cluster to split into multiple subsets, each electing its own Leader and operating independently, resulting in data inconsistency. Raft mathematically eliminates this possibility through the quorum mechanism: in a cluster of 2f+1 nodes, any two majority subsets must have an intersection (by the pigeonhole principle). Therefore, it is impossible for two candidates to simultaneously receive more than half the votes. Typical Raft deployments use 3 nodes (tolerating 1 failure) or 5 nodes (tolerating 2 failures), with node counts usually being odd to maximize fault tolerance efficiency.

Raft Election Process in Detail

Leader election triggering relies on two key timer mechanisms.

Randomized Election Timeout Design

Each Follower maintains an election timeout timer, typically set to a random value between 150ms and 300ms. This randomization is crucial — it effectively reduces the probability of multiple nodes simultaneously initiating elections and causing split votes.

Notably, this design is closely related to the FLP impossibility theorem in distributed systems theory. The FLP impossibility theorem (Fischer, Lynch, Paterson, 1985) proves that in a completely asynchronous system, even if only one node may crash, no deterministic consensus algorithm can guarantee termination. Raft circumvents this theoretical limitation by introducing timeout mechanisms (i.e., a partial synchrony assumption). The randomization range of election timeouts requires careful tuning: it must be significantly larger than the network round-trip time (RTT) to avoid frequent false positives about Leader failure, yet it cannot be too long, or it will extend system unavailability. The Raft paper recommends satisfying the timing relationship: broadcastTime ≪ electionTimeout ≪ MTBF (Mean Time Between Failures).

When a Follower does not receive a heartbeat from the Leader or a valid vote request within the timeout period, it will:

1. Increment its term number by one
2. Transition to the Candidate state
3. Vote for itself
4. Send RequestVote RPCs in parallel to all other nodes in the cluster

RequestVote Voting Rules

A node receiving a vote request follows these rules to decide whether to grant its vote:

• If the term number in the request is less than its own current term, reject the vote.
• Within the same term, each node can cast at most one vote (first-come, first-served).
• The candidate's log must be at least as up-to-date as the voter's own log to receive the vote (this guarantees safety).

The specific comparison for the third rule works as follows: first compare the term number of the last log entry — a higher term number is more up-to-date; if the term numbers are equal, the longer log is more up-to-date. This rule ensures an important invariant — Election Safety: only a candidate that contains all committed log entries can win the election. This means committed data is never lost, which is Raft's State Machine Safety property. Without this rule, a node with a lagging log could be elected and overwrite committed new data with old data, completely destroying the system's consistency guarantees.

Three Possible Election Outcomes

After a Candidate initiates an election, three outcomes are possible:

1. Wins the election: Receives votes from more than half the nodes in the cluster, immediately becomes Leader, and begins sending heartbeats.
2. Discovers a new Leader: While waiting for votes, receives a heartbeat from another node with a term number no less than its own, and reverts to the Follower state.
3. Election times out with no result: No node receives a majority of votes (split vote), and no Leader is elected for the current term. The Candidate waits a random period before starting a new election round.

It is precisely the "majority" requirement that guarantees at most one Leader can be elected at any given time — because two candidates cannot simultaneously receive more than half the votes.

The Practical Value of Building Raft Election from Scratch

Why should you understand Raft by "building it from scratch"? Paper-based algorithm descriptions often overlook many implementation details. When you implement election logic yourself, you encounter a series of practical questions:

• How do you gracefully handle concurrent RPC requests and state transitions?
• When exactly should timers be reset? The election timeout must be reset after receiving a valid heartbeat.
• After a network partition heals, how is a stale Leader "demoted"?

By building it hands-on, these abstract rules transform into concrete code logic, allowing you to truly internalize your understanding of the algorithm. This also embodies Raft's design philosophy — a consensus algorithm simple enough for engineers to reproduce by hand is far more valuable than one that is theoretically perfect but nearly impossible to implement.

In engineering practice, MIT 6.824 (now renamed 6.5840) Distributed Systems course features Raft implementation as its core lab project, requiring students to implement the complete Raft protocol including election from scratch. Experience from this course shows that the most error-prone areas tend to be: concurrency lock granularity control, timing of RPC response handling, and choosing when to persist state. These are all issues that papers don't discuss in detail but must be handled correctly in engineering.

Summary

Raft's leader election elegantly solves the problem of leader selection in distributed systems through three pillars: the term mechanism, randomized timeouts, and majority voting. Its core ideas can be summarized as:

• Use monotonically increasing terms as a logical clock to prevent multiple Leaders from coexisting.
• Use randomized timeouts to break symmetry and reduce split votes.
• Use the majority principle to guarantee Leader uniqueness and data safety.

Mastering leader election is the first step toward understanding the entire Raft algorithm. The subsequent log replication and safety guarantees are all built upon this stable Leader foundation. For any engineer looking to go deep into distributed systems, implementing Raft by hand is undoubtedly an invaluable learning journey.