Master Raft in 10 Minutes: A Clear Guide to Consensus Algorithms

Consensus Algorithms Overview

In a distributed system a consensus algorithm enables a set of nodes to agree on a single value, command sequence, or decision without relying on an external coordinator. This differs from consistency in ACID transactions, which only guarantees that a transaction moves the system from one valid state to another.

The primary purpose of consensus is to allow replicas to maintain a replicated state machine : if all nodes start from the same initial state and apply the same ordered commands, they will reach the same final state. Consensus therefore provides the ordering and leader‑selection mechanisms required for high‑availability replication.

Raft: An Understandable Consensus Algorithm

Raft was designed to be easier to understand than Paxos by decomposing consensus into three independent sub‑problems and by limiting the state space to three node roles.

State Simplification and Terms

Each server is always in exactly one of three states: leader , follower or candidate . Time is divided into terms , identified by monotonically increasing integers. A term begins with an election; at most one leader may exist in a given term. If an election fails to produce a leader, the term ends without a leader and a new term starts after a short timeout.

RPC Mechanism

RequestVote RPC : Sent by a candidate during an election to ask other servers for their vote.

AppendEntries RPC : Sent by the leader to replicate log entries and to act as a heartbeat.

Leader Election

Leaders periodically send AppendEntries heartbeats. If a follower does not receive a heartbeat within its election timeout, it increments its current term, transitions to candidate , votes for itself, and issues RequestVote to all other servers.

Possible outcomes of an election:

The candidate receives votes from a majority of servers → becomes the new leader and starts sending heartbeats.

Another server wins the election → the candidate reverts to follower upon receiving the new leader’s heartbeat.

No candidate obtains a majority → each candidate waits a random timeout, increments its term again, and starts a new election.

Log Replication

Once a leader is established, client commands are appended to the leader’s log as new entries. The leader issues AppendEntries RPCs to all followers, including the previous log index and term for consistency checking.

If a follower’s log does not contain the previous entry, it rejects the RPC; the leader then backs up to the first missing entry and retries, ensuring the follower’s log becomes a prefix of the leader’s log.

The leader retries failed RPCs until a majority of followers have stored the entry. When a majority acknowledges, the entry is considered committed; the leader applies it to its state machine and returns the result to the client.

If a follower crashes and later recovers, the consistency check forces it to receive any missing entries before it can accept new ones.

If the current leader crashes before committing some of its entries, a new leader is elected. The new leader may overwrite conflicting uncommitted entries on followers, because only entries that have been committed on a majority are guaranteed to survive.

Safety Guarantees

Raft enforces two key safety properties:

Only a leader that contains all entries committed in previous terms may be elected. A server votes for a candidate only if the candidate’s log is at least as up‑to‑date as its own (i.e., the candidate’s last term is greater, or the terms are equal and the last index is greater).

Once an entry is committed (replicated on a majority), it is never lost: any future leader must contain that entry because it would not have received a majority otherwise.

These rules guarantee that all servers apply the same sequence of commands, preserving the replicated state machine invariant.