In Search of an Understandable Consensus Algorithm (Extended Version)

In one breath — the whole paper, compressed

Raft manages a replicated log with the same guarantees as multi-Paxos, but it is designed so that people can actually understand and implement it. It elects a single strong leader whose log is authoritative: clients talk only to the leader, entries flow one way from leader to followers, and an AppendEntries consistency check together with the Log Matching Property forces divergent follower logs back into agreement. Time is divided into terms that act as a logical clock, elections use randomized timeouts so split votes are rare, and an election restriction - a candidate's log must be at least as up-to-date as that of the majority which votes for it - guarantees every new leader already holds all committed entries, so log entries never need to flow backwards. The paper also specifies joint consensus for online membership changes, snapshot-based log compaction, and linearizable client semantics. A user study of 43 students found 33 scored higher on Raft than on Paxos, with mean quiz scores of 25.7 versus 20.8 out of 60.

Before this paper — the world it landed in

For the decade before this paper, consensus was effectively synonymous with Paxos: it was the protocol taught in courses and the starting point for nearly every implementation. But Lamport's presentation centred on single-decree Paxos, a two-stage protocol whose stages have no simple intuitive explanation and cannot be understood independently, and the composition rules for multi-Paxos were only sketched, so no widely agreed-upon multi-Paxos algorithm existed. Practical systems - Chubby, ZooKeeper, and the coordination layers under GFS, HDFS and RAMCloud - each began with Paxos, hit the missing details, and ended up with a significantly different architecture whose details usually went unpublished; the Chubby implementers wrote that their final system would be based on an unproven protocol. Ongaro and Ousterhout report an informal survey of NSDI 2012 attendees in which few people, even seasoned researchers, were comfortable with Paxos, and say it took them almost a year, several simplified explanations, and designing their own alternative before they understood the complete protocol. Their conclusion was that Paxos was a poor foundation for both system building and education, and that the problem of agreeing on a log deserved a different decomposition entirely.

The problem — what was actually breaking

Paxos is exceptionally difficult to understand: the full explanation is notoriously opaque, and the authors themselves could not understand the complete protocol until they had read several simplified explanations and designed their own alternative, a process that took almost a year.
The paper argues that Paxos' opaqueness derives from building on the single-decree subset, which is dense and subtle, divided into two stages that have no simple intuitive explanations and cannot be understood independently.
There is no widely agreed-upon algorithm for multi-Paxos: Lamport's descriptions are mostly about single-decree Paxos and only sketch possible compositions, and the published elaborations differ from each other and from those sketches.
The Paxos architecture is a poor foundation for real systems, because choosing a collection of log entries independently and then melding them into a sequential log just adds complexity, and its symmetric peer-to-peer core does not match how systems that must make a series of decisions actually operate.
Because each implementation discovers the difficulties and then develops a significantly different architecture, the existing correctness proofs have little value for the code that actually runs, which is both time-consuming and error-prone.
A practical consensus algorithm must stay safe under all non-Byzantine conditions including network delays, partitions, packet loss, duplication and reordering, remain available with any majority of servers, never depend on timing for log consistency, and in the common case commit after a single round of RPCs.

Core ideas — the contributions, and why they work

Understandability as the design goal

The authors' primary goal was not novelty or minimal message count but that a large audience could comfortably understand the algorithm and develop intuitions about it. At every design fork they asked how hard an alternative would be to explain and how complex its state space was, and they leaned on two repeatable techniques: problem decomposition, splitting consensus into leader election, log replication, safety and membership changes, and state space reduction, eliminating nondeterminism and forbidding holes in logs. This matters because the published form of an algorithm is never what ships; developers inevitably deviate from and extend it, and only a deep intuition lets them preserve its properties while doing so. Randomization was kept in exactly one place precisely because it reduces the state space rather than growing it - every possible choice is handled the same way, so the reader can think choose any, it doesn't matter.

Strong leadership, one-way log flow

Raft uses a stronger form of leadership than Paxos or Viewstamped Replication: log entries flow only outward from the leader, and a leader never overwrites or deletes entries in its own log. The leader alone decides where a new entry goes, so no agreement is needed about placement, and the whole problem of reconciling divergent replicas collapses into one direction - followers are forced to duplicate the leader's log - instead of a symmetric merge. In Viewstamped Replication log entries flow both ways because a leader can receive entries during the election process, which costs extra mechanism. This is also why Raft needs only four message types, two RPC requests plus their responses, for basic consensus and membership changes, where VR and ZooKeeper each define ten.

