In Search of an Understandable Consensus Algorithm
📜 Abstract
Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos; this makes Raft more understandable than Paxos and also provides a better foundation for building practical systems. 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. Results from a user study demonstrate that Raft is easier for students to learn than Paxos. Raft also includes a new mechanism for changing the cluster membership, which uses overlapping majorities to guarantee safety.
✨ Summary
Summary
The paper introduces Raft, a consensus algorithm for replicated state machines designed primarily to improve understandability without sacrificing safety, availability, or performance. Raft organizes consensus around a strong leader and decomposes the problem into leader election, log replication, and safety. Servers operate as followers, candidates, or leaders, and logical terms help detect stale leadership and coordinate elections.
The leader accepts client commands, appends them to its log, and replicates them to followers using AppendEntries RPCs. Followers use consistency checks based on log indexes and terms; conflicting uncommitted entries are removed so that follower logs converge with the leader’s log. Randomized election timeouts reduce split votes and enable rapid leader replacement after failures.
Safety depends on several invariants: election safety, leader append-only behavior, log matching, leader completeness, and state-machine safety. In particular, candidates must have logs at least as up-to-date as the servers that vote for them, and a leader generally commits entries from earlier terms only after committing an entry from its current term. These rules ensure that once a command has been applied at a given log position, no different command can later be applied at that position.
The paper also specifies joint consensus for changing cluster membership safely. During a transition, decisions require majorities from both the old and new configurations, preventing the two configurations from independently electing leaders or committing conflicting entries. Snapshotting is used for log compaction, and an InstallSnapshot RPC allows lagging followers to recover when the leader has already discarded older log entries. Client serial numbers prevent duplicate execution after retries, while leader confirmation with a majority supports linearizable reads without necessarily appending reads to the log.
The evaluation reports that, in a study of 43 students, participants scored an average of 4.9 points higher on Raft questions than on Paxos questions. The authors also provide a formal specification and safety arguments, and report performance comparable to Paxos because normal log replication requires a single round of communication with a majority. The paper received the USENIX ATC ’14 Best Paper Award. (usenix.org)
Influence on research and industry
Raft became a commonly used consensus protocol and implementation foundation. The official etcd Raft library describes itself as a stable, feature-complete implementation and identifies its use in systems including etcd, Kubernetes, Docker Swarm, Cloud Foundry Diego, CockroachDB, TiDB, Project Calico, Flannel, and Hyperledger. (github.com)
Industry systems adopted Raft for replicated control-plane or database state: Consul uses Raft to manage distributed datacenter operations and replicate log entries among server agents, while CockroachDB uses Raft for each replicated range and developed MultiRaft to manage many consensus groups efficiently. (developer.hashicorp.com)
The paper also influenced subsequent educational and formal-verification work. The Raft project identifies later work on formally verifying Raft and provides the paper, formal specification, and related research as core project materials. (raft.github.io)