Raft: 寻找易于理解的一致性算法<下>

原文地址

6. 集群成员变更

到目前为止，我们都假定集群配置(参与到一致性算法的服务器)是固定不变的。在实际中，偶尔需要改变配置，比如说当某个服务器故障后更换它，或者改变复制的程度。虽然可以通过将整个集群下线来完成这些变更，但是这么做会导致集群在转换的这段时间内不可用。此外，如果有需要人工处理的步骤，可能会操作失误。为了避免这些问题，我们决定自动化配置变更的过程，并将它集成到Raft算法中。

split.jpg

要让配置变更的过程安全，必须不能出现这样的时间点：同一个term中出现两个leader。不幸的是，所有直接从旧配置变更到新配置的方案都无法避免这个问题。由于不可能一次性更换所有的服务器，集群在转换的过程中可能会分裂为两个独立的大多数(如图10所示)。

为了保证正确性，配置变更必须使用两阶段的方案。有很多实现两阶段的方法，比如，一些系统[^]在第一个阶段将旧的配置禁用，这样系统就无法处理客户请求了；然后在第二阶段开启新的配置。在Raft中，集群首先切换到一个过渡的配置，我们称作联合一致；一旦联合一致提交了，系统再转换到新的配置。联合一致包括了旧的和新的配置：

• 日志条目被复制到所有的服务器中，包括旧的和新的。
• 两个配置中的任何服务器都可能成为leader。
• 达成一致(用于选举和提交日志条目)需要两个配置中各自的大多数成员的承认。

联合一致让每个=服务器可以在不同的时间进行转换，同时不影响正确性。此外，联合一致让集群能在配置变化的过程中继续服务客户端请求。

change.jpg

集群配置信息通过复制日志中一个特殊的条目来存储和通信；图11展示了配置变化的过程。当leader收到请求要将配置从C_old变更至C_new，它会将联合一致的配置(图中的C_old,new)存储为一个日志条目并按照之前说明的方法复制它。其他服务器一旦受到了这个日志条目，他就会在后续的决定中使用这个配置(服务器总是使用日志中最新的配置信息，无论这条日志是否提交)。这意味着leader会使用C_old,new的信息来判断C_old,new是否已经提交。如果leader崩溃了，可能从C_old或者C_old,new中选举出一个新leader，取决于获胜的candidate是否收到了C_old,new这个条目。无论那种情况，C_new都不能在这个过程中单独做决定。

一旦C_old,new这个条目提交了，C_old和C_new都不能在没有对方同意的情况下做决定，Leader完整属性保证了只有存储了C_old,new条目的服务器才能被选择为leader。此时，leader就可以安全的创建一条描述C_new的日志条目并复制到集群中。同样的，每个服务器一旦看到这个条目就会立即使用它。当新配置在C_new中提交了，旧的配置就无关紧要了，不在新配置中的服务器就可以关机了。如图11中所示，不存在C_old和C_new都能够单独做决定的时刻；这保证了正确性。

配置变更中还有三个问题需要考虑。第一个是，新的服务器在开始的时候可能没有存储任何日志条目。如果它们以这种状态加入到集群中，可能要花费相当的时间来赶上当前的日志进度，在这段时间内它们都无法提交新的日志条目。为了避免可用性受损，Raft在配置变化之前引入了一个额外的阶段，这个阶段中新的服务器会以不投票成员的身份加入集群(leader会把日志复制给它们，但不将它们认为是大多数)。一旦新的服务器追上了集群中的其他成员，配置变更的过程就按照之前描述的那样展开。

第二个问题是，集群leader可能不在新的配置中。这种情况下，在提交了C_new后，leader会立即退下来(转换为follower)。这意味着在一段时间内(提交C_new期间)，leader管理着一个不包括它自己的集群；它复制日志条目，但是不把自己当作大多数。leader的转换发生在C_new提交后，因为从此时开始新的配置能够独立运作了(它会从C_new中选举一个leader)。在这之前，可能出现只有C_old中的服务器才能成为leader的情况。