Terms as a logical clock

Raft divides time into terms of arbitrary length numbered with consecutive integers; each term begins with an election and has at most one leader, and a term can end with no leader at all if the vote splits. Every server stores a monotonically increasing currentTerm, and current terms are exchanged on every RPC: a server that sees a larger term adopts it, and a candidate or leader that discovers its own term is stale immediately reverts to follower state. Requests carrying a stale term are simply rejected. This single mechanism detects stale leaders, obsolete messages and healed partitions without any physical clocks, turning the question of whether information is current into an integer comparison.

Randomized election timeouts

Rather than ranking candidates or bolting on a separate election protocol, Raft has each follower wait a timeout drawn randomly from a fixed interval, for example 150-300ms, before becoming a candidate, and re-draws that timeout at the start of every election. Spreading the servers out in time means usually only one times out first, wins, and sends heartbeats before anyone else wakes up; when a split vote does occur, the fresh random wait makes a repeat unlikely. The authors first tried a deterministic ranking scheme in which a lower-ranked candidate deferred to a higher-ranked one, but every fix for its availability corner cases produced new corner cases. Randomization won on understandability grounds: it handles all choices identically, so there is nothing to reason about case by case.

Log Matching from one consistency check

Raft maintains the Log Matching Property: if two logs hold an entry with the same index and term, they store the same command there and are identical in every preceding entry. The first half follows because a leader creates at most one entry per index per term and entries never change position. The second half is enforced by a single check - every AppendEntries carries the index and term of the entry immediately preceding the new ones, and the follower refuses the append if it has no matching entry. That check is an induction step: empty logs satisfy the property and the check preserves it on every extension, so a successful AppendEntries tells the leader that the follower's log is identical to its own up through the new entries.

The election restriction

Instead of electing any server and then shipping it the entries it lacks, Raft guarantees that a new leader already holds every committed entry at the moment of its election. RequestVote carries the candidate's lastLogIndex and lastLogTerm, and a voter refuses if its own log is more up-to-date: the log with the later last term wins, and if the last terms tie, the longer log wins. Since a candidate needs a majority and every committed entry sits on a majority, the two sets intersect, so at least one voter holds the committed entry and would have denied its vote to a candidate lacking it. This is what makes one-directional log flow possible and removes the entry-transfer machinery that Viewstamped Replication needs during or just after an election.

Joint consensus for membership change

Switching servers directly from an old configuration to a new one is unsafe because servers switch at different moments, so the cluster can briefly split into a majority of Cold and a majority of Cnew that each elect a leader for the same term. Raft instead commits a transitional configuration Cold,new in which entries replicate to all servers of both configurations, any server of either configuration may lead, and every agreement - elections and commitment alike - requires separate majorities from both. Overlapping majorities mean neither configuration can ever decide alone, so no window of divergence exists and the cluster keeps serving clients throughout the change. Configurations travel as ordinary log entries and take effect the moment a server appends them, committed or not, which is exactly what lets servers cross over at different times without compromising safety.

How it works — the mechanism, concretely

Server states, terms and the two RPCs

Each server is a leader, a follower or a candidate; followers are passive and only respond to RPCs, and a client that reaches a follower is redirected to the leader. Persistent state on every server, written to stable storage before responding to any RPC, is currentTerm, votedFor and log[], where each entry holds a state machine command plus the term in which the leader received it; volatile state is commitIndex and lastApplied, and a leader additionally keeps nextIndex[] and matchIndex[] per follower. Basic consensus needs only two RPCs: RequestVote, issued by candidates, and AppendEntries, issued by leaders both to replicate entries and to serve as heartbeats; Section 7 adds InstallSnapshot. RPCs are issued in parallel and retried until answered, and any server that sees a term larger than its own sets currentTerm to it and converts to follower.

Leader election and the timing requirement

