Raft：寻求一种可理解的共识算法

Apr 9, 2022 13:00 · 8995 words · 18 minute read Algorithm Distributed System

来自斯坦福大学的论文 In Search of an Understandable Consensus Algorithm。

Mind Mapping

Raft is a consensus algorithm for managing a replicated log.

Raft 是一个管理复制的日志的 共识 算法。

Raft 源于 Paxos，与 Paxos 一样高效，但因为其更易于理解，故更适合作为构建生产系统的理论基石。

为了增强可理解性，Ratf 将共识的核心元素拆分为：

  • leader election
  • log replication
  • safety

同时引入了一种全新的变更集群成员的机制来保证安全。

1. 介绍

共识算法使得集群能够在一定程度的成员故障时仍能够正常工作。正因为如此，在构建大规模分布式系统中起到了关键作用。Lamport 的 Paxos 是共识算法的鼻祖，绝大多数实现都基于 Paxos，但它太难理解了。此外，工程化它也需要复杂的修改才能应用于生产系统。

为此 Stanford 探索出了 Raft 协议，更适合软件系统构建和教学。Raft 协议的首要目标是可理解性：

  • 对于学生来说比 Paxos 更容易学习
  • 对于开发者来说更易于工程化

It was important not just for the algorithm to work, but for it to be obvious why it works.

不仅要让算法奏效，而且要让大家知道它为啥起作用。

Raft 有这些新颖的特点：

  • strong leader

    相较于其他共识算法，Raft 采用更强势的 leader，比如日志条目只从 leader 流向其他服务器。

  • leader election

    Raft 使用随机计时器来选举，只对任何共识算法都需要的心跳机制做了少许变更。

  • membership changes

    使用*联合共识（joint consensus）*机制，使得集群在配置变更时持续正常运作。

Paxos 相关论文

2. 复制的状态机（Replicated State Machines）

多副本被用作分布式系统的容错方案。像 GFS、HDFS 和 RAMCloud 这样的大规模分布式系统通常有且只有一个集群 leader，它们使用一个外部的复制式状态机来管理 leader 选举和存储配置信息。Chubby 和 Zookeeper 都是这种复制式状态机的实现。

复制式状态机通常由日志复制来实现。

Figure 1

如图 1 所示，每台服务器都存储了一份日志，内容为所有状态变更指令，状态机会按序执行这些指令。所有日志副本的内容和顺序都一样，这样状态机就是状态确定（deterministic）的。

共识算法的任务就是保持日志副本一致。服务器的共识模块从客户端接收指令并将它们添加到日志。每个服务器上的共识模块与其他服务器通信确保日志最终是一致的，即使有些服务器发生故障。一旦指令被正确复制，每台服务器的状态机会按序执行，结果将被回复给客户端。因此，集群形成了一个相当可靠的状态机。

生产系统中的共识算法要具备这些特性：

  • 在所有非拜占庭将军问题（永不返回错误的结果）下保证安全，包括网络延迟、分区、丢包、消息重复和乱序。
  • 只要大多数服务器没问题就完全可用。因此一个五节点的集群能够容忍两个节点故障。故障的节点恢复后会重新加入集群。
  • 不依靠时间来确保日志的一致性：错误的时钟和消息延迟很可能会导致系统不可用。
  • 通常情况下，只要集群中大多数服务器都应答 RPC，指令就算完成；慢服务器不会影响到整个系统的性能。

3. Paxos 的问题

Lamport 的 Paxos 协议曾经几乎是共识的同义词。Paxos 首次定义了一种能够就单一决策达成一致的协议。但是有几个重大缺陷：

  1. 第一个就是 Paxos 非常难以理解，它被分成两个阶段，没有简单只管的解释。Multi-Paxos 的组合规则大大增加了复杂性。多次决策才能达成共识其实可以通过其他更直接和明显的方式分解。
  2. 第二个问题是 Paxos 没有为实际的实现提供一个良好的理论基础。Lamport 提出的 Paxos 只是一个蓝本，很多细节都没有。Chubby 实现了类 Paxos 算法，但细节并没有公开。
  3. 还有选择一组日志条目然后将它们拼接到一份连续的日志没啥好处，徒增复杂度；设计一个日志条目按顺序追加的日志系统更简单高效。
  4. Paxos 的核心在于点对点，但如果有一系列决策，选一个 leader 然后让它来协调更简单快速。

