Raft 论文研读笔记

摘要

Raft 是用于管理复制日志的一致性协议，与 Multi-Paxos 作用相同，效率相当，但是架构更简单，更容易实现。Raft 将共识算法的关键因素分为几个部分：

Leader election 领导者选举
Log replication 日志复制
Safety 安全性

且 Raft 用了一种更强的共识性来减少要考虑的状态 state 的数量。

Raft 对比于现有的共识算法有几个新特性：

Strong leader（强领导性）：相比于其他算法，Raft 使用了更强的领导形式。比如，日志条目只能从 leader 流向 follower（集群中除 leader 外其他的服务器）。这在使 Raft 更易懂的同时简化了日志复制的管理流程。
Leader election（领导选举）：Raft 使用随机计时器来进行领导选举。任何共识算法都需要心跳机制（heartbeats），Raft 只需要在这个基础上，添加少量机制，就可以简单快速地解决冲突。
Membership changes（成员变更）：Raft 在更改集群中服务器集的机制中使用了一个联合共识（joint consensus）的方法。在联合共识（joint consensus）下，在集群配置的转换过程中，新旧两种配置大多数是重叠的，这使得集群在配置更改期间可以继续正常运行。

复制状态机

复制状态机用于解决分布式系统中的各种容错问题，通常使用日志复制来实现。如图，每个服务器保存一份含有一系列命令的日志，然后服务器上的复制状态机按顺序执行日志中的命令。每一份日志按相同顺序包含了相同的命令，因此每个状态机都能处理相同的命令序列。

共识算法主要是保证复制日志的一致性。每个服务器上的共识模块收到来自客户端的指令后，先按顺序存到日志里，然后与其他服务器上的共识模块通信，确保每个服务器上的日志都以相同顺序包含相同命令。当命令复制完成时，每台服务器上的状态机就会按日志顺序处理命令，并将输出结果返回给客户端。

共识算法通常包含以下特征：

确保在非拜占庭错误下的安全性，从不返回一个错误的结果。（即使网络延迟、分区、数据包重复、丢包、乱序）
只要过半服务器是可运行的，且能互相通信和与客户端通信，那么共识算法可用。
保证日志一致性上不依赖于时序：错误的时钟和极端消息延迟在最坏情况下会产生影响可用性的一系列问题。
只要集群中过半服务器响应了 RPC，命令就可以被视为完成。

Paxos 存在的问题

非常难理解作者选择了 Single-decree Paxos 来作为基础，而 Single-decree Paxos 的两个阶段没有简单直观的说明，又不能分开理解，所以很难理解为什么这个算法能起作用。而 Multi-Paxos 的合成规则又很复杂。
没有为实际实现提供一个良好的基础：没有广泛认同的针对 Multi-Paxos 的算法，Lamport 在论文中概述了针对 multi-Paxos 的可能的方法（he sketched possible approaches to multi-Paxos），但是缺失了很多细节。虽然有人实现，但是实现时需要解决很多问题，解决后又成为了一个与 Paxos 不同的架构。

Designing for understandability

主要讲了作者在设计 Raft 算法时以可理解性为优先，在多个备选方案中做抉择时优先考虑可理解性：

问题分解。将问题划分为几个相对独立解决、解释和理解的子问题。
通过减少状态的数量来简化状态空间，尽可能使系统变得更连贯，尽可能消除不确定性。比如日志不允许有空档，限制日志之间可能不一样的方式，另一个例子是随机化方法，引入不确定性来处理可能的选择，减少状态空间，如 leader election。

The Raft consensus algorithm

在 Raft 中，首先选举一个 leader，由这个 leader 全权负责复制日志的管理，Leader 从多个客户端接收日志条目，然后将他们复制给其他的服务器，并在保证安全性的前提下通知其他服务器将日志条目 apply 到他们的状态机中。有了这个 leader，大大简化了复制日志的管理流程。当然，一个 leader 可能会崩溃，此时 Raft 会选举出一个新的 leader 来。

通过选主方式，拆分为三个独立子问题：

