Raft 论文原文传送门:
In Search of an Understandable Consensus Algorithm (Extended Version)

这篇文章大头是原文翻译,但我在很多地方加入了自己的理解,
主要作为我自己的笔记,不保证读者可以看懂,但你若有问题可以写在评论区,我会回复。

论文第 9 节及以后没有在本文记录笔记,因为这之后的内容不再是 Raft 共识算法的一部分。

0. 摘要

Raft 是一种用于管理复制日志的共识算法。

Raft 产生的结果和 (multi-)Paxos 一样,并且和 Paxos 一样高效,但是 Raft 的结构和 Paxos 不同。这使 Raft 比 Paxos 更容易理解,也为在构建实际系统提供了更好的基础。

为了更容易理解,Raft 分离了共识的关键要素,例如领导选举(leader election),日志复制(log replication)和安全性(safety)。

Raft 加强了一致性,以减少必须考虑的情况的数目。

一个用户研究的结果说明,对于学生来说,Raft 比 Paxos 更容易学。

Raft 还包括一种用于更改集群成员的新机制,该机制使用重叠多数(overlapping majorities)来保证安全。

1. 导论

共识算法允许一组机器作为一个一致的组来工作,这个组能够在其部分成员故障时幸存。因此,在构建可靠的大规模软件系统中,共识算法扮演着关键的角色。在过去十年间,关于共识算法的讨论被 Paxos 统治:大部分共识实现都是基于 Paxos 或受 Paxos 影响的,并且 Paxos 成为了给学生讲关于共识内容的主要工具。

不幸的是,尽管有数次让 Paxos 更平易近人的尝试,其还是相当难于理解。此外,Paxos 的架构需要复杂的修改以支持实际的系统。结果就是,系统构建者和学生都在为 Paxos 苦苦挣扎。

在我们与 Paxos 斗争之后,我们开始寻找一个新的共识算法,期望此算法能够为系统构建和教育提供更好的基础。我们的主要目标是可理解性,我们的方法不太寻常:我们能否为实际系统定义一个共识的算法,并且以比 Paxos 容易学得多的方式描述这个算法?此外,我们希望此算法能够促进对系统构建者至关重要的直觉的发展。不仅仅是算法能够工作很重要,能明显看出为什么可以工作也很重要。

这项工作的结果就是一个名为 Raft 的共识算法。在设计 Raft 过程中,我们应用了特定的技术来提高可理解性,包括分解(Raft 分离了领导选举,日志复制和安全性)和减小状态空间(相对于 Paxos,Raft 降低了非确定性的程度以及服务器之间可能不一致的方式)。一个包含了来自两所大学的 43 个学生的用户研究表明,Raft 比 Paxos 容易理解的多得多:在学习了两个算法以后,33/43 个学生在回答关于 Raft 的问题时比回答关于 Paxos 的问题是表现更好。

Raft 在很多方面都和现存的共识算法类似(最显著的是,Oki 和 Liskov 的 Viewstamped Replication),但 Raft 有几个新颖的特征:

  • 强领导者(Strong leader):Raft 使用比其他共识算法更强大的领导形式。例如,日志条目仅从领导者流向其他服务器。这简化了对复制日志的管理,并使 Raft 更易于理解。
  • 领导选举(Leader election):Raft 使用随机计时器来选举领导者。这只会为任何共识算法已经需要的心跳(HeartBeat)添加少量机制,同时简单快速地解决冲突。
  • 成员变更(Membership changes):Raft 用来变更集群中服务器集合的机制中使用了一个新的方法 — 联合共识(joint consensus),在两个不同的配置中,大部分机器在转换期间重叠,这允许集群在成员变更期间继续正常运行。

不管是以教育为目的,还是作为实现基础,我们都认为 Raft 比 Paxos 和其他共识算法更好。Raft 比其他共识算法更简单、更好理解;Raft 的描述足够完整,足以满足实际系统的需要;Raft 有几个开源实现,有几个公司在使用 Raft;Raft 的安全特性已被正式规定和证明;Raft 的效率与其他算法相当。

这篇论文的剩余部分介绍了复制状态机问题(第 2 节),讨论了 Paxos 的优缺点(第 3 节),描述了我们理解可理解性的一般方法(第 4 节),介绍 Raft 共识算法(第 5-8 节),评估 Raft(第 9 节),最后讨论了相关工作(第 10 节)。

2. 复制状态机(Replicated state machines)

共识算法通常出现在复制状态机(Replicated state machines)的上下文中。在这个方法中,服务器集合上的状态机计算同一状态的相同副本,并且即使某些服务器 down 机了也可以继续运行。复制状态机用于解决分布式系统中的各种容错问题。例如,在像 GFS、HDFS 和 RAMCloud 这样的只有单个集群领导者的大规模系统中,通常使用单独的复制状态机来管理领导选举并存储必须在领导者崩溃后幸免的配置信息。在 Chubby 和 ZooKeeper 中有复制状态机的例子。

图 1:复制状态机架构。共识算法管理一个复制日志,其中包含来自客户端的状态机命令。这个状态机处理来自日志的相同命令序列,所以它们产生一样的输出。

复制状态机一般使用复制日志实现,如图 1。每个服务器(Server) 存储一个包含了一系列命令的日志(Log),其状态机(State Machine) 按顺序执行这些命令。每个日志包含相同顺序的相同命令,所以每个状态机处理相同的命令序列。由于状态机是确定性的,因此每个状态机计算相同的状态和相同的输出序列。

保持复制日志一致是共识算法的工作1。① 服务器上的共识模型(Consensus Module) 接收来自客户端(Client) 的命令,② 把这些命令添加到服务器的日志中,且和其他服务器上的共识模型通信以确保每个日志最终包含相同顺序的相同请求,即便一些服务器故障了。一旦命令被正确复制,③ 每个服务器的状态机都会按日志顺序处理它们,并 ④ 将输出返回给客户端。 结果,服务器似乎形成了一个单一的、高度可靠的状态机。

