摘要

分布式共识是构建容错系统的基础。它容许一组机器作为一个整体来工作，通过这样来避免部分机器成员失效导致而带来的问题。不幸的是，大多数共识算法，如Paxos，很难被理解和正确的工程实现。

本论文提出了一种名为Raft的新共识算法，该算法涉及的主要关注点是可理解性。Raft先选举一个服务器作为Leader，然后将左右的工作委托给这个Leader来负责。这两个步骤是分开的，也形成了一个比Paxos好的算法结构（Paxos算法中的功能模块很难分开，也就是说整个算法的结构耦合较为严重，多个目的/功能放在同一个方法/模块中来实现）。Raft通过投票和随机超时来选举Leader。选举过程可保证Leader已经保存了所有必要的信息，因此数据只需要从Leader向其它服务器流动就好（也就是说，整个系统中的数据/信息已Leader的为准）。与其它基于Leader的算法相比，Raft简化了相关选举操作。一旦某个Leader被选出，这个Leader将管理日志副本（Replicated Log）。Raft利用在日志增长方面设计了简单的变种方法来减少算法的状态空间。

Raft相比于之前的共识算法也更适合于工程实现。Raft在实际部署时也表现的很好，它解决了构建完整分布式系统所需解决的所有问题，包括如何管理客户交互、如何进行集群成员变更以及如何压缩日志以减少存储空间。为了进行成员变更，Raft容许一次对一个服务器进行增加或移除（复杂的需求可基于这个要求自行扩展），而且集群在成员变更期间可正常对外提供服务。

我们相信Raft比其他的共识算法摇号，不管是从教学方面还是从工程实现方面来说。从一个用户调研结果显示，Raft比Paxos更荣誉理解。Raft算法已经被形式化的说明和证明，Leader选举算法在大多数环境下运行的很好，性能与Multi-Paoxs差不多。当前已经有很多的工程实现来实现Raft，而且有一些公司已经实际部署了Raft。

一、简介

当今的数据中心和应用软件运行在高度变动的环境中。他们通过横向的扩展来利用更多的服务器资源，并根据需求来扩充或所建服务器的数量。服务器和网络的故障在这些场景中很常见：每年大约有2%-4%的磁盘故障，服务器宕机也很常见，而且每天数十条网络线路的时效也很常见。

因此，系统需要吃力服务器频繁的上线和下线。系统必须能够在几秒内适应这些变化，系统的不可用对用户来说是不可接受的。这是一个很大的挑战，再这样的环境中，错误处理、协调、服务发现以及配置管理都很难处理。

幸运的是，共识算法客户帮助解决这些问题。共识容许一组机器通过协作的的方式来组成一个整体并能够承受部分机器的失效。在一个共识组内，错误被以一种规则化和以证明的方式来处理。因为共识组高度可用和可靠，其它系统组件可通过共识组作为基础来构建自己的容错能力。那么，共识就在这样的软件系统中扮演了很重要的角色。

当我们开始这项工作时，达成共识的必要性正变得很明显，但许多系统仍在与达成共识可以解决的问题作斗争。一些大型系统仍然受到单一协调服务器的单点故障的限制，如HDFS。

很多人选择自行实现Paxos作为解决问题的方案。Paxos已经通知了共识算法领域20多年：大多数共识算法都是基于Paxos来实现或者受到其思想的启发，而且Paxos也是共识算法教学的唯一选择。

不幸的是，Paxos太难理解了，尽管许多文献试图让其变得更能接受，更易于理解。而且，Paxos的算法结构比较复杂，难以支撑实际的系统，工程师需要自行设计和实现很多Paxos算法原文中没有说明的细节。所以，系统开发者和学生都在Paxos的世界中苦苦的挣扎。

另外两个比较有名的共识算法是Viewstamped Replication和Zab（被用于Zookeeper中）。尽管我们相信这两个算法的结构比Paoxs简单，但是他们的设计目的也不是提升算法的可理解性。这两个算法的学习和实现成本仍然很高。

每一种共识算法都难以理解，也难以执行。不幸的是，当与已验证的算法实现共识的成本太高时，系统构建者就留下了一个艰难的决定。他们可以完全避免共识，牺牲系统的容错或一致性，或者他们可以开发自己的特殊算法，这样通常会导致不安全行为。此外，当解释和理解共识的成本太高时，并不是所有的教师都试图教授它，也不是所有的学生都成功地学习了它。共识和2PC协议一样是基础知识；理想情况下，许多学生应该学会它（尽管共识更难理解）。