A follower that receives no valid RPC for its election timeout increments currentTerm, becomes a candidate, votes for itself and sends RequestVote to every other server in parallel. Three outcomes are possible: a majority of the full cluster votes for it in that term and it becomes leader and immediately heartbeats to suppress rivals; it receives an AppendEntries from a server whose term is at least its own and reverts to follower; or the timeout elapses with no winner and it starts a new election at a higher term. Each server votes at most once per term on a first-come-first-served basis, which by itself gives the Election Safety Property of at most one leader per term. Safety never depends on timing but availability does: Raft holds a steady leader only when broadcastTime is much less than electionTimeout, which is much less than MTBF, and the paper estimates broadcastTime at 0.5-20ms because RPCs typically persist to stable storage, electionTimeout at 10-500ms, and typical server MTBFs at several months or more.

Log replication and repairing divergent logs

The leader appends a client command to its own log, sends AppendEntries in parallel, and applies the entry and answers the client once it is committed, meaning the leader that created it has replicated it on a majority; that also commits all preceding entries, including entries created by previous leaders. The leader piggybacks commitIndex on subsequent AppendEntries and heartbeats so followers learn what to apply, and every server applies entries strictly in log index order. Leader crashes leave followers missing entries, holding extra uncommitted entries, or both, spanning multiple terms as catalogued in Figure 7; the leader repairs this using nextIndex, initialized to its own last index plus one, decremented after each consistency-check rejection and retried until the logs match, at which point AppendEntries deletes the follower's conflicting suffix and appends the leader's entries. An optional optimization has the rejecting follower report the conflicting term and the first index it stores for that term, so the leader skips a whole term per RPC instead of one entry per RPC. Follower and candidate crashes need no special handling at all: the leader retries indefinitely and Raft's RPCs are idempotent, so a redelivered AppendEntries whose entries are already present is simply ignored.

Commitment rules and the safety argument

A leader may not conclude that an entry from an earlier term is committed merely because it now sits on a majority: Figure 8 shows S1 replicating a term-2 entry to a majority, then S5 winning a later term and overwriting it. Raft therefore never commits entries from previous terms by counting replicas - the commit rule requires log[N].term to equal currentTerm - and once any current-term entry commits, all prior entries commit indirectly through Log Matching. Entries keep their original term numbers when a new leader re-replicates them, which makes reasoning easier and sends fewer redundant entries than algorithms that must renumber before committing. The Leader Completeness proof sketch is a contradiction argument: if the leader of the smallest term U greater than T lacks an entry committed by the leader of term T, some voter both accepted that entry and voted for leader U, and the up-to-date check then forces either that leader U's log contains everything the voter had, or that leader U's last log term came from an earlier leader that itself held the entry - a contradiction either way. State Machine Safety follows, since servers apply entries in index order and every later leader stores the same entry at that index.

Cluster membership changes

A reconfiguration request makes the leader append a Cold,new entry and replicate it; a server adopts a configuration as soon as it appears in its log, whether or not it is committed, so the leader judges Cold,new committed under Cold,new's own rules, meaning separate majorities of both configurations. If the leader crashes mid-change, a new leader may be chosen under Cold or under Cold,new, but Cnew can never make unilateral decisions during this period. Once Cold,new commits, Leader Completeness ensures only servers holding that entry can be elected, so the leader safely appends Cnew; when Cnew commits under its own rules, servers outside it can be shut down. Three practical wrinkles are handled explicitly: new servers first join as non-voting members that receive entries but are not counted in majorities, so a slow catch-up cannot stall commits; a leader not in Cnew keeps replicating without counting itself and steps down once Cnew commits; and removed servers, which stop receiving heartbeats, would otherwise time out and depose the leader with ever-higher terms, so servers disregard RequestVote RPCs received within the minimum election timeout of hearing from a current leader.

Log compaction with snapshots

Each server independently snapshots the committed prefix of its log: the state machine writes its current state, plus metadata giving the last included index, the last included term, and the latest configuration in the log as of that index, and then discards all log entries up through that index along with any prior snapshot. The last included index and term exist so the AppendEntries consistency check still has a predecessor to match against for the first entry after the snapshot. When the leader has already discarded an entry that a lagging follower needs - an exceptionally slow server or one newly added to the cluster - it sends InstallSnapshot, chunked and in order so each chunk also gives the follower a sign of life to reset its election timer; the follower discards its entire log unless the snapshot describes a strict prefix of it, in which case only the covered entries are deleted. Independent snapshotting deliberately departs from strong leadership, justified because consensus has already been reached on those entries so no decisions can conflict, and because leader-only snapshotting would waste bandwidth and complicate the leader. Snapshotting when the log passes a fixed size in bytes keeps disk overhead small, and copy-on-write - the authors' implementation uses fork on Linux - keeps writing a snapshot from delaying normal operations.