Ledaer election 领导选举一个 leader 故障时，会选举一个新的 leader
Log replication 日志复制 leader 必须接收来自客户端的日志并复制给集群中的其他节点，并强制其他节点的日志和自己的保持一致
Safety 安全性 Raft 安全性的关键指状态机中的安全性。如果一个节点将一个有给定 index 的日志条目发给它的状态机，那么集群中不会有节点将相同 index 引用到不同的日志条目。这保证了一个 index 在集群中只会标识唯一一个日志条目。

Raft 基础

一个典型的 Raft 集群中会包含 5 个节点，它可以容忍两个节点失效的情况。在任意一个时刻，集群中的每一个节点都只可能是以下三种身份之一：

leader：它会处理所有来自客户端的请求（如果一个客户端与一个 follower 通信，follower 会将请求重定向到 leader 上）
follower：不会发送任何请求，只是简单响应来自 leader 和 candidate 的请求
candidate：选主时的一个临时状态

一般来说，一个集群只会有一个 leader，其余节点都是 follower。下图是状态的转换关系：

Raft 将时间划分为任意长度的任期（term），每一段任期从选举开始，如果一个 candidate 赢得了选举，则在任期剩余时间内担任 leader。某些情况下一次选举可能选不出 leader，这个任期就会随着无 leader 而结束，同时会有新的一个任期开始，伴随着新的一轮选举。Raft 会保证一个任期内至多只有一个 leader。

由于网络或其他原因，集群中不同节点见到任期转换次数可能是不同的，一个节点甚至可能没观察到整个任期过程。此外，任期还担任了逻辑时钟（logical clock）的角色，使得服务器能发现一些过期的信息，如过期的 leader。

每个节点存储一个当前任期号（current term number），随着时间单调递增，节点通信时会交换任期号，如果发现一个节点的当前任期号比其他节点的任期号小，那么它会将自己的当前任期号更新为较大的那个。如果一个 candidate 或 leader 发现自己的任期号过期了，那么它会立刻回到 follower 状态。如果一个节点收到一个带着过期任期号的请求，它会拒绝这个请求。

Raft 中集群节点以 RPC 形式通信，一般的共识算法主要有两种 RPC：

RequestVote RPCs（请求投票）：由 candidate 在选举过程中发出
AppendEntried RPCs（追加条目）：由 leader 发出，用于日志复制和提供心跳机制。
Raft 为了在节点之间传输快照（snapshot），加了第三种 RPC。当节点没收到 RPC 响应时会重试。

Leader election

Raft 采用心跳机制来触发 Leader 选举。当服务器启动的时候，所有节点都是 follower。一个节点只要从 candidate 或者 leader 那接收到有效的 RPC 就会一直保持 follower 状态，同理，Leader 需要周期性向所有 follower 发起心跳来维持自己的 Leader 低位。心跳，即不包含日志条目的 AppendEntried RPC。

当一个 follower 在一段时间内没收到任何信息时，会导致选举超时（election timeout），那么它会假定目前集群中没有一个有效的 Leader，会开启一个选举来选择一个新的 Leader。

开启选举时，一个 follower 会变成 candidate，然后给自己投票，同时以并行的方式向集群中的每个节点都发送一个 RequestVote RPC，希望得到它们的投票。一个 candidate 会保持这个状态直到以下三个事情之一发生：

它赢得选举，成为新的 Leader
别的节点赢得选举，它会变为 follower
一段时间内没有任何节点赢得选举，开启下一轮选举

当一个 candidate 获取了集群中半数以上节点对同一任期的投票时，它会赢得选举成为新的 Leader，向集群中其他节点发送心跳信息来维持自己的地位，同时阻止新的选举。对于同一个任期，每一个服务器节点按照先来先服务原则只会给一个 candidate 投票，如开启选举的 follower，会给自己投票然后请求别人投票给自己，而自己不能投票给别人。这样保证了集群中最多只有一个 candidate 赢得选举。

