Consensus in distributed systems was long regarded as an esoteric domain dominated by Paxos—notoriously subtle, difficult to understand, and notoriously resistant to bug-free implementations in production software. In 2014, Diego Ongaro and John Ousterhout introduced Raft, deliberately designed around an explicit design goal: understandability without sacrificing formal safety. By decomposing the monolithic consensus problem into three strictly segregated orthogonal subproblems—Leader Election, Log Replication, and Safety—Raft transformed modern distributed infrastructure, serving as the foundational consensus engine powering Kubernetes (etcd), TiKV, HashiCorp Consul, and CockroachDB.
1. The Architecture of Decomposed Consensus
Unlike symmetric consensus protocols where all nodes propose concurrently, Raft relies on a strong, authoritative leader model. At any discrete logical moment, each node resides in exactly one of three states:
- Leader: Handles all client requests, dictates log sequence order, and replicates log entries across followers.
- Follower: Passive participant responding strictly to Remote Procedure Calls (RPCs) from leaders and candidates. If no communication is received within an election timeout, it transitions to a candidate.
- Candidate: An active seeker of leadership attempting to gather votes from a majority quorum of nodes.
Time is discretized into arbitrary, monotonic logical epochs called Terms ($t in mathbb{N}$). Terms act as a distributed logical clock, allowing nodes to detect obsolete leaders and stale state instantaneously:
$$ au_{i} < au_{j} implies ext{Node } i ext{ must step down and update its current term to } au_j$$
2. Randomized Leader Election & Split-Vote Prevention
When a follower’s election timer expires without receiving a heartbeat (`AppendEntries` RPC with empty payload), it initiates an election cycle:
- Increments its current term: $ au leftarrow au + 1$.
- Transitions to the Candidate state and casts a self-vote.
- Dispatches `RequestVote(term, candidateId, lastLogIndex, lastLogTerm)` RPCs concurrently to all other peers.
A fundamental failure mode of symmetric majority voting is the split-vote anomaly: if multiple followers timeout simultaneously, votes split evenly, causing election deadlock across consecutive rounds. Raft eliminates this pathological condition through randomized election timeouts chosen uniformly from a calibrated interval:
$$T_{ ext{election}} sim mathcal{U}(T_{min}, T_{max}) quad ext{where usually } T_{min} = 150, ext{ms},, T_{max} = 300, ext{ms}$$
Because election timeouts are staggered stochastically, one node invariably times out first, increments its term, broadcasts vote requests, and secures a majority quorum before any competing follower triggers an election.
3. The Log Matching Invariant
Replicating state safely across asynchronous networks requires a strict structural invariant governing log entries. Each log entry stores an index $i$, a term $ au$, and a client state-machine command $c$:
$$e = langle i, au, c
angle$$
Raft guarantees the Log Matching Property through two formal invariants:
- Index & Term Identity: If two entries in different logs have identical index and term, they store the exact same command:
$$orall e_1, e_2: (e_1.i = e_2.i land e_1. au = e_2. au) implies e_1.c = e_2.c$$ - Prefix Coherence: If two entries in different logs have identical index and term, then their logs are completely identical in all preceding entries from $1$ up to $i$:
$$orall k le i, quad ext{Log}_A[k] equiv ext{Log}_B[k]$$
This invariant is enforced inductively via the consistency check in `AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit)`. A follower rejects the RPC if its local log does not contain an entry at `prevLogIndex` with matching term `prevLogTerm`. If the follower accepts, it overwrites any conflicting local entries and appends the new entries, preserving log prefix equivalence.
4. The Election Safety Constraint & The Leader Completeness Invariant
In many consensus algorithms, an elected leader can pull missing log entries from other nodes. In Raft, data flow is strictly unidirectional: from leader to followers. Consequently, a candidate cannot be elected unless its log contains all previously committed entries. This critical invariant is known as Leader Completeness.
When a voter evaluates a `RequestVote` RPC from candidate $c$, it enforces the Up-to-Date Rule:
- If the candidate’s last entry term $ au_c$ differs from the voter’s last entry term $ au_v$, the candidate with the higher term is strictly more up-to-date:
$$ au_c > au_v implies ext{Candidate is more up-to-date}$$ - If the terms are identical ($ au_c = au_v$), the candidate with the longer log is more up-to-date:
$$( au_c = au_v) land (i_c ge i_v) implies ext{Candidate is more up-to-date}$$
If the candidate’s log is less up-to-date than the voter’s, the voter denies its vote. By Pigeonhole Quorum Intersection, any committed entry must reside on at least one node in any majority quorum gathered by a prospective leader. That node will reject the vote of any candidate lacking that committed entry, formally guaranteeing that no candidate lacking a committed entry can ever become leader.
5. Committing Entries from Previous Terms
A subtle edge case in Raft consensus involves uncommitted entries from prior terms. If a leader crashes before replicating an entry to a majority, a subsequent leader might replicate that entry to a majority of servers. However, Raft enforces that a leader can never commit a log entry from an older term simply by counting replicas.
Instead, a leader commits log entries only by counting replicas for an entry created during its current term. Once an entry from the current term is committed on a majority quorum, the Log Matching Invariant transitively commits all preceding entries from older terms, avoiding retroactive rollback anomalies.
6. Cluster Membership Changes & Joint Consensus
Changing cluster configuration (adding or removing nodes) safely without downtime cannot be done in a single asynchronous transition because disjoint majorities could form between the old configuration $mathcal{C}_{ ext{old}}$ and the new configuration $mathcal{C}_{ ext{new}}$.
Raft solves this via Joint Consensus ($mathcal{C}_{ ext{old,new}}$):
- The leader logs and commits a transition entry entering joint consensus: $mathcal{C}_{ ext{old,new}}$.
- During joint consensus, decisions require separate majorities from both $mathcal{C}_{ ext{old}}$ and $mathcal{C}_{ ext{new}}$:
$$Q in mathcal{C}_{ ext{old,new}} iff (Q cap mathcal{C}_{ ext{old}} > |mathcal{C}_{ ext{old}}|/2) land (Q cap mathcal{C}_{ ext{new}} > |mathcal{C}_{ ext{new}}|/2)$$ - Once $mathcal{C}_{ ext{old,new}}$ is committed, the leader issues a second entry committing the final configuration $mathcal{C}_{ ext{new}}$, returning to single-majority rule without vulnerability to split-brain.
