Raft Consensus Algorithm

A replicated state machine is a technique for making a service fault-tolerant by running identical copies on multiple servers and ensuring each copy processes the exact same sequence of commands in the exact same order. If all replicas start in the same state and apply the same deterministic operations in the same order, they remain identical forever. The hard part is not applying operations — it is agreeing on their order in the presence of crashes and unreliable networks. That agreement problem is consensus. Raft solves consensus by imposing structure that Paxos deliberately avoids. Every server is at all times in exactly one of three roles: follower, candidate, or leader. Time is partitioned into consecutive, monotonically increasing terms, each identified by an integer. At most one server can be leader in a given term — this is enforced by a majority-vote election — and a term may also have no leader if an election fails (split vote). The leader is the sole point of contact for clients; it appends new commands to its local log and replicates that log to followers. Followers are purely passive: they accept the leader's log entries and respond to RPCs, but never initiate anything except starting an election when they suspect the leader has failed. The key terminology: a log entry is a tuple `(term, index, command)`. An entry is committed once the leader has confirmed it is stored on a majority of servers in the cluster; once committed, Raft guarantees the entry will never be lost or reordered, no matter how many subsequent leader crashes occur. Log matching is the property that if two logs contain an entry with the same index and term, all preceding entries in both logs are identical — this lets a leader replicate incrementally without ever needing an expensive log-reconciliation protocol. Election safety guarantees at most one leader per term, and leader completeness guarantees that any server elected leader in a later term already holds all entries committed in earlier terms. These properties compose into the overall safety guarantee: no two servers ever apply different commands at the same log index.

Raft's mechanism has three interlocking parts.

1. Leader election. Every follower runs an election timer with a randomized timeout (typically 150–300 ms). If it receives no `AppendEntries` heartbeat from a leader before the timer fires, it assumes the leader is dead, increments its `currentTerm`, transitions to candidate, votes for itself, and sends `RequestVote` RPCs to all other servers in parallel. A server grants its vote if (a) it has not already voted in this term, and (b) the candidate's log is at least as up-to-date as its own (the election restriction, detailed below). A candidate becomes leader upon receiving votes from a majority. If it instead receives an `AppendEntries` from a legitimate leader with an equal or higher term, it steps down to follower. If neither happens before its own timeout expires, it starts a new election with an incremented term — randomization keeps the probability of repeated split votes low.

2. Log replication. Once elected, the leader accepts commands from clients, appends each as a new entry to its own log, and sends `AppendEntries` RPCs (in parallel) to replicate the entry to every follower. Each RPC includes the index and term of the entry immediately preceding the new ones (`prevLogIndex`, `prevLogTerm`); a follower rejects the RPC unless its log already contains a matching entry at that position, which enforces the Log Matching Property inductively. When the leader learns that an entry is stored on a majority of servers, it marks that entry (and all preceding ones) as committed and applies it to its own state machine; it communicates the new commit index to followers via subsequent heartbeats, and followers then apply the same entries to their own state machines.