candidate 在选举时可能会收到另一个自称 Leader 的节点发来的 AppendEntried RPC。如果这个 leader 的任期号不小于自己的任期号，则这个 candidate 会变为 follower。如果这个 leader 的任期号比自己的任期号还小，candidate 会拒绝请求，保持 candidate 状态。

在第三种情况的结果是重新开启一次选举。举个例子，集群中所有节点都成为 candidate，同时给自己投票，并同时向其他节点请求投票，这个情况会尬住，没有一个 candidate 获取半数以上的投票数，此时每个 candidate 都会进行一次响应超时（timeout），然后自增任期数，开启新一轮选举。

为了避免上述的情况再次发生，Raft 采用了随机选举超时时间（randomized eleection timeouts）来减少无结果投票的发生。为了防止选票一开始被瓜分，选举超时时间从一个固定的区间内随机选择（如 150ms-300ms），这样能将节点分散开，确保大多数情况下只会有一个节点率先结束超时，此时这个节点会在其他节点超时前发送心跳，成为新的 leader，大概率不会产生无结果投票的情况。

选票瓜分的情况亦同，每一个 candidate 在开启一次新选举时重置随机选举超时时间，能够减少一轮无结果投票后再发生一次无结果投票的可能性。

Log replication

当 Leader 被选举出来后，它就要开始为客户端请求提供服务了。每一个客户端请求都包含一条将被复制状态机执行的命令。Leader 会将其作为一个新条目追加到自己的日志中，并同步向其他节点发送含有该日志的 AppendEntries RPC，让它们复制条目。当条目被安全地复制时（创建该日志条目的 Leader 将其复制到过半的节点上），Leader 会将该条目应用到自己的状态机中，状态机执行指令，然后将执行结果返回给客户端。

如果 follower 崩溃或网络丢包导致 Leader 无法收到响应，Leader 会不断重试AppendEntries RPC，直到所有 follower 都成功存储所有日志条目。

当创建该日志条目的 Leader 将其复制到过半的节点上时（如下图），此时该日志被称为已提交的日志，同时，Leader 日志中该条目之前的所有日志都会被提交，包括由其他 Leader 创建的日志条目。Leader 将要提交的日志条目的最高索引包含在未来的 AppendEntries RPC（包括心跳）中，当一个 follower 通过 RPC 知道了一个日志条目被提交时，它会将该条目日志顺序应用到自己的状态机中。

Raft 通过维护两个特性来构成日志匹配特性（Log Matching Property）：

如果不同日志的两个条目有着相同的索引和任期值，那么它们存储着相同的命令
如果不同日志的两个条目有着相同的索引和任期值，那么它们之前的所有日志条目都相同

第一条特性源于给定的一个任期值和一个日志索引中，一个 Leader 最多可以创建一个日志条目，且日志条目在日志中的位置（索引）不会被改变。

第二个特性则是 AppendEntries RPC 执行的简单一致性检查保证的。可以看做是一个懒检查，Leader 会将前一个日志索引位置和任期号包含在 AppendEntries RPC 中，也就是说，这个 AppendEntries RPC 不仅会有当前要同步复制的日志条目（可能，心跳是没有的），还会有前一个日志索引位置和任期号。一个 follower 如果在它的日志中找不到包含相同索引和任期号的条目，它就会拒绝新的日志条目。一致性检查保证了日志扩展时的日志匹配特性，当 follower 响应时，Leader 就知道 follower 的日志一定和自己相同。

正常情况下一致性检查肯定是成功的，但是当 Leader 崩溃时，可能会导致日志处于不一致的状态。

在 Raft 中，Leader 通过强制 follower 复制 Leader 日志来解决日志不一致的问题，即 follower 中与 Leader 冲突的日志会被 Leader 的日志条目所覆盖。

Leader 需要删除 follower 日志中从两者达成一致的最大的条目索引后的所有日志条目，并将自己那个索引后的所有日志条目都发给 follower，这些操作都包含在针对前文的 AppendEntries RPC 的一致性检查的响应中。Leader 维护一个针对每一个 follower 的 nextindex，代表 Leader 要发给 follower 的下一个日志条目的索引。当选出一个新 Leader 时，该 Leader 将所有 nextindex 的值都初始化为自己最后一个日志条目的 index+1（选举时已经保证了 Leader 的数据是最新的，持有最高的任期号），如上图的 11。