对于实际系统,共识算法往往有以下属性:

  • 共识算法确保所有 non-Byzantine 条件下的安全性(永远不会返回错误的结果),包括网络延迟、分区、丢包、重复和重新排序。
  • 只要大多数服务器都可以运行,可以相互通信,可以与客户端通信,共识算法就可以正常工作(可用)。因此,一个典型的五台服务器集群可以容忍任何两台服务器的故障。假设服务器因停止而故障,它们稍后可能会从稳定存储上的状态恢复并重新加入集群。
  • 共识算法不依赖于时间来确保日志的一致性:错误的时钟和极端的消息延迟在最坏的情况下会导致可用性问题。
  • 在一般情况下,只要集群的大部分响应了一轮远程过程调用,命令就可以完成。少数慢速服务器不需要影响整体系统性能。

3. Paxos 有什么问题?

在过去的时间里,Leslie Lamport 的 Paxos 协议成为了“共识”的同义词:大学里关于共识协议的课程中教 Paxos 的最常见,大部分共识实现使用 Paxos 作为起点。Paxos 首先定义了一种能够就单个决策达成一致的协议,例如单个复制日志条目,我们将此子集称为单法令 Paxos (single-decree Paxos)。然后 Paxos 结合了该协议的多个实例,以促进一系列决策,例如日志,这种情况称为 multi-Paxos。Paxos 确保了安全性和活跃性,并且它支持集群成员变更。Paxos 的正确性已经被证明,并且在正常情况下是有效的。

不幸的是,Paxos 有两个严重的缺点。

第一个缺点是,Paxos 非常非常难理解,其完整的解释是出了名的晦涩难懂,很少有人能仅仅通过付出巨大的努力就能成功理解。因此,已经有几次尝试(几篇论文)用更简单的术语来解释 Paxos,这些解释聚焦 single-decree 子集,然而这些仍然具有挑战性。在 NSDI 2012 对出席者的非正式调查中,我们发现很少有人对 Paxos 感到满意,即使是经验丰富的研究人员也是如此。我们自己在 Paxos 上苦苦挣扎,直到我们阅读几个简化的解释,并设计了我们自己的替代协议以后,我们才能理解完整的 Paxos 协议,这个过程花了几乎一年的时间。

我们假设 Paxos 的晦涩难懂源于它选择单一法令子集作为其基础。Single-decree Paxos 是密集和微妙的:分为两个阶段,没有简单直观的解释,无法独立理解。正因为如此,很难对 single-decree 协议的工作原理产生直觉。multi-Paxos 的组合规则显着增加了复杂性和微妙性。我们相信,就多个决策(即日志而不是单个条目)达成共识的整体问题可以用其他更直接和明显的方式分解。

第二个缺点是,Paxos 没有为构建实际实现提供一个好的基础。一个原因是,对于 multi-Paxos,没有广泛认可的算法。Lamport 的描述大部分是关于 single-decree Paxos 的,他勾勒出了实现 multi-Paxos 的可能方法,但缺少许多细节。尽管已经有多次尝试充实和优化 Paxos,但它们彼此不同,也与 Lamport 的草图不同。像 Chubby 这样的系统已经实现了类 Paxos 算法,但在大多数情况下,它们的细节还没有公布。

此外,Paxos 架构对于构建实际系统来说是一种糟糕的架构,这是 single-decree 分解的另一个结果。例如,单独选择一组日志条目然后将它们融合到一个顺序日志中几乎没有什么好处,这只会增加复杂性。围绕日志设计一个系统更简单、更有效,其中新条目以受约束的顺序顺序追加。另一个问题是 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 将共识问题分解为三个相对独立的子问题,这些子问题将在以下小节中讨论:

  • 领导选举:当现存的领导者故障时,必须选出一个新的领导者(第 5.2 节)。
  • 日志复制:领导者必须接受来自客户端的日志条目,并把这些条目跨集群复制,强制其他日志与自己的一致(第 5.3 节)。
  • 安全性:Raft 的关键安全属性是图 3 中的状态机安全属性(State Machine Safety):如果任何服务器已将特定日志条目应用到其状态机,则没有其他服务器可以为相同的日志索引应用不同的命令。第5.4 节描述了 Raft 如何确保这个属性,该解决方案涉及对第 5.2 节中描述的选举机制的额外限制。

在介绍了共识算法之后,本节讨论了可用性问题和时间在系统中的作用。

此图 2 为翻译版本,但保留了部分相对重要的英文原词。在这里查看原图。
点击图片,再点击图片,可以放大。

图 2:Raft 共识算法的精简摘要(不包括成员变更和日志压缩(compaction))。左上方框中的服务器行为被描述为一组独立且重复触发的规则。§5.2 等章节编号表示讨论特定功能的位置。

图 3:Raft 保证这些属性中的每一个在任何时候都是正确的。章节编号表示每个属性的讨论位置。

5.1. Raft 基础

一个 Raft 集群包含几个服务器:一般是 5 个,即可以容忍系统中有 2 个服务器故障。在任何给定的时间,每个服务器都处于三种状态之一:领导者(leader)追随者(follower)候选人(candidate)。在一般的操作中,有一个确定的领导者,所有其他的服务器都是追随者。追随者是被动的:他们自己不发出请求,而只是响应来自领导者和候选人的请求。领导者处理所有的客户端请求(如果一个客户端和追随者联系,追随者会把其重定向到领导者)。第三个状态,候选人,用于选举一个新的领导者,像在第 5.2 节描述的那样。图 4 显示了这些状态以及状态之间的转换,转换规则在下面讨论。

图 4:服务器状态。追随者只响应来自其他服务器的请求。如果追随者没有收到任何通信,他将成为候选人并发起选举。获得整个集群中大部分服务器选票的候选者成为新的领导者。领导者通常会一直工作,直到故障。

Raft 将时间划分为任意长度的任期(terms),如图 5 所示。任期用连续的整数编号。每个任期都以选举(election)开始,其中一个或多个候选人尝试成为第 5.2 节所述的领导者。如果一个候选人赢得选举,他就会在这个任期的剩余时间内担任领导者。在某些情况下,选举将导致分裂投票。在这种情况下,任期将在没有领导者的情况下结束,一个新的任期(带着新的选举)将很快开始。Raft 确保在给定的任期内最多有一个领导者。

图 5:将时间划分为任期(terms),每个任期以一个选举开始。选举成功后,一个领导者管理这个集群,直到任期结束。某些选举可能失败,这种情况下,任期将在没有领导者的情况下结束。任期之间的转换可以在不同服务器上的不同时间观察到。