在我自己在Paxos算法中挣扎了很久之后，我们开始寻找一种新的共识算法，可以为系统建设和教育提供更好的基础。我们的方法很不寻常，因为我们的主要目标是可理解性：我们是否可以为实际系统定义一个共识算法，并以一种比Paxos更容易学习的方式来描述它？此外，我们希望该算法能够为系统开发者提供直觉上的理解。重要的不仅仅是算法可以工作，还要让其工作原理变得更加直白，更容易理解。

该算法还必须足够完整，以解决构建实际系统的各个方面的问题，并且它必须在实际部署中具有足够好的性能。核心算法不仅必须指定接收消息的效果，还必须描述应该发生什么和什么时间发生，这些对于系统建设者来说同样重要。同样，它必须保证一致性，而且还必须尽可能提供可用性。它还必须处理除了共识之外的其它问题，例如改变协商一致意见小组的成员。这些在实践中是必要的，并且将这一负担留给系统构建者将会面临特别、次优甚至不正确的解决方案的风险。（就是说算法要容易理解、而且对具体的工程化落地具有指导性，能够一步一步指导实现者开发出这个系统）

本文工作的结果是一个共识算法，称为Raft。在设计Raft时，我们应用了特定的技术来提高可理解性，包括分解（Raft分离Leader选举、日志复制和安全)和状态空间减少(Raft减少了不确定性的程度和服务器彼此不一致的方式）。我们还讨论了建立一个完整的基于共识的系统所需的所有问题。我们仔细考虑了每一个设计选择，不仅是为了我们自己的实现，也是为了我们希望实现的许多其他选择。

我们相信Raft优于Paxos和其他共识算法，无论出于教育目的还是作为实现的基础。它比其他算法更简单、更容易理解；它的描述完全足以满足实际系统的需求；它有几个开源实现，并被几家公司使用；它的安全性已被正式指定和证明；它的效率可与其他算法相媲美。 本文的主要贡献如下：

- Raft共识算法的设计、实现和评估。Raft在许多方面类似于现有的共识算法(最著名的是Oki和Liskov的Viewstamped Replication)，但它是为可理解性而设计的。这形成了几个特性。例如，Raft使用了一种比其他共识算法更强大的领导形式。这简化了复制日志的管理，使Raft更容易理解。

- Raft的可理解性评估。一项对两所大学43名学生的用户研究表明，Raft比Paxos更容易理解：在学习了这两种算法之后，其中33名学生能够比关于Raft的问题更好地回答关于Raft的问题。我们相信这是第一个基于教学和学习来评估共识算法的科学研究。

- Raft领导人选举机制的设计、实施和评价。虽然许多共识算法没有规定一个特定的领导者选择算法，但Raft包括一个涉及随机计时器的特定算法。这只为任何共识算法所需的心跳增加了少量的机制，同时简单而快速地解决冲突。对领导人选举的评估调查了它的行为和表现，得出结论，这种简单的方法在各种实际环境中是足够的。它通常会在集群20倍以下的单向网络延迟中选择一个领导者。

- Raft集群成员资格变更机制的设计与实现。Raft允许一次添加或删除单个服务器；这些操作简单地保持安全，因为至少在更改过程中有一台服务器与大多数服务器重叠。更复杂的更改是一系列单服务器的变更。Raft允许集群在更改期间继续正常运行，并且仅通过对基本共识算法的少数扩展即可实现成员身份更改。

- 全面讨论和实现一个完全基于共识的系统所需的其他组件，包括客户端交互和日志压缩。虽然我们不相信Raft的这些方面是特别新颖，但一个完整的描述对于可理解性和使其他人能够构建真实的系统都很重要。我们已经实施了一个完整的基于共识的服务，以探索和解决所有涉及的设计决策。

- Raft算法的安全性和证明形式化说明。形式化说明中的不同层面的细节描述有助于仔细推理算法，并阐明算法非正式描述中的细节。安全证明有助于建立人们对Raft正确性的信心。它还帮助其他希望扩展Raft的人，明确对其扩展的安全的影响。

本文已经为Raft提供了一个开源实现，详细内容见第10章。第2章说明了Raft的状态及问题并讨论了Paxos的优缺点；第3-6章说明了Raft算法，以及其成员变更扩展和日志压缩，以及客户端如何与Raft交互等问题；第7-10章对Raft的可理解性、正确性以及Leader选举和日志压缩的性能进行了评估；第11章对共识算法的相关工作进行了讨论。

下一章：Raft算法的目的 >>