1. 介绍

Paxos 的问题

1. 难理解（Paxos is quite difficult to understand, in spite of numerous attempts to make it more approachable）

2. 难落地。要落地到实际的业务系统，paxos 还需要进行一些调整和扩展。不幸的是，业界并没有对这些调整的细节达成共识（Furthermore, its architecture requires complex changes to support practical systems, and building a complete system based on Paxos requires developing several extensions for which the details have not been published or agreed upon. As a result, both system builders and students struggle with Paxos.）

Zab & ZooKeeper

在构建系统方面，比 Paxos 要好，但不是为了简单和可理解的目的而设计的，理解和实现算法的负担依然非常重。

2 动机

共识是容错系统中的一个基础问题：即使面对故障，服务器如何就共享状态达成一致？ 这个问题存在于需要提供高水平可用性且不能牺牲一致性的各种系统中；因此，几乎所有保证一致性的大规模存储系统都使用共识。

2.1 通过复制状态机实现容灾（fault tolerance）

共识通常出现在复制状态机的上下文中。复制状态机通常由复制日志来实现，如下图所示：有一组机器，每台机器存储一个包含一系列命令的日志，状态机按照顺序执行这些命令。所有机器的日志里包含相同顺序的相同命令，所以所有的状态机都执行相同的命令序列。由于状态机是确定的，所以它们计算相同的状态、输出相同的结果序列。

而保证复制日志的一致性就是共识算法的任务。一个服务的共识模块从客户端接收命令，将命令添加到本地的 log 中，并发送给其它服务的共识模块，最终所有的 log 都包含相同顺序的相同命令，即使部分服务发生故障。所有服务的状态机按照相同的顺序执行日志中的命令，并返回结果给客户端。最终，所有的服务一起构成一个单一的、可靠的状态机。

在实际系统中，共识算法通常具有如下特性：

1. 在所有非拜占庭场景下保证安全性（绝不返回不正确的结果），包括网络延迟、分区、丢包、重传和乱序。

2. 只要集群中的大多数服务是可用的并可以相互以及与客户端通讯，就能提供全部功能（可用性）。

3. 不依赖于计时(timing)来确保日志的一致性：在最坏的情况下，错误的时钟（定时器不能工作这种）以及极端的消息延迟可能导致不可用。也就是说，它们使用一种异步模型来维护安全性，在该模型中，消息传输和处理可以以任意速度进行。

4. 通常，只要集群中的大多数节点成功对一轮 rpc 请求作出响应，就可以完成一条命令的执行。少数比较慢的节点不会影响整体性能。

2.2 复制状态机的常用示例

最典型的场景是，由 3 或 5 个实例构成一个复制状态机，其它服务可以使用该状态机来协调它们的行为，如图 2.2 (A)所示。比如提供配置管理、锁、组管理等。图(b)是其中一个示例场景：一组服务中同一时刻只有一个 leader 来管理剩下的所有实例，leader 会将关键的状态数据写入共识系统，一旦 leader 故障，其它实例可以使用共识系统来竞争 leader，并从共识系统中取出状态数据来恢复集群状态。很多大型存储系统都是这么做的，比如 GFS、HDFS、RAMCloud 等

共识有时候也被用于复制大量数据，如图 2.3 所示。比如 Megastore、Spanner、Scatter 这些大型分片存储系统

2.3 Paxos 的问题

Paxos 首先定义了一个能够就单个决策达成一致的协议，比如单个复制的日志条目。我们称之为 Single-Decree Paxos。Paxos 然后联合多个协议实体来实现多个决策的达成，称之为 Multi-Paxos。Paxos 的正确性已经被证明，正常情况下，Paxos 也是高效的，也支持集群成员变更。

有两个大的缺点：

1. 难理解。有一些用更简单的术语来简化 Paxos 的尝试，但只针对 single-decree Paxos。Raft 的作者花了一年时间看了许多文档，并设计了自己的 raft 协议后，才真正理解了 Paxos。

2. 难实现。没有为开发一个实际的系统提供好的基础。Lamport 大多数的描述都是针对 Single-Decree Paxos，并简单描绘了实现 Multi-Paxos 的可能方法，但缺少很多细节。有很多补充和优化 Paxos 的尝试，但它们互不相同，也与 Lamport 的描述不一样。

3. Paxos 的结构也不适合构建实际的系统，基于 Single-Decree 来组装 Multi-Paxos 增加了复杂性。另一个问题是 Paxos 使用对称的 Peer-to-Peer 作为它的核心（尽管也建议使用弱 Leader 关系来优化性能）。在简单的、只做一个裁定场景下还可行，但现实中很少这种简单场景。如果要做一系列的裁定，还是先选出一个 leader，再由该 leader 来协调操作更简单和高效一些。

所以很多共识算法最开始是基于 Paxos 来开发的，但到最后却与 Paxos 的论文相去甚远，最终得到一个未经证明的系统。

3 Raft 的基本算法

3.1 为可理解性而设计

Raft 时有若干目标：它必须为系统构建提供完整且可实现的基础，以减少开发者所需要的大量设计工作。它在所有的情况下都必须是安全的，且在典型的运营环境下都是可用的，并且在一般的情况下都是高效的。但 Raft 最重要的目标--也是最难的挑战--是可理解性。它必须让大量受众轻松理解。另外，它必须能够培养开发者对该算法的直觉，以便他们能够扩展该算法--这在实际开发中是不可避免的。

在设计 Raft 时经常要在多个方案中做出取舍，此时我们会评估这些方案的可理解性：每种方案解释起来有多难（比如，它的状态空间复杂度是多少，是否有微妙的副作用），阅读者要完全理解方案和它的副作用有多难。

我们意识到这个分析是非常主观的，所以我们采用了 2 个通用的技巧。第一种技巧是众所周知的问题拆解：只要有可能，我们就将问题拆解可以相对独立地解决、解释和理解的单独部分。比如我们把 Rart 拆解为：Leader 选举、日志复制、安全性。

我们的第二种技巧是通过减少要考虑的状态数量来简化状态空间，使系统更加连贯并尽可能消除不确定性。具体来说，我们不允许日志存在空洞，这限制了不同节点间日志可能出现不一致的途径。虽然我们在大多数情况下都尽力消除不确定性，但有时候不确定性反而有利于提高可理解性。比如用随机数来简化 Leader 选举算法。

3.2 Raft 概览

Raft 实现共识的方式是首先选出一个节点担任 leader，然后由 leader 全权负责复制日志的管理。leader 从 clients 接收 log entries，把它们复制给其它节点，并告诉这些节点何时可以安全地将这些 log entries 应用到它们的状态机中。拥有 leader 角色可以简化复制日志的管理。比如，leader 可以自行决定将 entries 放在 log 中的哪个位置，而不用跟其它节点协商，另外，log entries 总是从 leader 流向其它节点。leader 可能会发生故障，或者与其它节点断开连接，此时会有另一个节点被选举为新 leader。

