Raft——一种易理解的一致性算法（一）

本文为RAFT一致性算法论文的译文，原文是《In search of an Understandable Consensus Algorithm (Extended Version)》，作者为 Diego Ongaro 和 John Ousterhout 。

摘要

Raft 是一种用于管理日志复制的一致性算法，它与 Paxos 算法在效果和性能上相近。但得益于其独特的结构，Raft 比 Paxos 更易于理解，且更易于在实际项目中落地。为了便于理解，Raft 将一致性算法的关键部分分为：leader 选取，日志复制，安全性。并且，Raft 通过使用更强的一致性以减少必须考虑的状态。因此，对于学生群体，Raft 比 Paxos 更易于学习，这在一项用户调查研究中得到了印证。此外，Raft 引入了新的机制——重叠多数（overlapping majorities）原则来保证安全地动态调整集群成员。

1 引言

一致性算法保证一组机器像一个整体一样工作，即使其中一些机器出现故障。因此，一致性算法是建立可靠的大规模软件系统的关键。在过去的十年中 Paxos 一直主导着有关一致性算法的讨论：大多数一致性算法的实现都基于它或者受它影响，并且 Paxos 也成为了教学中关于一致性知识的主要工具。

然而，尽管研究人员在降低它的复杂性方面做了许多努力，Paxos 依旧很难理解。并且，Paxos 需要经过复杂的修改才能应用于实际系统中。这些导致了系统构建者和学生都对 Paxos 十分头疼。

在被 Paxos 折磨之后，我们开始寻找一种新的在系统构建和教学上更好的一致性算法。与常规方法不同，我们的首要目标是让一致性算法易于理解：我们能不能定义一种面向实际系统的、比 Paxos 更容易学习的一致性算法呢？此外，我们希望这种算法直观易懂，这对一个系统构建者来说是十分必要的。对于一个算法，不仅要能够实现并且正常工作，还要清楚地明白其中的原理。

这项工作的结果是一种新的一致性算法，叫做 Raft。在设计 Raft 的过程中我们应用了许多专门的技巧来便于理解，包括算法分解（分为领导选取，日志复制和安全性）和约简状态空间（state space reduction，相对于 Paxos，Raft 减少了非确定性的程度和导致服务器之间不一致的可能）。在针对两所大学43名学生的用户调查中发现，Raft 比 Paxos 更易于理解：在学习了两种算法之后，回答问题时，其中的33个学生对 Raft 的问题回答的更好。

Raft 算法与现在一些已有的算法在某些地方很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是 Raft 有如下新特性：

• 强领导者（Strong Leader）：Raft 使用一种比其他算法更强的领导形式。例如，日志只从 leader 发送给其他服务器。这简化了对日志复制的管理，使得 Raft 更易于理解。
• 领导选取（Leader Selection）：Raft 使用随机定时器来选取 leader 。这种方式仅仅是在所有一致性算法都需要的心跳机制上进行些许改进，然而这使得 Raft 在解决冲突时更简单和快速。
• 成员调整（Membership Change）：在实现调整集群中成员的机制时，Raft 使用了新的联合一致性（joint consensus）的方法，这种方法中大多数不同配置的机器在转换关系的时候会交叠（overlap）。这使得在配置发生改变的时候，集群能够继续正常工作。

我们认为，在教学和实际实现方面，Raft 比 Paxos 和其他算法更优秀。Raft 比其他算法更简单，更易于理解；它能满足一个实际系统的需求；它拥有许多开源的实现并且被许多公司使用；它的安全特性已经被证明；并且它的效率和其他算法相比也具有竞争力。

这篇论文剩下的部分会讲如下内容：复制状态机（replicated state machine）问题（第2节），讨论 Paxos 的优缺点（第3节），讨论为了使算法更便于理解所用的方法（第4节），陈述 Raft 一致性算法（第5~8节），评价 Raft 算法（第9节），对相关工作的讨论（第10节）。

2 复制状态机（Replicated State Machine）

一致性算法是在复制状态机的背景下提出来的。在这个方法中，一组服务器的状态机计算产生相同状态的副本，即使其中一些服务器崩溃，这组服务器也还能继续运行。复制状态机用于解决分布式系统中多种容错相关的问题。例如，GFS，HDFS和 RAMCloud 之类大规模系统都是用独立的复制状态机来管理 leader 选取，以及存储配置信息来应对 leader 崩溃的情况。 Chubby 和 ZooKeeper 就是使用复制状态机的例子。

图1. 复制状态机的架构。一致性算法管理来自客户端的日志，日志中包含了客户端的状态机指令。 状态机执行的日志中命令的顺序都是一致的，因此会得到相同的执行结果。

如图1所示，复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机通过计算得到相同的状态，最后的输出结果也就一致了。

一致性算法的工作就是保证复制的日志一致。在一台服务器上，一致性模块接收到客户端的指令后把指令写入到日志中，并与其他服务器上的一致性模块通信，以确保每一个日志最终包含一致的请求序列，即使有某些服务器宕机。一旦这些指令被正确的复制了，每一个服务器的状态机都会按同样的顺序去执行它们，然后将结果返回给客户端。最终，这些服务器看起来就像一台可靠的状态机。在实际系统中应用的一致性算法一般有以下特性：

• 确保安全性（从来不会返回一个错误的结果），即使在所有的非拜占庭（Non-Byzantine）情况下，包括网络延迟、分区、丢包、冗余和乱序。
• 高可用性，只要集群中的大部分机器都能运行，可以互相通信并且可以和客户端通信，这个集群就可用。因此，一般来说，一个拥有 5 台机器的集群可以容忍至多两台机器宕机。服务器可以通过备份还原并在此加入到集群中。
• 保证一致性且不依赖时序，在最坏的情况下，时钟错误和极端的消息延迟才会引起可用性问题。
• 通常情况下，在单轮 RPC 中，只要集群中大多数节点对 RPC 做出响应，那么这条指令就算完成了，一小部分慢的服务器不会影响系统的整体性能。