3.1 Raft: Election, Log Replication, and Commit

Consensus enables multiple nodes to reach a mutually consistent decision on a replicated log, even in the face of partial failures or message delays. Starting from the same initial state, replicas applying deterministic commands in the same order reach the same state. If a command depends on time or randomness, record the chosen value in the log. Independent dice rolls on each replica defeat even a beautifully ordered log.

Raft organizes nodes into Follower, Candidate, and Leader roles, and uses monotonically increasing terms to mark leadership periods.

Majorities Provide Intersecting Sets

A cluster composed of 2f + 1 voting members can tolerate up to f unavailable members if the remaining members can communicate and keep processing requests. For example, a 5-member cluster requires 3 votes and can tolerate 2 failures.

Increasing membership from 3 to 4 still tolerates only one unavailable member. It requires 3 votes and adds replication cost. The semantics of witnesses, learners, and non-voting replicas depend on the specific implementation and cannot be determined solely by counting processes.

State and Persistent Data

Each node must maintain at least the following:

• currentTerm, votedFor: changes are persisted before sending RPC responses or messages that depend on them;
• Log entries: each contains an index, term, and command, and must be durable before successful replication is acknowledged;
• commitIndex, lastApplied;
• the leader maintains nextIndex and matchIndex for each follower.

Progress such as commitIndex can be reconstructed according to the protocol. If the state machine itself is durable, lastApplied must recover consistently with its data to avoid applying an increment twice. The state machine can only apply committed entries in index order. After a crash recovery, previously persisted votes and logs must not be lost, or safety may be compromised.

Leader Election

When a Follower does not receive valid Leader communication within a randomized election timeout:

1. Increment its term and transition to Candidate state;
2. Persist the new term and a vote for itself;
3. Send RequestVote to all other members;
4. Become Leader once it obtains a majority of votes for the current term;
5. Transition back to Follower state if it receives an RPC with a higher term.

Each member can cast at most one vote per term. A vote is granted only if the Candidate’s log is at least as up-to-date as the voter’s: first compare the term of the last log entry, then the index. A last entry at (term=5, index=8) is newer than one at (term=4, index=20); a longer log does not necessarily win. A Candidate must also return to Follower on a valid Leader’s AppendEntries for the current term.

Randomized election timeouts reduce the likelihood of ties, but do not guarantee that ties will never occur. After network recovery, a new election typically results in a Leader being elected. During prolonged partitioning or extreme network fluctuations, the system may remain without a Leader for an extended period, yet still maintain safety.

AppendEntries copies and verifies the prefix simultaneously

After receiving client commands, the Leader first appends the command to its local log and then sends it to the Followers:

term
leaderId
prevLogIndex
prevLogTerm
entries[]
leaderCommit

A Follower first rejects an outdated term, then checks prevLogIndex/prevLogTerm. If that prefix does not match, it rejects the request and the Leader moves nextIndex back to find a common prefix. Once the prefix matches, the Follower truncates its uncommitted suffix only when an incoming entry conflicts with the local term at the same index, starting at that conflicting entry. It then appends missing entries. Matching entries are retained, as is a suffix that the request does not cover.

AppendEntries with empty entries also carries heartbeats and commitIndex updates, and still checks the prefix. The commit position can advance only to the smaller of leaderCommit and the last index confirmed to match by this request. It cannot pass the verified prefix.

Suppose a Follower already has indexes 1–5 and receives a delayed heartbeat confirming only through index 3. That heartbeat must neither delete 4 and 5 nor commit those unverified entries. A late message is no reason to shorten the log.

Key Limitations of Commit Rules

The leader can advance entries from the current term to committed status after a majority has durably stored them. Once an entry from the current term is committed, all prior log entries in its prefix are also considered committed.

An entry from an older term cannot be committed merely because it now exists on a majority. Committing a current-term entry indirectly commits the preceding entries.

Consider five nodes A–E. A writes x in term 2, only on itself. E later wins term 3 and writes a different value y at the same index, again only on itself. A wins term 4 and copies its old-term x to A, B, and C: apparently a majority. But if A becomes unreachable, E’s last term 3 is still newer than C’s term 2. E can win votes from C, D, and E and overwrite x. That earlier majority was insufficient to establish commitment. If A first replicates and commits a term-4 entry on a majority, the election freshness check prevents E from winning.

Client command
  → Leader append
  → Majority persistence
  → Leader commit
  → State machine apply
  → Respond to client

The timing of responding to clients must align with both persistence and state machine semantics. If the leader crashes before responding, the result becomes indeterminate, and the client must rely on a request ID for deduplication.

Log Safety Comes from Election Limits and Majority Intersections

Committed entries, or snapshots containing their effects, are retained by a majority. A future leader must receive votes from another majority, and these two majorities must intersect at least one node; the candidate log's newness vs. oldness comparison prevents nodes lacking a committed prefix from winning.

Intuition helps with understanding, but production implementations cannot rely solely on intuition to skip fsync, term persistence, conflict resolution, or recovery testing.

The next lesson covers linearizable reads, member changes, snapshots, and Raft's operational boundaries.

References

• Ongaro, Ousterhout, In Search of an Understandable Consensus Algorithm
• Raft Visualization