In Search of an Understandable Consensus Algorithm

The problem: everyone needs consensus, nobody could implement it

A great deal of infrastructure comes down to one need: several machines must agree on a sequence of commands and keep agreeing while some of them crash and restart. That is consensus, and by 2013 the field had a complete answer to it in Paxos, Lamport’s algorithm from 1989. It also had a problem. Paxos is famously hard to understand, and the published algorithm covers agreeing on a single value; building a real system that agrees on an entire log required extensions the literature left vague, so every production system, Google’s Chubby, Apache ZooKeeper, filled the gaps differently and nobody could check anyone else’s work.

Diego Ongaro and John Ousterhout set an unusual goal for an algorithm paper. Correctness and performance were required, but the explicit objective was understandability: an engineer should be able to hold the whole algorithm in their head and implement it correctly from the paper. They then tested that claim on 43 students, who scored better on Raft than on Paxos after equivalent lectures.

The idea: elect a leader, let the leader decide

Raft divides time into numbered terms, each beginning with an election. Every node is a follower, a candidate, or a leader, and at most one leader exists per term. The leader alone accepts client commands, appends them to its log, and replicates them to the followers; entries flow in one direction only. A follower that hears nothing from a leader for a randomly chosen interval assumes it is dead, becomes a candidate, and asks the others for votes. The randomness is doing real work: it makes two nodes timing out at once unlikely, so most elections finish in one round.

How it works

Two remote calls carry the whole protocol. RequestVote asks for a vote in a new term and includes the candidate’s last log index and term, which is how voters apply the completeness rule. AppendEntries carries new log entries from the leader, and when empty serves as the heartbeat that keeps followers from timing out. Each AppendEntries names the entry that should precede the new ones; a follower whose log disagrees rejects it, and the leader walks back one entry at a time until the logs match, then overwrites the follower’s divergent tail. This is the log matching property: if two logs agree on an entry, they agree on everything before it.

The paper finishes the job that Paxos papers left to the reader. Membership changes use a joint configuration in which decisions need majorities of both the old and new sets, so no two leaders can be elected during the transition. Logs are compacted by snapshotting the state machine. Clients retry safely because every command carries a serial number. None of this is deep; all of it is the difference between an algorithm and a system.

What it changed

Raft did what its authors hoped. Within a few years there were implementations in every major language, many of them correct, and new systems stopped inventing their own consensus. etcd adopted it and became the store under Kubernetes, so every object in every cluster is a Raft log entry; Consul, CockroachDB, TiKV and YugabyteDB run thousands of small Raft groups, one per range of data; Kafka replaced ZooKeeper with its own Raft (KRaft) in 2022. Paxos is still the deeper theory, but Raft is what gets built.

Where you meet it today

• Kubernetes. The control plane’s truth lives in etcd; a three- or five-node etcd cluster is a Raft group, and “lost quorum” is a Raft election that cannot complete.
• Distributed SQL. CockroachDB, TiDB and YugabyteDB replicate each shard with Raft and layer transactions on top.
• Message brokers. Kafka’s metadata, RabbitMQ’s quorum queues and NATS JetStream are Raft logs.
• Your own leader election. If you ever need “exactly one of these runs at a time”, reach for an existing Raft store rather than a database lock.