RAFT : In Search of an Understandable Consensus Algorithm

Diego Ongaro, John Ousterhout; Stanford University

Description

InSearchofanUnderstandableConsensusAlgorithm DiegoOngaroandJohnOusterhout StanfordUniversity (DraftofApril7,2013,undersubmissiontoSOSP) Abstract was our most important criterion in evaluating de- Raftisaconsensusalgorithmformanagingareplicated sign alternatives. We applied specific techniques to improveunderstandability,includingdecompositionlog. It produces a result equivalent to Paxos, and it is (Raft separates leader election, log replication, andas efficient as Paxos, but its structure is different from safety so that they can be understood relatively in-Paxos; this makes Raft more understandable than Paxos dependently)andstatespacereduction(Raftreducesand also providesa better foundationfor building practi- the degree of nondeterminism and the ways serverscal systems. In order to enhance understandability, Raft separates the key elements of consensus, such as leader canbeinconsistentwitheachother,inordertomake electionandlogreplication,anditenforcesastrongerde- iteasiertoreasonaboutthesystem). greeofcoherencytoreducethenumberofstatesthatmust • Strongleader: Raftdiffersfromotherconsensusal- be considered. Raft also includes a new mechanism for gorithms in that it employs a strong form of leader- changingtheclustermembership,whichusesoverlapping ship where only leaders (or would-be leaders) issue majorities to guarantee safety. Results from a user study requests; other servers are completely passive.

Sujets

• Informatique
• Marketing et communication

Informations

• Publié par: kyann
• Publié le: 07 mai 2013
• Nombre de lectures: 718
• Langue: English

Extrait

In Search of an Understandable Consensus Algorithm Diego Ongaro and John Ousterhout Stanford University (Draft of April 7, 2013, under submission to SOSP) Abstract was our most important criterion in evaluating de- Raft is a consensus algorithm for managing a replicated  sign alternatives. We applied specific techniques to log. It produces a result equivalent to Paxos, and it is  improve understandability, including decomposition as efficient as Paxos, but its structure is different from  (Raft separates leader election, log replication, and Paxos; this makes Raft more understandable than Paxos  safety so that they can be understood relatively in- and also provides a better foundation for building practi-  dependently) and state space reduction (Raft reduces cal systems. In order to enhance understandability, Raft  the degree of nondeterminism and the ways servers separates the key elements of consensus, such as leader  can be inconsistent with each other, in order to make election and log replication, and it enforces a stronger de-  it easier to reason about the system). gree of coherency to reduce the number of states that must • Strong leader: Raft differs from other consensus al- be considered. Raft also includes a new mechanism for  gorithms in that it employs a strong form of leader- changing the cluster membership, which uses overlapping  ship where only leaders (or would-be leaders) issue majorities to guarantee safety. Results from a user study  requests; other servers are completely passive. This demonstrate that Raft is easier for students to learn than  makes Raft easier to understand and also simplifies Paxos. the implementation. 1 Introduction • Membership changes: Raft’s mechanism for changing the set of servers in the cluster uses a sim- Consensus algorithms allow a collection of machines  ities toworkasacoherentgroupthatcansurvivethefailures o p f le tw jo o in d t if c f o er n e s n e t ns c u o s nfi a g p u p r r a o t a i c o h ns w o h v e e r r e la t p he dur m i a n j g or tran- of some of its members. Because of this, they play a  sitions. key role in building reliable large-scale software systems. Paxos[9,10]hasdominatedthediscussionofconsensus att W w e o p u e n r i f v o e r rs m it e i da t us t e e r st st o u u d r y hy w p it o h th 4 es 3 is g t r h a a d t u R at a e ft s i t s ud m e o n r ts e algorithms over the last decade: most implementations  es o of consensus are based on Paxos or influenced by it, and  understandable than Paxos. After learning both algo- Paxoshasbecometheprimaryvehicleusedtoteachstu- r 2 i 3 th % m b s, et s t t e u r d t e h n a t n s q w u e e r s e ti a o b n l s et a o bo an ut sw Pa er xo q s u . estionsaboutRaft dents about consensus. Unfortunately, Paxos is quite difficult to understand, in  We have implemented Raft in about 1500 lines of spite of numerous attempts to make it more approach-  C++ code, and the implementation is used as part of able. Furthermore, its architecture is unsuitable for build-  RAMCloud [18]. We have also proven the correctness ing practical systems, requiring complex changes to cre-  of the Raft algorithm. ate an efficient and complete solution. As a result, both  The remainder of the paper introduces the replicated system builders and students struggle with Paxos.  state machine problem (Section 2), discusses the strengths After struggling with Paxos ourselves, we set out to  and weaknesses of Paxos (Section 3), describes our gen- find a new consensus algorithm that could provide a bet-  eral approach to understandability (Section 4), presents ter foundation for system building and education. Our ap-  the Raft consensus algorithm (Sections 5-7), evaluates proach was unusual in that our primary goal was under- Raft (Section 8), and discusses related work (Section 9). standability : could we define a consensus algorithm and 2 Achieving fault-tolerance with replicated describe it in a way that is significantly easier to learn than machines Paxos, and that facilitates the development of intuitions state that are essential for system builders? It was important  Consensus algorithms typically arise in the context of not just for the algorithm to work, but for it to be obvi- replicated state machines [20]. In this approach, state ma- ous why it works. In addition, the algorithm needed to be  chines on a collection of servers compute identical copies complete enough to cover all the major issues required for  of the same state and can continue operating even if some an implementation.  of the servers are down. Replicated state machines are The result of our effort is a consensus algorithm called  used to solve a variety of fault-tolerance problems in dis- Raft. Raft is similar in many ways to existing consensus  tributed systems. For example, large-scale systems that algorithms (most notably, Oki and Liskov’s Viewstamped  have a single cluster leader, such as GFS [4], HDFS [21], Replication [17]), but it has several novel aspects:  and RAMCloud [18], typically use a separate replicated • Design for understandability: understandability state machine to manage leader election and store config-

1