如果一个 follower 的日志与 leader 冲突，那么下一次的一致性检查就会失败，AppendEntries RPC 被 follower 拒绝后，leader 对该 follower 的 nextindex-1，重试，直到满足一致性检查，那么这个 index 就是两者达成一致的最大的条目索引。此时将 follower 中冲突位置后的所有日志条目删除，然后根据 leader 发送的日志条目进行追加。如此就能保证 follower 的日志和 leader 的一致。

总结来说，需要两次 RPC 广播来同步状态机。

同步日志 AppendEntries RPC，得到过半节点响应，Leader 状态机推进 commitIndex，追加日志到自己的状态机中，返回 Client 成功
在下一次 AppendEntries RPC 中附加上一次的 commitIndex，follower 收到后再追加日志到自己的状态机中。

Safety

上述讨论的机制都无法保证每一个状态机都会按相同的顺序执行相同的命令。如一个 follower 可能会进入不可用状态，期间 leader 提交了很多日志条目，当这个 follower 重新加入集群时，它可能会被选举为新的 leader，且用新的日志条目去覆盖旧 leader 已经提交的日志条目。

Raft 通过一个限制保证对于给定的任意任期号，其对应的 leader 都包含了之前各个任期所有被提交的日志条目。

Election restriction 选举限制

在很多基于 leader 的共识算法中，一个节点即使没有包含所有已提交的日志条目，它也有可能被选举为 leader。而在 Raft 中，日志条目的传输只能从 leader 到 follower，因此 leader 从来不会覆盖本地日志中已有的日志，保证了新 leader 当选时就将包含了所有任期中已提交的日志条目。

以投票为例，一个 candidate 想当选为 leader，必须获得集群中半数以上节点的投票，如果能获得半数以上节点的投票，说明其日志至少与半数以上的节点一样新（日志中最后一个日志条目的索引和任期号最新，任期号不同，则任期号大的新，任期号相同，则索引最大的新），因此它一定包含了所有已提交的日志条目。当有的节点的日志条目比 candidate 还新，那么它会拒绝投票请求，而 candidate 就必然不会赢得选举。

Committing entries from previous terms

Raft 的 Figure 8 讲了什么问题？为什么需要 no-op 日志？

Leader 不能提交之前任期的日志，只能通过提交自己任期的日志，从而间接提交之前任期的日志。当 leader 交替宕机时，如果允许提交之前任期的日志，可能会产生这种情况：一个索引的日志条目被提交两次甚至是多次，覆盖了已经提交的日志。

这种情况下，超出了选举界定的限制，一个任期号本该不足以赢得选举的节点却选举成功。因此要添加约束：Leader 只能提交自己任期的日志。

Safety argument

反面论证了 leader 的完整性特征，讨论证明了 leader 一定包含以往任期提交的所有日志条目，证明了状态机的安全特性，这样就能保证所有的节点都会按照相同的顺序应用相同的日志条目到自己的状态机中。

follower 和 candidate 崩溃

如果一个 follower 或 candidate 崩溃，后面发送给他们的 RequestVote 和 AppendEntries RPCs 都会失败。Raft 通过无限重试来处理这种失败，如果崩溃的节点重启了，那么这些 RPC 就能被正常响应。Raft 的 RPCs 都是幂等的，发送相同的 RPC 不会造成任何损害，follower 会忽略新的 AppendEntries RPC 中包含的自己已有的日志。

时序与可用性（Timing and availability）

Raft 的安全性不能依赖于时序（timing，整个系统不能因为某些时间运行得比预期快一点或慢一点就产生错误的结果），但是可用性必须要依赖于时序。当信息交换时间比节点崩溃持续时间还长时，会导致集群缺少一个稳定的 leader，而 Raft 将无法正常工作。

Raft 中最关键的地方在于 Leader Election，需要满足以下时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

