The Raft Consensus Algorithm, Step by Step

Three database nodes accept the same command. One loses power halfway through writing, another cannot reach the network, and the third keeps serving traffic. Which value is now true? More importantly, how can every surviving node eventually make the same decision without an oracle telling it what happened?

That is the problem of consensus. Raft solves it by reducing the system to a replicated log with a strong leader. Clients send commands to the leader; the leader orders them in its log; a majority confirms each durable decision; every node applies committed entries to the same deterministic state machine. The result is not magic availability. It is a precise protocol for preserving one history while machines stop, restart, duplicate messages, and disagree about time.

Raft was designed to be understandable, but “easier than Paxos” does not mean trivial. Its safety comes from several rules working together. Removing an apparently conservative check, such as comparing candidate logs or committing only entries from the leader’s current term, can produce histories that no longer agree.

Build the mental model first #

A Raft server is always in one of three roles: follower, candidate, or leader. Normal operation has one leader and the rest followers. A follower that hears nothing for a randomized election timeout becomes a candidate. A candidate that wins a majority becomes leader. Every server persists three pieces of consensus state before replying successfully:

• currentTerm: a monotonically increasing logical era;
• votedFor: the candidate, if any, that received this server’s vote in the term;
• log: ordered entries shaped like (index, term, command).

The term acts like a logical clock. Any message carrying a higher term forces the receiver to update its term and become a follower. Messages from older terms are stale and may be rejected. Volatile state includes commitIndex, the highest entry known to be committed, and lastApplied, the highest entry already executed by the local state machine. A leader additionally tracks nextIndex and matchIndex for every follower.

Consensus requires a quorum, not every node. For a cluster of $N$ voting members, the majority size is

Any two majorities intersect in at least one server. That overlap carries knowledge from one decision to the next. A three-node cluster tolerates one unavailable node; a five-node cluster tolerates two. Adding an even-numbered voter usually increases coordination cost without increasing failure tolerance.

Elect one leader without trusting clocks #

Followers reset their election timer whenever they receive valid AppendEntries from the current leader or grant a vote. Timeouts are randomized, commonly over a range such as 150–300 ms in the original paper’s setting, so followers are unlikely to campaign simultaneously. Production values must reflect actual network and storage latency; copying laboratory numbers into a cross-region deployment invites needless elections.

When a timeout fires, the follower increments currentTerm, becomes candidate, votes for itself, persists those changes, and sends RequestVote to peers. A receiver grants its one vote only if the candidate’s term is current and the candidate’s log is at least as up-to-date as its own. “Up-to-date” compares the term of the final entry first, then its index. Length alone is insufficient because an entry from a newer leader term carries stronger evidence.

The log check is what connects election safety to data safety. A candidate missing a committed entry cannot be more up-to-date than every member of the majority that committed it, so it cannot collect a majority of votes. This is the foundation of leader completeness: every committed entry from an earlier term appears in the logs of later leaders.

Split votes are harmless. Candidates eventually time out, increment the term, and try again with fresh random delays. The system may pause during repeated partitions, but it does not appoint two leaders in the same term. A former leader can continue believing it is leader while isolated; its lower-term messages will be rejected once they reach nodes that advanced.

Replicate and commit the log #

After election, the leader appends each client command locally and sends AppendEntries to followers. Every request names prevLogIndex and prevLogTerm, effectively asking, “Does your history match mine immediately before these new entries?” A follower accepts only when that pair matches. If it finds a conflicting entry at the same index, it deletes that entry and everything after it, then appends the leader’s entries. The leader retries from an earlier nextIndex until the histories meet.

The following TypeScript model omits transport, batching, snapshots, and persistence mechanics, but preserves the important transitions. A real implementation must durably write currentTerm, votedFor, and new log entries before acknowledging them.

import { randomElectionTimeout } from './timers.js';

type Role = 'follower' | 'candidate' | 'leader';

interface Entry<Command> {
  term: number;
  command: Command;
}

interface AppendEntries<Command> {
  term: number;
  leaderId: string;
  prevLogIndex: number;
  prevLogTerm: number;
  entries: ReadonlyArray<Entry<Command>>;
  leaderCommit: number;
}

interface AppendResult {
  term: number;
  success: boolean;
  matchIndex: number;
}

class RaftNode<Command> {
  role: Role = 'follower';
  currentTerm = 0;
  votedFor: string | undefined;
  log: Array<Entry<Command>> = [];
  commitIndex = -1;
  lastApplied = -1;
  electionDeadline = randomElectionTimeout();

  receiveAppend(request: AppendEntries<Command>): AppendResult {
    if (request.term < this.currentTerm) {
      return { term: this.currentTerm, success: false, matchIndex: -1 };
    }

    if (request.term > this.currentTerm) {
      this.currentTerm = request.term;
      this.votedFor = undefined;
    }
    this.role = 'follower';
    this.electionDeadline = randomElectionTimeout();

    if (request.prevLogIndex >= 0) {
      const previous = this.log[request.prevLogIndex];
      if (!previous || previous.term !== request.prevLogTerm) {
        return { term: this.currentTerm, success: false, matchIndex: -1 };
      }
    }

    let targetIndex = request.prevLogIndex + 1;
    for (const incoming of request.entries) {
      const local = this.log[targetIndex];
      if (local && local.term !== incoming.term) {
        this.log.splice(targetIndex);
      }
      if (!this.log[targetIndex]) {
        this.log.push(incoming);
      }
      targetIndex += 1;
    }

    const lastNewIndex = request.prevLogIndex + request.entries.length;
    this.commitIndex = Math.min(
      request.leaderCommit,
      Math.max(request.prevLogIndex, lastNewIndex),
    );

    return {
      term: this.currentTerm,
      success: true,
      matchIndex: lastNewIndex,
    };
  }