Client interaction and linearizable reads

A client starts by contacting a randomly chosen server; if that server is not the leader it rejects the request and supplies the most recent leader it has heard from, since AppendEntries requests carry the leader's network address. A retry after a leader crash can execute a command twice, because the old leader may have committed the entry and died before replying, so each command carries a unique client serial number and the state machine remembers the latest serial and its response per client, answering a duplicate immediately instead of re-executing. Read-only operations bypass the log but need two extra precautions to avoid stale data: the leader commits a blank no-op entry at the start of its term so it learns which entries are actually committed, and it exchanges heartbeat messages with a majority before answering a read to confirm it has not been deposed. A lease derived from the heartbeat interval would save that round trip but would make safety depend on bounded clock skew, which Raft otherwise never does.

What the paper showed — measurements and proofs

In the user study, 43 upper-level undergraduates and graduate students at Stanford and U.C. Berkeley each watched a Raft lecture and a Paxos lecture in counterbalanced order and took a quiz on each; 33 scored higher on Raft, mean scores were 25.7 for Raft against 20.8 for Paxos out of 60, and a paired t-test gives 95% confidence that the true Raft mean is at least 2.5 points higher.
A linear regression controlling for which quiz, prior Paxos experience and learning order predicts a 12.5-point advantage for Raft, much larger than the observed 4.9 points because 15 of the 43 participants already had some Paxos experience, and it also predicts a statistically significant 6.3-point drop on Raft for people who took the Paxos quiz first, which the authors say they cannot explain.
In a post-quiz survey, 33 of 41 participants said Raft would be easier to implement in a correct and efficient system and 33 of 41 said it would be easier to explain to a CS graduate student, though the authors caution these self-reports may be biased by knowledge of their hypothesis.
Correctness rests on a roughly 400-line TLA+ specification that makes Figure 2 completely precise; Log Completeness was mechanically proven with the TLA proof system, and a complete informal proof of State Machine Safety that relies on the specification alone runs about 3500 words.
Leader-election measurements on five servers with a broadcast time of roughly 15ms show that with no randomization elections consistently took longer than 10 seconds because of repeated split votes, that just 5ms of randomization gave a 287ms median downtime, and that 50ms of randomization held the worst case over 1000 trials to 513ms.
Shrinking the election timeout to 12-24ms cut the mean time to elect a leader to 35ms with a longest trial of 152ms, but the authors still recommend a conservative 150-300ms because tighter timeouts violate the broadcastTime margin and cause unnecessary leader changes; their own implementation is about 2000 lines of C++ inside RAMCloud's coordinator, and roughly 25 independent third-party implementations already existed.

Limits and trade-offs — conceded and discovered

Conceded by the paper: strong leadership simplifies the algorithm but precludes some performance optimizations. The authors point to Egalitarian Paxos, where any server can commit a command in one round as long as concurrently proposed commands commute, giving better load balance and lower latency than Raft in WAN settings, at the cost of significant added complexity. Later practice confirmed the single leader as a throughput ceiling, which is why production systems shard into many Raft groups.
Conceded: the commitment rule is deliberately conservative. There are situations where a leader could safely conclude an older entry is committed, for example when it is stored on every server, but Raft refuses to commit any previous-term entry by counting replicas, accepting extra rules in exchange for simpler reasoning.
Conceded: safety never depends on timing but availability entirely does. A leader crash leaves the system unavailable for roughly one election timeout, timeouts pushed below the broadcastTime margin cause unnecessary leader changes and lower availability, and the cheaper lease-based read-only path is explicitly rejected because it would assume bounded clock skew.
Conceded: the formal guarantee is partial. Only the Log Completeness Property was mechanically proven, and that proof relies on invariants that were not mechanically checked - the authors note they did not prove the type safety of the specification - while State Machine Safety has only an informal proof. Snapshotting also knowingly breaks the strong-leader principle, since followers snapshot without the leader's knowledge.
Exposed by later work: the membership-change story proved harder than the paper suggests. Ongaro's 2014 dissertation replaced joint consensus with single-server-at-a-time changes, which were themselves later found to need the leader to commit an entry from its current term before starting a change, and added an explicit Pre-Vote phase, since the paper's disruption defence is stated only inside the membership-change section and was widely omitted by implementers.