有了 leader 角色后，Raft 将共识问题拆解为相对独立的 3 个子问题：

• leader 选举：系统启动时，或 leader 故障时，必须选出一个新的 leader。

• 日志复制：leader 从 client 接收日志条目，并复制给集群中的其它节点，强制其它节点的日志跟自己的保持一致。

• 安全性：一旦任意节点应用(apply)了一条日志，其它的节点在相同的 log index 处不能应用不同的日志条目。

除了上面 3 个核心部分，Raft 还包括关系变更、日志压缩、client 交互等。

图 3.1 凝练地总结了 Raft 算法：

图 3.2 列举了该算法的关键属性：

3.3 Raft 算法基础

在任一时刻，每个节点处于这 3 种角色中的一种：领导者（leader），追随者（follower），候选人（candidate）。正常情况下，集群中只会有一个 leader，其它所有节点都是 follower。follower 自己不发送任何请求，只接收和响应从 leader 和 candidate 发过来的请求（如果 follower 收到了 client 的请求，需要转发给 leader 来处理）。

Raft 将时间划分为长度不定的任期(terms)，任期号是单调、连续递增的。每一个任期都开始于一次选举，即一个或多个 candidate 竞选成为新的 leader。如果一个 candidate 胜选，它会作为当前任期剩余部分的 leader。有时候会选举失败

Raft 使用任期作为逻辑时钟，使得节点可以发现已淘汰的消息，例如过期失效的 leader。每个节点都存储当前的任期号，任期号只可单调递增。并在节点间通信时交换任期号，当一个节点的任期号比其它节点的小时，它会更新为较大的那个值。当 leader 和 candidate 发现自己的任期号已过期时，它会立马切换为 follower。当节点收到任期号已过期的消息时，会忽略该消息。

3.4 Leader 选举

每个节点在启动时的角色都是 follower, 在一定时间内收不到来自 leader 的消息，就会触发选举超时，开始选举。开始竞选时，先将角色切换为 candidate，递增任期号（未开启预选举的情况下），然后自己给自己投一票，然后向集群中所有其它节点发送选举消息，其它节点收到 candidate 的选举消息后，按照先到先得的方式投票，每个 follower 同一时刻最多只能给一个 candidate 投票，一旦 candidate 得到大多数节点的认可，就当选为 leader。成为 leader 后，会定时向其它节点发送心跳，以维持自己的 leader 权威。其它节点收到 leader 发送的 term 大于自己 term 的消息后，就会保持为 follower 角色。一旦有某个节点长期未收到来自 leader 的消息，就会触发新一轮选举。

每次选举，有 3 种结果：1) 自己当选; 2) 别人当选; 3) 没有任何人当选，超时后，开始新一轮选举。为了降低选举冲突，避免 3)这种情况无限循环，选举超时并不是一个固定的时间，而是在一定范围内取随机数。

Candidate 在等待其它节点投票的时候，可能会收到来自 Leader 的 AppendEntries RPCs，只要这个 leader 的 term 大于等于 candidate 的 term，candidate 就认可 leader 的合法性，切换为 follower。如果 leader 的 term 小于 candidate 的 term，candidate 就忽略该消息，继续竞选。

如果多个 candidate 同时开始竞选，投票可能被分散，最终没有节点竞选成功。Candidate 会等待选举超时，然后递增 term，开始新一轮的选举。最坏的情况是，这种分裂(split)情况会无限循环下去。Raft 使用随机的选举超时时间（比如 150~300ms）来解决这个问题，降低多个节点同时选举超时的几率，最先选举超时的节点发起竞选，收到选举消息的 followers 会重置选举超时时间，candidate 赢得竞选后，会第一时间向所有节点发送心跳，阻止其它节点再竞选。

3.5 日志复制

选出 leader 后，leader 就可以开始接收 client 的请求。每个 client 请求都包含一个需被复制状态机执行的命令。leader 会将该命令作为一条 entry 追加到它的 log（是一个先入先出队列）中，然后向所有其它节点并行发送 AppendEntries RPCs，以将这条新 entry 复制给其它节点。一旦这条 entry 被安全的复制了（下面会介绍安全性），leader 就会将其应用到状态机中，并将结果应答给 client。如果 followers 挂掉或运行缓慢，或网络丢包，leader 会无限尝试重传 AppendEntries RPCs，直到所有的 followers 成功存储所有的 log entries，即使 leader 已经完成应答 client。

如图 3.5 所示，Log 由 entries 组成，每条 entry 会包含收到该 entry 的 leader 的 term，以及该 entry 在 log 中的位置索引 Index, index 能且只能连续递增。leader 自己来决定每条 entry 何时可被安全地应用到状态机，这种 entry 被称为已提交的(committed)。Raft 保证所有已提交的 entries 是持久化存储的，而且最终会被所有可用的状态机应用。一旦 entry 被创建它的 leader 成功复制到集群中的大多数节点，它就可被认为 committed。log 中所有在它之前的 entries 也会自动被认为 committed，包括被其它旧 leader 创建的 entries。P.S. 重点是可被认为 committed 的 entry 一定得是当前 leader 创建的，所以刚竞选成功的 leader 会首先创建一个空的 entry 复制到其它节点。leader 会跟踪记录最新的已提交 entry 的 index，并会在后续的 AppendEntries RPCs 中带上这个 index，以便让其它节点也能知道这个 index。followers 会应用所有已提交的 entries。

3.5.1 Log Matching Property

• 如果位于不同 Log 中的两条 entries 具有相同的 term 和 index，那么它们包含的命令相同。

• 如果位于不同 Log 中的两条 entries 具有相同的 term 和 index，那么在它之前的所有 entries 都完全相同。

第 1 个属性成立的原因是：leader 在同一个任期最多只会创建一条具备指定 index 的 entry，并且 entry 绝不会改变它在 log 中的位置。第 2 个属性的成立依赖于 AppendEntries RPCs 提供的一致性检查，leader 复制新 entry 时，会带上在 log 中紧挨着该 entry 的前面那条 entry 的 index 和 term，如果 follower 在自己的 log 中无法找到匹配该 index 和 term 的 entry，它就会拒绝新的 entry。

正常情况下，一致性检查都能成功。但如果旧 leader 挂掉了，而它还没有把它 log 中的 entries 复制完，就会导致 log 不一致。多个 leader 或 followers 接连故障，会加剧这种不一致性。followers 可能会缺失 leader 中的 entries，也可能会包含在 leader 中不存在的 entries。

Raft 处理这种不一致的方式是强制用自己的 log 覆盖 followers 中不一样的 entries。第 3.6 节会介绍如何在选举流程中增加一些约束来保证这种做法是安全的。leader 首先需要找出与 follower 最后一致的那条 entry，然后覆盖其后所有的 entries。follower 会在 AppendEntries RPCs 的应答包中告知 leader 这个信息。leader 会为每个 follower 维护一个 nextIndex，用于记录下一次需要发送给该 follower 的 entry 的 index。leader 刚当选时，会将该值设置为其 log 中最后一条 entry 的 index。如果 follower 发现自己的 log 跟 leader 的不一致，会拒绝，leader 收到拒绝消息后，会递减 nextIndex 直到成功为止。