第三个问题是，删除的服务器(不在C_new中)可能会破坏集群。这些服务器不会收到心跳，因此它们会超时并开始新的选举。它们将发送带有新的term值的RequestVote RPC，这会导致当前leader转换到follower状态。新的leader最终会被选举出来，但是被删除的服务器会再次超时，这个过程会重复发生，导致极差的可用性。

为了组织这种现象，当服务器认为当前存在leader的时候，它们会拒绝RequestVote RPC。尤其是，当服务器在最小选举超时时间内收到了RequestVote RPC时，它不会更新自己的term或者赞同此次投票。这不会影响正常的选举，在正常选举中，每个服务器至少等待一个最小选举超时时间后才开始新的选举。然而，它可以帮助避免让被删除的服务器破坏当前集群：如果leader能够获取到集群的心跳，它不会因为一个大term值而解雇自己的leader身份。

7. 日志压缩

Raft的日志会随着日常处理客户请求而不断增大，在实际系统中，不可能让日志无限的增长下去。日志增大会占用更多的空间，并需要更多时间来响应。如果没有某种清除日志中堆积的陈旧信息的机制，这最终会导致可用性问题。

做快照是最简单的压缩方案。使用快照的方式，整个系统的状态被写入到稳定存储中，然后所有在这个快照时间点之前的日志都被丢弃。Chubby和ZooKeeper中都使用了快照，本小节剩余部分讲述Raft中的快照。

使用增量方案来压缩也是可行的，比如日志清理[^]和log-struct merge trees[^]。这种操作每次处理一小部分数据，这样就把压缩的负担平均的分摊到不同时间内。首先选择一部分数据，其中累计了很多被删除被覆盖的对象，然后重新写入其中的有效对象，并释放这部分数据。和快照相比，这需要大量额外的机制和复杂性，快照总是操作所有数据，简化了处理。使用日志清理需要对Raft进行改动；使用LSM的方式，状态机可以直接使用相同的接口来实现LSM和快照。

snapshot.jpg

图12展示了Raft中快照的基本思想。每个服务器单独做自己的快照，快照只包含已经提交的日志条目。大多数情况下，当前状态机的状态会一并写入到快照中。Raft的快照中还包括了一小部分元信息：最近的index指的是由快照取代的日志中最后一个条目的index，最近的term指的是这个条目的term。它们被保留下来以用于支持后续的第一个日志条目的AppendEntries一致性检查，因为这个条目需要之前的日志index和term。为了支持集群成员变更(第6章)，快照也包括了最近的配置信息，作为最后的日志条目index。一旦服务器完成了快照的写入，它就可以删除所有在快照包括的最后index之前的所有日志，以及所有之前的快照。

虽然正常情况下服务器都是单独做快照，leader偶尔也会需要把快照发送给落后的follower。当leader丢弃了一条它需要发送给follower的日志条目时，就需要发送快照了。幸运的是，这种情况不会出现在正常操作中：紧跟leader的follower会已经包含了这个条目。然而，异常慢的follower或者一个新加入集群(第6章)的服务器可能不会包括此条目。更新这种follower的方法就是通过网络发送快照。

install.jpg

leader使用一个叫做InstallSnapshot的RPC来发生快照给那些落后的follower；如图13所示。当一个follower收到了这个RPC，它必须决定如何处理自己当前的日志。通常快照会包含当前日志没有的信息，这种情况下，follower会丢弃所有它自己的日志；它们被快照取代并可能包含着和快照冲突的条目。如果follower收到的快照只包括了它自己日志的前面一部分(由于重传或者错误)，那么被快照覆盖的那部分日志会被删除，剩余的部分则继续保留下来。

快照机制背离了Raft的强leader原则，因为follower可以在不知道leader的情况下接收快照。然而我们认为这个背离是有道理的。在有一个帮助集群达成一致的leader的情况下，做快照时一致性已经达到，没有冲突的决定。数据仍然只会从leader流向follower，只有follower可以重组它们的数据。