不同的服务器可能会在不同的时间观察到任期之间的转换,并且在某些情况下,服务器可能不会观察到选举甚至整个任期。任期在 Raft 中充当逻辑时钟,它们允许服务器检测过时的信息,例如过时的领导者。每个服务器存储一个当前任期编号,该编号随时间单调增加。每当服务器通信时,都会交换当前任期编号,如果一台服务器的当前任期编号小于另一台服务器的当前任期编号,则它会将其当前编号更新为较大的值。如果候选人或领导者发现其任期已过时,它将立即恢复为追随者状态。如果服务器收到具有过时任期编号的请求,它将拒绝该请求。

Raft 服务器通过远程过程调用(RPC)通信,基本的共识算法只需要两种类型的 RPC 请求:请求投票 RPC (RequestVote RPC) 由候选人在选举期间发起(第 5.2 节),追加条目 RPC (AppendEntries RPC) 由领导者发起以复制日志条目并提供一种心跳形式。第 7 节添加了第三个 RPC,用于在服务器之间传输快照(snapshot)。 如果服务器没有及时收到响应,则服务器会重试 RPC,并且它们会并行发出 RPC 以获得最佳性能。

5.2. 领导选举

Raft 使用心跳机制来触发领导选举。当服务器启动时,他们一开始先作为追随者。只要服务器从领导者或候选人那里收到有效的 RPC,他就会保持追随者状态。领导者定期发送心跳(不携带日志条目的追加条目 RPC)给所有追随者,以维护这些追随者的权限。如果一个追随者在称为选举超时(election timeout)的一段时间内没有收到任何通信,则它假定没有可行的领导者并开始选举以选择新的领导者。

要开始选举,一个追随者会增加其当前任期并转换到候选人状态,随后给自己投一票,并给集群中每个其他服务器并行发出请求投票 RPC。一个候选人会持续其候选人状态直到发生下面三件事之一:(a) 它赢得选举,(b) 另一台服务器将自己建立为领导者,或 (c) 一个时间周期过去,但没有服务器赢得选举。这些结果将在下面的段落中单独讨论。

如果一个候选人在同一任期内获得来自整个集群中大部分服务器的选票,它就会赢得选举。在给定的任期内,每个服务器最多只能给一个候选人投票,基于先来先服务(first-come-first-served)(注意:第 5.4 小节增加了对投票的额外限制)。这个大多数规则确保了在一个指定的任期内最多只有一个候选人可以胜出(图 3 中的 Election Safety)。一旦一个候选人赢得选举,它就成为了领导者,随后它就会给所有其他服务器发送心跳消息以建立它的权威,并阻止新的选举。

在等待投票时,候选人可能会从另一个声称自己是领导者的服务器收到追加条目 RPC。如果这个领导者的任期(任期信息包含在 RPC 中)至少和这个候选人的当前任期一样大,候选人就会意识到这个领导者是合法的,然后返回追随者状态。如果这个领导者的任期小于这个候选人的当前任期,候选人就会拒绝这个 RPC 并继续保持候选人状态。

第三个可能的结果是,一个候选人既没有赢得选举,也没有输掉选举:如果很多追随者在同一时间成为候选人,选票就会被划分(分裂)的太多,导致没有任何一个候选人可以获得大多数选票(大多数选票指的是票数超过总服务器数量的一半,例如,5 个服务器时,获得至少 3 张选票的候选人会胜出)。在这种情况下,每个候选人都会超时,并开始一个新的选举(增加其任期编号,发起另一轮请求投票 RPC)。然而,如果没有额外的措施,分裂投票可能无限重复。

Raft 使用随机选举超时来确保分裂投票很少发生并且可以快速解决。首先,为了防止分裂投票,选举超时是从固定区间(例如,150-300 ms)中随机选择的。这分散了服务器,因此在大多数情况下,只有一个服务器会超时,它会赢得选举并在任何其他服务器超时之前发送心跳。相同的机制用于处理分裂投票。每个候选人在选举开始时重新开始其随机选举超时,并在开始下一次选举之前等待该超时过去,这减少了在新选举中再次分裂投票的可能性。第 9.3 节表明,这种方法可以快速选举领导者。

选举是可理解性如何引导我们在设计备选方案之间进行选择的一个例子。最初我们计划使用排名系统:为每个候选人分配一个唯一的排名,用于在竞争候选人之间进行选择。如果一个候选人发现另一个候选人有更高的排名,他就会回到追随者状态,所以有更高排名的候选人更容易赢得下一次选举。我们发现这种方法在可用性方面产生了微妙的问题(如果排名较高的服务器发生故障,排名较低的服务器可能需要超时并再次成为候选者,但如果它过早地这样做,它可能会重置选举领导者的进度)。我们对排名系统算法进行了多次调整,但每次调整后都会出现新的极端情况。最终我们得出结论,随机重试的方法更加明显和易于理解。

5.3. 日志复制

一旦一个领导者被选出,它就会开始服务客户端请求。每个客户端请求包含一条命令,这个命令由复制状态机执行。领导者将这个命令作为新的条目追加到其日志中,然后并行地向每个其他服务器发送追加条目 RPC 来复制条目。当这个条目被安全地复制(如下面描述的那样)完成后,领导者将这个条目应用于其状态机,然后返回执行结果给客户端。如果追随者崩溃或运行得很慢,或者网络包丢失,领导者无限次重试追加条目 RPC(即便已经回复了客户端),直到最终所有追随者都存储了所有日志条目。

图 6:日志由按顺序编号的条目组成。每个条目都包含创建它的任期(每个框中的数字)和状态机的命令。如果将条目应用于状态机是安全的,则该条目被视为已提交的(committed)。

日志的组织如图 6 所示。当领导者收到条目时,每个日志条目都会存储一个状态机命令以及任期编号。日志条目中的任期编号用于检测日志之间的不一致,并确保图 3 中的某些属性。每个日志条目还具有一个整数索引,用于标识其在日志中的位置。

领导者决定何时将日志条目应用到状态机是安全的,这样的条目称为已提交的(committed)。Raft 保证已提交的条目是持久的,并且最终会被所有可用的状态机执行。一旦创建条目的领导者在大多数服务器上复制了这个日志条目(例如,图 6 中的条目 7),这个日志就会被提交。这也会提交领导者日志中的所有先前条目,包括以前的领导者创建的条目。第 5.4 节讨论了在领导者变更后应用此规则时的一些微妙之处,并且还表明这种提交的定义是安全的。领导者跟踪它知道要提交的最高索引,并将该索引包含在未来的日志追加 RPC(包括心跳)中,以便其他服务器最终发现。一旦追随者得知日志条目已提交,它就会将该条目应用于其本地状态机(按日志顺序)。