可以对协议优化，以加快这个过程。略。

3.6 安全性

前面介绍了 leader 选举和日志复制，然而这还不足以保证所有节点都按相同顺序执行相同的命令。比如，在 leader 提交一串 entries 时，某个 follower 可能故障了，等它恢复后，它可能会竞选成为新的 leader，创建新的 entries，覆盖掉老 leader 创建的 entries，导致不同的节点执行的命令不一样。本节为选举流程增加一个约束来完善 Raft 算法，该约束保证在任一任期当前的 leader 包含所有前面任期已提交的所有 entries。

3.6.1 选举约束

所有基于 leader 的共识算法都要求 leader 存储所有已提交 entries，有的算法允许 leader 当选时不包含所有已提交 entries，它们有额外的机制来识别新 leader 缺失哪些 entries，然后在选举过程中或选举完稍后一点把这些 entries 传输给 leader。但这会带来额外的复杂性。Raft 采用更简单的方法，它要求新 leader 在发起竞选那一刻必须包含所有之前任期已提交的所有 entries。这意味着日志复制是单向的，只能由 leader 流向 followers，leader 绝不会删除或覆盖 Log 中已存在的 entries。

Raft 是通过投票过程来实现这个约束的，要赢得选举，candidate 必须与集群中大多数节点通讯。如果一条 entry 已提交，那么它必然要出现在这些节点中的至少一个中。如果 candidate 的 log 跟大多数节点比，都要新或至少一样新（at leaset as up-to-date as any other log in that majority)，那么它肯定包含所有已提交的 entries。candidate 向其它节点发送 RequestVote RPC 时，要带上自己的 log 信息，如果 follower 发现自己的 log 更新，就会拒绝该 candidate 的竞选。“more up-to-date”的定义是：如果两个 log 相比较，最后一条 entry 的 term 越大，log 就越新；如果 term 一样大，index 越大，log 就越新。

3.6.2 提交前一个任期的 entries

3.5 节介绍过，当前任期内创建的 entry 一旦被成功复制到大多数节点，leader 就会认为它已提交。如果 leader 在提交 entries 之前挂掉了，未来的新 leader 会继续尝试完成这些 entries 的复制。然而，即使之前任期的 entries 已经被存储在大多数节点，新 leader 也不能直接认为它是可提交的。图 3.7 演示了一种场景：已存储在大多数节点的旧任期 entries，仍然可能会被其它 entries 覆盖。

为了解决这个问题，raft 绝不利用副本数量来决定是否能提交之前任期的 entries，只有 leader 当前任期内产生的 entries 才能用副本数来决策是否已提交，一旦本任期生产的 entries 被提交，所有之前任期生产的 entries 都会自动被提交，日志匹配属性（Log Matching Property）能保证安全性。即使有些情况（比如某个 entry 已经存储到所有节点上了）leader 能够确定 entries 是可提交的，raft 也会采取上述比较保守（conservative）的方式来保证简单性。另外，Raft 与其它有些共识算法不一样的地方是，raft 复制之前任期产生的 entries 时，不会修改这些 entries 的任期号。

3.6.3 安全性保证

为了证明 leader 完整性原则的存在，我们先假设不符合该原则，然后得出相反的结论。假设任期 T 提交了一条 entry，然后新任期 U 的 leader-u 没存储该 entry。

1. leader-u 在竞选时，肯定存储了该 entry。因为 leader 绝不删除或覆盖已存在的 log entries。

2. leader-T 已经把这条 entry 复制到集群中的大多数节点，leader-U 要当选，必须收到集群中大多数节点的投票。那么至少存在一个这样的节点（The Voter)：它存储了 Leader-T 提交的 entry，但又给 Leader-U 投票了。

3. 未完成。略。

3.7 Follower 和 Candidate 故障

到目前为止，只介绍了 leader 故障的情况，follower 和 candidate 故障（比如它们和 Leader 之间的网络连接异常）的处理方式要简单一些，这俩的处理方式一样。故障后，后续发送给它们的 RueqestVote 和 AppendEntry 都会失败，Raft 的处理方式是无限重试，直到成功。如果是在收到 RPC 消息后、还未回复前故障的，那么在它恢复后，会再次收到该 RPC 消息。Raft RPC 都是幂等的，所以无影响。

3.8 持久化状态以及服务重启

每个节点都必须持久化足够的信息来应对可能的重启。在实践中，每个节点都必须存储当前任期号以及投票，以防在同一个任期内给两个不同的节点投票，也防止用从已被废黜的 leader 收到的 entries 覆盖从新 leader 收到的 entries。每个节点也会持久化收到的新 entries，以防已提交的 entries 丢失。

其它的信息都不用持久化，因为它们可以被重建。最有意思的是提交索引（commit index），即使所有节点在同一时间全部重启，也可以先初始化为 0，只要新的 leader 当选后，它会立即提交一条新 entry，然后提交索引就可以直接赋值到最新的值，并将最新的 commit index 传播给其它节点。

状态机既可以是易失性的，也可以是持久化的。 易失性状态机必须在重新启动后通过重新应用 log entries 来恢复（在应用最新快照后；请参阅第 5 章）。 然而，持久化的状态机在重启后已经应用了大部分条目； 为了避免重新应用它们，其最新的 apply index 也必须是持久的。

如果某个节点丢失了它的持久化状态数据，那么它不能使用它之前的 ID 号重新加入该集群，这是不安全的。但它可以作为一个新节点使用新的 ID 号加入到该集群。如果集群中大多数节点同时丢失了持久化数据，那么 entries 可能会丢失，也无法自动恢复集群成员关系，需要管理员手动介入。

3.9 时钟（Timing）和可用性

要确保 Raft 的安全性，就不能依赖时钟：不能仅仅因为系统中某些事件的发生比预期的快一点或慢一点，就影响状态机的最终结果。然而可用性（系统及时地、正确地响应客户端的请求）不可避免的要依赖时钟，比如：如果消息交换所需要的时间，比通常情况下先后两次节点故障之间的间隔时长还长，那么 candidate 就无法赢得选举，没有稳定的 leader，raft 就无法正常工作。leader 选举是 raft 对时钟要求最严格的地方，只要满足如下时钟要求，raft 就能维持稳定的 leader：广播时间 << 选举超时时间 << MTBF 。其中 MTBF(the Mean Time Between Failures)是单个节点两次故障之间的平均时长。

3.10 领导人转让

领导人转让在两种情况下比较有用：

