分布式一致性算法：Raft 算法(论文翻译)

分布式一致性算法：Raft算法（论文翻译）本文章来自于阿里云云栖社区摘要：Raft算法是可以用来替代Paxos算法的分布式一致性算法，而且raft算法比Paxos算法更易懂且更容易实现。本文对raft论文进行翻译，希望能有助于读者更方便地理解raft的思想。点击我的博客查看原文。Raft算法是可以用来替代Paxos算法的分布式一致性算法，而且raft算法比Paxos算法更易懂且更容易实现。本文对raft论文进行翻译，希望能有助于读者更方便地理解raft的思想。如果对Paxos算法感兴趣，可以看我的另一篇文章：分布式系列文章——Paxos算法原理与推导摘要Raft是用来管理复制日志（replicatedlog）的一致性协议。它跟multi-Paxos作用相同，效率也相当，但是它的组织结构跟Paxos不同。这使得Raft比Paxos更容易理解并且更容易在工程实践中实现。为了使Raft协议更易懂，Raft将一致性的关键元素分开，如leader选举、日志复制和安全性，并且它实施更强的一致性以减少必须考虑的状态的数量。用户研究的结果表明，Raft比Paxos更容易学习。Raft还包括一个用于变更集群成员的新机制，它使用重叠的大多数（overlappingmajorities）来保证安全性。1介绍一致性算法允许多台机器作为一个集群协同工作，并且在其中的某几台机器出故障时集群仍然能正常工作。正因为如此，一致性算法在建立可靠的大规模软件系统方面发挥了关键作用。在过去十年中，Paxos[15,16]主导了关于一致性算法的讨论：大多数一致性的实现都是基于Paxos或受其影响，Paxos已成为用于教授学生一致性相关知识的主要工具。不幸的是，Paxos实在是太难以理解，尽管许多人一直在努力尝试使其更易懂。此外，其架构需要复杂的改变来支持实际系统。结果是，系统开发者和学生都在与Paxos斗争。在我们自己与Paxos斗争之后，我们开始着手寻找一个新的一致性算法，可以为系统开发和教学提供更好的基础。我们的方法是不寻常的，因为我们的主要目标是可理解性：我们可以为实际系统定义一个一致性算法，并以比Paxos更容易学习的方式描述它吗？在该算法的设计过程中，重要的不仅是如何让该算法起作用，还有清晰地知道该算法为什么会起作用。这项工作的结果是一个称为Raft的一致性算法。在设计Raft时，我们使用了特定的技术来提高可理解性，包括分解（Raft分离leader选举，日志复制和安全）和状态空间减少（相对于Paxos，Raft减少了不确定性程度和服务器之间彼此不一致的方式）。一项针对两个大学的43名学生的用户研究表明，Raft比Paxos更容易理解：在学习两种算法后，其中33名学生能够更好地回答关于Raft的问题。Raft在许多方面类似于现有的一致性算法（尤其是Oki和Liskov的ViewstampedReplication[29,22]），但它有几个新特性：Strongleader：在Raft中，日志条目（logentries）只从leader流向其他服务器。这简化了复制日志的管理，使得raft更容易理解。Leader选举：Raft使用随机计时器进行leader选举。这只需在任何一致性算法都需要的心跳（heartbeats）上增加少量机制，同时能够简单快速地解决冲突。成员变更：Raft使用了一种新的联合一致性方法，其中两个不同配置的大多数在过渡期间重叠。这允许集群在配置更改期间继续正常运行。我们认为，Raft优于Paxos和其他一致性算法，不仅在教学方面，在工程实现方面也是。它比其他算法更简单且更易于理解;它被描述得十分详细足以满足实际系统的需要;它有多个开源实现，并被多家公司使用;它的安全性已被正式规定和验证;它的效率与其他算法相当。本文的剩余部分介绍了复制状态机问题（第2节），讨论了Paxos的优点和缺点（第3节），描述了我们实现易理解性的方法（第4节），提出了Raft一致性算法（第5-8节），评估Raft（第9节），并讨论了相关工作（第10节）。2复制状态机一致性算法是在复制状态机[37]的背景下产生的。在这种方法中，一组服务器上的状态机计算相同状态的相同副本，并且即使某些服务器宕机，也可以继续运行。复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个leader的大规模系统，如GFS[8]，HDFS[38]和RAMCloud[33]，通常使用单独的复制状态机来进行leader选举和存储leader崩溃后重新选举需要的配置信息。Chubby[2]和ZooKeeper[11]都是复制状态机。复制状态机通常使用复制日志实现，如图1所示。每个服务器存储一个包含一系列命令的日志，其状态机按顺序执行日志中的命令。每个日志中命令都相同并且顺序也一样，因此每个状态机处理相同的命令序列。这样就能得到相同的状态和相同的输出序列。一致性算法的工作就是保证复制日志的一致性。每台服务器上的一致性模块接收来自客户端的命令，并将它们添加到其日志中。它与其他服务器上的一致性模块通信，以确保每个日志最终以相同的顺序包含相同的命令，即使有一些服务器失败。一旦命令被正确复制，每个服务器上的状态机按日志顺序处理它们，并将输出返回给客户端。这样就形成了高可用的复制状态机。实际系统中的一致性算法通常具有以下属性：它们确保在所有非拜占庭条件下（包括网络延迟，分区和数据包丢失，重复和乱序）的安全性（不会返回不正确的结果）。只要任何大多数（过半）服务器都可以运行，并且可以相互通信和与客户通信，一致性算法就可用。因此，五台服务器的典型集群可以容忍任何两台服务器的故障。假设服务器突然宕机，它们可以稍后从状态恢复并重新加入群集。它们不依赖于时序来确保日志的一致性：错误的时钟和极端消息延迟在最坏的情况下会导致可用性问题（译者注：言外之意是可以保证一致性）。在通常情况下，只要集群的大部分（过半服务器）已经响应了单轮远程过程调用，命令就可以完成;少数（一半以下）慢服务器不会影响整个系统性能。3Paxos存在的问题在过去十年里，LeslieLamport的Paxos协议[15]几乎成为一致性的同义词：它是课堂上教授最多的一致性协议，并且大多数一致性的实现也以它为起点。Paxos首先定义了能够在单个决策（例如单个复制日志条目）上达成一致的协议。我们将这个子集称为single-decreePaxos。然后Paxos组合该协议的多个实例以促进一系列决策，例如日志（multi-Paxos）。Paxos能够确保安全性和活性，并且支持集群成员的变更。它的正确性已被证明，并且在正常情况下是高效的。不幸的是，Paxos有两个显著的缺点。第一个缺点是Paxos非常难以理解。Paxos的描述晦涩难懂，臭名昭著（译者注：《ThePart-timeParliament》比较晦涩难懂，但是《PaxosMadeSimple》就比较容易理解）;很少有人成功地理解它，即使能理解也必须付出巨大的努力。因此，已有几个尝试用更简单的方式来描述Paxos[16,20,21]。这些描述集中在single-degreePaxos，但它们仍然具有挑战性。在对NSDI2012参会者的非正式调查中，我们发现很少有人喜欢Paxos，即使是经验丰富的研究人员。我们自己也跟Paxos进行了艰苦的斗争;我们也无法完全理解整个协议，直到阅读了几个更简单的描述和自己设计替代Paxos的协议，整个过程花了将近一年。Paxos晦涩难懂的原因是作者选择了single-degreePaxos作为基础。Single-decreePaxos分成两个阶段，这两个阶段没有简单直观的说明，并且不能被单独理解。因此，很难理解为什么该算法能起作用。Multi-Paxos的合成规则又增加了许多复杂性。我们相信，对多个决定（日志而不是单个日志条目）达成一致的总体问题可以用其他更直接和更明显的方式进行分解。Paxos的第二个问题是它不能为构建实际的实现提供良好的基础。一个原因是没有针对multi-Paxos的广泛同意的算法。Lamport的描述主要是关于single-decreePaxos;他描述了multi-Paxos的可能方法，但缺少许多细节。已经有几个尝试来具体化和优化Paxos，例如[26]，[39]和[13]，但这些彼此各不相同并且跟Lamport描述的也不同。像Chubby[4]这样的系统已经实现了类Paxos（Paxos-like）算法，但大多数情况下，它们的细节并没有公布。此外，Paxos的架构对于构建实际系统来说是一个糟糕的设计，这是single-decree分解的另一个结果。例如，独立地选择日志条目集合，然后再将它们合并到顺序日志中几乎没有任何好处，这只会增加复杂性。围绕日志设计系统是更简单和有效的方法，新日志条目按照约束顺序地添加到日志中。Paxos的做法适用于只需要做一次决策的情况，如果需要做一系列决策，更简单和快速的方法是先选择一个leader，然后让该leader协调这些决策。因此，实际的系统跟Paxos相差很大。几乎所有的实现都是从Paxos开始，然后发现很多实现上的难题，接着就开发了一种和Paxos完全不一样的架构。这样既费时又容易出错，而且Paxos本身晦涩难懂使得该问题更加严重。Paxos的公式可能可以很好地证明它的正确性，但是现实的系统和Paxos差别是如此之大，以至于这些证明并没有什么太大的价值。下面来自Chubby作者的评论非常典型：在Paxos算法描述和实现现实系统之间有着巨大的鸿沟。最终的系统往往建立在一个还未被证明的协议之上。由于以上问题，我们得出的结论是Paxos算法没有为系统实践和教学提供一个良好的基础。考虑到一致性问题在大规模软件系统中的重要性，我们决定尝试设计一个能够替代Paxos并且具有更好特性的一致性算法。Raft算法就是这次实验的结果。4为可理解性而设计在设计Raft算法过程中我们有几个目标：它必须提供一个完整的实际的系统实现基础，这样才能大大减少开发者的工作；它必须在任何情况下都是安全的并且在典型的应用条件下是可用的；并且在正常情况下是高效的。但是我们最重要的目标也是最大的挑战是可理解性。它必须保证能够被大多数人容易地理解。另外，它必须能够让人形成直观的认识，这样系统的构建者才能够在现实中进行扩展。在设计Raft算法的时候，很多情况下我们需要在多个备选方案中进行选择。在这种情况下，我们基于可理解性来评估备选方案：解释各个备选方案的难道有多大（例如，Raft的状态空间有多复杂，是否有微妙的含义）？对于一个读者而言，完全理解这个方案和含义是否容易？我们意识到这样的分析具有高度的主观性；但是我们使用了两种通用的技术来解决这个问题。第一个技术就是众所周知的问题分解：只要有可能，我们就将问题分解成几个相对独立的，可被解决的、可解释的和可理解的子问题。例如，Raft算法被我们分成leader选举，日志复制，安全性和成员变更几个部分。我们使用的第二个方法是通过减少状态的数量来简化状态空间，使得系统更加连贯并且尽可能消除不确定性。特别的，所有的日志是不允许有空洞的，并且Raft限制了使日志之间不一致的方式。尽管在大多数情况下我们都试图去消除不确定性，但是在某些情况下不确定性可以提高可理解性。特别是，随机化方法虽然引入了不确定性，但是他们往往能够通过使用相近的方法处理可能的选择来减少状态空间。我们使用随机化来简化Raft中的leader选举算法。5Raft一致性算法Raft是一种用来管理第2节中描述的复制日志的算法。图2是该算法的浓缩，可用作参考，图3列举了该算法的一些关键特性。图中的这些内容将在剩下的章节中逐一介绍。Raft通过首先选举一个distinguishedleader，然后让它全权负责管理复制日志来实现一致性。Leader从客户端接收日志条目，把日志条目复制到其他服务器上，并且在保证安全性的时候通知其他服务器将日志条目应用到他们的状态机中。拥有一个leader大大简化了对复制日志的管理。例如，leader可以决定新