type
Post
status
Published
date
Nov 30, 2022
slug
raft-paper
summary
学习 Raft 必备，熟读讲解核心思想和实现的论文你就可以自己实现一个 Raft 库
tags
论文
分布式
共识算法
category
技术分享
icon
password
Property
Dec 1, 2022 05:58 AM
背景
因为最近在学习分布式共识算法 Raft，找到了官网上的一篇论文，粗读一遍后发现很有帮助，所以有了翻译的想法，也当做自己学习的输出之一。
官网是学习 Raft 的不二之选，有很多宝藏需要去挖掘，放上连接
论文原文也一并贴出来
摘要
Raft 是管理备份日志的共识算法。它跟 (Multi-)Paxos 的结果一致，效率一致，但是结构不同，这点让 Raft 比 Paxos 更易于理解，也为构建实际系统提供了更好的基础。为了提高可理解性，Raft 不仅把共识算法中的关键组成部分进行了拆分，比如领导者选举、日志复制和数据安全，它还执行了更强的一致性，以减少必须考虑的状态数量。一个用户研究表明，Raft 比 Paxos 更易于学生来学习。Raft 还为成员变动引入新的处理机制，这个机制采用重叠多数来保证数据安全。
1 介绍
共识算法可以让一组机器像一个统一团体一样来运行，这样当其中的某些机器发生故障时，团体仍能继续工作。因此，共识算法在构建可靠的大规模软件系统中扮演了关键的角色。Paxos 在过去的十年中对共识算法的研讨里最具影响力，大多数共识算法的实现方案或基于 Paxos 算法或受它影响，并且它成为了教授学生共识知识的主要载体。
不幸的是，尽管有很多让它更加容易上手的尝试，Paxos 还是太难理解了，而且如果要用来支持实用的软件系统，它的架构需要复杂的修改才行，系统开发者和学生都在尝试理解和使用 Paxos 时苦苦挣扎。
在自己与 Paxos 苦苦斗争之后，我们开始着手寻求一个能够给系统开发和教育提供更好基础的共识算法。我们的方法注定不寻常，因为我们的主要目标是可理解性：我们是否能够为实用的软件系统提供一种新的共识算法的定义并且用明显比 Paxos 更容易学习的方式描述出来么？ 此外，我们还想要这个算法能够促进对系统开发者来说至关重要的直觉的发展。重要的是，不仅要让算法发挥作用，而且要让人知道它为什么能够发挥作用。
这项工作的成果就是被命名为 Raft 的共识算法。设计 Raft 的时候，我们应用了特定的技术来提供可理解性，包括分解（Raft 将领导者选举、日志复制和数据安全分开）和减少状态空间（相比 Paxos，Raft 减少了非确定性程度和服务器之间产生不一致的途径）。在两所大学共计 43 名学生的用户调查中显示，Raft 明显比 Paxos 更容易理解：在学习了两种算法之后，33 名学生相比解答 Paxos 的问题能够更好的解答 Raft 的。
Raft 在许多方面与现有的共识算法相似（最显著的是 Oki 和 Liskov 的 Viewstamped
复制），但它有几个新的特点：
- 更强的领导者：Raft 采用了比其他共识算法更强的领导模式。比如，日志条目只能从领导者流向其他服务器，这让复制日志的管理更加简单也让 Raft 更易于理解。
- 领导选举：Raft 采用随机定时器来选举领导者，这只需要在已经被共识算法普遍需要的心跳机制上添加少量的新机制即可实现，还能简单快捷的解决选举冲突。
- 成员变动：Raft 在变更集群中的服务器集的机制中使用了一种新的联合共识方法，这种方法中两个不同配置的大多数在转换过程中是重叠的，这让集群能够在配置变动的时候继续正常运作。
我们相信无论是出于教育目的还是作为实现基础，Raft 都优于 Paxos 和其他共识算法。它比其他算法更简单也更容易理解，它的描述很完整，足以满足实际系统的需要，它有几个被一些公司使用的开源实现，它的安全性已被正式规定和证明，它的效率可与其他算法相媲美。
本文的其余部分介绍了复制状态机问题（第 2 节），讨论了 Paxos 的优点和缺点（第 3 节），描述了达成可理解性的一般方法（第 4 节），描述了 Raft 共识算法（第 5-8 节），评估了Raft的性能（第 9 节），并讨论了 Raft 相关工作（第 10 节）。
2 复制状态机（Replicated state machine）
共识算法通常出现在复制状态机的背景下。在复制状态机的做法中，一组服务器上的状态机计算同样状态的相同副本，并且即使部分服务器宕机，也能继续正常运行。复制状态机被用来解决分布式系统中的各种容错问题。比如，拥有单一集群领导者的大规模系统，如GFS、HDFS 和 RAMCloud，通常使用单独的复制状态机来管理领导者的选举，并存储在领导者崩溃后为了工作所必须的配置信息。复制状态机的例子包括 Chubby 和 Zookeeper。
复制状态机通常使用复制日志来实现，如图 1 所示。每个服务器存储了包含一系列命令的日志，服务器中的状态机按顺序执行这些命令，每条日志副本都以相同的顺序包含相同的命令，所以每个状态机都以相同的顺序处理这些命令。由于状态机具有确定性，每个状态机都计算出相同的状态和相同的输出序列。
保持复制日志的一致性是共识算法的工作。服务器上的共识模块接收来自客户端的命令，并将它们添加到服务器的日志中，它还和同其他服务器上的共识模块通信以确保，即使在部分服务器发生了故障的情况下，最终每个日志都以相同的顺序包含了相同的请求。一旦命令被正确复制出来，每个服务器的状态机都按照日志顺序来处理他们，输出结果并将结果返回给客户端。这样，这些服务器似乎就形成了一个单一的、高度可靠的状态机。
实际系统中的使用的共识算法通常具有以下的属性：
- 在所有非拜占庭的条件下，包括网络延迟、分区以及数据包丢失、重复和重新排序，它们都能确保数据安全（永远不会返回错误的结果）
- 只要大多数服务器都在运行，并能相互通信且能与客户通信，它们就能完全发挥作用（可用）。因此，一个由五台服务器组成的典型集群可以容忍任何两台服务器的故障。服务器被假定以停止的方式失能，它们稍后可能从可靠存储中的状态中恢复并重新加入集群。
- 它们不依赖时间来确保日志的一致性，因为时钟故障和极端的消息延迟在最坏的情况下会导致可用性问题。
- 在一般情况下，只要集群中的大多数人对单轮远程过程调用作出反应，命令就可以完成；少数慢的服务器需要能够不影响整个系统的性能。
3 Paxos 有什么问题
在过去的十年里，Leslie Lamport 的 Paxos 协议几乎成了共识的代名词：它是课程中最常教授的协议，大多数共识的实现都以它为起点。Paxos 先是定义了一个能够就单一决定达成协定的协议，例如单一的复制日志条目。我们把这个子集称为单决策的 Paxos。然后，Paxos 将这个协议的多个实例结合起来，以促进一系列的决定（可以称为 multi-Paxos），如一条日志（而不是一个日志条目）。Paxos 既保证了安全性，又保证了有效性，而且它支持集群成员的变化。它的正确性已被证明，而且在正常情况下是高效的。
然而，Paxos 有两个明显的缺点。第一个缺点是 Paxos 特别难以理解。完整的论文解释是出了名的晦涩难懂，很少有人能成功地理解它，即便能也是在付出巨大努力之后。因此，已经有一些人试图用更简单的术语来解释 Paxos，这些解释集中在单决策子集上，可是它们仍然很有挑战。在对 NSDI 2012 的与会者进行的非正式调查中，我们发现很少有人对 Paxos 感到满意，即使在经验丰富的研究人员中。我们自己也在 Paxos 中挣扎，在阅读了几个简化的解释和设计我们自己的替代协议后，我们才能够理解完整的协议，这个过程花了将近一年的时间。
我们认为 Paxos 的晦涩来自于它选择单决策子集作为基础。单决策的 Paxos 是费解而微妙的：它分为两个阶段，没有简单直观的解释，且不能独立分开来理解，正因为如此，要深入理解单决策协议为什么能工作是很困难的。multi-Paxos 的组成规则增加了大量的额外复杂性和微妙性。我们相信就多个决定达成共识的整体问题（即一个日志而不是一个条目）可以通过其他更直接和明显的方式进行分解。
Paxos 的第二个问题是，它没有为构建实际的实现提供一个良好的基础。原因之一是没有广泛认同的multi-Paxos 的算法。Lamport 的描述主要是关于单决策 Paxos 的，他勾画了 multi-Paxos 的可能实现方法，但缺少许多细节。已经有一些尝试对 Paxos 进行充实和优化，但这些尝试彼此不同，也与Lamport 的草图不同。像 Chubby 这样的系统已经实现了类似 Paxos 的算法，但大多数情况他们的细节还没有公布出来。
此外，Paxos 的架构对于构建实用系统来说是一个糟糕的架构，这是单决策 Paxos 的两阶段分解的另一个后果。例如，选择一组独立的日志条目，然后将它们拼接成一个连续的日志，这没有什么好处，只会增加复杂性。围绕日志去设计一个系统更简单、更有效，新的条目是以限定的顺序依次添加到日志中的。另一个问题是，Paxos 在核心部分使用对称的点对点方法（尽管它最终建议采用弱的领导形式作为性能优化），这在只做一个决定的简单世界里是有意义的，但很少有实际的系统使用这种方法。如果必须做出一系列的决定，那么首先选举一个领导者，然后由领导者来协调这些决定，这样会更简单、更快速。
因此，实际系统与 Paxos 几乎没有相似之处。每个实施方案都从 Paxos 开始，发现实施过程中的困难之处，然后开发一个明显不同的架构。这既费时又容易出错，而 Paxos 的难以理解又加剧了这个问题。Paxos 的表述对于证明其正确性的定理来说可能是一个很好的表述，但是真正的实现与Paxos有很大的不同，所以证明的价值不大。以下来自 Chubby 实现者的评论是典型的：
Paxos 算法的描述与现实世界系统的需求之间存在着巨大的差距。......最终的系统将基于一个未经证实的协议。
由于这些问题，我们得出Paxos既不能为系统建设也不能为教育提供一个良好的基础的结论。考虑到共识在大规模软件系统中的重要性，我们决定看看我们是否能设计出一种比 Paxos 具有更好特性的替代性共识算法。Raft 就是这个实验的结果。
4 为可理解性做设计
我们在设计 Raft 时有几个目标：它必须为系统建设提供一个完整而实用的基础，从而大大减少开发人员所需的设计工作量；它必须在所有条件下都是安全的，并在典型的操作条件下可用；它必须对普通操作具有高效性，但我们最重要的目标和最困难的挑战是可理解性。必须让广大观众能够轻松地理解该算法，此外，还必须有可能获得对该算法的洞见，以便系统构建者能够对其进行扩展，而这在现实世界的实现中是不可避免的。
在 Raft 的设计过程中，有许多时候我们必须在备选方法中做出选择。在这些情况下，我们根据可理解性来评估替代方案：解释每个替代方案有多困难（例如，它的状态空间有多复杂，它是否有微妙的含义）和读者完全理解这种方法及其含义有多容易。
我们知道到此类分析具很大程度的主观性，不过我们使用了两种普遍适用的技术。 第一种技术是众所周知的问题分解的方法：只要有可能，我们就将问题分成单独的部分，这些部分可以相对独立地解决、解释和理解。 例如，在 Raft 中，我们将领导选举、日志复制、安全和成员变更分开。
我们的第二个方法是通过减少需要考虑的状态数量来简化状态空间，使系统更加连贯，并尽可能消除非确定性。具体来说，不允许日志有空洞，而且 Raft 限制了日志相互之间变得不一致的途径。尽管在大多数情况下我们试图消除非确定性，但在某些情况下，非确定性实际上会提高可理解性。特别是随机化的方式，虽然引入了非确定性，但它们倾向于通过以类似的方式（"选择任意一个；这并不重要"）处理所有可能的选择来减少状态空间。我们使用随机化来简化 Raft 领袖选举算法。
5 Raft 共识算法
Raft 是一种管理复制日志的算法，其形式如第 2 节所述。图 2 简练的概括了该算法以供参考，图 3 列出了该算法的关键属性。这些图的元素将在本节的其余部分逐一讨论。
Raft 保证的属性，上图的翻译
- 选举安全性：给定的任期内，最多只有一个领导者可以当选
- 领导者日志只追加属性：领导者从不重写或者删除日志中的条目，只能追加新条目
- 日志匹配属性：如果两个日志包含一个具有相同索引和任期的条目，那么这两个日志在这个索引之前的条目都完全一致
- 领导者完备属性：如果一个日志条目在给定的任期内被提交，那么该条目将会在所有更高任期编号的领导者日志中出现
- 状态机安全：如果一个服务器在给定的索引上应用了一个日志条目，不会有任何其他服务器在该索引上使用了不同的日志条目
Raft 通过先选举一个杰出的（最优的）领导者，然后让这个领导者完全负责管理复制日志来实现共识。领导者从客户端接收日志条目，复制到其他服务器，并告诉服务器何时可以安全地将日志条目应用到他们的状态机中。拥有领导者可以简化复制日志的管理，比如，领导者可以不向其他服务器咨询就能决定将新的日志条目置于何处，并且数据会以一种简单的方式从领导者流向其他服务器。领导者可以发生故障或者与其他服务器失联，这种情况下一个新的领导者会被选举出来。
考虑到采用领导者这种方法，Raft 将共识问题拆解成三个相对独立的子问题，这些子问题将在下面的子章节中讨论：
- 领导者选举：新的领导者必须在已有领导者发生故障的时候被选中（5.2 节）。
- 日志复制：领导者必须从客户端接收日志条目并在集群中复制，强制其他（节点的）日志跟自己的一致（5.3 节）。
- 安全：对 Raft 来说主要的安全特性是图 3 所示的状态机安全特性：如果任意一个服务器在自己的状态机上应用了一个特定的日志条目，那么没有一个服务器可能在相同的日志索引下使用了不同的命令。5.4 节描述了 Raft 是如何保证这一特性的，该解决方案涉及对 5.2 节中描述的选举机制的额外限制。
在介绍了共识算法之后，本节讨论了系统中的可用性问题和计时的作用。
5.1 Raft 基础
一个 Raft 集群包含多个服务器，5 个是一个典型的数量，这样系统可以容忍 2 个服务器同时故障。在任意时刻，每个服务器处于三种状态中的一个：领导者、跟随者或者候选人。在正常情况下，有且只有一个领导者，其他服务器都是跟随者。跟随者都是被动的：他们从不自己发起请求，只会简单地响应领导者和候选人的请求。领导者处理所有客户端的请求（如果客户端联系了跟随者，跟随者会转发这个请求到领导者）。第三个状态，候选人，如 5.2 节所述，用来选举新的领导者。图 4 显示了这些状态和它们的转换关系，下面将讨论这些转换。
如图 5 所示，Raft 将时间划分为任意长度的任期。任期用连续的整数来编号。每个任期从选举开始，在选举中一个或多个候选人试图成为领导者，如第 5.2 节所述。如果一个候选人在选举中获胜，那么他将在任期剩下的时间内担任领导者。在某些情况下，选举的结果是分裂票，在这种情况下，任期将会以没有领导者的状态结束，新的任期（新的选举）将很快开始。Raft 确保在一个给定的任期内最多有一个领导者。
不同的服务器可能会在不同的时间观察到任期的转换，在某些情况下，一个服务器可能不会观察到一个选举甚至整个任期。任期在 Raft 中充当了逻辑时钟，它们让服务器能够检测到过时的信息，如过时的领导者。每个服务器都存储一个当前的任期编号，该编号随时间单调地增加。每当服务器进行通信时，就会交换当前任期信息；如果一个服务器的当前任期比另一个服务器的小，那么它就将其当前任期更新为较大的值。如果一个候选人或领导者发现它的任期已经过时，它将立即恢复到跟随者状态。如果一个服务器收到的请求有着一个过时的任期编号，它将拒绝该请求。
Raft 服务器使用远程过程调用（RPC）进行通信，而基本的共识算法只需要两种类型的RPC。
RequestVote RPC 由候选人在选举期间发起（第5.2节），AppendEntries RPC 由领导者发起，用于复制日志条目并提供一种心跳形式（第5.3节）。第 7 节增加了第三个RPC，用于在服务器之间传输快照。如果服务器没有及时收到响应，它们会重试 RPC，并且为了获得最佳性能，它们会并行地发出 RPC。5.2 领导者选举
Raft 使用心跳机制来触发领导者选举。当服务器启动时，它们的初始状态都是跟随者。只要服务器收到来自领导者或候选人的有效 RPC，它就一直处于跟随者状态。领导者定期向所有跟随者发送心跳（
AppendEntries RPCs，不携带任何日志条目），以保持他们的权威。如果跟随者在一段被称为选举超时的时间内没有收到任何通信，那么它就认为没有可行的领导者，并发起选举以选择一个新的领导者。发起选举时，跟随者增加它的当前任期编号并过渡到候选状态。然后，它为自己投票并且并行地向集群中其他服务器发出
RequestVote RPC。候选人一直处于这种状态，直到发生以下三种情况之一：（a）它赢得了选举，（b）另一个服务器确立了自己的领导地位，或者（c）一段时间内没有赢家。这些结果将在下面的段落中分别讨论。如果一个候选人在同一任期内获得了整个集群中大多数服务器的选票，那么它就赢得了选举。每台服务器在给定的任期内以先来后到的原则最多为一名候选人投票（注：第5.4节增加了一个关于投票的额外限制）。大多数的原则保证了最多只有一名候选人能在某个任期内赢得选举（图3中的选举安全属性）。一旦一个候选人在选举中获胜，它就成为领导者，然后，它向所有其他服务器发送心跳信息，以建立其权威并防止新的选举。
在等待选票的过程中，候选人可能会收到另一个服务器的
AppendEntries RPC，声称自己是领导者。如果领导者的任期编号（包含在这个 RPC 数据中）不小于候选人的当前任期，那么候选人就会承认领导者是合法的，并返回到跟随者状态。如果 RPC 中的任期编号小于候选人当前的任期，那么候选人就拒绝此 RPC，继续处于候选状态。第三个可能的结果是候选人既没有赢得选举，也没有输掉选举：如果许多追随者同时成为候选人，选票可能被分割，因此没有候选人获得多数选票。当这种情况发生时，每个候选人都会超时，并增加其任期编号和发起新一轮的
RequestVote RPC 来开始新的选举。然而，如果没有额外的措施，分裂选票的情况可能会无限期地重复。Raft 使用随机的选举超时时间，以确保分裂投票的情况很少并能被快速解决。为了从一开始就防止分裂投票，选举超时时间是从一个固定的时间间隔中随机选择的（如150-300ms），这使服务器分散开以至于在大多数情况下，只有一个服务器会超时，它赢得了选举，并在任何其他服务器超时之前发送心跳信号。同样的机制被用来处理分裂投票。每个候选人在发起选举的最开始重新启动其随机的选举超时时间，并等待超时后才开始下一次选举，这减少了在新的选举中再次出现分裂票的可能性。第 9.3 节显示，这种方法可以迅速选出一个领导者。
选举是一个说明可理解性是如何指导我们在设计方案之间进行选择的例子。最初我们计划使用一个排名系统来完成选举：每个候选人被分配一个独特的排名，用来在竞争的候选人之间进行选择。如果一个候选人发现了另一个排名更高的候选人，它就会回到追随者的状态，这样排名更高的候选人就能更容易地赢得下一次选举。我们发现这种方法在可用性方面产生了一些微妙的问题（如果一个排名较高的服务器失败了，一个排名较低的服务器可能需要超时并再次成为候选人，但如果它过早地这样做，它可能会重置选举领导者的进展）。我们对算法进行了多次调整，但每次调整后都会出现新的极端用例。最终我们得出结论，随机重试的方法更加明显和容易理解。
5.3 日志复制
一旦一个领导者被选出，它就开始为客户请求提供服务。每个客户请求都包含一个要由复制状态机执行的命令。领导者将该命令作为一个新条目追加到它的日志中，然后向其他每个服务器并行地发出
AppendEntries RPCs 来复制该条目。当条目被安全复制后（如下所述），领导者将条目应用于其状态机，并将执行结果返回给客户端。如果跟随者崩溃或运行缓慢，或者网络数据包丢失，领导者会无限制地重试 AppendEntries RPCs（甚至在它响应了客户端之后），直到所有跟随者最终存储所有的日志条目。日志的组织方式如图 6 所示。每个日志条目都存储了一个状态机命令，以及领导者收到该条目时的任期编号。日志条目中的任期编号被用来检测日志之间的不一致，并确保图 3 中的一些属性。每个日志条目也有一个整数索引，用于识别它在日志中的位置。
领导决定何时将日志条目应用于状态机是安全的，能够安全应用的条目被称为已提交条目。Raft 保证已提交的条目是持久化的，最终会被所有可用的状态机执行。一旦创建该条目的领导者将其复制到大多数服务器上，该日志条目就会被提交（例如，图6中的条目7）。这也会提交领导者日志中所有之前的条目，包括之前领导者创建的条目。第5.4节讨论了在领导者变更后应用这一规则时的一些微妙之处，它还表明这种已提交的定义是安全的。领导者跟踪它所知道的已提交条目的最高索引，并在未来的
AppendEntries RPCs（包括心跳）中包括该索引，以便其他服务器最终发现它。一旦追随者得知一个日志条目被提交，它就会将该条目应用于其本地状态机（按日志顺序）。我们设计 Raft 日志机制来在不同服务器上的日志之间保持高度的一致性。这不仅简化了系统的行为，使其更具可预测性，而且也是确保安全的重要组成部分。Raft 维护以下属性，它们共同构成了图 3 中的日志匹配特性：
- 如果在不同日志中的两个条目有着相同的索引和任期，那么他们就保存着同样的命令。
- 如果在不同日志中的两个条目有着相同的索引和任期，那么这个两个日志在此条目之前的所有条目都是完全相同的。
第一个属性来自于这样一个事实，即一个领导者在一个给定的任期中最多创建一个具有给定日志索引的条目，而且日志条目永远不会改变它们在日志中的位置。第二个属性是由
AppendEntries 执行的简单一致性检查保证的。当发送 AppendEntries RPC 时，领导者在其中包含了其日志中紧接新条目之前条目的索引和任期，如果跟随者在其日志中没有找到具有相同索引和任期的条目，那么它将拒绝新条目。一致性检查以归纳法的步骤来运行：日志的初始空状态满足了日志匹配属性，而一致性检查在日志被扩展时保持了日志匹配属性，因此，每当 AppendEntries 成功返回时，领导者知道跟随者的日志与自己的日志在新条目之前是相同的。在正常运行期间，领导者和追随者的日志保持一致，所以
AppendEntries 一致性检查不会失败。然而，领导者崩溃会使日志不一致（老领导者可能没有完全复制其日志中的所有条目）。这些不一致会在一系列领导者和追随者的崩溃中加剧。图 7 说明了追随者的日志可能与新领导者的日志不同的方式。跟随者可能会丢失领导者有的条目，可能会有领导者没有的额外条目，或者两种情况都有。日志中的缺失和不必要的条目可能跨越多个任期。
在 Raft 中，领导者通过强迫跟随者的日志复制自己的日志来处理不一致的情况。这意味着追随者日志中的冲突条目将被领导者日志中的条目覆盖。第 5.4 节将表明，当再加上一个限制条件时，这是安全的。
为了使追随者的日志与自己的日志保持一致，领导者必须找到两个日志一致的最新日志条目，删除追随者日志中此后的任何条目，并向追随者发送自己此后的所有条目。所有这些动作都是为了响应
AppendEntries RPCs 所进行的一致性检查。领导者为每个追随者维护一个 nextIndex，它是领导者将发送给该追随者的下一个日志条目的索引。当领导者首次上台时，它将所有的 nextIndex 值初始化为其日志中最后一个条目的索引的下一个值（图7中的11）。如果跟随者的日志与领导者的日志不一致，那么在下一个 AppendEntries RPC中，AppendEntries 一致性检查将失败。在被拒绝之后，领导者会递减 nextIndex 并重试 AppendEntries RPC。最终，nextIndex 将到达领导者和追随者日志匹配的一个点。当这种情况发生时，AppendEntries 将成功，这将删除跟随者日志中的任何冲突条目，并从领导者的日志中添加条目（如果有的话）。一旦 AppendEntries 成功，追随者的日志就会与领导者的日志一致，并且在剩下的任期里保持这种状态。如果需要，该协议可以被优化以减少被拒绝的
AppendEntries RPC的数量。例如，当拒绝一个 AppendEntries 请求时，跟随者可以包括冲突条目的任期和它为该任期存储的第一个索引。有了这些信息，领导者可以递减 nextIndex以绕过该任期中的所有冲突条目；每个有冲突条目的任期需要一个 AppendEntries RPC，而不是每个条目一个RPC。在实践中，我们怀疑这种优化是否有必要，因为故障不常发生，而且不太可能有很多不一致的条目。有了这种机制，领导者在上台时不需要采取任何特别的行动来恢复日志的一致性。它只是开始正常的操作，而日志会自动收敛以应对
AppendEntries 一致性检查的失败。一个领导者永远不会覆盖或删除它自己日志中的条目（图3中的领导者只追加属性）。这种日志复制机制表现出第 2 节中所描述的可取的共识特性：只要大多数服务器是在线的，Raft 就可以接收、复制和应用新的日志条目；在正常情况下，一个新的条目可以通过单轮RPC复制到集群的大多数；而且一个缓慢的跟随者不会影响性能。
5.4 安全
前面的章节描述了 Raft 如何选举领导和复制日志条目。然而，到目前为止所描述的机制还不足以确保每个状态机以相同的顺序执行完全相同的命令。例如，当领导者提交一些日志条目时，一个跟随者可能不可用，然后它可能被选为领导者，并用新的条目覆盖这些条目；结果，不同的状态机可能执行不同的命令序列。
本节对 Raft 算法进行了完善，增加了对哪些服务器可以被选为领导者的限制条件。该限制确保了任何给定任期的领导者都包含之前任期中已提交的所有条目（图 3 中的领导者完备性属性）。考虑到选举限制，我们会使提交的规则更加精确。最后，我们提出一个领导者完整性属性的证明草图，并说明它如何导致复制状态机的正确行为。
5.4.1 选举限制
在任何基于领导者的共识算法中，领导者最终必须存储所有已提交的日志条目。在一些共识算法中，例如 Viewstamped Replication，即使最初不包含所有已承诺的条目，也可以选为一个领导者。这些算法包含额外的机制来识别缺失的条目，并在选举过程中或之后不久将它们传送给新的领导者。不幸的是，这导致了相当多的额外机制和复杂性。Raft 使用了一种更简单的方法，它保证从每一个新的领导者当选的那一刻起，以前任期所有已提交条目都存在于其身上，而不需要将这些条目传输给领导者。这意味着日志条目只在一个方向流动，即从领导者到追随者，而且领导者永远不会覆盖他们日志中的现有条目。
Raft 使用投票过程来防止候选人赢得选举，除非其日志包含所有承诺的条目。候选人必须与集群中的大多数人联系才能当选，这意味着每个已提交的条目必须至少存在于其中一个服务器中。如果候选人的日志至少与该多数人中的任何其他日志一样新（这里的 "新 "在下面有精确的定义），那么它将包含所有已提交的条目。
RequestVote RPC 实现了这一限制：RPC 包括关于候选人日志的信息，如果投票人自己的日志比候选人的日志更新，则拒绝投票。Raft 是通过比较日志中最新的索引和任期来判定两个日志哪个更新，如果日志最后一个条目有着不同的任期，那么有更晚任期的日志是更新的那一个，如果日志最后一个条目有相同的任期，那么索引越大的日志越新。
5.4.2 提交上个任期的条目
如第 5.3 节所述，一旦一个条目被存储在大多数服务器上，领导者就知道其当前任期的条目已被提交。如果一个领导者在提交条目之前崩溃了，未来的领导者将试图完成对该条目的复制。然而，领导者不能立即得出上一届的条目被提交的结论，即使它被存储在大多数服务器上。图 8 说明了这样一种情况：一个旧的日志条目被存储在大多数服务器上，但仍然可以被未来的领导者覆盖。
为了消除类似图 8 中的问题，Raft 决不会通过统计副本的数量来提交前任的日志条目。只有领导者当前任期的日志条目是通过计算副本数量来提交的，一旦当前任期的条目以这种方式被提交，那么由于日志匹配属性，所有之前的条目都被间接地提交。在某些情况下，领导者可以安全地断定一个较早的日志条目已被提交（例如，如果该条目存储在每个服务器上），但 Raft 为了简单起见，采取了更保守的做法。
Raft 在提交规则中产生了这种额外的复杂性，因为当领导者复制先前任期的条目时，日志条目会保留其原始任期编号。在其他共识算法中，如果一个新的领导者复制之前 "任期"中的条目，它必须用新的 "任期编号 "来做。Raft 的方法使得对日志条目的推理更加容易，因为它们在不同的时间和不同的日志中保持相同的任期编号。此外，与其他算法相比，Raft 的新领导发送的前任期的日志条目更少（其他算法必须发送额外的日志条目，在他们可以被提交之前重新编号他们）。
5.4.3 安全性保证
有了完整的 Raft 算法，我们现在可以更精确地论证领导者完备性属性是否成立（这个论证是基于安全证明的，见第 9.2 节）。我们假设领导者完备性属性不成立，然后我们推导出矛盾之处。假设任期 T 的领导者（leader T ）在它的任期中提交了一个日志条目，但是这个日志条目没有被未来某个任期的领导者所存储。假设存在最小的任期 U > T 且其领导者（领导者 U）不存储该条目。
- 这个已提交的条目肯定没有在赢得选举的时候出现在领导者 U 的日志中（领导者从不删除或者覆盖自己的条目）
- 领导者 T 将条目复制到集群中大多数服务器中，并且领导者 U 收到了来自集群大多数的选票，因此，至少有一个服务器（投票者）既收到了领导 T 的条目也投票给了领导 U，如图 9 所示。这个投票者就是达成反例的关键。
- 该投票者一定是在投票给领导 U 之前从领导 T 处接收已提交的条目，否则它会拒绝领导 T 的
AppendEntries请求（如果是之后，它的当前任期比 T 的大，T就没法给他发送该请求）
- 该投票者在投票给领导 U 的时候仍然存储着来自领导 T 的条目，因为在 T 和 U 之间的领导者都包含此条目（根据假设：领导 U 是不存在该条目的最小任期的领导），领导者从不移除条目，跟随者只会在跟领导者冲突的时候移除条目。
- 该投票者授予自己的选票给领导者 U，那么领导者 U 的日志必定跟该投票这一样新，这会导致出现下面两个矛盾点中的一个
- 如果投票者和领导者 U 有着相同的最近日志任期，那么领导者 U 的日志必定至少跟投票者的一样长，所以他的日志里包含所有投票者日志里的条目。这是一个矛盾点，因为投票者包含着那个已提交的条目，而领导者 U 被假定不包含。
- 否则，领导者 U 的最后一个日志任期一定比投票者的大，而且还比 T 的大，因为投票人的最后一个日志任期至少是 T（它包含 T 任期内的已提交条目）。创建领导者 U 的最后一个日志条目的早期领导者，其日志中一定包含了已提交的条目（根据假设：领导 U 是不存在该条目的最小任期的领导）。那么，根据日志匹配属性，领导者 U 的日志也必须包含已提交的条目，这是一个矛盾点。
- 这就完成了矛盾推导。因此，所有大于 T 的任期领导必包含所有在 T 任期内中提交的 T 任期的条目。
- 日志匹配属性保证未来的领导者还将包含间接提交的条目，例如图 8（d）中的索引 2。
根据领导者完备性属性，我们可以证明图 3 中的状态机安全属性，即如果一个服务器在其状态机上应用了一个给定索引的日志条目，那么没有其他服务器会在同一索引上应用一个不同的日志条目。当一个服务器在其状态机上应用一个日志条目时，其日志从开始直到该条目都必须与领导者的日志相同，并且该条目必须被提交。现在考虑任意服务器应用一个给定的日志索引的最低任期，领导者日志完备性属性保证所有更高任期的领导者将存储相同的日志条目，因此在以后的任期中应用索引的服务器将应用相同的值。因此，状态机安全属性成立。
最后，Raft 要求服务器按照日志索引顺序应用条目，结合状态机安全属性，这意味着所有的服务器都将按照完全一致的顺序应用完全相同的日志条目集合到他们的状态机上。
5.5 跟随者和候选人崩溃
在这之前，我们一直专注于领导者的故障。跟随者和候选人的崩溃比领导者的崩溃更加容易处理，而且它们的处理方式都是一样的。如果一个追随者或候选人崩溃了，那么此后发送给它的
RequestVote 和 AppendEntries RPC 将会失败。Raft 通过无限次重试来处理这些失败，如果崩溃的服务器重新启动，那么 RPC 将成功完成。如果服务器在完成 RPC 后但在响应前崩溃，那么它将在重新启动后再次收到相同的RPC。Raft RPC 是幂等的，所以这不会造成任何破坏。例如，如果一个跟随者收到一个AppendEntries 请求，其中包括已经存在于其日志中的日志条目，那么它将忽略新请求中的这些条目。5.6 时间和可用性
我们对 Raft 的要求之一是安全不能依赖于时间：系统不能因为某些事件发生得比预期快或慢而产生错误的结果。然而，可用性（系统及时响应客户的能力）必须不可避免地取决于时间。例如，如果消息交换的时间超过了服务器崩溃的一般间隔，那么候选人就不会保持在线足够长的时间来赢得选举，没有一个稳定的领导者，Raft 就不能开始工作。
领导者选举是 Raft 中时间至关重要的一个体现。只要能满足下面的时间要求，Raft 将能一直选举并保持一个稳定的领导者：
broadcastTime ≪ electionTimeout ≪ MTBF在这个不等式中，
broadcastTime 是一台服务器向集群中的每台服务器并行发送 RPC 并接收到响应所需的平均时间；electionTimeout 是第 5.2 节中描述的选举超时时间；MTBF 是单台服务器的平均故障间隔时间。广播时间应该比选举超时少一个数量级，这样领导者就可以可靠地发送心跳信息，以防止跟随者开始选举，考虑到选举超时时间使用的随机方法，这种不平等也使得分裂投票不太可能发生。选举超时时间应该比 MTBF 小几个数量级，这样系统才能稳步前进。当领导者崩溃时，系统将在大约选举超时的时间内不可用，我们希望这只占总体时间的一小部分。广播时间和
MTBF 是底层系统的属性，而选举超时时间是我们必须选择的。Raft 的 RPC 通常要求接收者将信息持久化到稳定的存储中，所以广播时间可能在 0.5ms 到 20ms 之间，这取决于存储技术。因此，选举超时时间可能是在 10ms 到 500ms 之间。通常服务器 MTBF 是几个月或更长时间，这很容易满足时间要求。6 成员变更
到目前为止，我们假设集群的配置（参与共识算法的服务器集合）是固定的。在实践中，偶尔有必要改变配置，例如在服务器故障时更换服务器或改变复制的程度。虽然这可以通过关闭整个集群，更新配置文件，然后重新启动集群来完成，但这将使集群在转换期间不可用。此外，如果有任何手动步骤，就有可能出现操作错误。为了避免这些问题，我们决定将配置变更自动化，并将其纳入 Raft 共识算法。
为了使配置变化机制安全，在过渡期间必须没有任何一个时间点可以让两个领导人在同一个任期当选。不幸的是，任何服务器直接从旧的配置切换到新的配置的方法都是不安全的。不可能一次性地切换所有的服务器，所以集群有可能在过渡期间分裂成两个独立的多数（见图10）。
为了确保安全，配置变更必须使用两阶段的方法。实现这两个阶段的方法有很多种。例如，一些系统（如[22]）使用第一阶段禁用旧的配置，使其无法处理客户端请求；然后第二阶段启用新的配置。在Raft中，集群首先切换到一个过渡性的配置，我们称之为联合共识；一旦联合共识被提交，系统就会过渡到新的配置。联合共识结合了新旧两种配置:
- 日志条目会复制到两个配置的所有服务器
- 来自任意一个配置的任意服务器都有可能成为领导者
- 达成协议（选举和条目提交）需要来自老配置和新配置各自的大多数同意
联合共识允许单个服务器在不同时间在配置之间转换，而不影响安全。此外，联合共识允许集群在整个配置变化过程中继续为客户请求提供服务。
集群的配置是通过复制日志中的特殊条目来存储和交流的，图 11 说明了配置的变化过程。当领导者收到将配置从 C-old 变为 C-new 的请求时，它将联合共识的配置（图中的C old,new）存储为一个日志条目，并使用前面描述的机制复制该条目。一旦某个服务器将新的配置条目添加到其日志中，它就会将该配置用于所有未来的决策（服务器总是使用其日志中的最新配置，而不管该条目是否已提交）。这意味着领导者将使用C-old,new 的规则来决定 C-old,new 的日志条目何时被提交。如果领导者崩溃了，可能会在 C-old 或 C-old,new 下选择一个新的领导者，这取决于获胜的候选人是否得到了 C old,new。 在任何情况下，C-new 都不能在此期间做出单边决定。
一旦 C-old,new 被提交，C-old 和 C-new 都不能在未经对方批准的情况下做出决定，而且领导者完备属性确保只有具有 C-old,new 日志条目的服务器才能被选为领导者。现在，领导者创建一个描述 C-new 的日志条目并将其复制到集群中是安全的。同样，这个配置一旦被看到，就会在每个服务器上生效。当新的配置在 C-new 的规则下被提交时，旧的配置就不重要了，不在新配置中的服务器可以被关闭了。如图11所示，在任何时候，C-old 和 C-new 都不能同时做出单方面的决定，这保证了安全。
在重新配置方面还有三个问题需要解决。第一个问题是，新的服务器最初可能没有存储任何日志条目。如果它们在这种状态下被添加到集群中，可能需要相当长的时间才能赶上，在此期间，可能无法提交新的日志条目。为了避免可用性差距，Raft 在配置改变之前引入了一个额外的阶段，在这个阶段，新的服务器作为非投票成员加入集群（领导者将日志条目复制给他们，但他们不被考虑为多数）。一旦新的服务器赶上了集群的其他部分，重新配置就可以按上述方法进行。
第二个问题是，集群领导者可能不是新配置的一部分。在这种情况下，一旦提交了C-new 日志条目，领导者就会退出（返回到跟随者状态）。这意味着会有一段时间（当它提交 C-new 的时候），领导者在管理一个不包括自己的集群，它复制日志条目，但不把自己算在多数中。领导者的转换发生在 C-new 被提交的时候，因为这是新的配置可以独立运行的第一个点（总是可以从 C-new 中选择一个领导者）。在这之前，可能只有来自 C-old 的服务器可以被选为领导者。
第三个问题是，被移除的服务器（那些不在 C-new 中的）会扰乱集群。这些服务器不会收到心跳，所以它们会超时并开始新的选举。然后他们会发送带有新任期编号的
RequestVote RPCs，这将导致当前的领导者恢复到追随者状态。一个新的领导者最终将被选出，但被移除的服务器将再次超时，这个过程将重复，导致可用性差。为了防止这个问题，当服务器认为存在一个当前的领导者时，它们就会忽略
RequestVote RPCs。具体来说，如果一个服务器在当前领袖的最小选举超时时间内收到 RequestVote RPC，它不会更新其任期或投出自己的选票。这并不影响正常的选举，因为每个服务器在开始选举之前至少要等待一个最小的选举超时时间。然而，这有助于避免被移除的服务器的干扰：如果一个领导者能够得到其集群的心跳，那么它就不会被更大的任期数字所废黜。7 日志压缩
Raft 的日志在正常运行中不断增长，以收入更多的客户端请求，但在一个实际的系统中，它不能无限制地增长。随着日志的增长，它占据了更多的空间，需要更多的时间来重放，如果没有某种机制来丢弃积累在日志中的过时信息，这最终会导致可用性问题。
快照是最简单的压缩方法。在快照中，整个当前系统状态被写入稳定存储的快照中，然后丢弃截至该点的整个日志。快照在 Chubby 和 ZooKeeper 中使用，本节的其余部分将介绍 Raft 中的快照。
递增的压缩方法，如日志清理和日志结构的合并树，也是可行的。这些方法一次性对小部分数据进行操作，因此它们将压缩的负荷在时间上更均匀地分散。它们首先选择一个积累了许多删除和覆盖对象的数据区域，然后将该区域的活对象重写得更紧凑，并释放该区域。与快照相比，这需要大量的额外机制和复杂性，因为快照总是在整个数据集上操作，简化了问题。同时日志清理需要对 Raft 进行修改，但状态机可以使用与快照相同的接口实现 LSM 树。
图 12 显示了 Raft 中快照的基本思路。每台服务器独立进行快照，只覆盖其日志中已提交的条目。大部分的工作由状态机将其当前状态写入快照组成。Raft 还在快照中包含了少量的元数据：最后包含的索引（last included index）是快照所取代的日志中最后一个条目的索引（状态机应用的最后一个条目），最后包含的任期（last included term）是这个条目的任期。这些都被保留下来以支持快照后的第一个日志条目的
AppendEntries 一致性检查，因为该条目需要一个先前的日志索引和术语。为了实现集群成员的变化（第6节），快照还包括了日志中的最新配置，即最后包含的索引。一旦服务器完成了写快照，它可以删除所有的日志条目，直到最后包含的索引，以及任何先前的快照。尽管服务器通常是独立进行快照，但领导者偶尔必须向落后的跟随者发送快照。这种情况发生在领导者已经丢弃了它需要发送给跟随者的下一个日志条目。幸运的是这种情况在正常操作中不太可能发生：一个跟上领导者的追随者已经有了这个条目，但是，一个特别慢的跟随者或一个新加入集群的服务器（第6节）就不会有这个条目。让这样的跟随者掌握最新数据的方法是领导者通过网络向它发送一个快照。
领导者使用一个叫做
InstallSnapshot 的新 RPC 来向落后于它的跟随者发送快照，见图13。当跟随者收到这个 RPC 的快照时，它必须决定如何处理其现有的日志条目。通常情况下，快照将包含新的信息，而不是在接收者日志中的条目，在这种情况下，跟随者丢弃它的整个日志，因为都被快照取代了，并且可能有与快照相冲突的未提交的条目。相反，如果跟随者收到描述其日志前置代码的快照（由于重传或错误），那么被快照覆盖的日志条目将被删除，但快照之后的条目仍然有效，必须保留。这种快照方法偏离了 Raft 的强领导原则，因为跟随者可以在领导不知情的情况下进行快照。然而，我们认为这种偏离是合理的。虽然有一个领导者有助于避免在达成共识时出现决策冲突，但在快照时已经达成了共识，所以没有决策冲突。数据仍然只从领导者流向追随者，只是追随者现在可以重新组织他们的数据。
我们考虑了另一种基于领导者的方法，即只有领导者会创建快照，然后它将把这个快照发送给它的每个跟随者。然而，这有两个缺点。首先，向每个追随者发送快照会浪费网络带宽，并减缓快照过程。每个追随者都已经拥有产生其自身快照所需的信息，而且对于服务器来说，从其本地状态产生快照通常比通过网络发送和接收快照要廉价得多。第二，领导者的实现将更加复杂，例如，领导者需要在向追随者复制新的日志条目的同时向他们发送快照，以便不阻塞新的客户请求。
还有两个影响快照性能的问题。首先，服务器必须决定何时进行快照。如果服务器快照的频率过高，就会浪费磁盘带宽和能源；如果快照的频率过低，就会有耗尽其存储容量的风险，而且会增加重启时重放日志的时间。一个简单的策略是，当日志达到一个固定的字节大小时进行快照。如果这个大小被设定为比快照的预期大小大得多，那么快照的磁盘带宽开销就会很小。
第二个性能问题是，写入快照可能需要大量的时间，我们不希望因此而延误正常的操作。解决方案是使用写时复制技术，这样新的更新可以被接受而不影响正在写入的快照。例如，用函数式数据结构构建的状态机天然支持这一点。另外，操作系统的写时拷贝支持（例如 Linux 上的fork）可以用来创建整个状态机的内存快照（我们的实现采用了这种方法）。
8 客户端交互
本节介绍了客户端如何与 Raft 交互，包括客户端如何发现集群领导者以及 Raft 如何支持可线性化语义。这些问题适用于所有基于共识的系统，而 Raft 的解决方案与其他系统类似。
Raft 的客户端将他们所有的请求发送给领导者。当客户端首次启动时，它会连接到一个随机选择的服务器。如果客户端的第一选择不是领导者，该服务器将拒绝客户端的请求，并提供最新的领导者的信息（
AppendEntries 请求包括领导者的网络地址）。如果领导者崩溃了，客户端的请求就会超时，然后客户端会在随机选择的服务器上再次尝试。我们给 Raft 设定的目标是实现可线性化的语义（每个操作在其调用和响应之间的某个点上看起来都是瞬间完成且正好一次）。然而，正如目前所描述的那样，Raft可以多次执行一个命令：例如，如果领导者在提交日志条目后但在响应客户端之前崩溃，客户端将用一个新的领导者重试该命令，导致它被第二次执行。解决方案是让客户端为每个命令分配唯一的序列号。然后，状态机跟踪为每个客户处理的最新序列号以及相关的响应。如果它收到一个序列号已经被执行的命令，它会立即响应，而不重新执行该请求。
只读操作可以在不向日志中写入任何内容的情况下进行处理。然而，如果没有额外的措施，这将有返回陈旧数据的风险，因为响应请求的领导者可能已经被它不知道的较新的领导者所取代。可线性化的读取必须不返回陈旧的数据，不使用日志的话，Raft 需要两个额外的预防措施来保证这一点。首先，领导者必须拥有关于哪些条目已被提交的最新信息，领导者完整性属性保证领导者拥有所有已提交的条目，但在其任期开始时，它可能不知道是哪些条目，为了弄清楚，它需要从其任期内提交一个条目，Raft 通过让每个领导者在其任期开始时向日志提交一个空白的无操作条目来处理这个问题。其次，领导者必须在处理只读请求之前检查自己是否被罢免（如果最近的领导者被选出，其信息可能是过时的），Raft 通过让领导者在响应只读请求之前与集群中的大多数人交换心跳信息来处理这个问题。另外，领导者可以依靠心跳机制来提供一种租赁形式，但这要依靠时间来保证安全（它假定了有界的时钟偏移）。
完结
论文剩下的部分是对 Raft 的一些验证和性能评估，感兴趣的可以找原文来继续阅读，这里就不再翻译。
下一步，我将按照此论文的思路和设计，使用 Go 语言实现一个基本可用的 Raft 库。