1. Leader 必须要下线，比如要重启机器。一旦 leader 下线，Raft 集群至少在一个选举超时时间内是不可用的。如果在下线前把 leader 转让给其它节点，就可以避免这种情况。

2. 有时候其它机器更适合当 leader，比如其它机器配置更高、负载更低。

具体步骤如下：

1. 旧 leader 停止接收 client 请求

2. 旧 leader 确保所有的 log entries 都已复制到目标 leader 上了

3. 旧 leader 向目标 leader 发送一个 TimeoutNow 消息，目标 leader 收到消息后，会立即开始竞选。

4. 目标 leader 胜选后，会向集群中所有节点发送心跳包，里面带有自己的任期号。旧 leader 收到后，会立即下线。转让完成。

如果在完成转让前，目标 leader 挂掉了，旧 leader 无法在一个选举超时时间内完成转让，就会终止转让，恢复对 client 请求的接收和处理。如果旧 leader 搞错了，新 leader 已经胜选了，最坏的情况就是额外触发一次选举。

4 集群成员变更

有时候需要变更组成集群的节点，比如替换某个故障节点、更改副本数量。可以通过以下 2 种方法手动变更：

1. 关停整个集群，修改配置文件，再重启集群。在变更期间，集群不可用。

2. 把被替换节点的 IP 地址分配给新机器，新机器就可以代替旧节点添加到集群中。但管理员必须保证旧节点永远不会重新回到集群，否则 Raft 就会丧失安全属性。

这两个办法都有巨大的缺点，另外，只要需要管理员手动操作，就必然不可避免会出现操作失误的可能。

为了避免上述问题，对 Raft 增加一点扩展来实现自动化的成员变更。

4.1 安全性

如果在单次配置变更中添加或删除多个节点，由于不能保证所有的节点都在同一时刻同时由老配置切换到新配置，可能会出现旧集群的大多数跟新集群的大多数不重叠，旧、新集群分别选出一个 leader 的情况，如图 4.2 所示。

大多数共识算法为了避免这个问题，都增加额外的过渡机制，而不是直接由旧配置切换到新配置。Raft 算法设计者最开始用的也是这个比较复杂的办法，但他们在开发 LogCabin 的过程中发现了另一种更简单的办法：限制每次配置变更只能添加或删除一个节点，更复杂的操作则由一系列简单变更组成。

由于每次只添加或删除一个节点，新、旧集群的大多数必然存在重叠，基于 3.6 节介绍的规则，就能避免新、旧集群选出不一样的 leader。所以每次只添加或删除一个节点，就能安全地直接切换到新配置。如图 4.3 所示：

集群的配置信息被作为一种特殊的 entry 保存在 Raft Log 中，以便可以利用 Raft 已有的复制和持久化 Log 的能力。

leader 一旦收到从当前配置（Cold）中添加或删除一个节点的请求，就会在自己的 Log 中追加一条 Cnew entry 配置信息，并使用正常的机制将该 entry 复制给其它节点。节点收到新的配置信息 entry 后，只要该 entry 成功追加到本地 log 中，新的配置就立即生效：开始使用 Cnew 的配置来决策集群的大多数（Majority）。不需要等该 entry 被 Committed，任一节点始终使用自己 Log 中的最新配置。

一旦 Cnew entry 被提交，配置变更就完成了。此时，leader 知道还没采用 Cnew 的节点不可能组成大多数，也不可能被选举为 leader。也意味着：

1. leader 知道配置变更完成了

2. 如果配置变更是删除节点，这个节点可以下线了

3. 可以开始下一个配置变更了。如果在这个时间点前开启新的配置变更，就可能有安全问题。

如果在 Cnew entry 被提交之前，发生了 leader 变更，Cnew entry 有可能会被从节点上删除。删除后，节点就使用 log 中上一个最新的配置。在 Raft 中要遵循下面的规则：

1. 节点 A 要接受来自 leader 的 AppendEntries 请求，即使该 leader 不在节点 A 的最新配置中。否则，新节点 A 永远不能被添加到集群（因为新节点被添加到集群前，需要先追上 leader 的 log）

2. 节点需要给不在它最新配置中的 candidate 投票（只要该 candidate 的 log 不比自己旧，且任期号比自己大）。比如向一个 3 个节点的集群中添加第 4 个节点的过程中，leader 故障了，如果第 4 个节点不投票，就无法选出新 leader。

4.2 可用性

4.2.1 追上集群的 Log

当一个新节点被添加到集群中时，它通常没有存储任何 log entries。如果让新节点就以这种状态直接加入集群，可能会增加集群不可用的风险。详见下图：

为了避免这个问题，Raft 在配置变更前新增一个阶段，新服务在该阶段以非投票角色（non-voting member，注：etcd 中叫作 leaner）加入集群。一旦新节点的 log 追上来了，就可以按照上面描述的方式继续配置变更。另外，非投票角色除了在这种场景被使用外，还可以在对一致性要求不太严格的场景下提供只读能力扩展。

至于新节点的 log 怎么才算追上了集群，则由 leader 决定。如果让新节点太快加入集群，集群要承担的不可用风险就越大。我们的目标是把集群不可用的时长控制在一个选举超时时间内，因为客户端必须已经能忍受 Raft 在这么长时间内不可用。我们要尽可能让新节点的 log 与 leader 接近。

leader 在极端情况下要能够终止配置变更流程：如果新节点故障了，或新节点太慢，永远都追不上 leader 的日志。

Raft 推荐使用如下算法来判断新节点是否追上 leader 的 log：将整个复制过程分隔成多个回合，如图 4.5 所示。在每个回合中，复制该回合开始时存储在 leader 的所有 log entries。在复制的过程中，leader 还会接收客户端请求，创建新的 log entries，下一个回合会负责复制这些 entries。如此往复，越后面的回合所需要的时长越短。leader 会等待固定的回合数（比如 10），如果最后一个回合的时长小于选举超时时间，就认为新节点已经追上 leader 了。否则，leader 就终止配置变更流程（管理员可以手动再重试，而且重试的成功率会更大，因为新节点上已经有部分 log entries 了）

新节点追赶 leader log entries 的第一步是 leader 要发现新节点的 log 是空的，也就是说 AppendEntries RPC 必然会失败很多次，直到 leader 将新节点的 $nextIndex 降为 1。在很多时候，这一步骤比较影响添加新节点的效率。有多种方法可以加快 leader 将 $nextIndex 调整为正确的值，比如在第 3 章中介绍的那些方法。不过对于添加新节点这个特定场景来说，最简单的办法是让 follower 在 AppendEntries RPC 的应答包中带上自己 log 的长度，这样 leader 就能直接将 $nextIndex 设置为相应的值。

4.2.2 移除当前 leader

当 leader 接受到移除自己的命令后，最直接的做法是先按照第 3 章介绍的方法把 leader 角色转让给其它节点，然后执行常规的成员变更操作来移除旧 leader 即可。

