Consensus & Raft

What consensus buys you

Consensus solves one problem: get a set of servers to agree on the same ordered sequence of commands, a replicated log, even when servers crash and messages are delayed, dropped, or reordered. Feed that identical log into a deterministic state machine on every node and each node computes the same state and outputs, so the cluster behaves like one reliable machine. That pattern is state machine replication, and it is how etcd, Consul, and CockroachDB keep their metadata alive across crashes.

Raft assumes crash-recovery faults, not Byzantine ones: a node may die and rejoin from stable storage, but no node lies. It stays available while a majority can communicate, so a 5-node cluster tolerates 2 failures, since a quorum is floor(N/2)+1 = 3. Correctness never depends on timing; faulty clocks or slow messages cost availability, never agreement. Paxos solves the same problem with the same majority requirement and normal-case cost; Raft's claim is understandability, reached through a strong-leader design and by splitting the problem into election, replication, and safety.

How a leader gets elected

Every server is a follower, a candidate, or a leader, and there is at most one leader per term. Terms are numbered integers that act as a logical clock: each term opens with an election, every RPC carries the sender's term, and a server that sees a higher term steps down to follower while one that sees a stale term rejects the message. A leader holds authority by sending empty AppendEntries as heartbeats.

A follower that hears no valid RPC within its election timeout increments its term, becomes a candidate, votes for itself, and sends RequestVote RPCs in parallel. Split votes are broken by randomizing the timeout over a fixed interval (150 to 300 ms in the paper) and re-randomizing it each election, so one candidate usually times out first.

Wrong "a candidate wins once a majority of the servers that answered vote for it." Right it needs votes from a majority of the whole cluster for that term, and each server grants at most one vote per term, which keeps a term to a single leader.

How log replication commits an entry

Each log entry holds an index, the term it was created in, and the command. Only the leader takes client writes; a follower redirects the client to it. The leader appends the entry, replicates it with AppendEntries, and once the entry is stored on a majority it is committed: the leader applies it to its state machine, answers the client, and piggybacks the new commit index so followers apply it too, in log order.

Consistency comes from the Log Matching Property: if two logs hold an entry with the same index and term, every earlier entry matches too. Each AppendEntries carries the index and term of the entry immediately before the new ones (prevLogIndex, prevLogTerm), and a follower rejects the request when that slot does not match. On a rejection the leader decrements its nextIndex for that follower and retries, overwriting any conflicting tail until the logs line up. Logs only ever flow from leader to follower, and a leader never overwrites its own entries.

The election restriction on who can become leader

A majority of votes is necessary but not sufficient. Raft's election restriction makes a voter reject any candidate whose log is less up-to-date than its own, and up-to-date has a precise meaning: compare the last entries of the two logs; the higher last term wins, and if the last terms are equal, the longer log wins. The test is the last entry alone, never total log length or the commit index, so a candidate with the longest log still loses if its last entry is from an older term than a voter's. Because a committed entry already sits on a majority and any electing majority overlaps that set, the new leader is guaranteed to hold every committed entry: the Leader Completeness Property, from which State Machine Safety (no two servers apply different commands at one index) follows.

Why a majority does not make an entry committed

A leader cannot treat an entry from a previous term as committed merely because it now sits on a majority. Raft never commits prior-term entries by counting replicas; only an entry from the leader's current term commits by replica count, and once it does, everything beneath it commits indirectly through Log Matching. Figure 8 in the paper shows the trap: an inherited entry can reach a majority and still be overwritten, because a later leader can replace that index.

Wrong "it is on three of five nodes, so it is committed." Right it commits only once a current-term entry above it reaches a majority. A new leader forces the point by committing a blank no-op at the start of its term, which drags the older entries along.

What a linearizable read requires

A read served by the leader is not automatically linearizable. A superseded but still-partitioned leader believes it leads and can answer with data that misses the new leader's writes. Two measures close the gap. The leader must know its true commit index for the term, one more reason for the start-of-term no-op. And it must prove it still leads: the ReadIndex path records the commit index, confirms leadership with a heartbeat round-trip to a majority, then waits until the applied index reaches that recorded index. Committed and applied differ, and the barrier waits on applied. A leader lease skips the round-trip while the heartbeat interval stays shorter than the election timeout, but that assumes bounded clock skew, a timing guarantee rather than a quorum one. etcd exposes this as linearizable versus serializable reads, Consul as consistent, default, and stale.

Changing membership without electing two leaders

You cannot flip every server from the old configuration to the new one at once; during the overlap the cluster could split into two disjoint majorities and elect two leaders in one term. Raft's joint consensus adds a transitional configuration in which elections and commits need separate majorities from both the old and the new set, stored as a log entry that takes effect the moment a server sees it. The leader commits that joint configuration, then the new one, so the two sets never decide independently. Many systems instead change one server at a time, since a single-node delta cannot create two disjoint majorities, and add non-voting learners so a joining node catches up before it counts.