广播时间：指一个节点并行发送 RPCs 给集群其余节点，并得到响应的平均时间
选举超时时间：指 Leader Election 提到的选举超时时间
平均故障间隔时间：指对于一台机器，两次故障间隔时间的平均值

选举超时时间可以自定义，论文中提到，在一个集群中，广播时间约为 0.5ms-20ms 时，选举超时时间可以设置在 10ms-500ms 之间，而大部分机器的平均故障间隔时间都在几个月甚至更长时间。尽管 leader 崩溃后会有一小段选举超时时间不可用，但是这部分时间很短，远小于平均故障间隔时间，因此可以被接受。

Log compaction

正常情况下，Raft 的日志会随着请求的增加而不断增长，占用大量空间，当一个节点需要恢复到当前集群节点状态时，需要重新执行一遍 committed 的日志，如果这个日志很大，恢复耗时会很久。所以得用一定的方式来压缩日志，清除过时的信息。

最简单的方法就是快照技术（snapshotting），在某个时间点下的整个当前系统状态都会以快照的形式持久化，先前的日志就会被废除。

增量压缩方法（Incremental approaches to compaction），比如日志清理（log cleaning）和日志结构合并树（log-structured merge trees，熟知的 LSM-Tree），都是可行的。这些方法每次只对一部分的数据操作，分散了压缩的负载压力。首先选择一个积累了大量已删除数据和已覆写对象的区域，然后重写还存活的对象，释放该区域。比起快照技术，这种方式引入了大量额外机制和复杂性，而快照技术通过操作数据集来简化问题。当需要日志清理时，状态机会像快照技术一样使用相同的接口来实现 LSM 树。

如上图，每个节点都会独立生成快照，其中只包含自己日志中已提交的条目，其中主要工作是状态机将自己的状态写入快照中，快照还包含了少量的 metadata：

last included index：表示已添加的最后一个 entry 在日志中的 index
last included term：该条目所处的任期号

这些 metadata 支持了快照后的第一个 entry 的一致性检查，因为那个 entry 需要先前一个 entry 的 index 和 term。为了支持集群成员变更，快照包含了到 last included index 为止的最新的配置，一旦一个节点完成了写入快照，可能会删除所有在 last included index 之前的日志条目，以及之前的快照。

尽管通常情况下节点会独立生成快照，但在一个 follower 运行缓慢或刚加入集群时，leader 会发送快照给该 followers，使得它可以赶上 leader，更新到最新的状态。

leader 通过 InstallSnapshot RPC 发送快照给落后的 follower。当一个 follower 接收到这个快照，会决定如何处理当前已存在的日志条目。快照通常包含了已有日志中不存在的新信息，在这种情况下，follower 舍弃了它的所有日志条目，它的日志条目将由快照取代，且可能有与快照冲突的未提交日志条目。相反，当一个 follower 收到了一个描述其日志前缀的快照（可能因为重传或错误），这个被覆盖的日志条目将被删除，但快照后的日志仍然有效，且必须被保留。

在快照生成时，共识已经达成了，因此没有决策会出现冲突。这种情况下数据和以前一样只能从 leader 流向 follower，只是现在允许 follower 可以重新组织它们的数据而已。

作者想过一种可替代的方案，即只有 leader 可以创建快照，然后由 leader 将这份快照发送给其他所有 follower，但是这个方案有两个缺点：

浪费网络带宽和延缓了快照处理过程。实际上每个节点都已拥有自己创建快照的数据，很显然由节点根据本地状态来创建快照更方便。
使得 leader 的实现更复杂。不阻塞新的客户端请求，需要 leader 在发送快照给 follower 的同时做到并行将新的日志条目发给它们，实现起来更为复杂。

还有两个问题会影响快照的性能：