Raft 最初开发了另一种方法（4.3 节要介绍的），该方法支持任意多个节点的配置变更，但该方法在移除当前 leader 方面有些违反直觉的地方，所以不推荐。在此不介绍。

4.3.3 有破坏性的节点

如果不增加额外的策略，不在 Cnew 中的节点会破坏集群。一旦 Leader 创建了 Cnew entry，不在 Cnew 中的节点就不会再收到心跳包了，所以它很快就会选举超时并发起选举。另外，它也不会收到 Cnew entry 相关的信息，所以它无法得知自己已经被从集群中移除。它会自增任期号，然后向集群中的其它节点发送 RequestVote RPC，Leader 收到该 RPC 后，会被迫降级为 follower，然后 Cnew 中的某个节点会当选为新的 leader。但那些不在 Cnew 中的节点会继续选举超时，继续发起新一轮选举，如此往复，导致集群可用性非常差。如果有多个节点被从集群中移除，情况会更糟糕。

Raft 设计者最开始想到的解决方案是，在选举前引入一个新的步骤--预选举（Pre-Vote），即 Candidate 在正式竞选前先确保自己的 log 足够新，有机会赢得选举，否则就不自增任期号，也不发起竞选，以免耽误其它人的时间。

但不幸的是，预选举并不能解决这个问题。因为如果被删除节点的日志足够新，它仍然会发起正式选举，迫使当前 leader 下台。如图 4.7 所示：

Raft 的解决方案是，如果 leader 还能与大多数 followers 保持正常的心跳，那么就不能罢黜它。具体实现是：Raft 修改了 RequestVote RPC 的处理逻辑，一个节点收到 RequestVote 后，它会先判断上次收到来自现任 leader 的心跳时间有没有超过最小选举超时时间（the minimum election timeout），如果没有超过，就不变更自己的任期号，也不投赞成票（节点可以选择忽略、拒绝或延迟处理 RequestVote）。

然而，这个策略与第 3.10 节介绍的领导人转让有冲突，领导人转让允许节点在选举还没超时时就发起选举。Raft 建议在 RequestVote RPC 中新增一个字段，来表示本次选举是现任 leader 授权的。

4.2.4 可用性论证

1. 在配置变更的任意阶段中，都支持 leader 选举：

• 如果新集群中具备最新日志的健康节点有 Cnew entry，那么它可以得到 Cnew 中大多数节点的赞成票，然后当选为新 leader。

• 否则，Cnew entry 肯定还没被提交。在 Cnew 和 Cold 的大多数节点中，都同时具备最新日志的健康节点可以从 Cnew 和 Cold 的大多数节点收到赞成票，所以不管它用的配置是哪个，它都可以当选为 leader。

2. 一旦当选为 leader，假设它与自己配置的其它部分能保持正常心跳，那么它就会一直保持 leader 角色，除非它自己主动下台，因为它不属于 Cnew 的一部分，且已经提交了 Cnew entry。

• 只要 leader 能与自己配置的其它部分保持可靠的心跳，那么无论是该节点本身，还是其它节点，都不会接纳更高的任期号。因为不会出现选举超时，且它们会忽略 RequestVote RPC，所以不会强制它下台。

• 如果 leader 不在 Cnew 中，它提交了 Cnew entry，然后主动下台，Raft 会选举出一个新的 leader。被选举的 leader 大概率属于 Cnew，并继续完成配置变更。然而刚下台的旧 leader 也有很小的概率重新当选为 leader，那么它会确认 Cnew entry 的提交，然后又下台。接着又选出新 leader，新 leader 大概率属于 Cnew。

3. 在配置变更的整个过程中，leader 会继续服务 client 请求。

• 在配置变更的整个过程中，leader 都可以继续将 client 请求追加到自己的 log 中。

• 由于新节点在加入集群前就已经追上了日志，所以 leader 能够及时推进 commit index 并应答 client。

4. Leader(s)通过提交 Cnew entry 来推进并完成配置变更，如果它不在 Cnew 中就会主动下台，以便让 Cnew 中的节点能当选。

4.3 使用联合共识来支持任意配置变更

略

4.4 系统整合

略。

运维相关的，如果一次要做一系列的变更，最好先添加节点，再删除节点。自动删除故障节点比较危险，因为剩下的节点数量可能不足以保证持久化和容灾需要。

5 日志压缩

随着时间推移，Raft log 会变的越来越大，占用的存储资源越来越多、启动时需要更多时间来重放。所以必须要支持压缩 Log。日志压缩的大概思路是随着时间的推移，之前的命令可以被舍弃，比如第一个命令是将 X 的值设为 1，第二个命令是将 X 的值设为 3，一旦第二个命令执行成功后，第一个命令就可以被删除。

压缩 Log 的方法有很多种，不存在适合所有场景的万能方案。首先，需要根据具体场景在简单性和性能之间做取舍。其次，状态机需要密切参与日志压缩，而不同的状态机在存储量（size）和存储介质（whether they are based on disk or volatile memory）上都不同。

但是不同的方法在核心逻辑上也有共同之处：

• 首先，不是由 leader 中心化压缩，而是每个节点独立压缩。避免了 leader 向其它节点传输压缩后 log 的需要；也方便模块化，大部分的压缩逻辑包含在状态机中，不需要与 Raft 有太多交互。

• 其次，状态机和 Raft 之间的基本交互包括将“维护 log 前半部分的责任”从 Raft 转移给状态机。一旦 log entries 被应用后，状态机就会以可恢复的方式将这些 log entries 对应的状态持久化到磁盘，然后状态机就可以通知 Raft 丢弃这部分 log。Raft 在删除这部分 log 前，会记录最后一条被删 entry 的 index 和 term，以便后续的 AppendEntries RPC 执行一致性检查。Raft 也会保留最后一条 config entry。

• 最后，一旦 Raft 丢弃了 log 的前半部分，状态机就要肩负两个任务：1) 重启的时候，在它应用 Raft log 前，必须从磁盘恢复已删除 log entries 对应的状态；2）能够提供连续的状态镜像，以便发送给那些 log 远远落后于 leader 的节点。

5.1 基于内存的状态机快照

如果状态机的数据量在数 GB 或者数十 GB 时，该方法是合理的。由于不用写磁盘，性能更高。而且内存数据结构非常丰富，写代码也要更简单。

每个节点独立完成图 5.2 中的工作：

制作快照的最主要工作是序列化状态机的当前状态，不同的实现使用的数据结构不同，序列化方式也不同。LogCabin 的状态机使用的是树结构，它序列化算法是深度优先、前序索引。Etcd 使用的 protobuf。

一旦快照持久化到磁盘后，就可以截断 Log 的前半部分了。在这之前，Raft 还会保存一些重启所必须的状态，比如：快照中包含的最后一条 entry 的 term 和 index、最新的配置信息。然后就可以截断 Log 了，所有之前的快照也可以被删除了。

