Raft

The most widely deployed consensus protocol today—etcd, Consul, TiKV, and CockroachDB are all based on Raft. Its design goal is not to be the "strongest," but to be "easier to understand and implement than Paxos": it decomposes consensus into three orthogonal sub-problems: leader election, log replication, and safety guarantees.

Overview

The problem consensus aims to solve: enabling a group of machines that may crash, and where messages may be lost or reordered, to agree on "the order of a sequence of operations"—this is the foundation for distributed databases, configuration centers, and distributed locks. Paxos solved this theoretically, but it is notoriously difficult to understand and implement (even the paper's author, Lamport, had to write Paxos Made Simple as a clarification). Diego Ongaro’s 2014 PhD thesis made understandability itself a design goal, resulting in Raft.

Raft’s decomposition approach: the entire protocol revolves around a strong leader—all writes go through the leader, and logs flow only from the leader to followers. Thus, consensus is split into three sub-problems that can be understood separately:

1. Leader Election – How to elect a new leader if the current one fails.
2. Log Replication – How the leader safely replicates logs to a majority of nodes.
3. Safety – How to ensure that committed data is not lost even if the leader changes.

Nodes have only three roles, and their state transitions are summarized in one diagram:

flowchart LR
    F["🙋 <b>Follower</b><br><small>Passive responder · Waits for heartbeats</small>"]
    C["🗳️ <b>Candidate</b><br><small>term+1 · Campaigns to all nodes</small>"]
    L["👑 <b>Leader</b><br><small>Single write entry point · Broadcasts heartbeats</small>"]
    F -->|"Election timeout: 150-300ms<br>No heartbeat received"| C
    C ==>|"Majority votes received ✓"| L
    C -.->|"Received heartbeat from new leader<br>Concedes defeat"| F
    C -.->|"Split vote<br>Retry with term+1"| C
    L -.->|"Sees higher term<br>Immediately steps down"| F
    classDef follower fill:#64748b1f,stroke:#64748b,stroke-width:2px
    classDef candidate fill:#d2992226,stroke:#d29922,stroke-width:2px
    classDef leader fill:#4493f826,stroke:#4493f8,stroke-width:2.5px
    class F follower
    class C candidate
    class L leader

Time is divided into segments called terms (term), which are monotonically increasing and serve as a logical clock globally: at most one leader per term; any RPC participants first compare terms, and if a higher term is seen, they immediately downgrade to followers and update themselves—this rule eliminates all "stale leaders who still think they are leaders" split-brain scenarios.

Core Data Structures

The first three must be persisted because: if a node restarts and forgets votedFor, it might vote twice in the same term → resulting in two leaders; forgetting the log means losing confirmed data.

Leader Election Process

Each follower maintains a randomized election timeout (150-300ms). Receiving a leader’s AppendEntries (which also serves as a heartbeat) or casting a vote resets the timer; if it times out, the follower assumes the leader has died: increments the term, becomes a candidate, votes for itself, and sends RequestVote {term, candidateId, lastLogIndex, lastLogTerm} to all nodes.

Nodes receiving a RequestVote decide whether to vote based on three rules:

1. term < currentTerm → Reject (stale candidate).
2. Already voted for someone else in this term → Reject (one vote per node, votedFor).
3. The candidate’s log must be at least as up-to-date as mine—compare the last log entry: the one with the larger lastLogTerm is newer; if terms are equal, the one with the larger lastLogIndex is newer. If not satisfied → Reject.

There are three possible outcomes: get a majority of votes → become leader, immediately broadcast heartbeats to assert authority; receive a valid new leader’s heartbeat → revert to follower; timeout without result (split vote) → increment term and retry. Random timeouts are the mechanism to prevent split votes: since nodes have different timeout durations, almost always one node will initiate first and win the election, typically in a single round in practice.

The third voting rule is half of the safety guarantee: commit requires confirmation from a majority of nodes, and election requires votes from a majority of nodes—the two majorities must intersect. Nodes in the intersection hold committed logs and will only vote for someone whose log is not older than theirs. Therefore, any elected leader must already possess all committed logs. Raft therefore does not need to "catch up" on old values after election like Paxos does.

Log Replication

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: Write request
    L->>L: Append to local log (index=N, term=T)
    par Concurrent replication
        L->>F1: AppendEntries(prevLogIndex, prevLogTerm, entry)
        L->>F2: AppendEntries(...)
    end
    F1-->>L: ok (matchIndex=N)
    Note over L: Majority replicated → commitIndex = N
    L->>L: Apply to state machine
    L-->>C: Return result
    Note over L,F2: Next AppendEntries carries new commitIndex,<br>followers apply individually

AppendEntries includes a consistency check: the leader attaches the index and term of the previous log entry (prevLogIndex/prevLogTerm) before each log entry. Followers reject if these do not match. Upon rejection, the leader decrements the nextIndex for that follower and retries until it finds the last common point in both logs, then overwrites the follower’s log with its own log from that point onward. This mechanism ensures an invariant: if two logs have the same term at a given index, their contents before that index are identical.

Why Commit is Safe

Definition of commit: a log entry is considered committed once it is persisted by a majority of nodes. Key invariant: committed logs must appear in the logs of all subsequent leaders.

Proof sketch: Entry E is committed → Majority set S1 has E; New leader elected → Majority set S2 voted for it; S1 ∩ S2 is non-empty → Nodes in the intersection have both E and voted for the new leader → By voting rules, the new leader’s log is at least as up-to-date as theirs → The new leader must have E. ∎

A subtle pitfall (Paper Figure 8): a leader cannot directly commit logs from an old term, even if it has replicated them to a majority—the majority replication of the old term might be overwritten by logs from a higher term. The correct approach is to only commit logs from the current term; old logs are committed indirectly over time. In practice, after becoming leader, the leader first commits a no-op log entry for the current term to resolve this quickly.

Snapshots and Log Compaction

Unbounded log growth is unsustainable. The solution is to persist the current state of the state machine as a whole, then discard previous logs:

1. The state machine generates a snapshot, recording lastIncludedIndex / lastIncludedTerm.
2. If a follower is too far behind (nextIndex ≤ lastIncludedIndex, corresponding logs deleted), the leader sends an InstallSnapshot RPC, and the follower replaces its state with the snapshot.
3. Safely delete log[0..lastIncludedIndex].

Membership Changes: Joint Consensus

Expanding a cluster from 3 nodes to 5 nodes cannot be done in one step—at the moment of switch, the majority of the old configuration (2/3) and the majority of the new configuration (3/5) might not intersect, potentially electing two leaders (split-brain).

Raft’s solution is a two-phase transition, inserting a "joint configuration" C(old,new) in between:

1. Phase 1: The leader broadcasts C(old,new). From then on, any decision (including elections) requires simultaneous majorities from both the old and new configurations—both majorities must agree, making it impossible to have two leaders.
2. Phase 2: After C(old,new) is committed, the leader broadcasts C(new), requiring only the majority of the new configuration to confirm, completing the transition.

Even if the leader crashes mid-transition, the new leader will only operate under C(old,new) or C(new), preserving safety. In practice, etcd uses a simpler single-node change: adding/removing one node at a time, where old and new majorities naturally intersect, eliminating the need for joint consensus.

Differences Between Raft and Paxos

The original form and derivation of Paxos can be found in Paxos; engineering trade-offs of production systems like etcd/TiKV built on Raft are discussed in Real Systems; why consensus cannot avoid majority quorums and CAP constraints is covered in CAP and Consistency Models.

References

• Paper: "In Search of an Understandable Consensus Algorithm" (Ongaro & Ousterhout, 2014) · Ongaro’s PhD thesis (includes Figure 8 counterexample and correction)
• Visualization: raft.github.io (interactive animations, excellent) · thesecretlivesofdata.com/raft
• Implementations: etcd/raft (Go, production-grade) · hashicorp/raft (Go) · tikv/raft-rs (Rust)

Keywords: Raft, consensus protocol, leader election, log replication, term, split vote, joint consensus, membership change, snapshot, InstallSnapshot, etcd, TiKV, quorum