Raft 论文摘要（一）

Raft is a consensus algorithm for managing a replicated log.

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

Consensus algorithms allow a collection of machines to work as a coherent group that can survive the failures of some of its members.

Paxos has dominated the discussion of consensus algorithms over the last decade.

Paxos is quite difficult to understand, inspite of numerous attempts to make it more approachable.

Our approach was unusual in that our primary goal was understandability: could we define a consensus algorithm forpractical systems and describe it in a way that is significantly easier to learn than Paxos?

It was important notjust for the algorithm to work, but for it to be obvious whyit works.

In designing Raft we applied specific techniques to improve understandability, including decomposition (Raftseparates leader election, log replication, and safety) and state space reduction (relative to Paxos, Raft reduces thedegree of nondeterminism and the ways servers can be inconsistent with each other).

It has several novel features:

• Strong leader

• Leader election: Raft uses randomized timers to elect leaders.

• Membership changes: Raft’s mechanism for changing the set of servers in the cluster uses a new joint consensus approach where the majorities oftwo different configurations overlap during transitions.

Replicated state machines are used to solve a variety of fault tolerance problems in distributed systems.

Examples of replicated state machines include [Google Chubby] and [Apache ZooKeeper].

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.

Keeping the replicated log consistent is the job of theconsensus algorithm.

Consensus algorithms for practical systems typicallyhave the following properties:

• They ensure safety(never returning an incorrect result) under all non-Byzantine conditions, includingnetwork delays, partitions, and packet loss, duplication, and reordering.

• They are fully functional (available) as long as anymajority of the servers are operational and can communicate with each other and with clients.

• They do not depend on timing to ensure the consistency 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 performance.

Paxos first defines a protocol capable of reachingagreement on a single decision, such as a single replicatedlog entry. We refer to this subset assingle-decree Paxos.Paxos then combines multiple instances of this protocol tofacilitate a series of decisions such as a log (multi-Paxos).

Paxos has two significant drawbacks.

• The first drawback is that Paxos is exceptionally difficult to understand.

• The second problem with Paxos is that it does not provide a good foundation for building practical implementations

  • One reason is that there is no widely agreedupon algorithm for multi-Paxos.

  • Furthermore, the Paxos architecture is a poor one for building practical systems;

  • Another problem is that Paxos uses a symmetric peer-to-peer approach at its core

If aseries of decisions must be made, it is simpler and fasterto first elect a leader, then have the leader coordinate thedecisions.

Each implementation begins with Paxos, discovers the difficulties in implementing it, and then develops a significantly different architecture.

There are significant gaps between the description ofthe Paxos algorithm and the needs of a real-world system. . . . the final system will be based on an unproven protocol.