我们设计了 Raft 的日志机制以保持在不同服务器上的日志的高度一致。这个日志机制不仅简化了系统行为并使其更可预测,也是确保安全性的重要组成部分。Raft 维护下列属性,这些属性一起构成了图 3 中的 Log Matching。

  • 如果不同日志中的两个条目具有相同的索引和任期,则它们存储相同的命令。
  • 如果不同日志中的两个条目具有相同的索引和任期,则所有前面的条目中的日志都是相同的。

第一个属性来自这样一个事实,即领导者在给定任期内最多创建一个具有给定日志索引的条目,并且日志条目永远不会改变它们在日志中的位置。第二个属性由追加条目(AppendEntries)执行的简单一致性检查来保证。当发送一个记录追加 RPC 时,领导者在其中包含其日志中紧挨新条目的前一个条目的索引和任期,如果追随者没有在其日志中发现与之有相同的索引和任期的条目,追随者就会拒绝这些新条目。一致性检查作为一个归纳步骤:日志的初始空状态满足 Log Matching,并且一致性检查在日志扩展时保持 Log Matching。结果是,每当追加条目(AppendEntries)成功返回时,领导者通过新条目知道追随者的日志与自己的日志相同。

正常运行时,领导者和追随者的日志保持一致,所以追加条目的一致性检查永远不会失败。然而,领导者崩溃可能导致日志不一致(旧的领导者可能还没有完全复制完其日志中的所有条目),这些不一致会在一系列领导者和追随者崩溃中加剧。图 7 说明了追随者的日志可能与新领导者的日志不同的方式。一个追随者可能缺少领导者上存在的条目,可能有领导者上不存在的额外条目,或两者兼而有之。日志中缺失的和无关的条目可能跨越多个任期。

图 7:当顶部的领导者上台时,任何场景(a-f)都可能出现在追随者日志中。每个方框代表一个日志条目,方框中的数字代表其任期编号。一个追随者可能错过条目(a-b),可能有额外未提交的条目(c-d),也可能两者都有(e-f)。以 f 举例,发生 f 这种的场景的情况可能是:f 作为任期 2 的领导者,在其日志中添加了几个条目,然后在提交这些条目之前崩溃了,一个都没提交(这就导致其他服务器,即任期 2 时期的追随者,都没有这些条目)。f 迅速重启,并成为了任期 3 的领导者,在其日志中添加了比之前多了一点的日志,在任期 2 和任期 3 内的任何条目被提交前(前文说过,领导者提交一个条目时也会把其日志中的之前没提交的条目提交,包含以前领导者创建的条目),f 又崩溃了,并且在后来的几个任期内保持 down 机状态。

在 Raft 中,领导者处理不一致问题的方式是,强制追随者的日志复制其自己的日志。这意味着追随者日志中的冲突条目将被领导者日志中的条目覆盖。第 5.4 节将表明,当再加上一个限制时,这是安全的。

为了让追随者的日志和领导者自己的一样,领导者必须先找到他们两个日志最后一致的点,然后删除追随者日志中这个点之后的所有条目,再将自己这个点之后的所有条目发送给追随者。所有这些操作都是为了响应追加写入 RPC 执行的一致性检查而发生的。领导者为每个追随者维护一个 nextIndexnextIndex 表示领导者将要给追随者发送的下一个条目的索引。当一个领导者首次上台时,它会将所有 nextIndex 值初始化为其日志中最后一个条目之后的索引(图 7 中的 11)。如果追随者的日志与领导者的日志不一致,则追加条目一致性检查将在下一个追加条目 RPC 中失败。在追加条目 RPC 遭到拒绝后,领导者减小 nextIndex 并重试追加条目 RPC。最终 nextIndex 将达到领导者和追随者日志匹配的点。此时,追加条目将会成功,这将删除追随者日志中的任何冲突条目,并从领导者日志中追加条目(如果有)。一旦追加条目成功,追随者的日志就会与领导者的一致,并且在接下来的任期内都将保持这种状态。

如果需要,可以优化协议以减少被拒绝的追加条目 RPC 的数量。例如,当追随者拒绝一个追加条目请求时,它可以在拒绝信息中包含冲突条目的任期,以及它存储的这个任期的第一个索引。有了这个信息,领导者就可以把 nextIndex 减少到绕过这个任期的所有冲突的条目。这样,每个有冲突条目的任期只需要一个追加条目 RPC,而不是每个条目一个 RPC。在实践中,我们怀疑这种优化是否必要,因为故障很少发生,而且不太可能有很多不一致的条目。

通过这种机制,领导者在上台时无需采取任何特殊措施来恢复日志一致性,它只需要开始正常运行,日志自动收敛以响应 追加条目一致性检查的失败。领导者永远不会覆盖或删除自己日志中的条目(图 3 中的 Leader Append-Only 属性)。

这种日志复制机制展示了第 2 节中描述的理想共识属性:只要大多数服务器处于运行状态,Raft 就可以接受、复制和应用新的日志条目。在正常情况下,可以通过单轮 RPC 将新条目复制到大多数集群,并且单个慢速追随者不会影响性能。

5.4. 安全性

前面的小节描述了 Raft 如何选举领导者,如何复制日志条目。然而,到目前为止所描述的机制还不足以确保每个状态机以相同的顺序执行完全相同的命令。例如,一个追随者在领导者提交几个日志条目时不可用,后来这个追随者被选举为领导者并使用新的条目覆盖了这些没有提交的条目,结果就是,不同的状态机可能执行不同的命令序列。

前文说过,领导者先把日志条目复制到大多数服务器上以后,才会提交这些条目,然后追随者将复制来的条目应用到其状态机上。这里说的就是由于领导者提交的时候某个追随者不可用,导致追随者没有把这些提交的条目应用到其状态机。当这个追随者后来成为新的领导者时,可能先应用了其他日志条目到其状态机,最终导致不同的状态机执行的命令序列不一致。