有时候 leader 也需要发送快照给其它比较慢的 followers，以及准备加入到集群的新节点。followers 收到快照后，如果快照中包含自己 Log 中没有的新 entry，说明快照比较新，可以用快照覆盖自己的 Log，并完全删除自己的 Log；如果快照只包含自己 Log 的前半部分数据（重传或者失误），就可以覆盖这部分 Log，但 Log 后半部分仍然要保留。

5.1.1 并行制作快照

为了制作快照，序列化状态数据并将之写入磁盘，比较耗费时间。以现在的硬件性能，在内存内拷贝 10GB 数据，大概需要 1 秒。序列化状态数据和写磁盘需要的时间更久，即使是固态硬盘，一秒钟也只能写大概 500MB 数据。所以序列化和写磁盘都必须和其它正常操作并行，以免影响可用性。

有两种实现方式：

1. 写时复制。但需要操作系统支持。比如在 Linux 上，子进程与父进程共享同一份内存空间，可以在子进程中制作快照，而父进程继续服务客户端请求，等快照完成，子进程退出运行，父进程删除快照覆盖的 Log。LogCabin 就是使用该方案。

2. 使用不可修改数据结构来实现。大概意思是，状态机不直接修改状态，等快照完之后，再修改状态。

无论哪种方案，都需要额外的内存空间。如果内存不幸耗尽了，节点应该停止接受新请求，先完成快照制作。虽然会导致节点短暂不可用（整个集群还是可用的），但至少会让节点可恢复。最好不要暂停快照制作，因为下次启动快照制作，仍然会遇到内存耗尽问题。

5.1.2 何时启动快照

如果快照太频繁，会消耗磁盘带宽及其它资源。如果间隔太久才快照，有耗尽存储资源的风险，而且重启时需要花费更多时间来重放 Log。

最简单的策略是当 Log 达到一定大小后，就开始快照。如果设置的阈值太大，那么快照占用的磁盘带宽会较少，但对于较小的状态机来说，Log 会占用的太多不必要的存储资源。

一种更好的解决方案是比较 快照 和 Log 的大小。但要想在快照完成前计算快照的大小，比较难，而且所消耗的资源不一定比实际快照少。所以一种折中的方案是比较前一个快照和 Log 的大小。一旦 Log 的 size 大于前一个快照的 size 与配置的膨胀因数（expansion factor）之积，节点就立马启动快照。膨胀因数的值取决于磁盘带宽和空间利用率的权衡。比如膨胀因数为 4，意味着使用 20%的磁盘带宽，以及 6 倍的存储空间。

快照会导致 CPU 等硬件性能毛刺，从而影响服务 Client 请求。为了避免这个问题，可以协调让整个集群在任一时刻同时在进行快照的节点数占整个集群的小部分。因为只要大多数节点可用，Raft 就能正常对外提供服务。Leader 在开始快照前，可以主动把领导权交接给其它节点。

5.1.3 实现细节

• 保存 &加载快照。保存快照就是序列化状态机数据，并写到磁盘文件里。加载则是相反的过程。LogCabin 是先将快照写入一个临时文件，当确保写入完成，并刷写到磁盘后，再把临时文件名修改为正式名称。这样可以避免读到写了一半的快照。

• 传输快照。

• 消除不安全的日志访问 &丢弃整个日志。简单来说就是，快照完成后，会删除已被压缩的 log entries，注意不要再访问这些 entries。

• 使用写时复制来并行快照。

• 决定何时开始快照。

5.2 基于磁盘的状态机快照

大型状态机（数十乃至数百 GB）使用磁盘作为它们的主存储，这与那些为了应对 crash 而在磁盘中拷贝一份数据的状态机不同。每应用一条 entry，就要修改一次磁盘数据，就得到一份新的快照。所以只要 log entry 被应用了，就可以将它删除（状态机也可以在内存中缓存写，已达到更好的磁盘性能，一旦写磁盘完成，就可以删除已应用的 entry）。

为了支持 Leader 向较慢的 follower 传送快照，基于磁盘的状态机必须能够提供一致的快照。尽快在磁盘中始终有最新的状态快照，但它一直在不断地被修改。为了解决这个问题，也可以利用写时复制技术。比如 Linux 上的 LVM 支持对整个磁盘分区进行快照，较新的文件系统还支持对单个目录进行快照。

5.3 增量清理方案

使用日志清理（log cleaning）以及结构化日志合并树（LSM）,尽管会比较复杂，但能带来若干不错的收益：

1. 每次只操作一小部分数据，能够把压缩负载均匀的分摊在不同的时间上。

2. 无论正常操作还是压缩日志，写磁盘都比较高效。它们使用大块、顺序写。

3. 可以很容易地支持传输一致的快照，因为它不是立马就更新磁盘。

5.3.1 和 5.3.2 介绍日志清理和 LSM 的基本概念，5.3.3 讨论如何将其应用到 Raft。

5.3.1 日志清理的基础

日志清理最开始出现在结构化日志文件系统上下文中，最近也被应用到基于内存的存储系统中，比如 RAMCloud。

5.3.2 结构化日志树的基础

5.3.3 在 Raft 中使用日志清理和 LSM

5.4 可选：基于 Leader 的方案

Raft 开发者认为各节点独立完成快照，不需要 leader 参与，是合理的。数据仍然只能由 leader 流向 followers。但 Raft 开发者也提出了基于 leader 的可选方案。

6 客户端交互

本章描述客户端与基于 Raft 的状态机交互过程中的一些问题。这里仅讨论将 Raft 集群作为一个网络服务的场景，当然也可以将 Raft 嵌入到客户端内部，这种情况不在此讨论。

6.1 发现集群

如果集群节点不会变化的话，只需要将节点 IP 写死在配置文件中即可。但 Raft 的节点随着时间可能会发生变更。通常有如下 2 个办法：

1. 客户端使用广播或组播来发现集群节点，但这只能在特定的环境使用。

2. 客户端通过一个额外的目录服务来发现集群节点，比如 DNS。在目录服务中的节点列表不需要始终保持一致，但应当是包含性（inclusive）的：客户端应当能从目录服务中发现所有集群节点，但是在目录服务中的部分节点当前并不在集群中，却影响不大。所以，在向集群中添加新节点前，应该先更新目录服务；在从集群中移除节点前，应该移除后再更新目录服务。

6.2 将请求路由到 Leader

Raft 是通过 leader 来处理请求的，所以客户端需要发现 leader。客户端启动时，随机选择一台节点并建立连接，如果该节点不是 leader，它会拒绝请求，客户端再随机选择另一个节点。对于一个有 N 个节点的集群，平均需要 (N+1)/2 次尝试。对小集群来说，这也挺快的。但也可以进行一些优化，因为节点肯定知道当前的 leader 是谁。当非 leader 节点收到客户端请求后，它可以做下面 2 个事情中的一个：