最终导致每种实现从 Paxos 开始，遇到实现它的困难，然后开发了一种完全不同的架构。。。

Chubby 的开发者说过：

There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. . . . the final system will be based on an unproven protocol.

4. 易于理解的设计

设计 Raft 的目标：

  • 它必须系统构建提供完整且实际的理论基础，极大地减少开发者的设计工作量
  • 必须在所有条件下安全且可用
  • 必须高效
  • 最重要也是最难的挑战——易于理解
  • 易于扩展

为了做到这些，设计者使用了两种技巧：

  1. 问题分解，将问题拆解为可被独立解决的子问题。
  2. 减少并简化状态，使系统更加连贯，尽可能消除不确定性。

5. Raft 共识算法

Raft 是一种管理日志复制的算法。

  1. 选主

    完全由 leader 管理日志副本

    客户端给 leader 发送日志条目，leader 再将它们复制到其他服务器；通知服务器何时安全地将日志条目应用至状态机。

    leader 概念简化了日志副本的管理。

    当 leader 失联（故障）时，要重新选主。

通过 leader 这种方式将共识问题解构成三个单独的相关子问题：

  • 选主

  • 日志复制

    从客户端接收日志条目并复制到整个集群

  • 安全

    只要有服务器将日志条目应用至它的状态机，其他服务器都不能应用与之不同的命令。

State

  • 所有服务器都要持久化的状态

    在 RPC 应答前落盘

    • currentTerm 最新任期（系统初次启动后从 0 开始单调递增）
    • votedFor 当前收到投票的候选者 ID
    • log[] 日志条目；每条日志包含状态变更的命令；如果由 leader 接收到的话还有任期

  • 所有服务器都有的易失性状态

    • commitIndex 已知被提交的最高日志条目索引（从 0 开始单调递增）
    • lastApplied 被应用至状态机的最高日志条目索引（从 0 开始单调递增）

  • 只有 leader 才有的易失性状态

    选举后会被重新初始化

    • nextIndex[] 对每个服务器来说，发送给它的下一个日志条目索引（leader 最新日志索引 + 1）
    • matchIndex[] 对每个服务器来说，已知被复制的最新的日志条目索引（初始化为 0，单调递增）

AppendEntries RPC

由 leader 调用来复制日志条目；也用于心跳

  • 参数：

    • term leader 任期
    • leaderId follower 能够重定向客户端
    • prevLogIndex 紧接在新日志之前的条目索引
    • prevLogTerm prevLogIndex 日志条目所在的任期
    • entries[] 将要存储的日志条目
    • leaderCommit leader 的 commitIndex

  • 结果：

    • term 当前任期，leader 自我更新
    • success 如果 follower 的日志条目能够匹配 prevLogIndex 和 prevLogTerm 则为 true

  • 接收者实现：

    1. 如果 term < currentTerm 回复 false
    2. 如果日志在任期匹配 prevLogTerm 的 prevLogIndex 索引处不包含日志条目返回 false
    3. 如果已存在的日志条目与新的冲突（索引相同但任期不同），删掉现有的日志和所有后续
    4. 将新条目追加到日志中
    5. 如果 leaderCommit > commitIndex，将 commitIndex 设置为 leaderCommit 和最新的条目索引中较小的那个

RequestVote RPC

由 candidate 调用来拉票

  • 参数：

    • term candidate 任期
    • candidateId 拉票的 candidate
    • lastLogIndex candidate 最新日志条目的索引
    • lastLogTerm candidate 最新日志条目对应的任期

  • 结果：

    • term 当前任期，candidate 自我更新
    • voteGranted true 代表 candidate 收到选票

  • 接收者实现：

    1. 如果 term < currentTerm 回复 false
    2. 如果 votedFor 为空或者 candidateId，并且 candidate 日志和接收值的日志至少一样新，投票

