In Search of an Understandable Consensus Algorithm ...

1 In Search of an Understandable Consensus Algorithm (Extended Version)Diego Ongaro and John OusterhoutStanford UniversityAbstractRaft is a Consensus Algorithm for managing a replicatedlog. It produces a result equivalent to (multi-)Paxos, andit is as efficient as Paxos, but its structure is differentfrom Paxos; this makes Raft more Understandable thanPaxos and also provides a better foundation for build-ing practical systems. In order to enhance understandabil-ity, Raft separates the key elements of Consensus , such asleader election, log replication, and safety, and it enforcesa stronger degree of coherency to reduce the number ofstates that must be considered.

2 Results from a user studydemonstrate that Raft is easier for students to learn thanPaxos. Raft also includes a new mechanism for changingthe cluster membership, which uses overlapping majori-ties to guarantee IntroductionConsensus algorithms allow a collection of machinesto work as a coherent group that can survive the fail-ures of some of its members. Because of this, they play akey role in building reliable large-scale software [15, 16] has dominated the discussion of consen-sus algorithms over the last decade: most implementationsof Consensus are based on Paxos or influenced by it, andPaxos has become the primary vehicle used to teach stu-dents about , Paxos is quite difficult to understand, inspite of numerous attempts to make it more , its architecture requires complex changesto support practical systems.

3 As a result, both systembuilders and students struggle with struggling with Paxos ourselves, we set out tofind a new Consensus Algorithm that could provide a bet-ter foundation for system building and education. Our ap-proach was unusual in that our primary goal wasunder-standability: could we define a Consensus Algorithm forpractical systems and describe it in a way that is signifi-cantly easier to learn than Paxos? Furthermore, we wantedthe Algorithm to facilitate the development of intuitionsthat are essential for system builders. It was important notjust for the Algorithm to work, but for it to be obvious whyit result of this work is a Consensus Algorithm calledRaft.

4 In designing Raft we applied specific techniques toimprove understandability,including decomposition (Raftseparates leader election, log replication, and safety) andThis tech report is an extended version of [32]; additional material isnoted with a gray bar in the margin. Published May 20, space reduction (relative to Paxos, Raft reduces thedegree of nondeterminism and the ways servers can be in-consistent with each other). A user study with 43 studentsat two universities shows that Raft is significantly easierto understand than Paxos: after learning both algorithms,33 of these students were able to answer questions aboutRaft better than questions about is similar in many ways to existing Consensus al-gorithms (most notably, Oki and Liskov s ViewstampedReplication [29, 22]), but it has several novel features: Strong leader:Raft uses a stronger form of leader-ship than other Consensus algorithms.

5 For example,log entries only flow from the leader to other simplifies the management of the replicated logand makes Raft easier to understand. Leader election:Raft uses randomized timers toelect leaders. This adds only a small amount ofmechanism to the heartbeats already required for anyconsensus Algorithm , while resolving conflicts sim-ply and rapidly. Membership changes:Raft s mechanism forchanging the set of servers in the cluster uses a newjoint consensusapproach where the majorities oftwo different configurations overlap during transi-tions. This allows the cluster to continue operatingnormally during configuration believe that Raft is superior to Paxos and other con-sensus algorithms, both for educational purposes and as afoundation for implementation.

6 It is simpler and more un-derstandable than other algorithms; it is described com-pletely enough to meet the needs of a practical system;it has several open-source implementations and is usedby several companies; its safety properties have been for-mally specified and proven; and its efficiency is compara-ble to other remainder of the paper introduces the replicatedstate machine problem (Section 2), discusses the strengthsand weaknesses of Paxos (Section 3), describes our gen-eral approach to understandability (Section 4), presentsthe Raft Consensus Algorithm (Sections 5 8), evaluatesRaft (Section 9), and discusses related work (Section 10).

7 2 Replicated state machinesConsensus algorithms typically arise in the context ofreplicated state machines[37]. In this approach, state ma-chines on a collection of servers compute identical copiesof the same state and can continue operating even if someof the servers are down. Replicated state machines are1 Figure 1:Replicated state machine architecture. The con-sensus Algorithm manages a replicated log containing statemachine commands from clients. The state machines processidentical sequences of commands from the logs, so they pro-duce the same to solve a variety of fault tolerance problems in dis-tributed systems.

8 For example, large-scale systems thathave a single cluster leader, such as GFS [8], HDFS [38],and RAMC loud [33], typically use a separate replicatedstate machine to manage leader election and store config-uration information that must survive leader crashes. Ex-amples of replicated state machines include Chubby [2]and ZooKeeper [11].Replicated state machines are typically implementedusing a replicated log, as shown in Figure 1. Each serverstores a log containing a series of commands, which itsstate machine executes in order. Each log contains thesame commands in the same order, so each state ma-chine processes the same sequence of commands.

9 Sincethe state machines are deterministic, each computes thesame state and the same sequence of the replicated log consistent is the job of theconsensus Algorithm . The Consensus module on a serverreceives commands from clients and adds them to its communicates with the Consensus modules on otherservers to ensure that every log eventually contains thesame requests in the same order, even if some servers commands are properly replicated, each server sstate machine processes them in log order, and the out-puts are returned to clients. As a result, the servers appearto form a single, highly reliable state algorithms for practical systems typicallyhave the following properties: They ensuresafety(never returning an incorrect re-sult) under all non-Byzantine conditions, includingnetwork delays, partitions, and packet loss, duplica-tion, and reordering.

10 They are fully functional (available) as long as anymajority of the servers are operational and can com-municate with each other and with clients. Thus, atypical cluster of five servers can tolerate the failureof any two servers. Servers are assumed to fail bystopping; they may later recover from state on stablestorage and rejoin the cluster. They do not depend on timing to ensure the consis-tency of the logs: faulty clocks and extreme messagedelays can, at worst, cause availability problems. In the common case, a command can complete assoon as a majority of the cluster has responded to asingle round of remote procedure calls; a minority ofslow servers need not impact overall system What s wrong with Paxos?