每个节点需要判断何时生成快照。如果频率太高，会浪费大量磁盘带宽和其他资源，如果频率太低，需要承担耗尽存储的风险，也增加了重启时重新执行日志的时间。一个简单的策略是当日志达到一个固定阈值时生成一份快照，如果阈值设置的显著大于期望的日志大小，那么快照的磁盘开销会比较小。
写快照需要一定的时间，如果不希望它影响到正常操作，通常使用写时复制的技术。比如 Redis 的 AOF 日志重写，fork 一个子进程来写快照。但 fork 也会阻塞，阻塞时长与日志大小有关（数据大小->页数->页目录项->页表大小）。

Client interaction

Raft 的客户端将所有请求发给 Leader。当一个客户端第一次启动，它会连上一个随机选择的节点，如果这个节点不是 Leader，这个节点会拒绝客户端的请求，并提供关于最近 Leader 的信息（在 AppendEntries 请求中会写到 Leader 的网络地址）。如果 Leader crash 了，客户端请求会超时，然后客户端会重试，去请求一个被随机选中的节点。

线性化语义是指每次操作看起来都像是在调用和响应之间的某个节点上即时执行，我们希望 Raft 能实现线性化语义。在以上的通信规则中，Raft 可能对同一条执行多次，解决方法是客户端对于每一个指令都赋予一个唯一的序列号，状态机跟踪每个客户端已处理的最新的序列号以及相关联的响应。如果状态机接收到了一条已执行过的指令，就立即作出响应，而不是重复执行该指令。

读操作则可以直接处理而不需要日志记录，但是也会有过期读的风险，比如在网络分区的情况下，Leader 响应客户端请求的时候，它可能已经被新的 Leader 替代了，但是它自己却不知道。

线性化操作肯定不会返回过期的数据。而 Raft 主要通过两个额外的预防措施来保证：

Leader 必须拥有已提交日志条目的最新信息。在 Leader 任期刚开始时，它可能还不知道哪些是已提交的，因此它需要在它的任期中提交一个日志条目。即前文的Committing entries from previous terms，Raft 通过让 Leader 在任期开始的时候提交一个空的日志条目到日志中来解决这个问题。
Raft 在处理读请求时需要检查自己是否已经被替代了。Raft 通过让 Leader 在响应读请求前，先和集群中过半节点交换一次心跳信息来解决该问题。论文中提到另一种可选的方案是 Leader 依赖心跳机制来实现一种租约形式，但是这种方式的安全性依赖于时序（必须有严格的时间误差界限）。

Implementation and evaluation

论文中提供了大概 2000+行的 C++代码作为 Raft 实现。这一节通过可理解性、正确性以及性能三个方面来评估 Raft 算法。

Understandability

作者在斯坦福大学和加州大学伯克利分校进行了一项实验研究，研究调查结果表明大部分人认为 Raft 算法比 Paxos 更容易去实现或解释。

Correctness

作者用 TLA 证明系统机械地证明了日志完整性（Log Completeness Property），但是这个证明依赖的约束前提还没有被机械证明，比如规范中的类型安全。

Raft 是没有证明的，你是不知道他有没有缺陷的，所以需要补形式语言和自动机，要写 coq 或者 tla 去验证算法，这种多状态算法不验证是会出问题的。

Performance

Raft 的性能与其他共识算法如 Paxos 很类似。最关键的点在于 Leader 被选举出来后，它应该在什么时候复制新的日志条目，Raft 通过少量的消息就解决了这个问题（一轮从 Leader 到过半节点的消息传递）。还可以支持批量操作和管道操作来提高吞吐量和降低延迟，很多在其他共识算法中已提出的优化方案都可以用在 Raft 上。

作者反复使一个拥有 5 个节点的集群的 leader 宕机，并计算它检测崩溃和重新选出一个新 leader 所需的时间，结果是最小的宕机时间大约是最小选举超时时间的一半。表名了只需要在选举超时时间上使用很小的随机化即可大大避免出现选举失效的情况。当然，这个时间需要在一定的范围内。比如选举超时时间为 12-24ms 的情况下，只需要平均 35ms 就可以选举出新的 leader，进一步降低选举超时时间可能就会违反 Raft 的不等式的要求。作者推荐的保守的选举超时时间是 150-300ms，不大可能导致不必要 leader 更换，还能提供不错的可用性。