3. Safety enforcement. Two rules guarantee that a newly elected leader cannot silently erase committed history. First, the election restriction: a `RequestVote` is rejected if the candidate's last log entry is less up-to-date than the voter's — "more up-to-date" is defined by comparing `(lastLogTerm, lastLogIndex)` lexicographically. Because a committed entry lives on a majority, and any candidate needs a majority of votes, at least one voter must have seen every committed entry, so the candidate is forced to already have it (or something newer) before it can win. Second, Raft never commits an entry from a previous term merely because it is on a majority of servers — a leader only commits directly by counting replicas of its own current-term entries; entries from prior terms are committed only indirectly, as a side effect of committing a later entry in the current term. This closes a subtle failure case described in the correctness section below. ```pseudocode // Persistent state on every server (survives crashes) currentTerm := 0 votedFor := null log[] := [] // 1-indexed; each entry: (term, command) // Volatile state on every server commitIndex := 0 lastApplied := 0 // Volatile state on leaders only (reinitialized after election) nextIndex[] := {peer: len(log)+1 for peer in peers} matchIndex[] := {peer: 0 for peer in peers} state := FOLLOWER // ---- Election timeout on a follower or candidate ---- on ElectionTimeout: currentTerm += 1 state := CANDIDATE votedFor := self votesReceived := {self} resetElectionTimer(randomized) for peer in peers: send RequestVoteRPC(term=currentTerm, candidateId=self, lastLogIndex=len(log), lastLogTerm=log[len(log)].term) to peer // ---- Handling RequestVote RPC (any server) ---- on receive RequestVoteRPC(term, candidateId, lastLogIndex, lastLogTerm): if term < currentTerm: reply (currentTerm, voteGranted=false); return if term > currentTerm: currentTerm := term; votedFor := null; state := FOLLOWER candidateUpToDate := (lastLogTerm > log[len(log)].term) or (lastLogTerm == log[len(log)].term and lastLogIndex >= len(log)) if (votedFor in {null, candidateId}) and candidateUpToDate: votedFor := candidateId resetElectionTimer() reply (currentTerm, voteGranted=true) else: reply (currentTerm, voteGranted=false) // ---- Candidate tallying votes ---- on receive RequestVoteReply(term, voteGranted) while state == CANDIDATE: if term > currentTerm: currentTerm := term; state := FOLLOWER; votedFor := null; return if voteGranted: votesReceived.add(sender) if |votesReceived| > |peers+1| / 2: state := LEADER for peer in peers: nextIndex[peer] := len(log) + 1 matchIndex[peer] := 0 sendHeartbeatsToAll() // empty AppendEntries, asserts authority // ---- Leader: client request ---- on receive ClientCommand(cmd) while state == LEADER: log.append((term=currentTerm, command=cmd)) replicateToAll() // ---- Leader: periodic replication / heartbeat ---- def replicateToAll(): for peer in peers: prevIndex := nextIndex[peer] - 1 prevTerm := log[prevIndex].term if prevIndex > 0 else 0 entries := log[nextIndex[peer] : ] send AppendEntriesRPC(term=currentTerm, leaderId=self, prevLogIndex=prevIndex, prevLogTerm=prevTerm, entries=entries, leaderCommit=commitIndex) to peer // ---- Follower/any server: handling AppendEntries ---- on receive AppendEntriesRPC(term, leaderId, prevLogIndex, prevLogTerm, entries, leaderCommit): if term < currentTerm: reply (currentTerm, success=false); return if term >= currentTerm: currentTerm := term; state := FOLLOWER; votedFor := null resetElectionTimer() if prevLogIndex > 0 and (len(log) < prevLogIndex or log[prevLogIndex].term != prevLogTerm): reply (currentTerm, success=false); return // log doesn't match yet // Delete conflicting entries, then append new ones for i, e in enumerate(entries): idx := prevLogIndex + i + 1 if len(log) >= idx and log[idx].term != e.term: log := log[:idx-1] // truncate conflict if len(log) < idx: log.append(e) if leaderCommit > commitIndex: commitIndex := min(leaderCommit, len(log)) reply (currentTerm, success=true) // ---- Leader: handling AppendEntries reply ---- on receive AppendEntriesReply(term, success) from peer: if term > currentTerm: currentTerm := term; state := FOLLOWER; votedFor := null; return if success: matchIndex[peer] := prevLogIndex_sent + numEntries_sent nextIndex[peer] := matchIndex[peer] + 1 // Commit if a majority (incl. self) replicate an entry from THIS term for N from len(log) downto commitIndex+1: if log[N].term == currentTerm and |{p : matchIndex[p] >= N}| + 1 > |peers+1| / 2: commitIndex := N; break else: nextIndex[peer] := max(1, nextIndex[peer] - 1) // back off, retry replicateToOne(peer) // ---- Any server: apply committed entries to state machine ---- loop forever: if commitIndex > lastApplied: lastApplied += 1 apply(log[lastApplied].command) ```

Message complexity. Each `AppendEntries` round and each election round requires the leader/candidate to contact `n-1` peers, so both are `O(n)` messages per round, and elections need `O(n)` messages total (not `O(n²)`) since only the candidate initiates RPCs — replies go directly back to it. Steady-state replication sends one RPC batch per heartbeat interval per follower, so throughput-limiting cost is `O(n)` messages per committed batch of entries, and latency to commit is one round trip to a majority: `O(1)` round trips, independent of `n`, since RPCs fan out in parallel.

Time complexity of catching up a follower. If a follower's log has diverged from the leader by `k` entries, the naive backtrack-by-one strategy shown in the pseudocode costs `O(k)` RPC round trips in the worst case (real implementations optimize this with a "conflict term/index" hint returned by the follower, cutting it to `O(1)` amortized round trips per term of divergence — still `O(1)` in practice for typical crash-recovery scenarios).

Space. Each server stores the full log, `O(m)` entries where `m` is the number of commands ever proposed; production systems bound this with periodic log compaction / snapshotting, after which storage is `O(state size + uncommitted tail)`.