这小节通过在可能被选举为领导者的服务器上添加一个限制来完成 Raft 算法。这个限制确保任意给定任期的领导者都包含在以前任期提交的所有条目(图 3 中的 Leader Completeness 属性)。选举限制使得我们提交的规则更精确。最后,我们展示了图 3 中的 Leader Completeness 属性的证明草图,并展示了它如何导致复制状态机的正确行为。

5.4.1. 选举限制

在任何基于领导者的共识算法,领导者最终都必须存储所有已提交的日志条目。在一些共识算法中,例如 Viewstamped Replication,一个领导者可以被选举出,即使这个领导者一开始没有包含所有已提交的条目。这些算法包含额外的机制来识别缺失的条目,并将这些条目传输给这个新领导者,无论是在选举过程中还是之后不久。不幸的是,这导致了相当多的额外机制和复杂性。Raft 使用一种更简单的方法,它保证从选举的那一刻起,每个新领导者上都存在之前任期内所有已提交的条目,而无需将这些条目转移给领导者。这意味着日志条目只在一个方向流动,从领导者到追随者,领导者永远不会覆盖它们日志中的现有条目。

Raft 使用投票进程来阻止一个候选人赢得选举,除非这个候选人的日志包含全部已提交的条目。候选人为了被选举为领导者,必须和集群中的大多数服务器联系,这就意味着每个已提交的条目必须在这些服务器中的至少一个上存在。如果候选人的日志至少与这大多数服务器中的任意其他日志一样是最新的(up-to-date)(“最新的(up-to-date)”在下面精确定义),那么它将持有所有已提交的条目。这个限制由请求投票 RPC 实现:RPC 中包含关于候选人的日志的信息,如果投票者自己的日志比候选人的日志更新,则投票者拒绝投票。

Raft 通过比较日志中的最后一个条目的索引和任期来判断两个日志哪个是更新的。如果两个日志具有不同任期的最后条目,则具有较晚任期的日志是最新的。如果两个日志以相同的任期结束,那么认为较长的日志是最新的。

5.4.2. 提交以前任期中的条目

如第 5.3 节描述的那样,对于领导者的当前任期中的一个条目,一旦其已经存储在大多数服务器上了,领导者就知道这个条目已经被提交了。如果领导者在提交一个条目前崩溃,未来的领导者会尝试完成这个条目的复制,但是未来的领导者不能立即断定上一任期的条目一旦存储在大多数服务器上就是已提交的。图 8 描述了一个场景,一个旧的日志条目存储在大多数服务器上,然而仍然可能被未来的领导者覆盖。

图 8:一个时间序列,显示了新的领导者为什么不能使用更旧的任期的日志条目来确定提交。

  1. 在 (a) 中 S1 是任期 2 的领导者,其部分复制了索引 2 上的日志条目(即黄色方框,只在它自己和 S2 上复制了,没达到大多数要求)。方框中的数字代表任期编号,黑色加粗边框表示这个服务器是当前任期的领导者。
  2. 在 (b) 中 S1 崩溃了;S5 获得了 S3、S4 和其自己的选票(此时 S5 只与 S3、S4 有至少一样新的日志,S1 和 S2 会认为 S5 的日志更旧,不会给 S5 投票),达到了大多数要求,被选举为任期 3 的领导者。S5 接受了日志中索引 2 处的一个不同的条目(即蓝色方框,与之前的黄色方框不同)。
  3. 在 (c) 中 S5 崩溃了,其任期 3 内的条目(蓝色方框)还没有复制,只有 S5 有。S1 重启后被选举为任期 4 的领导者(除了 S5 都可以给 S1 投票)。S1 接受了其日志中索引 3 处的新条目(粉色方框,还没有复制)并继续复制(黄色方框)。S1 的旧的任期 2 的条目(黄色方框)复制完成后,在这一时刻,任期 2 中的日志条目已经在大多数服务器上完成复制,但还没有提交。
  4. (第 4, 5 点二选一)此时,如果 S1 像 (d) 中那样崩溃,S5 可以当选领导者(可以有 S2、S3 和 S4 和其自己的选票)并用自己的任期 3 中的条目(蓝色方框)在所有服务器上覆盖 S1 旧的任期 2 的条目(黄色方框)。
  5. (第 4, 5 点二选一)然而,如果 S1 在崩溃前复制了其当前任期 4 的条目(粉色方框)到大多数服务器,如 (e),然后黄色方框就是已提交的(前文说过领导者提交当前任期的条目时会一起把以前任期的没有提交的条目提交了。此后 S5 无法再赢得选举)。此时,S1 日志中的所有先前条目也都是已提交的了。

为了消除图 8 中的问题(上面第 4 点),Raft 永远不会通过计算副本数量来提交先前任期的日志条目,只有来自领导者当前任期的日志条目通过计算副本数量来提交,一旦以这种方式提交了当前任期中的条目,则由于日志匹配(Log Matching)属性,所有先前的条目都将间接提交。在某些情况下,领导者可以安全地断定较旧的日志条目是已提交的(例如,如果该条目存储在每个服务器上),但 Raft 为简单起见采取了更保守的方法。

Raft 在这种提交规则中产生了这种额外的复杂性,因为当领导者从之前的任期复制条目时,日志条目会保留其原始任期号。在其他共识算法中,如果新的领导者从先前的“任期”中复制条目,它必须使用新的“任期编号”来这样做。Raft 的方法使推理日志条目的信息变得更容易,因为它们随着时间的推移在日志保持相同的任期编号。此外,与其他算法相比,Raft 中的新领导者发送的先前任期的日志条目更少(其他算法必须发送冗余日志条目以重新编号,然后才能提交)。

5.4.3. 安全性论证

图 9:如果 S1(任期 T 的领导者)提交了当前任期的一个新日志条目,S5 被选举为后面任期 U 的领导者,那么必须至少有一个服务器(S3)接受了 S1 复制的日志条目,并投票给了 S5。

前文已经给出了完整的 Raft 算法,我们现在可以更准确地论证领导者完整性(Leader Completeness)属性成立(这个论证基于安全性证明,参见第 9.2 节)。我们假设 Leader Completeness 属性不成立,那么我们证明一个矛盾(反证法)。

