---
title: Raft
url: https://doc.liz6.com/en/distributed-systems/02-consensus-protocols/01-Raft
locale: en
area: distributed-systems
tags:
- Raft
- consensus
- leader election
- log replication
- distributed systems
- distributed-systems
- consensus-protocols
date: 2026-06-30
modified: 2026-07-16
description: 'A detailed explanation of the Raft protocol: leader election, log replication, commit safety proofs, snapshots, and membership changes (joint consensus). The most widely deployed consensus protocol today—etcd, Consul, TiKV, and CockroachDB are all based on it. Its design goal is to be easier to understand and implement than Paxos.'
---

# 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:

```mermaid
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

| State | Field | Meaning |
|---|---|---|
| Persistent (flushed to disk before every RPC response) | `currentTerm` | The latest term seen by this node |
| | `votedFor` | Who this node voted for in this term |
| | `log[]` | Log entries, each `{term, index, command}` |
| Volatile | `commitIndex` | The last committed index |
| | `lastApplied` | The last index applied to the state machine |
| Leader-only (in-memory) | `nextIndex[]` | The next index to send to each follower |
| | `matchIndex[]` | The index up to which each follower has confirmed replication |

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

```mermaid
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

| | Raft | Multi-Paxos |
|---|---|---|
| Leader Election | Independent sub-problem, driven by random timeouts | Coupled with replication |
| Log | Continuous indices, no gaps allowed | Arbitrary indices, gaps allowed |
| Learning committed values | Possessed upon election (guaranteed by voting rules) | Requires catching up on old values after election |
| Membership change | Joint consensus / single-node change | Usually relies on external mechanisms |
| Understandability | Clearly decomposed into 3 sub-problems | Fully coupled, requires holistic understanding |

The original form and derivation of Paxos can be found in [Paxos](/distributed-systems/02-consensus-protocols/02-Paxos.md); engineering trade-offs of production systems like etcd/TiKV built on Raft are discussed in [Real Systems](/distributed-systems/02-consensus-protocols/03-consensus-in-practice.md); why consensus cannot avoid majority quorums and CAP constraints is covered in [CAP and Consistency Models](/distributed-systems/01-basic-theory/01-cap-and-consistency-models.md).

## 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*