What it became — the systems that inherited it

Raft became the default consensus algorithm of the 2010s infrastructure stack, largely because Figure 2 is a specification that developers can implement almost line for line. etcd, written at CoreOS from drafts of this paper, is the store Kubernetes keeps all its cluster state in, and its Go raft library was reused wholesale by CockroachDB and TiKV, both of which run one Raft group per key range or region - multi-Raft - to get around the single-leader throughput ceiling. HashiCorp's Consul, Nomad and Vault, MongoDB's replication protocol version 1, Apache Kafka's KRaft mode replacing ZooKeeper, Neo4j causal clustering, RethinkDB, Hazelcast and Apache Ratis all adopted the same leader-plus-terms-plus-log skeleton. Joint consensus was the least-copied part: most systems took the single-server-at-a-time changes from Ongaro's 2014 dissertation instead, and nearly all added Pre-Vote and explicit leadership transfer. The 400-line TLA+ specification gave the community a machine-checkable reference that later model-checking and verification work built on, and courses such as MIT 6.824 now teach consensus by having students build Raft rather than read Paxos. Perhaps its broadest effect was legitimizing understandability as a stated, measurable design goal in a systems paper, backed by a controlled user study rather than assertion.

In the paper’s words — verbatim

“In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforces a stronger degree of coherency to reduce the number of states that must be considered.”

Abstract

“It was important not just for the algorithm to work, but for it to be obvious why it works.”

§1

“To eliminate problems like the one in Figure 8, Raft never commits log entries from previous terms by counting replicas.”

§5.4.2

Vocabulary — as this paper uses it

Replicated state machine: A collection of servers computing identical copies of the same state by executing the same deterministic command sequence from a replicated log, so the group survives the failure of some members. Raft's entire job is keeping those logs identical.
Term: An arbitrary-length period numbered with consecutive integers, beginning with an election and containing at most one leader; some terms end with no leader because the vote split. Terms act as Raft's logical clock, letting servers detect stale leaders and obsolete information.
Committed entry: A log entry that the leader which created it has replicated on a majority of servers, making it durable and guaranteed to be executed eventually by every available state machine. Committing an entry also commits all preceding entries in the leader's log.
Log Matching Property: If two logs contain an entry with the same index and term, they store the same command there and are identical in every preceding entry. It is maintained by the AppendEntries consistency check, which carries the index and term of the entry immediately preceding the new ones.
Leader Completeness Property: If a log entry is committed in a given term, it is present in the logs of the leaders of all higher-numbered terms. It is what allows entries to flow only from leader to follower, and it is enforced by the election restriction rather than by any recovery protocol.
State Machine Safety Property: If a server has applied a log entry at a given index to its state machine, no other server will ever apply a different entry at that same index. This is Raft's top-level correctness goal, derived from Leader Completeness plus the rule that entries are applied in index order.
Up-to-date: The comparison a voter applies in RequestVote: of two logs, the one whose last entry has the later term is more up-to-date, and if the last terms are equal the longer log is more up-to-date. A voter denies its vote to any candidate whose log is less up-to-date than its own.
Joint consensus (Cold,new): The transitional configuration in which entries replicate to servers of both the old and the new configuration, servers from either may serve as leader, and every election and every commitment requires separate majorities from both. It is written into the log as an ordinary entry and takes effect the moment a server appends it.
Last included index and term: The snapshot metadata naming the final log entry the snapshot replaces and that entry's term. They position the snapshot in the log so the AppendEntries consistency check still has a predecessor to match for the first entry following the snapshot.

On the timeline — where this sits in the story

Year2014

MilestoneRaft consensus algorithm

Problem solvedPaxos-style consensus was powerful but difficult for engineers to understand and implement correctly.

How it solved itRaft decomposed consensus into leader election, log replication, and safety properties with an understandability-first design.

Why it matteredBecame widely adopted in practical distributed databases and coordination systems.

DDIACh. 10: Consistency & Consensus

View on the timeline