假设任期 $T$ 的领导者($leader_T$)提交了其任期中的一个日志条目,但该日志条目并未由未来某个任期的领导者存储。考虑最小任期 $U$,$U \gt T$,其领导者($leader_U$)没有存储这个条目。

  1. 在选举时,$leader_U$ 的日志中必须没有这个已提交的条目(领导者永远不会删除或覆盖条目)。
  2. $leader_T$ 在集群的大多数服务器上复制了该条目,$leader_U$ 获得了集群大多数服务器的投票。因此,至少有一个服务器(“投票者”)既接受了 $leader_T$ 的条目,又投票给了 $leader_U$,如图 9 所示。这个投票者是达成矛盾的关键。
  3. 这个投票者必须是先接受来自 $leader_T$ 的已提交的条目,之后再给 $leader_U$ 投票。否则,投票者会拒绝来自 $leader_T$ 的追加条目 RPC,因为这时其当前的任期就大于 $leader_T$ 的任期 $T$ 了。
  4. 投票者在投票给 $leader_U$ 时仍然存储该条目,因为每个涉及的领导者都包含该条目(这里是假设 $leader_U$ 日志中有这个条目。这里投票者会认为 Leader Completeness 属性成立,即新的领导者的日志中一定包含这个已提交的条目,不然都不会给 $leader_U$ 投票的。第 5.4.1 小节说过,Raft 保证从选举的那一刻起,每个新领导者上都存在之前任期内所有已提交的条目)。领导者永远不会删除条目,而追随者只会在与领导者冲突时删除条目。
  5. 投票者投票给了 $leader_U$,所以 $leader_U$ 的日志必须和投票者的一样是最新的。这导致了以下两个矛盾之一(第 6, 7 点的两个矛盾之一)。
  6. 首先,如果投票者和 $leader_U$ 共享相同的最后日志任期(即二者一样新),那么 $leader_U$ 的日志必须起码和投票者的一样长,所以 $leader_U$ 的日志得包含投票者日志中的每个条目。这与我们一开始的假设矛盾,因为投票者包含已提交的条目而 $leader_U$ 被假定不包含。
  7. 否则,$leader_U$ 的最后一个日志任期必须大于投票者的。此外,它大于 $T$(且小于 $U$),因为投票者的最后一个日志任期至少为 $T$(它包含来自任期 $T$ 的已提交条目)。创建 $leader_U$ 最后一个日志条目的早前的领导者必须在其日志中包含这个已提交的条目(假设)。那么,根据日志匹配(Log Matching)属性,$leader_U$ 日志也必然包含这个已提交的条目,这与我们一开始的假设矛盾。
  8. 这样就完成了矛盾证明。因此,所有大于 $T$ 的任期的领导者必须包含任期 $T$ 的领导者在其任期 T 内提交的所有条目。
  9. 日志匹配(Log Matching)属性保证未来的领导者也将包含间接提交的条目,例如图 8(d) 中的索引 2。这里没搞清楚这个图咋回事,好像没能说明这一点的问题。

给定领导者完整性(Leader Completeness)属性,我们可以证明图 3 中的状态机安全(State Machine Saft)属性。该属性表明,如果一个服务器已将给定索引处的日志条目应用到其状态机,则没有其他服务器会为这个相同索引应用不同的日志条目。当服务器将一个日志条目应用到它的状态机时,它的日志必须与领导者的日志一致,并且该条目必须被提交。现在考虑任何服务器应用给定日志索引的最低任期,日志完整性(Log Completeness)属性(这个属性好像不是图 3 中的,但论文原文就是这么写的)保证所有更高任期的领导者将存储相同的日志条目,因此在更高任期应用索引的服务器将应用相同的值。因此,状态机安全属性成立。

最后,Raft 要求服务器按照日志索引顺序应用条目。结合状态机安全属性,这意味着所有服务器将以相同的顺序将完全相同的一组日志条目应用于其状态机。

5.5. 追随者和候选人崩溃

直到这一节以前,我们都在聚焦领导者的故障。相比领导者崩溃,处理追随者和候选人的崩溃要容易得多,且追随者和候选人的崩溃处理方法相同。

如果一个追随者或候选人崩溃了,未来给它发送来的请求投票 RPC 和追加条目 RPC 都会失败。Raft 通过无限次重试来处理这些失败,如果这个崩溃的服务器重启了,那重试的 RPC 将成功完成。

如果一个服务器处理完成了 RPC,但在响应前崩溃了,那它会在重启后收到一样的 RPC。Raft 的 RPC 是幂等的,所以这样做不会有问题。例如,如果一个追随者收到一个追加条目请求,这个请求中包含的日志条目已经存在于这个追随者的日志当中了,那么追随者就会忽略这个新请求中的这些条目。

5.6. 时间和可用性

我们对 Raft 的要求之一是安全性不能依赖于时间:系统不能仅仅因为某些事件比预期发生得更快或更慢而产生错误的结果。然而,可用性(系统及时响应客户的能力)一定会不可避免的依赖时间。例如,如果消息交换花费的时间比服务器崩溃的一般间隔时间更长,候选人不会为了赢得选举而一直等。没有一个稳定的领导者,Raft 就无法进行下去。

领导人选举是 Raft 的一个方面,其时机最为关键。只要系统满足以下时序要求,Raft 就能够选举并维持一个稳定的领导者:

在这个不等式中:

  • broadcastTime : 广播时间。一个服务器并行地向集群中的每个服务器发送 RPC 并收到响应平均时间。
  • electionTimeout : 选举超时时间。在第 5.2 节描述过的选举超时时间。
  • MTBF : Mean Time Between Failure,平均无故障工作时间。单个服务器多次崩溃的平均间隔时间。

广播时间 broadcastTime 应该比选举超时时间 electionTimeout 小一个数量级,以便领导者可以可靠地发送心跳消息以阻止追随者开始选举。鉴于用于选举超时的随机方法,这种不等式也使得分裂投票不太可能。选举超时时间应该比 MTBF 小几个数量级,这样系统才能稳步前进。当领导者崩溃时,系统将在大致的选举超时时间内不可用,我们希望这仅代表总时间的一小部分。

广播时间和 MTBF 是底层系统的属性,选举超时时间是由必须由我们选择的。因为 Raft 的 RPC 往往要求接收者将信息持久化到稳定的存储上,所以广播时间可能的范围是 0.5ms 至 20ms,依赖于存储技术。因此,选举超时时间可能在 10ms 至 500ms 之间。一般的服务器 MTBF 为几个月或更长,很容易满足时序要求。

6. 集群成员变更

