Raft

Raft solves the replicated state machine problem: keep an identical, ordered log of commands on a cluster of servers so that the system keeps working — and never disagrees with itself — while a minority of servers are down. It matches the fault-tolerance and performance envelope of Multi-Paxos, but its explicit design goal was understandability: the algorithm decomposes into leader election, log replication, and safety, so each piece can be reasoned about (mostly) on its own.

The problem, and the understandability stance #

Consensus was solved long before Raft — Paxos had been canonical since the 1990s. Building it was not: single-decree Paxos is subtle, Multi-Paxos (the version you actually deploy) is under-specified in the literature, and production systems like Chubby ended up with protocols that were merely "Paxos-like". Ongaro and Ousterhout's 2014 paper made understandability a first-class design criterion, validated with a user study in which students learned Raft measurably better than Paxos.

Two design choices do most of the work. First, strong leadership: log entries flow only from leader to followers, never sideways, which removes whole classes of interleavings from the state space. Second, problem decomposition: elections decide who may write, replication decides how entries spread, and a small set of safety rules guarantees the pieces compose. A cluster of $2f+1$ servers tolerates $f$ failures — 5 nodes survive 2 crashes — because every decision needs only a majority (quorum), and any two majorities intersect.

Leader election #

Every server is in one of three states: follower, candidate, or leader. Time is divided into terms, numbered with consecutive integers that only ever increase. Each term begins with an election; at most one leader can win a given term. Terms act as a logical clock: every RPC carries the sender's term, and any server that sees a higher term than its own immediately adopts it and reverts to follower. A server that receives an RPC with a stale term rejects it.

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: election timeout
    Candidate --> Candidate: split vote, new timeout
    Candidate --> Leader: majority of votes
    Candidate --> Follower: sees leader or higher term
    Leader --> Follower: sees higher term

Followers stay passive as long as they receive heartbeats (empty AppendEntries RPCs) from a leader. If a follower hears nothing for an election timeout — randomized per server, e.g. 150–300 ms in the paper — it assumes the leader is dead, increments its term, becomes a candidate, votes for itself, and sends RequestVote RPCs to everyone. Three outcomes are possible: it collects a majority and becomes leader; it receives an AppendEntries from a legitimate leader with term at least its own and steps down; or the vote splits, and each candidate times out again with a fresh random timeout and retries in a higher term. Each server grants at most one vote per term, first-come-first-served, and persists that vote before answering — that persistence is what makes "one leader per term" survive crashes.

Detecting a dead leader by timeout is the standard trade of failure detection: shorter timeouts mean faster failover but more spurious elections on a jittery network.

Log replication #

Once elected, the leader services all client writes. Each command is appended to the leader's log as an entry carrying the command, the leader's current term, and an index. The leader then pushes the entry to followers with AppendEntries RPCs and waits for a majority before considering it committed.

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: set x=5
    L->>L: append (term 3, index 8)
    L->>F1: AppendEntries(prevIndex 7, prevTerm 3)
    L->>F2: AppendEntries(prevIndex 7, prevTerm 3)
    F1-->>L: success
    Note over L: on majority (2 of 3) commitIndex = 8
    L->>L: apply x=5 to state machine
    L-->>C: ok
    L->>F2: next AppendEntries carries leaderCommit 8
    F2-->>L: success, follower applies x=5

Consistency between logs is enforced by a check built into every AppendEntries: the RPC carries the index and term of the entry immediately preceding the new ones (prevLogIndex, prevLogTerm), and the follower rejects the call if its own log has no matching entry there. This induction maintains the Log Matching Property: if two logs contain an entry with the same index and term, the entries are identical and so are all preceding entries. On rejection the leader decrements its nextIndex for that follower and retries, walking back until the logs agree, then overwrites the follower's divergent suffix (uncommitted junk from a deposed leader). Leaders never overwrite or delete their own entries — they only append.

Safety #

Replication alone doesn't make the system safe — elections could pick a server whose log is missing committed entries. Raft closes this with the election restriction: a server grants its vote only if the candidate's log is at least as up-to-date as its own. "Up-to-date" compares the last entries: higher last term wins; if the last terms are equal, the longer log wins. Since a committed entry sits on a majority, and winning requires a majority of votes, the two sets must intersect — at least one voter has the entry and will refuse any candidate who lacks it. This yields the Leader Completeness Property: whoever wins term $t$ holds every entry committed in terms $< t$. New leaders never need to "catch up" on committed data, and consequently never overwrite committed entries.

There is one more subtlety, the famous Figure 8 scenario of the paper:

One implementation detail is also load-bearing for safety: currentTerm, votedFor, and the log must be fsynced to stable storage before answering any RPC. Skip that and a restarted server can vote twice in one term, silently breaking the quorum-intersection argument.

Membership changes #

Switching the cluster from configuration $C_{old}$ to $C_{new}$ in one atomic step is unsafe: during the switch, $C_{old}$ and $C_{new}$ could each independently elect a leader for the same term from disjoint majorities. The paper's answer is joint consensus: first commit a transitional configuration $C_{old,new}$ in which every election and commit requires separate majorities from both configurations, then commit $C_{new}$. Ongaro's thesis replaces this with the simpler single-server change: add or remove one server at a time, so old and new majorities overlap by construction and no joint phase is needed. Most production implementations (etcd included) took the single-server route; TiKV kept joint consensus for batch changes. Configuration entries take effect when appended, not when committed — one of several subtleties that make the thesis, not the paper, the reference for implementers.

What Raft costs in practice #

Everything goes through one node. Every write costs a disk fsync on the leader plus one round trip to a majority, and the leader carries the full replication fan-out, so per-group write throughput is bounded by a single machine — CockroachDB and TiKV shard into many Raft groups precisely to spread leadership. During a leader failure, writes stall for the full detection-plus-election window: etcd's default election timeout is 1 s, so failover means roughly a second of write unavailability, landing squarely in your p99.9. Compared to leader-follower replication without consensus, you are paying quorum latency on every write to make failover safe and automatic instead of fast and hazardous.

The strictly sequential log is also a real constraint: entry $n{+}1$ cannot commit before entry $n$, so one slow follower round head-of-line-blocks everything behind it. Multi-Paxos permits out-of-order slot commits; Raft deliberately traded that flexibility away for a protocol people can implement correctly.

Where you will meet Raft: etcd (the default store behind Kubernetes control planes), Consul, CockroachDB, TiKV, RabbitMQ quorum queues, Kafka's KRaft mode. When one of these clusters loses quorum, nothing is broken — it is refusing writes by design, because a minority that accepted writes could never prove they survived.