1. 第一个方案是，如果节点不是 leader，它拒绝客户端的同时也向客户端返回当前 leader 的地址，如果它知道的话。该方案是比较推荐的，也是 LogCabin 中的实现方式。

2. 第二个可选方案是，该节点可以将客户端请求转发给 leader，再将 leader 的应答转发给客户端。这在某些场景下可能更简单。比如当客户端发送的是只读请求。

Raft 还必须能够避免陈旧的 leader 无限期地延迟客户端请求。leader 关系在整个系统的所有部分（leader、followers、客户端）都可能变得陈旧。

• Leader：一个节点可能之前是 leader，但后来不再是了，那么它可能一直不必要的延迟客户端请求。比如，一个 leader 与集群的其它部分发生网络分区，但它仍然在与部分客户端交互。那么它将无法正确处理客户端请求，因为要把 log entries 复制到集群大多数节点后才能完成客户端请求。与此同时，另一个处于大多数部分的节点将当选为新 leader，能够正确服务客户端请求。所以，如果 leader 在一个心跳超时时间内都无法向集群中的大多数节点发送心跳的话，它就主动下线，客户端会再尝试其它节点。

• Followers: followers 会记录 leader 的 ID，以便它重定向或代理客户端请求。在发起新一轮选举，或者任期号变更时，它必须丢弃该信息。否则客户端请求就可能会被不必要的延迟：可能有两个节点将客户端请求分别重定向给对方，导致客户端在两个客户端之间无限循环。

• Clients: 如果客户端与 leader（或其它任意节点）之间的连接断开了，就要随机尝试其它节点。如果坚持已知的最后一个 leader，如果该节点故障了，就会导致不必要的延迟。

6.3 实现线性一致性语义

到目前为止，Raft 可以向客户端提供至少一次（at-least-once) 语义保证。但有时候状态机会应用一条命令不止一次。比如，客户端向 leader 发送一条命令，leader 将其追加到 Log 中，并提交它。但是该 leader 在向客户端返回应答包前故障了，客户端收不到应答，就会向新 leader 重新发送该命令，新 leader 又会将其作为一个新 entry 追加到 Log 中，并提交它。最终导致一条命令被执行了 2 次，虽然客户端的期望是一次。有时候甚至不需要客户端调用 2 次，命令就可能被执行多次，比如网络重传。

至少一次语义对于共识系统来说是不够的，往往会导致很多意想不到的错误结果。图 6.2 是一个示例。

Raft 的目标是实现线性一致性，以避免上述问题。在线性一致性语义里，每个请求看起来是在发起调用和应答之间的某一刻立即、有且只有一次被执行。

为了实现线性一致性，节点就必须过滤掉重复的请求。基本的思路是节点保存客户端操作结果，并用它来跳过执行重复的命令。为了实现这个目的，给每个客户端分配一个唯一的 ID，且客户端为每个命令分配一个唯一的序列号。每个节点为每个客户端维护一个 session，跟踪记录为该客户端执行的最后一个命令的序列号，以及相应的应答。当再次收到一个序列号已经被执行过的命令时，就可以直接返回应答，而不用再次执行命令。

该方法还支持客户端并发请求。session 会保存多个命令的序列号和应答，而不是仅仅保存最后的那个。客户端每次请求都会带上它仍没收到应答的最低命令序列号，所有小于该序列号的记录都可以从 session 中删除。

不幸的是，节点的存储空间是有限的，所以不可能永远存储所有 session。这带来两个问题：①所有节点如何就让客户端 session 过期达成一致，②如果一个活跃客户端的 session 不幸被过早地过期了，该如何处理。

节点们必须就何时让客户端 session 过期达成一致，不然就会导致不同节点的状态机产生分歧。比如，如果某个节点将某一 client 的 sessoin 过期了，导致它重复执行了该 client 的命令，与此同时，其它节点没有过期该 client 的 session，所以没有重复执行它的命令，就会导致复制状态机不一致。为了避免这个问题，session 的过期必须是确定性的，就像其它的状态机操作一样。可选方案之一是设置一个 session 数量上限，并使用 LRU 来删除太久不活跃的 client。另一个方案是基于商定的时间源来使 session 过期。leader 再将命令追加到 log 中时，会同时添加上当前时间戳。各节点在提交该 entry 时会就该时间达成一致，并使用此时间来确定 client session 何时过期。健康的 client 在非活跃期间会发起 keep-avlive 请求，leader 也会将该命令附加上当前时间并追加到 Log 中，以使 session 不过期。

另一个问题是一个 session 被删除的 client 再次发起请求时该如何处理。一个可选方案是给每一个找不到 session 记录的 client 新分配一个 ID, 但这可能导致重复执行 session 过期前已经被执行过的命令。为了避免这个问题，节点必须区分 client 是新的，还是之前 session 过期了的。新 client 在启动时会首先调用 RegisterClient RPC 来获取一个唯一的 ID，后续请求都会带上该 ID。如果节点收到一个来自找不到 session 记录的 client 请求，不能处理该命令，而应该向客户端返回错误。LogCabin 在这个场景不是向客户端返回错误，而是直接让 client crash 掉（因为有的 client 可能没有正确地处理错误，但一定有处理 crash 事件）

6.4 更高效的执行只读请求

只读请求不会修改状态机，所以自然而然会有一个疑问，只读请求能不能旁路掉 Log 复制。这听起来很诱人，因为大多数应用都是读多写少，而追加命令到 Log 中需要写磁盘是非常耗时的。

然而，如果没有额外的预防措施，旁路掉 Log 会导致只读请求读到陈旧的数据。比如 leader 可能会跟集群其它部分发生网络分区，其它部分可能已经选出了新的 leader，并提交和应用了新的命令。如果旧 leader 未咨询集群其它节点就应答了客户端的只读请求，就可能会导致客户端读到陈旧的数据，这违反了线性一致性。线性一致性要求读结果能反应在发起该读请求后某一时刻系统的状态；每次读必须至少返回最新提交的写入的结果（允许读到陈旧数据的系统最多能提供串行一致性，比线性一致性要弱）。

幸运的是，旁路掉 Log 仍然能保证线性一致性。但需要 leader 采取下面的步骤：

1. 如果 Leader 还没有提交过任何来自当前任期的 entry，它必须等待完成这一步。Leader 完整性属性能保证 leader 拥有所有已提交的 entries，但在它任期的最开始，它并不知道哪些 entries 是已提交的。为了找到它们，它需要提交一个来自当前任期的 entry。Raft 的方案是 leader 在成功当选时，立即提交一个空白的 entry。一旦该空白 entry 被提交成功，那么在当前任期内，leader 的 commit index 就会大于或等于其它任何节点。

2. Leader 将当前 commit index 的值保存到本地变量 $readIndex 中，该值将作为读请求所对应的状态机版本下限。