到目前为止,我们都假设集群配置(参与共识算法的服务器集)是固定的。实际上,修改这个配置有时是有必要的,例如,在服务器发生故障时更换服务器或更改复制级别。尽管可以通过将整个集群离线再重启的方式来实现配置修改,但这会让集群在此期间不可用。此外,如果有任何手动步骤,则存在操作员犯错误的风险。为了避免这些问题,我们决定自动化配置修改并将它们合并到 Raft 共识算法中。

为了使配置更改机制安全,在过渡期间必须没有可能在同一任期内选举两个领导者。不幸的是,服务器直接从旧配置切换到新配置的任何方法都是不安全的。一次原子地切换所有服务器(上的配置)是不可能的,因此在过渡期间集群可能会分裂成两个独立的多数(如图 10)。

图 10:直接从一个配置切换到另一个配置是不安全的,因为各个服务器会在不同的时间切换。在这个例子中,集群从 3 个服务器增加到 5 个。不幸的是,有一个时间点,此时对于同一任期,可能有两个不同的领导者被选举出,一个持有旧配置(C_old)中的大多数选票,一个持有新配置(C_new)的大多数选票。

为了确保安全性,配置变更必须采用一种两阶段(two-phase)的方法。实现两阶段的方法有很多种,例如,一些系统使用第一阶段来禁用旧配置,所以此时系统无法处理客户端请求,然后用第二阶段启用新的配置。在 Raft 中,集群首先切换到一个过渡配置,这个过渡配置称为联合共识(joint consensus),一旦联合共识被提交,这个系统就会转换到新的配置。联合共识结合了新旧配置:

  • 日志条目将被复制到两个配置中的全部服务器上。
  • 来自任一配置的任何服务器都可以充当领导者。
  • 协议(用于选举和条目提交)同时需要与旧配置和新配置中的大多数。

联合共识允许各个服务器在不同时间在配置之间进行转换,而不会影响安全性。此外,联合共识允许集群在整个配置更改期间继续为客户端请求提供服务。

图 11:配置变更的时间线。虚线表示已创建但未提交的配置条目,实线表示最新提交的配置条目。领导者首先在其日志中创建配置条目 C_old,new,并将其提交给 C_old_new 配置中集群的大多数(这里的大多数含义为 C_old 中的大多数和 C_new 中的大多数)。然后领导者创建条目 C_new 并将其提交给新配置中的大多数。在 C_old_new 条目提交后至 C_new 条目创建前的任何时间点,新旧配置都不可以独立作出决策。

集群配置使用复制日志中的特殊条目进行存储和通信。图 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{old}$ 和 $C{new}$ 都不能在没有对方批准的情况下做出决定,并且领导者完整性(Leader Completeness)属性确保只有拥有 $C{old,new}$ 日志条目的服务器才能被选为领导者。领导者现在可以安全地创建描述 $C{new}$ 的日志条目并将其复制到集群。同样,此配置将在每台服务器上看到后立即生效。当根据 $C{new}$ 的规则提交新配置后,旧配置就无关紧要了,可以关闭不在新配置中的服务器。如图 11 所示,在任何时间 $C{old}$ 和 $C_{new}$ 都不能独立做决策,这保证了安全性。

对于变更配置,还有三个问题要解决。第一个问题是,新服务器一开始可能没有存储任何日志条目。如果它们以这个状态被添加到集群中,他们可能需要很长时间才能赶上,在此期间可能无法提交新的日志条目。为了避免可用性间隔,Raft 在变更配置前引入了一个额外的阶段,在该阶段中,新服务器作为非投票成员加入集群(领导者将日志条目复制给它们,但它们不被考虑为多数)。一旦新服务器赶上了集群的其余部分,变更后的配置就可以按之前讨论过的流程继续运作。

第二个问题是,集群的领导者可能不是新配置中的部分了。这种情况,这个领导者一旦将 $C{new}$ 日志条目提交,它会下台(返回追随者状态)。这就意味着存在一段时间(领导者正在提交 $C{new}$ 时,即正在复制 $C{new}$ 日志条目时),领导者会管理一个不包含它自己的集群,它复制条目时不会把自己算进大多数里。领导者转换发生在 $C{new}$ 提交时,因为这是新配置可以独立运行的第一个点(以后总是可以从 $C{new}$ 中选择领导者),在这一点以前,可能只有 $C{old}$ 中的服务器才能被选为领导者。

第三个问题是,被删除的服务器(不在 $C_{new}$ 中的服务器)可能会破坏集群。这些服务器不会收到心跳,所以它们会超时并开始新的选举,会发送带着新任期数的请求投票 RPC,这会导致当前的领导者转回追随者状态。最后,一个新的领导者被选出来,但是被移除的服务器会再次超市然后重复这个过程,导致集群可用性变得很差。为了预防这个问题,当服务器认为当钱有一个领导者存在时,它们会忽略请求投票 RPC。具体来说,如果服务器在听取当前领导者的最小选举超时时间内收到请求投票 RPC,它不会更新其任期或授予其投票。这不会影响正常的选举,每个服务器在开始选举之前至少等待一个最小的选举超时,但是它有助于避免被移除的服务器造成的中断:如果领导者能够获得其集群的心跳,那么它将不会被更大的任期号废止。

7. 日志压缩(Log compaction)

Raft 的日志在正常运行时会增长,以容纳更多的客户端请求,但在实际系统中,不能让它无限制地增长。随着日志变长,它会占据更多的空间,并会在重放时花费更多的时间,如果没有某种机制来丢弃日志中积累的过时信息,这最终会导致可用性问题。

快照是最简单的压缩方法。在快照中,整个当前系统状态被写入稳定存储上的快照,然后丢弃到该点以前的整个日志。Chubby 和 ZooKeeper 中使用了快照,本节的其余部分将介绍 Raft 中的快照。

压实的增量方法,例如日志清理和日志结构合并树,也是可能的。它们一次对一小部分数据进行操作,因此它们随着时间的推移更均匀地分布压缩负载。它们首先选择一个已经积累了许多已删除和覆盖对象的数据区域,然后他们更紧凑地重写该区域中的活动对象并释放该区域。与快照相比,这需要显着的额外机制和复杂性,快照通过始终对整个数据集进行操作来简化问题。虽然日志清理需要对 Raft 进行修改,但状态机可以使用与快照相同的接口来实现 LSM 树。