我们考虑过一个替代的基于leader的方案，其中只有leader会创建快照，leader把快照发送给所有的follower。然而这么做有两个劣势。第一，给每个follower发送快照会耗费大量的网络带宽并减慢快照处理过程。每个follower都已经有了足够的信息来创建它自己的快照，并且在本地创建快照比通过网络接收快照代价低得多。第二，leader的实现会变得更加复杂。比如，leader可能需要并行的发送快照和新的日志条目给follower，只有这样才不会阻塞客户请求。

还有两个问题会影响到快照的性能。第一，服务器必须决定何时做快照。如果服务器做快照过于频繁，会浪费磁盘的带宽的用电量(energy)；如果做快照过于不频繁，则面临着耗尽磁盘空间的风险，并增加了重启后加载日志的耗时。一个简单的策略是当日志大小达到一个固定值的时候进行快照。如果这个值设置的比预期快照的大小要大得多，那么生成快照过程中的磁盘带宽就会很小。

第二个问题是写快照可能会用很长时间才能完成，我们不想让这个过程影响到日常操作。解决方案是使用写时复制(copy-on-write)技术，这样新的更新可以在不影响写快照的情况下处理。比如，状态机天然的支持这种技术。作为替代方法，操作系统的写时复制支持(比如，linux上的fork)也可以用来创建一个内存中的快照(我们的实现使用了这个方案

8. 客户端交互

这一章描述客户端如何和Raft交互，包括客户端如何找到集群的leader，已经Raft是怎么支持线性语义的[^]。这些问题适用于所有一致性系统，Raft的解决方案和其他系统类似。

Raft的客户端把所有请求都发送给leader。当一个客户端刚启动后，它会随机选择一个服务器去连接。如果这个服务器不是leader，服务器会拒绝客户端的请求并告诉客户端它所知道的最近的leader(AppendEntries请求中包含了leader的网络地址)。如果leader崩溃了，客户端请求会超时；然后客户端就会再次随机选择一个服务器去连接。

我们对Raft的目标是实现线性语义(每个操作看上去都是立即执行，而且只执行一次，在操作的唤醒和响应之间)。然而，按照目前所描述的，Raft可能会多次执行同一个指令：比如说，leader在提交日志条目后，响应客户之前崩溃了，这个客户端会重新发送这个指令给新的leader，导致一个指令被执行第二次。解决方案是让客户端给每个指令分片一个唯一的序列号。这样的话，状态机就可以追踪每个客户端最近的一条指令，以及这个指令的响应信息。如果它收到一个已经执行过的序列号，那么就可以立即响应这个指令而不用再次执行。

处理只读操作不需要写任何数据到日志中。然而如果不采用一些额外的措施，可能会有返回陈就数据的风险，因为响应请求的leader可能已经被其他更新的leader所取代，而它自己毫不知情。线性读取一定不能够返回陈旧数据，Raft使用两种不需要读取日志的措施来防止这种问题。首先，leader必须知道最近被提交的条目是哪一条日志。Leader完整属性保证了leader拥有所有提交的条目，但是在term开始的时候，leader可能不知道哪些是已经提交的。为了找出这些条目，leader需要提交一个当前term的条目。Raft的解决方法是，让每个leader在term开始的时候提交一个空的条目。第二，leader在处理读请求之前必须查看自己是否已经被解雇了(如果有更新的leader被选出来，那么它自己的信息可能已经是过时的)。Raft处理这个问题的方法是，让leader在响应读请求之前和集群中的大多数服务器交换心跳消息。或者说，leader可以依靠心跳机制来维持租约(lease)[^]，但这么做需要时间上的保证(它假设时钟的不一致是有限的)。

9. 实现和评测

在用于存储RAMCloud[^] 配置信息和用于协调RAMCloud自动故障恢复的状态机中，我们实现了Raft。Raft的实现包括大约2000行C++代码。源代码可以免费获取^[1]。也有其他大概25种独立第三方实现的Raft，处于不同的开发阶段，都是基于本文草稿的实现。除此之外，一些公司在部署基于Raft的系统[^]。

本章剩余部分使用三个标准来评估了Raft：易懂性，正确性，性能。

9.1 易懂性

为了测试Raft相对于Paxos的易懂性，我们在斯坦福大学的高级操作系统课程和伯克利大学的分布式计算课程的高年级学生中进行了调研。我们录制了关于Raft的课件视频，以及一个Paxos的视频，并准备了相应的测试题目。Raft的课件包括了本文中除了日志压缩外的所有部分；Paxos课件中涵盖了足够的材料用于创建一个同等的状态机，包括单个Paxos，多Paxos，配置变更，以及一些实际系统中的优化手段(比如leader选举)。测试题目检查对算法的基本理解，也要求学生能够推理一些边缘情况。每个学生都先观看一个视频，回答问题，然后再观看第二个视频，再回到问题。一半学生先进行Paxos部分，另一半学生先进行Raft部分，以此来消除(account for?)在前面一部分获取的经验对后面的影响。我们比较了参与者在每个问题上的得分，以此来决定哪一部分学生对Raft理解的更好。

table.jpg

我们想要尽可能的公平对Raft和Paxos进行比较。实验对Paxos是有利的：43个学生中有15个之前了解过Paxos，并且Paxos视频比Raft视频长14%。如表1中的总结，我们采取了一些措施来减轻偏见。我们所有的材料是公开的[^]。

score.jpg

平均来看，参与者的Raft测试结果比Paxos测试结果高4.9分(取出一个最高分60，Raft平均数据是25.7，Paxos平均分是20.8)；图14列出了它们各自的分数。一对t-测试显示，95%的可信度下，Raft的真实得分平均要比Paxos至少高2.5分。

我们也建立了一个线性回归模型来预测一个新的学生的测验成绩，基于以下三个因素：他们使用的是哪个小测验，之前对Paxos的经验，和学习算法的顺序。模型显示，对小测验的选择会产生12.5分的差别在对Raft的好感度上。这显著的高于之前的4.9分，因为很多学生在之前都已经有了对于Paxos的经验，这相当明显的帮助Paxos，对Raft 就没什么太大影响了。但是奇怪的是，模型预测对于先进行 Paxos小测验的人而言，Raft的小测验得分会比Paxos低6.3分；我们不知道为什么，但这在统计学上是这样的。

explain.jpg

我们同时也在测验之后调查了参与者，他们认为哪个算法更加容易实现和解释；这个的结果在图15上。压倒性的结果表明Raft算法更加容易实现和解释(41人中的33个)。但是，这种自己报告的结果不如参与者的成绩更加可信，并且参与者可能因为我们的Raft更加易于理解的假说而产生偏见。

关于Raft用户调研的更详细讨论可以参考^[]。

9.2 正确性

在第5章，我们已经进行了一个正式的说明，和对一致性机制的安全性证明。这个正式说明通过TLA+让图2中的信息非常清晰。它大约有400行并且充当了证明的主题。同时对于任何想实现的人也是十分有用的。我们非常机械的通过TLA证明系统证明了Log完成属性。然而，这个证明依赖的约束前提还没有被机械证明(例如，我们还没有证明这个说明中的类型安全type safety)。而且，我们已经写了一个非正式的证明关于状态机安全性质是完备的，并且是相当清晰的(大约3500个词)。

9.3 性能

Raft的性能和其他一致性算法如Paxos差不多。对性能影响最大的是复制新的日志条目。Raft采取的方式是发送最少的消息(一轮请求从leader发送到集群中一半的服务器)。进一步提升Raft的性能也是可能的。比如说，支持批量和流式处理请求来获取更高吞吐和低延迟是简单的。其他算法中提出了各种优化手段；其中很多都可以应用到Raft中，我们把这些留到以后。

我们使用自己实现的Raft版本来测量Raftleader选举的性能以及回答两个问题。第一，选举过程是否能够很快收敛？第二，当leader崩溃后，最小的不可用时间可以缩短到什么程度？

test.jpg

为了测量leader选举，我们重复的让一个5节点集群的leader崩溃，并记下需要多长时间来检测到崩溃并重新选举一个leader(图16所示)。为了产生最坏的情形，每次尝试的服务器都着不同的日志长度，这样有些candidate就不够资格成为leader。更进一步，为了促成投票分裂，我们的测试脚本触发leader在终止自己的运作之前发送一轮广播心跳消息(这近似leader在崩溃前发送新日志条目给follower的行为)。leader在心跳间隔之间随机不均匀的崩溃，在所有测试中心跳间隔都被设置为选举超时的一半。因此，可能的最小的不可用时间大约是最小心跳时间的一半。

图16中上面的图表说明了一小部分随机化的选举超时就可以避免选举中的投票分裂。在我们的测试中，如果没有随机化因素，由于投票分裂，leader选举会持续占用超过10s。仅仅增加5ms的随机就可以大大改善这种情况，使得平均不可永久降为287ms。使用更多的随机可以改善最坏情况下的表现：50ms的随机可以让最坏的竞争时间(超过1000尝试)降低为500ms。

图16中下面的图表展示了不可用时间随着选举超时的降低而降低。选举超时在12-24ms时，平均需要35ms来选举一个leader(最长的是152ms)。然而，超时值设置如此之低违背了Raft的时序要求：leader难以在其他服务器开始选举之前发生心跳，这会导致不必要的leader变更以及降低整体的可用性。我们建议使用一个保守的选举超时比如150-300ms；这样就不太可能引发不必要的leader变更并且仍然可以提供高可用性。

10. 相关工作

很多关于一致性算法的工作已经发表，其中很多都可以归以下面类别：

• Lamport关于Paxos的原始描述，和尝试描述的更清晰的论文。
• 关于Paxos的更详尽的描述，补充遗漏的细节并修改算法，使得可以提供更加容易的实现基础。
• 实现一致性算法的系统，例如Chubby，ZooKeeper和Spanner。对于Chubby和Spanner的算法并没有公开发表其技术细节，尽管他们都声称是基于Paxos的。ZooKeeper的算法细节已经发表，但是和Paxos有着很大的差别。
• Paxos可以应用的性能优化。
• Oki和Liskov的Viewstamped Replication(VR)，一种和Paxos差不多的替代算法。原始的算法描述和分布式传输协议耦合在了一起，但是核心的一致性算法在最近的更新里被分离了出来。VR使用了一种基于领导人的方法，和Raft有很多相似之处。

Raft和Paxos最大的不同之处就在于Raft的强leader特性：Raft使用leader选举作为一致性协议里必不可少的部分，并且将尽可能多的功能集中到了leader身上。这样就可以使得算法更加容易理解。例如，在Paxos中，leader选举和基本的一致性协议是正交的：leader选举仅仅是性能优化的手段，而且不是一致性所必须要求的。但是，这样就增加了多余的机制：Paxos同时包含了针对基本一致性要求的两阶段提交协议和针对leader举的独立的机制。相比较而言，Raft就直接将leader选举纳入到一致性算法中，并作为两阶段一致性的第一步。这样就减少了很多机制。

像Raft一样，VR和ZooKeeper也是基于leader的，因此他们也拥有一些Raft的优点。但是，Raft比VR和ZooKeeper拥有更少的机制因为Raft尽可能的减少了非leader的功能。例如，Raft中日志条目都遵循着从leader发送给其他人这一个方向：附加条目RPC是向外发送的。在VR中，日志条目的流动是双向的(leader可以在选举过程中接收日志)；这就导致了额外的机制和复杂性。根据ZooKeeper公开的资料看，它的日志条目也是双向传输的，但是它的实现更像Raft。

和上述我们提及的其他基于一致性的日志复制算法中，Raft的消息类型更少。例如，我们数了一下VR和ZooKeeper使用的用来基本一致性需要和成员改变的消息数(排除了日志压缩和客户端交互，因为这些都比较独立且和算法关系不大)。VR和ZooKeeper都分别定义了10中不同的消息类型，相对的，Raft只有4中消息类型(两种RPC请求和对应的响应)。Raft的消息都稍微比其他算法的要信息量大，但是都很简单。另外，VR和ZooKeeper都在leader改变时传输了整个日志；所以为了能够实践中使用，额外的消息类型就很必要了。

Raft的强leader模型简化了整个算法，但是同时也排斥了一些性能优化的方法。例如，平等主义Paxos(EPaxos)在某些没有leader的情况下可以达到很高的性能。平等主义Paxos充分发挥了在状态机指令中的交换性。任何服务器都可以在一轮通信下就提交指令，除非其他指令同时被提出了。然而，如果指令都是并发的被提出，并且互相之间不通信沟通，那么EPaxos就需要额外的一轮通信。因为任何服务器都可以提交指令，所以EPaxos在服务器之间的负载均衡做的很好，并且很容易在WAN网络环境下获得很低的延迟。但是，他在Paxos上增加了非常明显的复杂性。

一些集群成员变换的方法已经被提出或者在其他的工作中被实现，包括Lamport的原始的讨论，VR和SMART。我们选择使联合一致(joint consensus)的方法因为它对一致性协议的其他部分影响很小，这样我们只需要很少的一些机制就可以实现成员变换。Raft没有采用Lamport的基于α的方法是因为它假设在没有领导人的情况下也可以达到一致性。和VR和SMART相比较，Raft的重新配置算法可以在不限制正常请求处理的情况下进行；相比较而言，VR需要停止所有的处理过程，SMART引入了一个和α类似的方法，限制了请求处理的数量。和VR、SMART比较而言，Raft的方法同时需要更少的额外机制来实现。

11. 总结

算法的设计通常会把正确性，效率或者简洁作为主要的目标。尽管这些都是很有意义的目标，但是我们相信，可理解性也是一样的重要。在开发者把算法应用到实际的系统中之前，这些目标没有一个会被实现，这些都会必然的偏离发表时的形式。除非开发人员对这个算法有着很深的理解并且有着直观的感觉，否则将会对他们而言很难在实现的时候保持原有期望的特性。

在这篇论文中，我们尝试解决分布式一致性问题，但是一个广为接受但是十分令人费解的算法Paxos已经困扰了无数学生和开发者很多年了。我们创造了一种新的算法Raft，显而易见的比Paxos要容易理解。我们同时也相信，Raft也可以为实际的实现提供坚实的基础。把可理解性作为设计的目标改变了我们设计Raft的方式；这个过程是我们发现我们最终很少有技术上的重复，例如问题分解和简化状态空间。这些技术不仅提升了Raft的可理解性，同时也使我们坚信其正确性。

12. 鸣谢

这项研究必须感谢以下人员的支持：Ali Ghodsi，David Mazie res，和伯克利CS294-91课程、斯坦福CS240课程的学生。Scott Klemmer帮我们设计了用户调查，Nelson Ray建议我们进行统计学的分析。在用户调查时使用的关于Paxos的幻灯片很大一部分是从Lorenzo Alvisi的幻灯片上借鉴过来的。特别的，非常感谢DavidMazieres和Ezra Hoch，他们找到了Raft中一些难以发现的漏洞。许多人提供了关于这篇论文十分有用的反馈和用户调查材料，包括Ed Bugnion，Michael Chan，Hugues Evrard，Daniel Giffin，Arjun Gopalan，Jon Howell，Vimalkumar Jeyakumar，Ankita Kejriwal，Aleksandar Kracun，Amit Levy，Joel Martin，Satoshi Matsushita，Oleg Pesok，David Ramos，Robbert van Renesse，Mendel Rosenblum，Nicolas Schiper，Deian Stefan，Andrew Stone，Ryan Stutsman，David Terei，Stephen Yang，Matei Zaharia以及24位匿名的会议审查人员(可能有重复)，并且特别感谢我们的领导人 Eddie Kohler。Werner Vogels 发了一条早期草稿链接的推特，给Raft带来了极大的关注。我们的工作由Gigascale系统研究中心和Multiscale系统研究中心给予支持，这两个研究中心由关注中心研究程序资金支持，一个是半导体研究公司的程序，由STARnet支持，一个半导体研究公司的程序由MARCO和DARPA支持，在国家科学基金会的0963859号批准，并且获得了来自Facebook，Google，Mellanox，NEC，NetApp，SAP 和 Samsung 的支持。Diego Ongaro由Junglee公司，斯坦福的毕业团体支持。

---

1. LogCabin souce code. http://github.com/logcabin/logcabin ↩