规则

  • 所有服务器

    • 如果 commitIndex > lastApplied，递增 lastApplied 并将 log[log[lastApplied] 应用至状态机
    • 如果 RPC 请求/应答所携带的任期 term T > currentTerm，把 currentTerm 设置为 T，状态转换为 follower

  • follower

    • 应答来自 candidate 和 leader 的 RPC
    • 如果选举超时，转换为 candidate 状态

  • candidate

    • 一旦切换至 candidate，开始竞选

      • 自增 currentTerm
      • 给自己投票
      • 重置选举计时器
      • 向其他服务器发送 RequestVote RPC 拉票

    • 如果收到大多数服务器的选票，当选 leader

    • 如果从新的 leader 收到 AppendEntries RPC：转换至 follower

    • 如果选举超时：发起新一轮选主

  • leader

    • 一旦当选：给所有服务器发送空 AppendEntries RPC（心跳）；重复以防选举超时

    • 如果收到客户端的指令：追加到本地日志，在条目应用至状态机后回复

    • 如果对一个 follower 来说 lastLogIndex >= nextIndex：发送携带日志条目的 AppendEntries RPC

      • 如果成功：更新那个 follower 的 nextIndex 和 matchIndex
      • 如果因为日志不一致 AppendEntries 失败，自减 nextIndex 并重试

    • If there exists an N such that N > commitIndex, a majority of matchIndex[i] ≥ N, and log[N].term == currentTerm: set commitIndex = N

5.1 Raft 基础

集群中的服务器有三种状态：

  • leader

    集群有且只有一个；只有 leader 处理客户端请求。

  • follower

    正常情况下除 leader 外其余服务器都是 follower；follower 将客户端请求转发至 leader。

  • candidate

    用于选主

Figure 4

Raft 将时间线切分为不同长度的任期（term），每段任期都以选主开始（可能会因为投票歧义无法选主），竞选成功后单个 leader 会管理集群直到任期结束，如图 5 所示：

Figure 5

在 Raft 中任期扮演了逻辑锁的角色，用于服务器检测信息是否过期。每台服务器将当前任期存储下来，随着时间单调递增。服务器之间通信时会交换当前任期：

  • 如果一个服务器的当前任期比另一个小，那就更新为大的那个。
  • 如果 candidate 和 leader 的任期过期了，就立刻切换至 follower 状态。
  • 如果服务器接收到携带着过期任期编号的请求，直接拒绝。

服务器之间使用 RPC（Remote Procedure Call）通信，最简单的共识算法只有两种 RPC：

  1. RequestVote 请求投票

    由 candidate 在选主期间发起

  2. AppendEntries 追加日志条目

    由 leader 复制日志条目或发送心跳时发起

5.2 Leader 选举

Raft 采用心跳机制触发选主。

所有服务器都以 follower 状态启动。leader 会定期发送心跳告诉 follower 它还活着。要是 follower 与 leader 通信超时，这段时间也叫选举超时时间（election timeout），就会发起一次选主。

开始一次选主：

  1. follower 递增它的当前任期并转换至 candidate 状态
  2. 给自己投上一票，并给集群中的其他服务器发送 RequestVote RPC 请求它们投给自己。

如果在同一个任期内 candidate 赢得集群中大多数节点的选票，那它就竞选成功，成为 leader。这里面有几个隐藏条件：

  1. 每台服务器在一次任期内至多只能投一次票
  2. 先来先得
  3. 大多数规则确保在一次任期内至多只有一个 candidate 当选 leader

当选 leader 后向所有其他服务器发送心跳防止“篡位”。

如果有很多 follower 同时成为 candidate，很有可能出现投票分歧，没有一家能够获得多数选票。为了防止投票陷入死循环，Raft 使用随机的选举超时时间（election timeout）来减小投票分歧的几率。绝大多数情况下只有一台服务器会超时；在其他服务器出现超时前它竞选成功并发送心跳。

为什么这样设计

选主是一个很好例子，说明了可理解性如何驱动设计者选择哪种方案。 开始他们想用评分系统：给每个 candidate 打分，如果一个 candidate 发现另一个比自己的分数高，就落回 follower 状态，这样分数更高的 candidate 就少了一个竞争对手。但是这种方式在可用性上有问题，如果高分的服务器 PK 失败了，一台低分的服务器要超时才能再次变成 candidate。他们对算法进行了几次调整，但每次调整后都会出现新的状况。最后得出结论：随机重试的办法更明显和容易理解。

5.3 Log 复制

leader 处理客户端请求。每条客户端请求都包含一条复制的状态机要执行的指令。

  1. leader 将指令追加到它的日志尾部
  2. 并行向其他服务器发送 AppendEntries RPC 来复制那条日志条目。
  3. 日志条目安全被复制后，leader 将命令应用至它的状态机并将执行结果回复给客户端
  4. 如果 follower 崩溃或运行缓慢，亦或者网络包丢了，leader 会不断重发 AppendEntries 直到所有 follower 都追加日志成功。

Figure 6

日志结构如上图，每个条目不仅存储了状态机命令还有任期数字。任期数字被用于检测日志中是否连续。

leader 决定何时才能安全地将日志条目应用至状态机，被称为提交。Raft 保证已提交的条目是持久的，并最终会被所有可用的状态机执行。实际上大多数服务器复制好日志条目就可以提交了（个别慢动作的 follower 不会影响到整体性能），follower 被通知到提交后就把日志条目应用至它本地的状态机。

但是 leader 崩溃会使得日志不一致，原先的 leader 可能还未完全复制好日志中的所有条目。这些不一致会随着一系列 leader 和 candidate 的崩溃被放大。

Figure 7

图 7 说明了 follower 的日志可能和新的 leader 不同。当新的 leader 上台后，a-f 中的情况都可能出现在 follower 的日志中。

  • a、b 丢失日志条目
  • c、d 有未提交的条目
  • e、f 以上两者兼具

在 Raft 中，强制 follower 复刻 leader 的日志来处理不一致，也就是说 follower 日志中冲突的条目会被来自 leader 的日志条目覆盖。AppendEntries RPC 的一致性检查执行上述操作。实现细节请阅读论文。

leader 永不会修改它自己的日志（Append-Only）。

为什么这样设计

Raft 日志机制保持了不同服务器上日志的高度一致性。

如此不仅简化了系统并使其更可被预测，而且这是确保安全性的重要因素。

5.4 安全性

目前为止描述的机制还不足以保证每个状态机以同样的顺序执行相同的指令：举个栗子，当 leader 提交好几个日志条目时，follower 有可能刚好不可用，然后它可能被选举为 leader 并覆盖掉这些日志条目；因此不同状态机可能执行不同指令序列。

通过对可能竞选成功的服务器加一条的限制来完善 Raft 算法，确保无论何时 leader 都拥有前一个任期所有已提交的日志。

5.4.1 选举限制

candidate 选举必须与大多数服务器联系，也就是说这些服务器中至少有一台有所有已提交的日志。通过 RequestVote RPC 实现这个限制：请求中包含 candidate 的日志信息，如果投票者的日志比 candidate 的要新的多，就不投给它。

Raft 通过比较日志中最后一条 index 和任期来判断哪份日志更新：

  • 如果日志的任期不同，任期更新的那份日志就是更新的。
  • 如果任期相同，日志更长的那份是更新的。

5.4.2 提交来自之前任期的日志条目

如果一个 leader 在提交日志前崩溃了，未来的 leader 将尝试完成日志复制。但还是不够安全。

Figure 8

图 8 解释了为什么 leader 无法使用上一个任期的日志条目来决策提交：

  1. a 时间 S1 是 leader，只有一部分复制了 index 为 2 的日志条目。
  2. b 时间 S1 挂了，S5 是任期 3 的 leader。
  3. c 时间 S5 崩溃了，S1 再次当选 leader，继续复制。此时，任期 2 的日志条目已经被复制到大多数服务器上了，但仍未提交。
  4. d 时间 S1 又挂了，S5 有可能成为 leader，用它自己的日志条目覆盖所有节点的日志。
  5. 但是如果 S1 在崩溃前将它任期内的日志条目复制到大多数服务器上，如 e 所示，而且还被提交了（S5 不可能当选 leader）。此时日志中所有先前的记录也被提交。

为了消除图 8 中的问题，Raft 从不提交之前任期的日志条目；只有来自当前 leader 任期的日志会被提交；所有先前的日志条目会被间接提交因为 Log Matching Property。

为什么这样设计

为提交带来额外的复杂度是因为日志条目保留了它们原来的任期编号。其他共识算法中，如果新的 leader 复制来自先前任期的日志条目，那它必须使用新的任期编号。而 Raft 的办法更容易推理日志条目，因为它们保持相同的任期编号。而且相比其他算法，Raft 中新的 leader 发送更少来自先前任期的日志条目。

5.4.3 安全论证

假设任期 T 的 leaderT 提前来自当前任期的日志条目，但是还未被未来某个任期 U 的 leaderU 保存：

  1. leaderU 当选后它的日志中缺失了已提交的日志

  2. leaderT 将日志复制到集群大多数服务器上，leaderU 收到大多数服务器的选票。因此至少有一个投票节点既接收到了 leaderT 的日志条目然后又投票给了 leaderU，如图 9。

    Figure 9

    1. 任期 T 的 leader S1 提交了来自它任期内的日志条目
    2. S5 当选为下一个任期 U 的 leader
    3. 至少有一台服务器 S3 既接收到了日志条目又反手给 S5 投上一票

  3. 当投票者给 leaderU 投票时它仍然保存着那条日志。只有 follower 与 leader 不一致时它才会删除日志条目。

  4. leaderU 必须至少和投票者一样新，这就导致了两个矛盾中的一个：

    1. 如果投票者和 leaderU 都经历最新的任期，那么 leaderU 的日志必须起码和投票者的一样新，也就是它的日志包含了投票者日志中的所有条目。这是一个矛盾，假设投票者包含了已提交的日志而 leader U 没有。
    2. leaderU 最新的日志任期编号一定要比投票者的大。假设创建了 leaderU 最新日志条目的那个更早的 leader 一定包含了 leaderU 所有日志条目。那么 leaderU 就一定包含了已提交的条目，这也矛盾。

  5. 因此任期编号大于 T 的 leader 一定要包含来自任期 T 所有已提交的日志条目。

  6. Log Matching Property 保证了未来的 leader 也会包含间接提交的日志，就像图 8 中的 index 2。

5.5 Follower 和 Candidate 崩溃

相比 leader 崩溃处理起来简单得多，而且相同。

follower 和 candidate 崩溃后发送给它的 RequestVote 和 AppendEntries RPC 当然会失败，Raft 就无限重发。

  • 如果挂掉的服务器重启了，RPC 就会顺利完成。
  • 如果服务器在完成 RPC 后应答前又挂了，重启后会再次收到相同的 RPC。

Raft RPC 是幂等的，不会造成破坏。

5.6 可用性

我们要求 Raft 的安全性必须不依赖于时钟：系统不可以因为事件提前或延后发生而产生不正确的结果。但是可用性却无法脱离时钟。举个栗子，如果有服务器崩溃时通信时间过长，那么 candidate 没有足够的时间来竞选；没有稳定的 leader，Raft 无法进行下去。

时间对于选主来说非常关键：

broadcastTime « electionTimeout « MTBF

  • broadcastTime：服务器向集群中所有服务器并行发送并接收 RPC 一趟来回的时间，0.5-20ms，取决于存储技术

  • electionTimeout：5.2 中描述的选举超时时间，10-500ms

  • MTBF：单台服务器的平均故障间隔时间，几个月甚至更长

  • 广播时间要远远小于选举超时时间这样 leader 能够靠谱地发送心跳信息防止 follower 篡位

  • 鉴于随机的选举超时时间，投票分歧不太可能发生

  • 选举超时时间应该比 MTBF 小几个数量级，这样的系统才稳定。

6. 集群成员变更

实际上系统的架构偶尔也会被变更，例如更换故障的服务器。但我们要保证集群尽量可用，就不可以关闭整个集群来搞。另外，只要有手动操作的步骤，就有可能操作失误。考虑到以上，他们决定将架构变更自动化，并纳入 Raft 算法中。

要保证架构变更机制的安全，在过渡期内必须杜绝出现脑裂（同时存在两个 leader）。不可能一次性地切换所有服务器，所以集群有可能在过渡期间分区。

Figure 10

在图 10 的案例中，集群从 3 节点增长到 5 节点。很不幸某个时间相同任期内会选举出来两个 leader，一个是老集群的大多数，另一个是新集群的大多数。

为了确保安全，架构变更必须分成两阶段，有很多种实现方案：

  • 有些系统在第一阶段禁用原先的架构，因此集群无法处理客户端请求；在第二阶段使能新架构

  • Raft 集群首先切换到一个过渡架构我们称其为联合共识（joint consensus）；一旦联合共识被提交，系统就转换到新架构，联合共识联结了新旧架构：

    • 两种架构日志条目都被复制到所有服务器
    • 两种架构中的任一台服务器都可以成为 leader
    • 达成一致需要新旧配置分别获得法定票数

    联合共识使得集群在架构变更时能够继续提供服务。

集群架构配置也存在复制的日志中，并使用特殊的日志格式来通信。

Figure 11

  • leader 收到请求集群从 C old 架构变更为 C new 架构，将中间态的联合共识架构配置（C old,new）作为日志条目存储下来并且复制。
  • 一旦服务器将新的配置追加到日志中，它就会使用这份配置。leader 将使用 C old,new 的规则来决策 C old,new 的日志何时被提交。

一旦 C old,new 被提交，无论 C old 还是 C new 未经对方批准都不可以决策。Leader Completeness Property 确保只有 C new,log 日志条目的服务器才能被选举为 leader。当新的架构配置在 C new 下提交后，不在新架构中的服务器就可以关掉了。

有三个问题需要解决：

  1. 新的服务器可能没有存储任何日志条目

    可能要花不少时间才能跟上。Raft 引入一种额外的阶段，新加入集群的服务器不能参与投票，一旦追上进度，就正常处理配置变更。

  2. 集群 leader 可能不在新的架构配置中

    这种情况，只要 leader 提交了 C new 日志条目，逐步回到 follower 状态。这就意味着有一段时间，leader 在管理着不包括它自己的集群；它也复制日志条目但计算“大多数”时却要把自己排除在外。

  3. 被移除服务器也可以破坏集群。

    这些服务器不会接收心跳包，所以在开始新的选主时将超时。但它们会用新的任期编号来发送 RequestVote RPC，这会导致现任 leader 落回 follower。为了防止这种情况，当服务器相信当前有 leader 存在时，会忽略 RequestVote RPC。

7. 日志压缩

Raft 的日志随着系统运行会日渐增长，但实际情况中不能无限制地增长，需要某种机制来删除过期的日志。

  • 打快照（snapshot）是一种简单的办法，整个当前系统状态被存储到快照文件中，快照点之前的日志都被丢弃。快照在 Chubby 和 ZooKeeper 中被使用。
  • 渐进式压缩，比如日志清理和 log-structured merge tree 也可以。这些都是一次操作一部分数据，所以负载更均衡。但相比快照要复杂得多，因为对整个数据集操作。日志清理需要修改 Raft，而状态机可以使用与快照相同的接口实现 LSM 树。

Figure 12

以上是 Raft 快照的基本思路。每台服务器各自打快照，只转换日志中已提交的条目。快照中也有一些元数据：lastIncludedIndex 和 lastIncludedTerm，这些用于 AppendEntries 一致性检查。为了启动集群成员变更，快照还包括了日志中的最新配置作为 lastIncludedIndex。一旦服务器完成快照写，就会删除所有 lastIncludedIndex 前的日志条目，还有以前的快照。

虽然集群中的服务器单独打快照，但是 leader 会向落后的 follower（“闪电”或者刚加入集群的新节点）发送快照。

leader 利用 InstallSnapshot RPC 向落后的 follower 发送快照。

InstallSnapshot RPC

由 leader 调用向 follower 发送快照文件的 chunk。

  • 参数：

    • term leader 任期
    • leaderId follower 能够重定向客户端
    • lastIncludedIndex 快照替换掉所有日志条目直到包括这个 index
    • lastIncludedTerm lastIncludedIndex 所在的任期
    • offset 快照文件中 chunk 位置的偏移量
    • data[] 快照 chunk 的真实字节，从偏移量开始
    • done 是否为最后一个 chunk

  • 结果：

    • term 当前任期，leader 自我更新

  • 接收者实现：

    1. 如果 term < currentTerm 立即回复
    2. 如果 offset 为 0（这是第一个 chunk）就创建快照文件
    3. 在给定的偏移量将数据写入快照文件
    4. 存储快照文件，丢掉索引较小的快照
    5. 如果已存在的日志条目和快照的 lastIncludedIndex index 和任期相同，保留后面的日志条目并回复
    6. 丢掉所有日志
    7. 使用快照内容重置状态机（并加载快照的集群配置）

为啥这样设计

这种快照方式违背了 Raft 的强势 leader 原则，因为追随者可以在 leader 不知情的情况下打快照。但这种背离是合理的，因为在快照时已经达成了共识，所以没有决策冲突。

他们还设计了一种只有 leader 才能创建快照的方案，leader 会将快照发给所有 follower。但是有两个缺点：

  1. 其一发送快照很吃带宽，还会拖慢快照进程。其实每个 follower 已经有足够多的信息来生成本地快照了，比从网络接收要省的多。
  2. leader 的实现会更复杂一些。

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

  1. 服务器必须决策何时快照。如果太频繁，浪费磁盘带宽和电能；但频率太低又存在耗尽存储空间的风险，而且重启后回放日志所需的时间也会增加。

    一种简单的方案是当日志达到一个设定大小就打快照。

  2. 写快照非常耗时间，我们不希望这影响到正常操作。

    使用 copy-on-write 技术（Linux fork）。

8. 客户端交互

客户端会随机从集群中选一台服务器连接，如果没选到 leader，服务器会拒绝请求并最新的 leader 信息。如果 leader 挂了，就再随机选一台。

Raft 的目标之一是实现线性化语义。但到目前为止 Raft 可以多次执行一条指令：如果 leader 在提前日志后但应答客户端前挂了，客户端给新的 leader 重发指令，导致二次执行。一种解决方案是客户端给每条指令分配一个唯一序列号。状态机发现收到的指令已经被执行过，就立即应答而非再次执行。

只读操作无需处理日志，但如果没有额外的措施，有可能返回过期数据，响应请求的 leader 可能已经被更新的 leader 取代了只是它还不知道。但是线性读一定不会返回过期数据。Raft 需要两个预防措施来保证：

  1. 首先，leader 必须知道那些日志条目已被提交

    Leader Completeness Property 确保 leader 拥有所有已提交的日志条目，但在其任期开始时，它可能还不知道。Raft 设计在 leader 任期开始时提交一种无操作（no-op）日志条目来处理这种情况。

  2. 再者，leader 在处理只读请求前，必须检查它是否还在位。

    Raft 通过 leader 与集群中大多数服务器交换心跳来应对。

11. 总结

算法的设计通常以正确、高效和简洁为目标，我们相信可理解性也同样重要。除非相当了解算法，否则很难在实现中还原出来其特性。

在本文中我们讨论了分布式共识问题，其中一个被广泛认可但难以攻克的算法——Paxos，多年来对学生和开发者来说都是巨大的挑战。于是 Raft 被设计出来了，并已经证明了它确实比 Paxos 更容易理解。Raft 为构建基础设施提供了一个更好的理论基础。将可理解性作为第一要义改变了 Raft 的设计方式，但本质上也只是重用一些技巧，例如问题解构和简化状态空间。