图 12:一个服务器使用一个新的快照替换其日志中已提交的条目(索引 1 ~ 5),该快照只存储当前状态(本例中的变量 `x <- 0` 和 `y <- 9`)。快照最后包含的索引和任期用于将快照定位在条目索引 6 之前的日志中。

图 12 给出了 Raft 中快照的基本思想。每个服务器独立制作快照,快照只覆盖其日志中已提交的条目。大部分工作由状态机将其当前状态写入快照构成。Raft 也在快照中包含一小部分元数据:最后包含的索引(last included index) 是快照替换的日志中最后一个条目的索引(状态机应用的最后一个条目),最后包含的任期(last included term) 是该条目的任期,保留这些以支持快照后第一个日志条目的追加条目一致性检查,因为该条目需要以前的日志索引和任期。为了启用集群成员变更(第 6 节),快照还包括日志中截止最后包括的索引的最新的配置,一旦服务器完成写入快照,它可能会删除所有日志条目,直到最后包含的索引,以及任何先前的快照。

尽管服务器通常独立制作快照,但领导者必须偶尔将快照发送给落后的追随者。当领导者已经丢弃了它需要发送给追随者的下一个日志条目时,就会发生这种情况。幸运的是,这种情况在正常操作中不太可能发生:跟上领导者的追随者已经有了这个条目。但是,异常缓慢的追随者或加入集群的新服务器(第 6 节)不会。让这样的追随者更新的方法是让领导者通过网络向它发送快照。

此图 13 为翻译版本,但保留了部分相对重要的英文原词。在这里查看原图。

图 13:安装快照(InstallSnapshot) RPC 摘要。快照被分割成块进行传输,这些块可以为追随者提供了活跃信号,使追随者可以重置其选举计时器。

领导者使用名为安装快照(InstallSnapshot)的新 RPC 将快照发送给落后太远的追随者,见图 13。当一个追随者收到一个带有此 RPC 的快照,它必须决定对它现存的日志条目做什么。通常这个快照中将包含没有已经存在于接受者日志中的新信息,在这种情况下,追随者丢弃它的日志条目,它全部被快照所取代,并且可能有未提交的条目与快照冲突。反之,如果追随者收到一个快照,快照中描述了其日志的一个前缀(由于重传或错误),则追随者会删除被快照覆盖的条目,但快照后面的条目仍然有效并且必须保留。

这种快照方法背离了 Raft 的强领导者原则,因为追随者可以在领导者不知情的情况下制作快照。然而,我们认为这种背离是合理的。虽然有一个领导者有助于在达成共识时避免冲突决策,但在创建快照时已经是达成了共识的,所以没有决策冲突。数据仍然只从领导者流向追随者,只是追随者现在可以重新组织他们的数据。

我们考虑了另一种基于领导者的方法,其中只有领导者会创建一个快照,然后它将这个快照发送给它的每个追随者。然而,这有两个缺点。第一,给每个追随者发送快照会浪费网路带宽、减慢快照进程。每个追随者已经有了创建其自己的快照所需要的信息,一个服务器从其本地状态生成一个快照往往比通过网络发送或接收一个快照要廉价得多。第二,领导者的信息更复杂。例如,例如,领导者需要在向追随者复制新日志条目的同时向追随者发送快照,以免阻塞新的客户端请求。

还有两个影响快照性能的问题。第一,服务器必须决定何时创建快照。如果一个服务器创建快照太频繁,会浪费磁盘带宽和能量;如果太不频繁,它可能会耗尽其存储容量,并且会增加重启期间重放日志所需的时间。一种简单的策略是在日志达到固定大小(以字节为单位)时拍摄快照。如果将此大小设置为远大于快照的预期大小,则快照的磁盘带宽开销将很小。

第二个性能问题是,写一个快照会花掉大量的时间,我们又不想延迟正常的操作。解决方案是使用写时复制(copy-on-write)技术,以便可以接受新的更新而不影响正在写入的快照。例如,使用功能数据结构构建的状态机自然支持这一点。或者,操作系统的写时复制支持(例如,Linux 上的 fork)可用于创建整个状态机的内存快照(我们的实现使用这种方法)。

8. 客户端交互

本节介绍客户端如何与 Raft 交互,包括客户端如何找到集群领导者以及 Raft 如何支持线性化语义。这些问题适用于所有基于共识的系统,Raft 的解决方案与其他系统类似。

Raft 的客户端将它们所有的请求发送给领导者。当一个客户端第一次启动,它会连接一个随机选择的服务器。如果这个客户端第一次选择的不是领导者,那这个服务器就会拒绝这个客户端的请求并提供它听到的(AppendEntries 请求中包含领导者的网络地址)最近的领导者信息。如果领导者崩溃了,客户端的请求会超时,然后客户端再试一个随机选择的服务器。

我们对 Raft 的目标是实现可线性化的语义(每个操作似乎在其调用和响应之间的某个时间点立即执行,恰好一次)。但是,到目前为止,Raft 可以多次执行命令。例如,如果领导者在提交日志条目后但在响应客户端之前崩溃,则客户端将使用新的领导者重试命令,导致其执行第二次。解决方案是让客户为每个命令分配唯一的序列号。然后,状态机跟踪为每个客户端处理的最新序列号以及相关响应。如果它收到一个序列号已经被执行过的命令,它会立即响应而不重新执行请求。

执行只读操作无需在日志中写入任何内容。然而,如果没有额外的措施,这将面临返回陈旧数据的风险,因为响应请求的领导者可能已被它不知道的新领导者取代。线性化读取不能返回陈旧数据,Raft 需要两个额外的预防措施来保证这一点,而不使用日志。第一,领导者必须拥有提交的条目的最新信息。领导者完整性(Leader Completeness)属性确保领导者持有所有已提交的条目,但是在其任期开始时,它可能不知道哪些条目是已提交的。为了找出这些已提交的条目,领导者需要提交一个其当前任期的条目。Raft 通过让每个领导者在其任期开始时将一个空白的 no-op 条目提交到日志中来处理这个问题。第二,领导者在处理一个只读请求时必须检查其是否已经被罢免(因为如果有一个更近的领导者被选出,它持有的信息可能就是旧的)。Raft 通过让领导者在响应只读请求前与集群中的多数交换心跳信息来处理这个问题。或者,领导者可以依靠心跳机制来提供一种租约形式,但这将依赖于安全时间(它假设有界时钟偏差)。