The Raft Consensus Algorithm

Raft (“In Search of an Understandable Consensus Algorithm” by Diego Ongaro and John Ousterhout) is a consensus algorithm for managing a replicated log across a cluster of servers. Its main design goal isn’t novelty — it’s understandability. Paxos works, but it’s notoriously hard to reason about and implement correctly; Raft aims to be functionally equivalent while being much easier to teach, learn, and build on.

The Problem

Distributed systems need to agree on a single sequence of operations (a replicated log) even when servers crash or messages are delayed. Paxos is the classical solution, but it intermingles leader election with log agreement in a way that makes the full algorithm difficult to follow, and most real-world systems end up building ad hoc, under-specified extensions on top of it (multi-Paxos) to make it practical.

Core Design: Decomposition

Raft’s key move is splitting consensus into three largely independent subproblems:

1. Leader election — choosing one server to coordinate the log
2. Log replication — the leader accepts client entries and copies them to followers
3. Safety — ensuring no two servers apply conflicting entries at the same log position

Every server is always in one of three states: follower, candidate, or leader. Time is divided into terms (monotonically increasing numbers), and at most one leader exists per term.

Leader Election

Followers expect periodic heartbeats from the leader. If a follower hears nothing within a randomized election timeout, it becomes a candidate, increments the term, votes for itself, and requests votes from peers. A candidate that gets a majority becomes leader. Randomized timeouts are the trick that keeps split votes rare and self-resolving without extra coordination.

Log Replication

Clients send commands to the leader, which appends them to its own log and replicates them via AppendEntries RPCs. Once an entry is stored on a majority of servers, the leader considers it committed and applies it to its state machine; followers apply committed entries in the same order. This gives the standard replicated state machine guarantee: as long as commands are deterministic, every server ends up in the same state.

Safety

Raft’s safety guarantees rest on a few simple rules rather than Paxos-style quorum reasoning:

• Election restriction: a candidate can only win votes if its log is at least as up-to-date as the voter’s — this guarantees leaders always hold all previously committed entries.
• Log Matching Property: if two logs contain an entry with the same index and term, all preceding entries are identical, enforced by consistency checks in AppendEntries.
• State Machine Safety: once an entry is applied at a given log index, no other server will ever apply a different entry at that index.

Together these avoid the need to reconcile divergent leader histories after the fact — the rules simply prevent a stale leader from being elected.

Membership Changes

Because a naive switch from one cluster configuration to another can create a window where two disjoint majorities both think they’re authoritative, Raft uses joint consensus: the cluster transitions through a combined old+new configuration where decisions require majorities from both the old and new sets of servers before the new configuration is finalized alone.

Log Compaction

Logs would grow forever without bound, so servers periodically write a snapshot of the full state machine state and discard log entries covered by it. Followers that fall too far behind can receive the snapshot directly (InstallSnapshot RPC) instead of replaying the entire history.

Raft vs. Paxos

Paxos treats leader election and log agreement as intertwined; Raft deliberately separates them and layers strong constraints (elect only from up-to-date logs, strict log matching) so that once a leader is elected, replication becomes close to trivial. The paper backs the “understandability” claim with a user study: subjects who learned Raft scored significantly better and found it easier to explain than subjects who learned Paxos, given comparable teaching materials.

Bottom Line

Raft achieves the same fault tolerance and performance characteristics as multi-Paxos but organizes the problem so each piece — election, replication, safety, membership changes, compaction — can be understood (and implemented) mostly in isolation. That decomposition is why it became the default consensus algorithm for new systems (etcd, Consul, CockroachDB, TiKV) rather than Paxos.

Links: Paper (PDF) · raft.github.io