Correctness — why safety holds. The central theorem is the Leader Completeness Property: if an entry is committed in term `T`, it will be present in the logs of leaders of all terms `> T`. The proof is by contradiction and uses two facts baked into the mechanism: 1. Committed implies majority. An entry is committed only after the leader confirms a majority of servers (including itself) have replicated it (via `matchIndex` counting). 2. Election requires majority, and voter comparison is monotone. To win an election a candidate needs votes from a majority of servers; because any two majorities intersect in at least one server, at least one voter for the new leader must be among the majority that stored the committed entry. Suppose for contradiction that leader `L` of a later term `T' > T` does not have the committed entry `e` (committed in term `T`). Since `L` won an election, some voter `V` granted its vote to `L`, and `V` must have stored `e` (because `e` was committed on a majority, and every majority overlaps every other majority by the pigeonhole principle). The election restriction says `V` only votes for candidates whose log is at least as up-to-date as `V`'s own log (compared lexicographically by `(lastLogTerm, lastLogIndex)`). Since `V` has `e` and votes for `L`, `L`'s log must be at least as up-to-date as `V`'s at the time of voting, which forces `L`'s log to already contain `e` (or an entry that supersedes it) — contradicting the assumption. Hence leader completeness holds. ∎ (sketch) A subtlety patched by the "commit only current-term entries directly" rule: without it, a leader could replicate an old-term entry to a majority, then crash before committing anything in its own term, and a later leader — legitimately elected via the restriction — could still overwrite that entry, because being "at least as up to date" only guarantees the entry survives in the log, not that it was safely committed by the original leader's count. Raft closes this gap by never marking an old-term entry committed via replica counting alone; it becomes committed only transitively, once a same-term entry above it is committed. This is the one non-obvious wrinkle that a correctness argument must include — omitting it is a classic source of subtly broken Raft implementations.

Tradeoffs versus Paxos. Raft's strong leader simplifies reasoning and implementation at the cost of a slightly less general failure model: it assumes non-Byzantine (crash-stop) failures, requires stable leader-based flow for all writes (a single bottleneck unless combined with sharding), and pays an availability cost during leader elections (`O(election timeout)` unavailability window on leader crash, typically hundreds of milliseconds). Multi-Paxos achieves comparable throughput but with a much harder-to-verify safety argument and no canonical, widely agreed pseudocode for the full protocol including reconfiguration.

Consider a five-server cluster `{S1, S2, S3, S4, S5}`. All start as followers in term 0 with empty logs.

What this trace demonstrates:

• The randomized timer breaks the tie for who becomes leader (step 1), avoiding a scenario where multiple candidates start simultaneously and split the vote.
• Commitment requires a majority, not all servers — S5's lost RPC in step 5 does not block progress (step 6).
• Leader completeness in action: S3, elected in term 2, must already hold the term-1 committed entry `x=1` to win votes from a majority that has it (step 8) — exactly the mechanism proven above.
• Log repair (step 11) uses the `prevLogIndex`/`prevLogTerm` consistency check and backoff to bring a lagging follower like S5 up to date without any special-case "recovery protocol" — it is the same `AppendEntries` path used for normal replication.

Raft was designed at Stanford as a direct response to the recognized difficulty of teaching, implementing, and formally verifying Paxos-family protocols. The design goal was explicitly pedagogical: decompose consensus into understandable pieces without sacrificing the fault-tolerance guarantees Paxos provides, and validate that understandability with a real user study comparing students learning Raft versus Paxos.

Raft is the replication engine inside etcd, the strongly-consistent key-value store that Kubernetes uses for all cluster state — every pod schedule, service definition, and config map is committed through a Raft log before it takes effect. HashiCorp Consul and Nomad use Raft for service-discovery and scheduler state. CockroachDB and TiDB/TiKV shard data into many small Raft groups (one per data range) to get horizontal scalability while keeping each range strongly consistent — an architecture sometimes called "Multi-Raft." Kafka's KRaft mode (replacing ZooKeeper) uses a Raft-derived protocol to replicate cluster metadata. Beyond storage systems, any service that needs a small, strongly-consistent coordination substrate — leader election for a job scheduler, distributed locks, configuration propagation — typically reaches for Raft rather than re-deriving Paxos, precisely because its clear decomposition into leader election, log replication, and safety makes it feasible to implement, test, and audit correctly. This is the practical bridge from single-decree consensus theory to the everyday Replication and Consistency Models that back cloud infrastructure.

Ask the tutor: How does Raft's read-index protocol interact with leader leases to provide linearizable reads without a full quorum round trip on every request?