Understanding Raft Consensus

Distributed systems have a fundamental problem: how do you get a collection of machines to agree on something when any of them might crash, messages might be delayed, and you can’t tell the difference between a slow node and a dead one? This is the consensus problem, and getting it right is what separates a database that stays consistent under failure from one that silently loses or corrupts data.

Raft is a consensus algorithm published by Diego Ongaro and John Ousterhout in 2014. Their explicit goal was understandability. Paxos, the algorithm that had dominated the field for two decades, is notoriously difficult to reason about and even harder to implement correctly. Raft covers the same ground but structures itself around three mostly-independent subproblems: leader election, log replication, and safety. Tackling them separately makes both the algorithm and its correctness argument much easier to follow.

What consensus actually requires

The problem is deceptively simple to state. You have a cluster of $n$ servers. Clients send them commands. The servers must all execute those commands in the same order, so that every server ends up in the same state, even if some servers crash and restart mid-stream.

Formally, a consensus algorithm must satisfy three properties:

• Safety: all servers that decide on a value decide on the same value, and only values that were actually proposed can be chosen
• Liveness: the system eventually makes progress if enough servers are reachable (Raft requires a majority)
• Fault tolerance: the system continues operating correctly through the failure of up to $\lfloor (n-1)/2 \rfloor$ servers

The liveness constraint is worth dwelling on. Raft requires a quorum (a majority of servers) to make progress. With 5 servers you can tolerate 2 failures; with 3 servers you can tolerate 1. You cannot get fault tolerance without paying some cost in availability, and Raft accepts that: a partition that isolates more than half the cluster will stall the system rather than risk inconsistency.

Terms and the replicated log

Raft organises time into terms, each identified by a monotonically increasing integer. A new term begins whenever an election is triggered. Terms act as a logical clock: any message carrying a term number lower than a server’s current term is stale and ignored. This is how Raft detects and discards messages from old leaders that have been partitioned away and haven’t yet noticed.

The shared state that Raft maintains is a replicated log: an ordered sequence of entries, each containing a command and the term in which it was appended. Once an entry has been committed, meaning replicated to a majority of servers, it is guaranteed to appear in the log of any future leader, and will therefore be applied by every server in the same position. The log is the source of truth; the server state machine is derived from it.

Leader election

At any given moment, each server is in one of three states: leader, follower, or candidate. Normal operation has exactly one leader; followers are passive and simply respond to requests from the leader and candidates.

Followers expect to receive periodic heartbeats from the leader (empty AppendEntries RPCs). Each follower has an election timeout, randomly chosen from a window (typically 150–300ms). If this timeout elapses without a heartbeat, the follower concludes that the leader has failed, increments its term, converts to a candidate, and starts an election.

As a candidate, the server votes for itself and sends RequestVote RPCs to all other servers. A server grants its vote if:

1. It has not already voted in this term, and
2. The candidate’s log is at least as up-to-date as its own (more on this below)

If the candidate collects votes from a majority of servers, it becomes leader and immediately begins sending heartbeats to suppress further elections. If no candidate achieves a majority (perhaps two candidates split the vote), the term ends without a winner and a new election begins after another randomised timeout.

The randomised timeouts are the key mechanism for avoiding split votes. If all servers had identical timeouts, they would all trigger elections simultaneously on every leader failure. By spreading the timeouts randomly, the first server to time out usually wins the election before others have even started.

Log replication

Once elected, the leader handles all client requests. When it receives a command, it appends the entry to its own log and then sends AppendEntries RPCs to every follower in parallel, asking them to append the same entry.

The AppendEntries RPC includes a consistency check: along with the new entry, the leader sends the index and term of the entry immediately preceding it. A follower only accepts the new entry if its own log matches at that position. If it doesn’t match, the follower rejects the request and the leader retries, working back through the log until it finds the point where the logs agree, then replaying entries forward from there. This guarantees the Log Matching Property: if two entries in different logs have the same index and term, then all preceding entries are identical.

Once the leader has received acknowledgement from a majority of servers, the entry is committed. The leader advances its commit index and notifies followers in subsequent AppendEntries messages. Followers apply committed entries to their state machines in order.

This means a client only gets a response once the entry is safely replicated to a majority. If the leader crashes after committing but before responding to the client, the client will retry and the new leader will have the entry, so it is applied exactly once. (Clients need to handle idempotency; Raft itself does not.)

Safety: why committed entries are never lost

The most important property Raft needs to guarantee is that a committed log entry is never overwritten or lost by a subsequent leader. This is enforced by the election restriction.

A candidate can only win an election if its log is at least as up-to-date as the logs of a majority of servers. “Up-to-date” is defined precisely: compare the term of the last entry first; whichever is higher wins. If the last entries have the same term, whichever log is longer wins.

Why does this suffice? Suppose entry $e$ is committed in term $t$, meaning a majority $Q_1$ of servers acknowledged it. Any future leader must have won a majority $Q_2$. Since $|Q_1| + |Q_2| > n$, the two majorities overlap in at least one server. That server has entry $e$ in its log. For the new candidate to beat it in the up-to-date comparison, the candidate’s log must be at least as current, which means it also has $e$. So any server that wins an election must already have all committed entries.

This is the core of Raft’s safety argument: committed entries always survive leadership changes because you cannot win an election without first having them.

Cluster membership changes

A practical Raft deployment needs to be able to add and remove servers without taking the system offline. This is more subtle than it sounds: if you switch directly from an old configuration to a new one, there is a window where two disjoint majorities are possible, which breaks safety.

Raft handles this with a joint consensus approach. The cluster first transitions into a joint configuration that includes both the old and new sets of servers. During this phase, majorities must be obtained from both groups simultaneously. Once this joint configuration is committed, the cluster transitions to the new configuration alone. At no point can two independent majorities exist.

What Raft doesn’t solve

Raft assumes a crash-fault model: servers fail by stopping. It does not tolerate Byzantine faults: servers that behave arbitrarily, send conflicting messages, or actively lie. A Byzantine server could, for instance, claim to have committed an entry it hasn’t, or vote in multiple elections simultaneously. Handling Byzantine faults requires a different class of algorithms (PBFT, HotStuff, Tendermint, etc.) and typically requires $n \geq 3f + 1$ servers to tolerate $f$ faults, compared with Raft’s $n \geq 2f + 1$.

Raft also says nothing about performance: a single leader handling all writes is a throughput bottleneck at scale. Production systems based on Raft (etcd, CockroachDB, TiKV) layer batching, pipelining, and sometimes multi-Raft sharding on top to work around this.

Why it’s taught

The reason Raft appears in distributed systems courses more often than Paxos does is not that it’s faster or more fault-tolerant. It isn’t, meaningfully. The reason is that when you implement it, you are less likely to accidentally implement something subtly wrong.

Paxos specifies a protocol for agreeing on a single value. Real systems need to agree on a sequence of values, and the extension from single-value Paxos to multi-Paxos is where most of the complexity hides, and where most of the real implementations diverged from the original paper in undocumented ways. Raft was designed as a complete system from the start, with explicit solutions to leader election, log replication, membership changes, and snapshots. The spec is the implementation guide.

Ongaro’s thesis includes a user study in which students who learned Raft significantly outperformed those who learned Paxos on comprehension questions. Whether that advantage persists as engineers gain experience with both is debatable, but as a starting point for understanding distributed consensus, Raft earns its place.