Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 36 ยท Consensus and Coordination

Raft Step by Step

Learn Raft: terms, leader election, log replication, the commitment rule and safety. Run a small Raft cluster in your browser, including a leader crash.

Paxos proves that agreement is possible, but it is famously hard to turn into a working system. Raft was designed in 2013 to give the same guarantees in a form people can actually understand and implement. It splits the problem into three parts: electing a leader, replicating a log from that leader, and keeping the whole thing safe. Systems such as etcd, Consul and many databases use it.

Raft keeps a replicated log: an ordered list of commands that every server applies in the same order, so every server ends up in the same state. In this lesson you will build a small Raft simulation and watch a leader get elected, replicate commands, crash, and be replaced.

The big picture

Three roles

Leader Takes client commands and replicates them.
Follower Passive. Answers the leader and candidates.
Candidate A follower asking for votes.

Exactly one leader per term, at most.

1 / 2

Time is divided into terms, numbered 1, 2, 3, and so on. Each term starts with an election. If a candidate wins, it leads for the rest of the term. If the vote splits, the term ends with no leader and a new term begins. Terms act as a logical clock (see leader election): any server that sees a higher term updates its own and becomes a follower.

Leader election

Followers expect regular heartbeats from the leader. Each follower has an election timeout, chosen at random (for example between 150 and 300 ms) so that servers rarely time out together. If a follower hears nothing before the timeout, it:

  1. increments its term and becomes a candidate,
  2. votes for itself,
  3. sends RequestVote to everyone else.

A server grants at most one vote per term, first come first served, and only if the candidate's log is at least as up to date as its own. Up to date means: compare the term of the last log entry first, and if they are equal, the longer log wins. A candidate that collects votes from a majority becomes leader and starts sending heartbeats immediately.

The up-to-date rule is what keeps committed entries safe. A committed entry exists on a majority, and any winning candidate also needs a majority, so the two majorities overlap. At least one voter has the entry and refuses to vote for a candidate whose log lacks it.

Log replication

The leader appends a client command to its own log, then sends AppendEntries to the followers. Every AppendEntries also includes the index and term of the entry just before the new ones. A follower accepts only if its own log has a matching entry at that spot. If not, it refuses, and the leader backs up one entry and retries until the logs match, then overwrites whatever the follower had after that point. This log matching check guarantees that if two logs agree on one entry, they agree on everything before it.

An entry is committed once the leader that created it has stored it on a majority of servers. The leader tells followers the commit index with the next heartbeat, and each server then applies committed entries to its state machine.

A Raft simulation

The cluster below has three servers with fixed election timeouts (4, 6 and 8 ticks) so every run is the same. A tick moves time forward. Real Raft sends messages over a network; here, calls between objects stand in for messages, and a crashed node simply doesn't answer. Read the code once, then follow the story in the output: election, two client writes, leader crash, new election, a third write, and the old leader coming back.

Python A three-node Raft cluster survives a leader crash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Walk through the output:

  1. Election. Node 1 has the shortest timeout, so it times out first, starts term 1 and wins all three votes.
  2. Replication. The leader appends x=1 and y=2, sends them out, and sees a majority has stored them, so its commit index becomes 2. Followers learn this on a heartbeat.
  3. Crash. Node 1 stops. Node 2 has the next shortest timeout and wins term 2 with votes from itself and node 3. Two out of three is a majority, so the cluster keeps working with one server down. A new entry, z=3, commits in term 2.
  4. Recovery. Node 1 returns still thinking it is in term 1. The first AppendEntries from node 2 carries a higher term, so node 1 becomes a follower, gets the missing entry and catches up.

The mermaid diagram below shows the role changes every server goes through.

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: election timeout
    Candidate --> Leader: majority of votes
    Candidate --> Candidate: split vote and new term
    Candidate --> Follower: sees leader or higher term
    Leader --> Follower: sees higher term

A server only becomes leader through a candidate round, and any higher term sends it back to follower.

The commitment rule and safety

Raft has one subtle rule that is worth a closer look. A leader may only count replicas to commit entries from its own current term. Older entries are committed indirectly: once an entry from the current term is committed, everything before it in the log is committed too.

Why? Without the rule, an old entry can sit on a majority and still get overwritten by a later leader whose log is "more up to date". Counting only current-term entries closes that hole. The next example calculates the commit index and checks the vote rule on a few cases.

Python The commit index and the vote rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the last two commit lines. When only two of five servers hold entry 4, nothing new commits. When entry 3 (from term 2) is on a majority but the leader has nothing from term 3 yet, the commit index stays at 0. Real leaders solve that by appending a no-op entry at the start of their term, which commits the older entries indirectly.

For the votes, a candidate with a longer log (B, with 9 entries) is still refused because its last entry is from an older term (2). A shorter log from the same last term (C) is refused too. Raft compares the term of the last entry before the length.

Practical points

  • A cluster of 2f + 1 servers tolerates f failures: three servers survive one, five survive two.
  • Randomized election timeouts, longer than the network round trip, make split votes rare.
  • Changing the membership safely needs extra care (Raft uses a joint-consensus or single-server-at-a-time approach).
  • Logs grow forever without snapshots: periodically a server saves the state and discards the log up to that point.
  • Reads can be stale unless they go through the leader and are confirmed with a heartbeat round or a lease. See consistency models.

You will put all of this together in Project: A Mini Raft Cluster.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does each Raft server use a randomized election timeout?

    If all followers timed out simultaneously, they would all become candidates and split the votes. Randomization usually lets one candidate win quickly.
  2. 2. When may a server vote for a candidate?

    One vote per term and the up-to-date check together ensure at most one leader per term and that a new leader holds every committed entry.
  3. 3. When is a log entry committed?

    A majority copy guarantees that any future winner of an election has the entry, so it is safe to apply.
  4. 4. A leader in term 4 sees an old entry from term 2 on a majority of servers. Why can't it commit that entry just by counting replicas?

    Raft commits old entries only indirectly, once an entry from the current term is committed after them. That closes a subtle safety hole.

Summary

  • Raft keeps a replicated log using terms, a single leader per term, and majority votes.
  • Elections use randomized timeouts; a vote is granted once per term and only to a candidate with an up-to-date log.
  • Log replication uses AppendEntries with a previous-entry consistency check, and the leader repairs diverging followers.
  • An entry is committed when a leader of the current term has stored it on a majority; older entries commit indirectly.
  • Majority quorums let a cluster of 2f + 1 servers survive f crashes without losing committed data.

Next: Distributed Locks, Leases and Fencing.