Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 3 · Lesson 16 · 6 min read

Raft Consensus Algorithm Explained

On this page
  1. Why Raft was designed
  2. Leader election, log replication and commit
  3. Raft's safety rules
  4. Raft's costs and limits
  5. Linearizable reads: ReadIndex and leases
  6. Changing cluster membership
  7. Pre-vote: stopping a rejoining node from disrupting the leader
  8. See Raft in action
  9. Check yourself

Why Raft was designed

Paxos is correct and famously hard to implement: the papers describe single-value agreement, and the parts real systems need (a log, leaders, membership changes) were left to practitioners, who each filled them in differently. Diego Ongaro and John Ousterhout designed Raft (2014) to make those parts explicit. It provides the same guarantees as Multi-Paxos and is now the default choice: etcd, Consul, CockroachDB, TiKV, RabbitMQ quorum queues, MongoDB's replication protocol (a Raft variant) and Kafka's KRaft all use it.

Leader election, log replication and commit

1. Leader election. Time is divided into terms, each with at most one leader. Nodes are followers, candidates or the leader. A follower that hears no heartbeat within its randomized election timeout (for example 150 to 300 ms) increments the term, becomes a candidate and requests votes. Each node votes for at most one candidate per term, and only for a candidate whose log is at least as up to date as its own. A majority of votes wins. Randomized timeouts make split votes rare (Day 17).

2. Log replication. Clients send commands to the leader. The leader appends each to its log and sends AppendEntries to followers, including the index and term of the entry just before the new ones. A follower accepts only if its log matches at that point; otherwise it rejects, and the leader backs up and resends older entries until the logs match. This log matching property keeps logs identical up to any agreed point.

3. Commit. An entry is committed once stored on a majority. The leader then applies it to its state machine, replies to the client, and tells followers the new commit index so they apply it too.

Raft's leader appends client commands to its log, replicates them with AppendEntries, and commits once a majority has stored them; elections pick only candidates with up-to-date logs.
Raft's leader appends client commands to its log, replicates them with AppendEntries, and commits once a majority has stored them; elections pick only candidates with up-to-date logs.

Raft's safety rules

  • Election restriction: a candidate can't win unless its log contains every committed entry, because voters refuse candidates with older logs, and any majority of voters includes a node with each committed entry. So a new leader never loses committed data.
  • Leaders never overwrite their own log; followers' conflicting, uncommitted entries are overwritten by the leader's.
  • A leader only counts replicas to commit entries from its own term; older entries are committed indirectly. (This subtle rule closes a corner case where an entry could otherwise be committed and later lost.)

The corner case, from the Raft paper, with five servers. S1 leads in term 2, copies entry X to S2, and crashes. S5 wins term 3 with votes from S3 and S4, writes a different entry Y at the same index, and crashes before copying it. S1 comes back, leads term 4, and copies X to S3, so X now sits on a majority (S1, S2, S3). If S1 counted that as committed and then crashed, S5 could still win an election: its last entry is from term 3, newer than X's term 2, so S2, S3 and S4 would all vote for it, and it would overwrite X with Y everywhere. So S1 waits until an entry from its own term 4 reaches a majority. Then no server without that entry can win, and X is committed along with it.

Raft's costs and limits

  • Every write needs a round trip to a majority: low latency within a region, noticeable across regions.
  • Throughput is limited by one leader; systems scale by running many Raft groups, one per data range (CockroachDB, TiKV) or per partition.
  • During a partition, the minority side can't elect a leader or commit: Raft is CP (Day 5).
  • Linearizable reads need care: the leader must confirm it's still leader (a round of heartbeats or a lease) before answering, or a deposed leader could serve stale data.

Linearizable reads: ReadIndex and leases

A leader can't simply answer reads from its own state: it may have been deposed a moment ago without knowing it. Two standard fixes:

  • ReadIndex: the leader notes its current commit index, sends a round of heartbeats and waits for a majority to answer (proving it's still leader), waits until it has applied up to that index, then answers. That's one round trip per batch of reads, but no log write. etcd serves linearizable reads this way by default.
  • Lease reads: the leader skips the round trip, reasoning that no other leader can be elected until an election timeout has passed since a majority last acknowledged it. Faster, but it trusts clocks to run at roughly the same rate (Day 3): a long pause or a fast clock breaks it.

Changing cluster membership

Moving from 3 servers to 5 in one step is unsafe. During the switch, some servers use the old configuration and some the new, and a majority of the old (2 of 3) and a majority of the new (3 of 5) needn't overlap, so two leaders could win the same term. Raft offers two fixes:

  • One server at a time: add or remove a single server per change. Any majority of the old configuration and any majority of the new one then share at least one server. Most implementations do this.
  • Joint consensus: a transitional configuration in which every decision needs a majority of the old servers and a majority of the new ones, then a switch to the new configuration alone.

etcd also adds a new member as a non-voting learner first, so it can copy the log without counting toward any majority, and promotes it once it has caught up. The consensus course's lesson on membership changes goes deeper, including snapshots.

Pre-vote: stopping a rejoining node from disrupting the leader

A server cut off by a partition keeps timing out and starting elections, raising its term each time. When the partition heals, its high term makes the healthy leader step down, and the cluster holds a needless election. With pre-vote, a would-be candidate first asks the others whether they'd vote for it, without raising its term. Servers that still hear from a leader say no, so the isolated server never disrupts anything. etcd turns pre-vote on by default, and CockroachDB uses it too.

See Raft in action

The Raft website (raft.github.io) has an interactive visualization: kill the leader, partition nodes, and watch terms, votes and logs change. It's the fastest way to build intuition.

Check yourself

When the leader has stored it on a majority of the cluster, including itself, for an entry from the leader's current term. At that point it can't be lost by any future election, so the leader applies it to its state machine and acknowledges the client.

Voters only vote for candidates whose logs are at least as up to date as theirs, and every majority contains a node holding each committed entry.

They split data into ranges or partitions, each replicated by its own Raft group with its own leader, as CockroachDB, TiKV and YugabyteDB do. Writes to different ranges proceed in parallel on different leaders.

A majority of the old configuration and a majority of the new one may not overlap, so two leaders could be elected in the same term; changing one server at a time or using joint consensus prevents it.