Papers
In Search of an Understandable Consensus Algorithm
Diego Ongaro, John Ousterhout · USENIX Annual Technical Conference (ATC) 2014, 2014
The problem: distributed consensus that is hard to understand and to implement
Distributed systems that need to survive machine failures typically replicate the same log of commands across several servers and use a consensus algorithm to ensure that all of them agree on the same sequence, even when some replicas go down or the network fails. Before Raft, Paxos was the reference algorithm for this problem, and it is provably correct, but the authors argue that it is notoriously hard to understand: its original formulation solves only consensus on a single value in an abstract way, and the task of composing that into a practical log, with multiple decisions, cluster membership changes, and acceptable performance, is left largely to the implementer, which historically led to divergent, ad hoc implementations. Ongaro and Ousterhout decided to treat understandability as a first-class design goal, on the same level as correctness and efficiency, and not merely as a desirable side effect. To validate this goal empirically, the authors ran a study with 43 students from two universities, who learned Raft and Paxos and then answered quizzes about both: the students scored about 23% better on the Raft questions than on the Paxos ones, and 33 of the 43 rated Raft as easier to understand.
The core idea: a single leader, terms, and two kinds of RPC
To make the problem more tractable, Raft decomposes consensus into three relatively independent subproblems: leader election, log replication, and safety. Unlike symmetric schemes, Raft always elects a single leader at a time, which takes exclusive responsibility for accepting client commands, appending them to its own log, and replicating them to the other servers (followers). Time is divided into terms, increasing integers that work as a kind of logical clock: each term has at most one leader, and comparing term numbers lets servers detect stale information, such as an old leader that still believes it is in charge. The election is triggered by a randomized timer: if a follower receives no message from the leader within that interval, it becomes a candidate, increments its term, and requests votes from the others through an RPC called RequestVote. Communication between leader and followers uses only two types of RPC in total: RequestVote, for elections, and AppendEntries, used both to replicate log entries and, when empty, as a heartbeat signal that prevents new elections while the leader is alive. The election timeout interval suggested in the paper is between 150 and 300 milliseconds, precisely to reduce the chance of two elections happening at the same time (split vote).
Log replication and the consistency guarantee between replicas
When a client sends a command, the leader first appends it to its own log and then fires AppendEntries RPCs in parallel to replicate it to the followers. An entry is considered 'committed' as soon as the leader confirms it has been successfully replicated on a majority of the servers in the cluster — from then on, it is safe to apply it to the state machine, and all earlier entries in the log are also considered committed. To keep the logs consistent with each other, Raft relies on the Log Matching Property: if two replicas have an entry with the same index and the same term, then their logs are identical in all entries up to that index. This is guaranteed because each AppendEntries includes the index and term of the immediately preceding entry, and a follower rejects the message if those values do not match its own log; when there is divergence, the leader forces the follower's log to converge to its own, overwriting conflicting entries. There is an important subtlety in the commit rules: the leader cannot conclude that an entry from a previous term is committed merely by counting replicas of it — it can only treat old entries as committed after an entry from its own current term is replicated on a majority.
Safety: the election restriction and the Leader Completeness Property
To ensure that an already committed entry is never lost, Raft restricts who can become leader: when answering a RequestVote, a server denies its vote to a candidate whose log is 'less up-to-date' than its own, comparing first the term of the last entry and, in case of a tie, the length of the log. This election restriction guarantees that any candidate able to win an election (that is, obtain a majority vote) already contains, in its own log, all entries committed up to that moment. This result is formalized by the Leader Completeness Property: if an entry was committed in a given term, it will be present in the logs of all leaders of later terms. This property is one of five safety guarantees that the paper states and formally proves: Election Safety (at most one leader elected per term), Leader Append-Only (a leader never overwrites or deletes entries in its own log, it only appends), Log Matching, Leader Completeness, and State Machine Safety (if a server has already applied an entry at a given index to its state machine, no other server will apply a different command at that same index). Together, these guarantees are what allow Raft to maintain a consistent replicated log even in the face of leaders that fail midway.
Practical extensions and legacy: cluster reconfiguration and adoption in real systems
Beyond the core of the algorithm, the paper addresses two practical problems that any real implementation of replicated consensus must solve. The first is changing the cluster's membership (for example, replacing servers or changing the size of the required majority) without stopping the system; Raft solves this with a joint consensus mechanism, in which the cluster goes through a transitional configuration that requires a majority in both the old and the new configuration before finalizing the switch, avoiding a window in which two independent leaders could be elected simultaneously under different configurations. The second is the unbounded growth of the log over time, solved by compaction via snapshotting: a server can periodically save the complete state of the state machine and discard the log prior to that point. The authors' stated goal — to prioritize understandability without giving up correctness — had a measurable practical effect: today Raft is the consensus algorithm behind several widely used production distributed infrastructure systems, such as etcd, Consul, CockroachDB, and TiKV, which rely on it as their core replication engine.
See the ideas at work
Practice the designs that use this paper in the System Design school.