  applyCommitted(apply: (command: Command) => void): void {
    while (this.lastApplied < this.commitIndex) {
      this.lastApplied += 1;
      const entry = this.log[this.lastApplied];
      if (!entry) throw new Error('committed entry is missing');
      apply(entry.command);
    }
  }
}

Replication and commitment are different. An entry can exist on several servers yet remain uncommitted. The leader advances commitIndex to an index $k$ only when a majority has replicated through $k$ and log[k].term === currentTerm. Once a current-term entry is committed, preceding entries become committed indirectly, including entries inherited from older terms.

That current-term condition prevents a subtle overwrite scenario after successive leadership changes. Counting replicas alone for an old-term entry can make a leader announce commitment even though a future candidate, legally elected under the log comparison rule, could replace it. The conservative rule closes that gap.

Preserve safety through failures #

Raft deliberately chooses safety over availability when no majority can communicate. In a five-node partition of two and three, the side with three can elect a leader and commit writes; the side with two cannot. A stale leader on the minority side may accept a request temporarily, but it cannot commit it. After healing, AppendEntries from the valid higher-term leader overwrites the stale uncommitted suffix.

Several failure cases are worth tracing explicitly:

• Leader crashes before replication: its local uncommitted entry may disappear when another leader is elected. The client must retry.
• Leader crashes after commitment but before replying: the command survives, but the client cannot know that. Deduplication makes the retry safe.
• Follower restarts: it reloads persistent term, vote, and log, then catches up from the leader. Commit and apply progress can be reconstructed, though snapshot metadata must also be durable.
• Delayed or duplicated RPC: term and index checks make stale messages ineffective; handlers should be idempotent.
• Clock jumps: correctness does not depend on synchronized wall clocks. Timing affects liveness, so a badly paused node can trigger elections without violating committed history.

Linearizable writes follow from the leader and commit rules when client retries are handled. Reads need additional care: a partitioned former leader must not serve stale state as current. Implementations use a quorum-confirmed ReadIndex, or a carefully bounded leader lease based on clock assumptions, before serving linearizable reads. Reading from followers is useful only when the API explicitly permits staleness.

The state machine must also be deterministic. If applying an entry calls the local clock, generates an unseeded random number, or depends on process-specific data, identical logs can produce different states. Put the chosen timestamp, identifier, or other nondeterministic result into the replicated command.

Change membership and compact history #

Long-running logs cannot grow forever. A server periodically serializes the state machine at an included index and term, then discards older log entries. If a follower is too far behind, the leader sends InstallSnapshot instead of replaying the entire history. Snapshot installation must be atomic: a crash must leave either the old valid state or the new valid state, never half of each. Checksums and versioned formats make corruption and upgrades diagnosable.

Changing voters is more dangerous than adding an address to a list. Switching directly from configuration $C_{old}$ to $C_{new}$ can briefly create two disjoint majorities, allowing two leaders. Raft’s joint consensus approach first commits a joint configuration where decisions require majorities of both old and new sets, then commits the new configuration alone. Many libraries expose a simpler single-server-at-a-time variant, but the underlying goal is identical: every decision quorum must overlap safely during transition.

Operationally, membership changes should be serialized, observable, and slow enough for a new voter to catch up before it affects availability. A frequently failing node should be repaired or replaced; automatically ejecting members during a network partition can turn a transient outage into permanent split-brain configuration.

Test the protocol, then understand its limits #

Happy-path unit tests barely exercise consensus. The valuable tests control time and transport: pause nodes, reorder RPCs, duplicate responses, lose acknowledgements, crash immediately before or after durable writes, and restart from persisted bytes. A deterministic simulator can generate thousands of schedules and assert invariants after every event:

• at most one leader exists per term;
• committed entries never change term or command at a given index;
• a server applies entries only in index order and never twice;
• commitIndex and lastApplied never decrease;
• every applied prefix is identical across servers;
• without a quorum, no new entry becomes committed.

Property-based generation and model checking are especially effective because the worst bugs require an unintuitive ordering of ordinary events. Jepsen-style black-box tests complement simulation by checking externally observed histories under real process pauses, disk faults, and partitions. Metrics should expose term changes, election duration, replication lag, commit latency, snapshot progress, and quorum health; logs should include term, index, peer, and RPC outcome.

Raft still has limits. The leader is the write-ordering bottleneck. Large or geographically dispersed clusters pay quorum latency and may churn leadership. Standard Raft does not tolerate malicious members, does not make a nondeterministic state machine safe, and does not provide exactly-once side effects outside the replicated state. Slow disks can destabilize elections because persistence sits on the critical path. Mature implementations therefore batch entries, pipeline replication, apply backpressure, pre-vote before disrupting a healthy term, and transfer leadership before maintenance.

Takeaways #

Raft works because its pieces reinforce one another. Terms reject stale authority. Randomized elections usually produce one candidate, while the log freshness rule prevents an incomplete candidate from winning. AppendEntries repairs divergent suffixes. Majority replication plus the current-term commit rule turns tentative entries into durable decisions. Deterministic application then makes every state machine converge.

When implementing or operating Raft, keep safety and liveness separate. Safety means committed history never changes, regardless of delay. Liveness means the cluster eventually makes progress when a stable majority can communicate. Timeouts, pre-vote, batching, and tuning improve liveness; durable state, quorum intersection, log matching, and commit rules protect safety. The protocol becomes much easier to reason about once every optimization is required to preserve those invariants rather than merely pass the normal-case demo.