3. Leader 需要确保它不会被一个它不知道的新 leader 所替代。为了保证这点，它会向集群的大多数节点发送一个新的心跳包，并等待它们回包。一旦成功收到回包，它就可以确定在它发送心跳包的那一刻不可能存在更新的 leader。因此，$readIndex 在当时肯定是集群所有节点所看到过的最大的 commit index。

4. Leader 会等待状态机的 apply index 至少等于 $readIndex，此时就足以保证线性一致性。

5. 最后，Leader 向状态机提交查询请求，并将结果返回给客户端。

这个方法比向 Log 中追加一条只读请求 entry，并提交它要高效很多，因为不用同步写磁盘。为了进一步提升性能，Leader 可以分摊确认领导关系的消耗：leader 先积攒一些只读请求，再集中发送心跳确认领导关系。

Followers 也可以分担只读请求，提高系统只读请求吞吐量，让 Leader 可以服务更多读/写请求。然而，如果没有额外的措施，客户端也会读到陈旧的数据。比如，发生了网络分区的 Follower 在很长一段时间内都无法再从 leader 处接收到新的 log entries，即使它能收到 leader 的心跳，这个心跳也可能来自一个不知道自己已被废黜的 leader。为了提供安全的读服务，folllower 可以向 leader 询问最新的 readIndex（leader 会执行上面的 1~3 步骤），然后 follower 再在本地状态机执行 4~5 步骤。

LogCabin 在 Leader 上实现了上面的算法，并且在负载高时，Leader 会积累一些只读请求以分摊心跳成本。LogCabin 目前不支持 Followers 提供只读服务。

6.4.1 利用时钟来减少只读请求所需要的通信

前面所介绍的方案在异步模型（不依赖时钟、进程和消息执行的快慢）里可以提供线性一致性只读。但每一批只读请求，都必需一轮与集群半数节点之间的心跳，会增加请求延迟。只本节介绍另一种不需要发消息，但得依赖时钟的可选方案。LogCabin 目前没有实现该方案，而且也不推荐该方案，除非确实对性能有较高需求。

为了使用时钟，而不是发消息来实现只读请求，需要利用正常的心跳来实现一种租约机制。一旦 Leader 成功收到大多数节点的心跳应答包，它就可以假定在接下来的一个选举超时时间内，不会有另一个节点当选为新 leader，因此，它可以将租约相应地往后续期一段时间。在这段时间内它就可以直接应答客户端的只读请求，而不用先发消息确认自己的领导地位。

租约方案有一个假定前提，即节点的时钟漂移有一个界限。如何发现并维护这个界限，对运维来说是个比较难得挑战（比如调度或垃圾回收导致的世界暂停、虚拟机迁移、时钟频率调整以同步时间）。一旦界限被突破，系统就可能返回任意陈旧的数据。

幸运的是，一个简单的扩展可以改善为客户端提供的保证，因此即使在异步假设下（即使时钟行为不当），每个客户端也会看到复制的状态机单调进展（顺序一致性）。比如，客户端在一个节点上看到了索引 n 位置的 log entry 所对应的状态，切换到另一个节点，它不会仅仅能看到索引 n-1 位置的 log entry 所对应的状态。为了实现这一点，节点在应答客户端的时候，会带上与状态机相对应的索引，客户端会记录自己看到过的最新的索引，并在后续每个请求中带上该索引，节点收到请求时，如果客户端带过来的索引比自己状态机当前的 apply index 还要大，就拒绝服务该请求。

10 实现与性能

10.1 实现

设计者已经在 LogCabin 中实现了 Raft。LogCabin 作为一个复制状态机，最开始为了给 RAMColud 存储配置信息以及辅助其故障转移而开发的。最开始是想用 Paxos 的，但是发现太难了，从而促使他们开发了 Raft。

10.1.1 线程架构

LogCabin 使用了多线程架构来实现，如下图所示：

10.2 性能方面的考虑

10.2.1 Leader 并行写磁盘

10.2.2 批处理和流水线

Raft 支持使用 batching and pipelining 来处理 log entries，二者对提升性能都很有帮助。如果积攒多个请求再批量处理，就可以分摊处理请求过程中的许多消耗。比如，在一个网络数据包中一次性发送 2 个 entries，要比分成 2 个数据包要快，一次性写 2 个 entries 到磁盘，也比分开 2 次写要快。因此，批处理可优化吞吐量，这在系统负载较高时非常有用。另一方面，流水线允许在一个 entry 正在被处理时，就开始处理另一个 entry，从而优化中等负载下的延迟。比如，在 follower 正在将前一个 entry 写到磁盘时，流水线就可以让 leader 通过网络发送下一个 entry 给 follower。甚至在高负载时，一定量的流水线也可以更高效地利用系统资源，从而提高吞吐量。比如，follower 得先从网络中接收到 entries，然后才能将它们写到磁盘，如果没有流水线，follower 就无法同时利用网络和磁盘资源。流水线在某种程度上也与批处理有冲突。比如，积攒一大批请求然后集中批处理，可能比通过流水线处理多个小请求要快一些。

对 Raft 来说，使用批处理是非常自然的事情，因为 AppendEntries RPC 支持一次请求发送多条连续的 entreis。LogCabin 是每次发送 $nextIndex 到 log 尾部的所有 entries，上限是单次 1MB。1MB 是可配置的，不过这个大小已经足够高效利用网络和磁盘资源了，同时仍然能保持正常的心跳频率（如果单次 RPC 太大，follower 可能会怀疑 leader 故障了，并发起新一轮选举）。follower 收到后，一次性将这些 entries 写到磁盘，所以也能高效地利用磁盘资源。

Raft 也能很好的支持流水线。AppendEntries RPC 的一致性检查能够确保使用流水线的安全性，事实上 leader 可以安全地以任意顺序发送 entries。为了支持流水线，leader 乐观地处理每个 follower 的 $nextIndex，发送完一批 entries，leader 就更新 follower 的 $nextIndex，而不用等待 follower 的应答包。然后就可以通过流水线发送下一批 entries 了。如果 RPC 失败了，记账会变得较复杂。如果 RPC 超时了，leader 必须将 $nextIndex 回退到最开始的值，然后重试。如果 AppendEntries RPC 一致性检查失败了，leader 甚至可能需要将 $nextIndex 回退更多，或者 leader 等待之前的 entries 的应答包，然后将 $nextIndex 回退到相应的值，然后重试。

在一般情况下，如果希望按顺序传递消息，则这种流水线方法效果最佳，因为重新排序可能会导致低效的重传。幸运的是，大多数场景并不需要频繁地重新排序消息。比如，LogCabin 中 leader 与每个 follower 之间都维持一个唯一的 TCP 连接，除非它怀疑这个 TCP 连接有问题，才会换一个新的 TCP 连接。由于单个 TCP 连接对应用层屏蔽了网络层的消息乱序，所以 LogCabin 的 followers 很少收到乱序的 entries。即使收到了，follower 也可以在应用层把这些 entries 临时缓存起来，再重新排序即可。