前言

这个部分来自课程 MIT6.824，这门课每节课都会精读一篇分布式系统领域的经典论文，并由此传授分布式系统设计与实现的重要原则和关键技术。

个人认为阅读论文比课程本身更加重要，课程围绕论文展开，可以快速获取论文的核心观点，课程的一切细节以及未提及的内容在论文中具有最详细的解释。另外教授会从当今立场（2022）评价论文的意义和缺陷，同时可能补全论文中缺失的信息解释，教授对学生提问的一些回答具有很好的启发意义，这些内容不被包含在论文中。

本文综合课程内容和论文核心观点，并参考一些其他资料整理，希望对你学习课程有所帮助。

课程官方：https://pdos.csail.mit.edu/6.824/

博主整理：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824

B 站录屏：https://www.bilibili.com/video/BV1qk4y197bB

​请阅读论文 VMware FT： https://pdos.csail.mit.edu/6.824/papers/vm-ft.pdf

相关推荐：Debugging by Pretty Printing (josejg.com)

Raft 是一种一致性算法，它被誉为更容易理解的 Paxos 算法，用于解决单点故障和日志一致性问题。

脑裂 (Split Brain)

首先我们需要了解 Raft 出现的背景，简单来说 Raft 的出现就是为了解决脑裂 (Split Brain) 的问题。其实我们在前面的章节中多次提到了脑裂的概念，即网络分区。

在 MapReduce 中，我们使用计算的复制来实现容错，其中我们的算法由单一的 master 控制，在这个章节中我们讨论了如何使用复制解决 worker 的故障，但并未讨论如何处理 master 的故障。在 Google File System 中，我们提到了 master 同时具有 standby 和 shadow 用于处理其故障但并未讨论其细节；另一方面，我们也讨论了 Primer Chunk 的租约问题，其中提到 master 只会在成功废弃租约或租约过期时任命新的 Primer。在 VMware-FT 中，我们虽然大量讨论如何实现主备的状态机复制，但最终仍然依赖 Test and Set 服务避免脑裂。

事实上，在我们之前的所有讨论中，系统的脑裂问题始终依赖外部的单点故障。如果这个外部服务也故障了，那么系统只能停止所有工作等待外部服务恢复正常，否则就有出现脑裂的风险。例如在 GFS 中一旦出现脑裂，master 必须等待原租约过期，才会任命新的 Primer，这段时间该 Chunk 是不可用的；而在 VMware-FT 中，一旦无法访问 Test and Set 服务，Backup 必须等待，不能擅自提升为 Primer。所以我们说之前的所有讨论都依赖单点故障。

这基本上是上世纪 80 年代前必须面临的挑战，当时又的确有多副本系统的需求。例如控制电话交换机的计算机系统，或者运行银行系统的计算机系统。当时为了排除脑裂，不得不使用这两种技术：

  • 第一种是构建不可能出现故障的网络。这是可行的，例如我们的计算机中连接 CPU 和内存的网络就是不可能出现故障的。这样我们需要小心的控制物理环境，例如不要将网线拖在地板上让谁都可以踩到。这样如果另一台设备无法访问，一定是机器故障而非网络分区。当然这样的大型网络系统需要足够的资金。
  • 另一种解决方案是人工解决。例如当服务不可用时，不要做任何事情，给运维人员打电话。运维人员会去检查是否是真的机器故障或者是网络故障，运维人员将决定是否启动一台新的服务器或者修复网络。这实际上依然将系统依赖于单点故障，那就是运维人员。

多数决议 (Majority Vote)

尽管存在脑裂的可能，但是随着理论研究的深入，人们发现哪怕网络存在故障，我们也有办法实现自动完成故障切换的系统。在构建网络故障的自动切换，同时又避免脑裂的多副本系统时，人们发现多数决议（Majority Vote）是问题的核心，而解决这类的算法统称为一致性算法。不管是我们今天将要介绍的 Raft 还是早期的其他一致性算法都基于这一核心原则。

多数决议系统的第一步在于系统首先需要具有奇数个 server。例如上面这个两台 server 的系统现在由于网络问题被分为两部分，它们过于对称并分别运行相同的程序，这就发生了脑裂。但是当一个网络拥有奇数例如 (2n+1) 台 server 时，一个基本的事实是如果网络分区发生，不会有超过一个分区拥有超过半数即 (n+1) 台设备。因此在这个一致性系统中，所有的决议，包括我们即将提到的 Raft 中的 leader 选举和日志提交，都需要超过半数 server 的表决通过（leader 也可以给自己投一票），这样系统容许少于半数的 server 发生故障。这就是构建一致性系统的基础。

这里有一点需要明确，server 的总数并不是处于开机状态的 server 具有多少，而是所有加入这个 Raft 系统的 server 有多少，这个点困扰了我（教授）很久。因为网络是不可靠的，我们永远无法知道一台 server 是因为宕机还是网络中断而无法访问，而我们所有的讨论都将基于所有的机器都明确这个集群中总共拥有多少机器。在论文的 Section 6 有讨论 Raft 可以在不中断的情况下进行配置更新，它们借助一种介于新旧配置之间的中间状态实现。

另一个值得一提的性质是，如果新的 leader 得到 “多数派” 的支持，当然旧 leader 在此前也得到了另外 “多数派” 的支持，这两个 “多数派” 中必然至少存在一个支持者是重叠的。相比于其他的一致性系统，Raft 更依赖于这种特性。因为旧 leader 的支持者中未支持新 leader 的可能并不知道新 leader 的存在，它们依然支持旧 leader。但是由于它们中必然存在新 leader 的支持者，这确保了依然支持旧 leader 的必然不再超过半数，因此旧 leader 此后的所有提交都无法再被表决通过。

所以，在这种多数决议的思想支持下，大概在 1990 年代，有两个算法基本被同时提出。这两个系统指出，你可以使用这种多数决议系统，从某种程度上解决解决之前明显无法避免的脑裂问题。这两个系统中一个是 Paxos，Raft 论文中对它有较多的介绍；另一个是 View Stamped Replication（VSR），由 MIT 发明。尽管 Paxos 要知名的多，但论文批判它是臭名昭著的，Raft 在设计上更接近于 VSR。这两个系统都有着数十年的历史，但只在最近 15 年，也就是它们发明后的 15 年，才开始走到最前线被大量的大规模分布式系统应用。

Raft 与应用程序

Raft 会以库（Library）的形式存在于服务中，我们的服务是一个应用程序，例如我们这节课的实验目标 K/V 数据库。那么我们的服务可以分为两部分：应用程序和 Raft 库。应用程序会接收 RPC 和其他客户端请求，然后它会调用 Raft 库，不同节点的 Raft 库会相互协作，来维护多副本之间的一致性。

从软件的角度来看，我们可以认为在该节点的上层是应用程序，而下层是 Raft 库。首先应用程序具有状态，它在调用 Raft 库时需要传递它的状态，这个状态 Raft 将它称为 log entry，它描述了上层应用程序进行的一个确定性操作，之后这个 entry 会在网络中广播，其他节点也会收到这个 entry 并执行相同的操作。这个 log entry 有一个 commit 的动作，即 Raft 向网络广播后确认这个操作被多数决议通过可以安全执行，它会响应上层应用，上层应用只有收到 commit 动作后才实际执行操作，当然这个操作也有可能被撤销来保证一致性。当然这是对于 Raft 的 leader 节点，对于其他节点它可能主动向上层应用发送 commit 动作，因此应用程序也应该支持监听这个动作。

同时，如 Raft 论文所说 Raft 本身也具有状态。对我们而言这些状态最重要的部分就是 log，它存储了应用程序提交的所有操作日志即 log entry，它包括已提交的和未提交的，当 Raft 接收来自应用程序或 leader 的 log entry 时会向这个队列追加，而撤销未提交日志时会从这个队列删除。

日志同步时序

我们已经基本了解了 Raft 分为选举（Election / Vote Request）和日志提交（Log / Apply Entry）两个环节。现在我们先跳过选举这个环节，假设 leader 和网络是始终可靠的。

假设我们的 Raft 系统拥有三台 server，这时 client 向 leader 发送请求，然后 leader 会向网络广播 ApplyEntryRPC。follower 在收到后会首先将 log entry 记录在本地的 log 中，然后它将回复 leader 表决提交这条 entry。由于这个系统只有三台 server，加上自己的决议，leader 只需再收到一个表决后就会将 entry 提交，并向 client 响应。与此同时，leader 还会向网络广播提交 entry，这条信息通常被包含在下一次 ApplyEntryRPC 或者 heartbeat 中，leader 也不再需要等待这条记录响应。

当然这里我们假设 leader 和网络是可靠的，我们将在后面讨论如何处理可能的故障，例如 leader 没有成功向网络广播提交 entry 就立即宕机了。这时可能新的 leader 上任，我们依然需要保证已提交的记录在多数 server 提交等等。

我们关心一个问题：为什么 Raft 这么关注 log，log 究竟在 Raft 中起了什么作用？这非常值得讨论。

  • Raft 之所以这么关注 log，是因为它是用来操作排序的一种手段。对于复制状态机而言这至关重要，它们必须以相同的顺序执行相同的指令，log 实际上就确定了这个顺序。
  • 另一方面，在一个副本收到 log entry 时，它不会立即提交它，它需要等待 leader 确认提交。这可能需要很长一段时间，可能会有多条记录同时处于未提交状态，log 提供了这样的存储。而对于 leader 它无法保证所有 follower 收到提交，它需要 log 作为存储向 follower 实现故障重传。
  • 最后一点是只需多数决议 log entry 就会提交，这可能有一些机器始终落后于当前状态，例如一台机器宕机了，它可能在几天后才被运维人员修复。这些 log 存储在磁盘中，这样故障重启后这些 log 依然存在，而这些 log 会用来在故障重启后帮助机器同步状态。所以 log 提供了可持久化存储操作，机器可以依赖它来恢复状态。

leader 选举 (Leader Election)

首先第一个问题是，Raft 系统为什么需要一个 leader。实际上一致性系统确实不必须引入 leader，Paxos 就是一个这样的系统。有很多原因导致 Raft 具有 leader，首先具有 leader 是更高效的。假设一个系统具有 leader，它的每次决议只需一轮消息就可以完成多数决议；而对于一个没有 leader 的系统，例如 Paxos，它必须每次选举一个临时的 leader，然后再进行一轮多数决议。假设 leader 是可靠的，使用 leader 将性能提升到 2 倍，当然实际上多数时候机器都是可靠的。

另外，使用唯一的 leader 可以帮助我们构建更易于理解的 Raft 系统。Raft 的生命周期中可能出现多个 leader，它们使用任期（Term）区分，每个任期至多只有一个 leader。follower 不需要知道谁是 leader，它们只需要知道当前 leader 的任期，错误的任期一定无法在系统内达成多数决议。

那 leader 是如何创建出来的？原先的 leader 会周期性的向 follower 发送 heartbeat，follower 具有一个选举计时器（Election Timer），当 follower 在计时器时间耗尽而没有收到 heartbeat，它就会发起选举。发起选举的意思是，follower 想任选新的 leader，它将 term +1，然后发送 RequestVoteRPC，这时候 follower 被称为候选人（candidate）。

这里需要注意的一个问题是，并不是说 leader 没有发生故障时就不会发生选举，但 leader 没有故障时一定发生选举。比如 leader 仍然健康运行，只是由于丢失了几个 heartbeat 而发生选举。比如网络分区发生时，旧的 leader 可能仍然正常运行，并且依然受到 “少数派” 的支持；但此时新的 leader 选举产生，旧的 leader 可能并不知道新的 leader 已经产生而继续运行。这些都应该被考虑在我们将来的实验中。

为了能够当选，Raft 要求一个候选人（candidate）获得过半选票。每个节点在一个任期内只会投出一张选票。这样，就不可能有两个候选人同时获得过半的选票，因为每个节点只会投票一次。所以这里是过半原则导致了最多只有一个胜出的候选人，这样我们在每个任期会有最多一个选举出的候选人。

同时，也是非常重要的一点，过半原则意味着，即使一些节点已经故障了，你仍然可以赢得选举。如果少数节点故障或者出现网络问题，我们仍然可以选举出 leader。如果超过一半的节点故障，或者在另一个网络分区，那么系统会不断地尝试选举Leader，并永远也不能选出一个 leader，因为没有过半的服务器在运行。

如果一次选举成功了，整个集群的节点是如何知道的呢？当一个节点赢得了一次选举，这个节点会收到过半的认可投票，这个服务器会直接知道自己是新的 leader。但是其他节点并不能直接知道谁赢得了选举或者是否有人赢得选举。这时赢得选举的候选人，会通过 heartbeat 通知其他节点，而这些节点会将最大的任期认为是新的 leader，其他一些未任选的候选人也将退出候选人状态。

选举定时器 (Election Timer)

任何一条 ApplyEntryRPC（heartbeat 也是一条 ApplyEntryRPC）都会重置选举定时器。这样只要 leader 还在正常工作，正常发送 entry 或者 heartbeat，follower 就会重置选举计时器，从而阻止选举的产生。当然，如果网络故障或者丢包，不可避免的会产生选举。如果这一切正常，不太有可能有新的选举产生。

如果一次选举产生 0 个 leader，很显然这次选举失败了。这种情况事实上很容易发生，例如产生太多网络分区或者太多的机器发生故障，那么永远无法凑够足够的选票产生新的 leader。另一个有趣的事情是，如果太多选举同时发生，那么很有可能无法产生一个 leader，因为它们同时竞争选票以及它们本身会为自己投票。

于是选举失败发生了，如果候选人没有收到足够的选票，或者 follower 没有在定时器周期内发现新的 leader，它们会开始新一轮的选举。最坏的情况是这样的选举不断失败并重试，这种现象称为 “活锁”。Raft 不能完全避免选票分裂（Split Vote），但是大大减少这种现象发生的概率。Raft 通过为选举定时器设置随机的超时时间来达到这个点。由于选举定时器具有不同的超时时间，因此如果一个网络分区产生或者原 leader 发生故障，不太可能同时触发定时器超时，其中最先超时的机器更有可能成为新的 leader。

这里对于选举定时器的时间设置有一些细节，选举定时器的时间随机应该属于一个区间，这个区间有上限和下限。首先下限的设计时间至少应该大于一次 heartbeat 发生的时间间隔，我们当然不能允许一次 heartbeat 还没发生就进行一次选举，当然我们通常容许一些丢包的发生，可能将下限设置为 heartbeat 间隔的 3-4 倍更合适。另外，我们需要设计上限，上限的设计决定了系统从故障恢复需要的时间，因为在这个等待的周期内，系统是不可用的。对于从故障恢复的时间的需求取决于系统发生故障的频率，如果故障经常发生我们可能希望它能很快恢复；当然如果故障每年发生一次，那故障恢复时间就显得不是很重要了。最后一个需要考虑的点是，两个随机的选举定时器超时时间应该超过 RPC 往返（Round Trip）时间，否则实际上选票分裂依然很容易发生。

日志恢复 (Log Backup)

现在我们来讨论日志恢复。当新的 leader 上任，它并不知道 follower 的日志处于什么状态，也不知道应该从何处开始恢复。如下面这个示例：S1 拥有一个 Term3 的 entry，S2 和 S3 拥有两个 Term3 的 entry，但分别拥有 Term4 和 Term5 的 entry。首先我们需要讨论这种情况是存在的，因为如果情况不可能发生我们就没必要解决它。事实上 Raft 确实具有一些约束使得满足一个好的性质，一些情况不可能出现，我们会在后面介绍这些约束，而在这里我们假设讨论的情况是满足约束的。

这还是一个拥有三台机器的 Raft 系统。Term3 时我们假设 S3 作为 leader，它提交了两条 entry，其中第一条 entry 成功提交到所有机器，第二条成功提交到多数机器。此时由于网络不稳定，S2 成为 Term4 的 leader，它在本地加入了一条 entry，还未发送就宕机了。然后 S3 可能又成为 Term5 的 leader，它在本地加入了一条 entry，还未发送就宕机了。但是它立即恢复后 Term6 可能依然任选 leader。于是如图假设的情况发生了，并且我们假设 S3 成为 Term6 的 leader。

Raft 初始化时假设所有机器和自己都是同步的，现在它需要发送一条 Term6 Index13 的 ApplyEntryRPC，这个过程它将同时发送 prevLogTerm 和 prevLogIndex 表示上一条记录的任期和索引。这条消息到达目标机器，它会首先核验 prevLogIndex 所在槽位的任期是否与 prevLogIndex 一致，如果不一致它会返回 Reject 到 leader。对于 S1 由于槽位 12 是空的，因此它将回复 Reject；对于 S2 由于槽位 12 是 Term4 与 prevLogTerm=5 不一致，因此它将回复 Reject。

leader 为每个 follower 维护一个 nextIndex，用以维护应该向某个 follower 发送哪一条 entry。初始化时，leader 会假定 follower 与自己是同步的，因此所有的 nextIndex 都是最新的索引。当一条 ApplyEntryRPC 成功时，显然地，它会将对应 follower 的 nextIndex 自增；相应的对 Reject，它将 nextIndex 自减，然后尝试发送新的 entry，如果依然 Reject 那么继续自减。因此最后 nextIndex 会回退到合适的位置，并且它们将开始追加或者覆盖原有的记录。例如对于 S1，它将回退到 Index11 并开始追加；对于 S2，它将回退到 Index12 并开始覆盖。这样所有机器的 log 最终都会保持一致。

Raft 提到了日志的快速恢复，它是指日志的快速回退。我们前面介绍的回退方法是正确的，但他每次只回退一条 entry。事实上我们可以做的优化是每次回退一个 term，如果 leader 向 follower 发送了 ApplyEntryRPC，follower 在 Reject 时会同时发送这个位置的 term 和这个 term 开始的索引。leader 收到 Reject 信息后可以计算出应该回退多少，这需要分类讨论：第一种情况是 leader 和 follower 在这个索引具有不同的 term，那么 leader 应该直接回退到这个位置；第二种情况是 leader 和 follower 在这个索引具有相同的 term，那么它应该向后查找第一个 term 不同的位置，然后回撤到这个位置；第三种情况是 follower 的这个位置是空，那么直接回撤到它的结尾位置即可。有学生提到可以使用二分查找的方式进一步提高效率，不过这可能需要一种新的 RPC 方式支持。

这里必须讨论的一个问题是，我们在这里删除了一些日志，这里必然有一些客户端请求被丢弃了。为什么这些日志可以安全删除？显然我们不能删除一些 committed 的记录。我们将在下一节讨论这个问题。

选举约束 (Election Restriction)

（这部分均为笔者个人总结）

在前面的例子中，我们选取了 S3 作为新的 leader。那么现在的问题是，所有节点都可以作为新的 leader 吗？答案是不是的，选举具有一定的约束，只有一部分节点有机会成为 leader；其他节点有可能发起选举，但会被否决。

显然我们必须保证，选举产生的新 leader 不存在覆盖已提交记录的行为，否则系统就会出现混乱。一种显而易见的解决方案是，我们保证选举产生的 leader 总是具有最新的 committed 记录，并以前面提到的日志恢复方式进行，这一定不会覆盖 committed 的记录。事实上 Raft 就是这么做的，因此我们需要通过一些选举约束的方式来保证上面的假设总是正确，我们下面就将来讨论这个问题。

首先我们来介绍选举约束的正确做法。当选举发生时候选人会将 prevLogTerm 和 prevLogIndex 发出，节点只会在满足下面的条件时才会发出赞成票：

  • 候选人的最后一条记录的 Term 大于本地的最后一条记录。
  • 如果两者最后一条记录的 Term 相同，候选人的最后一条记录的 Index 大于等于本地的最后一条记录。

这个操作很简单并且容易记忆，但是我们需要证明它为什么是正确的，论文中对这部分有非常多的讨论。在决定是否赞成新的候选人时实际在比较元组 (Term，Index)，为什么选择比较这个元组？我们称之为逻辑时钟（logical clock）。物理时钟是不可靠的，两个节点的时间无法绝对的同步，因此逻辑时钟是一种更加可靠的，可以体现时序关系的表达式。我们发现 term 的自增是满足时序关系的；如果两个 entry 的 term 相同，那么就需要比较它们分别是当前 term 的第几条记录。这里有个非常好的性质，我们通过日志恢复的讨论，每个 term 的所有 entry 要么不出现在某个节点的日志中，要么它们一定从相同的 Index 开始。因此当 term 相同时，我们通过比较 Index 可以考察两条 entry 的时序关系。这就是逻辑时钟的概念，我们通过比较 (Term，Index) 来进行时序的表决，从整体上看系统更倾向于表决更新的候选人。

并不是只有最新的候选人有机会成为 leader，为了获得多数选票至少多数节点都有机会成为新的 leader。我们假设总数有 (2n+1) 个节点，那么最新的至少 (n+1) 个节点都有机会成为新的 leader（排名 (n+1) 的节点可能成为新的 leader 因为它可以获取 n 个节点的选票和自己的选票；另外可能会有多于半数的节点有机会成为 leader，例如如果所有节点都是最新的，那么它们都可以成为新的 leader）。

我们称每次选举出的 leader 总是具有所有 committed 的记录的性质为领导完整性（leader completeness），我们可以使用归纳法证明这个性质总是被满足。首先我们假设所有的前任 leader 是满足领导完整性的，因此所有任期发生在拥有最后一条 committed 记录的节点上，我们称之为 “多数派”；因为没有新的任期发生，在不满足领导完整性的节点上一定不存在比最后一条 committed 记录更新的任期，我们称之为 “少数派”。因此 “少数派” 永远无法获取 “多数派” 的支持，它们永远无法成为新的 leader，只有满足领导完整性的 “多数派” 可能继续任选新 leader。

这就是选举约束，我们在这里证明了这种选举约束的正确性。

日志压缩 (Log Compaction and Snapshot)

日志压缩存在的背景是，如果一些节点运行了几个月甚至几年，按照我们之前的逻辑所有的记录都会被保存。这需要占用越来越大的存储空间，另外这时如果加入新的机器，它们必须从头执行所有日志，这需要花费相当长的时间。因此日志压缩就显得非常必要。

每台机器会分别对自己进行日志压缩，其实质就是将一些陈旧的记录变成一个快照，当然它们只会压缩 committed 的记录。每台机器会分别做这件事，也就是说它们完成日志压缩的进度可能是不一样的，例如一台具有更多机器的日志可能压缩更多日志，而一台更少日志的机器压缩更少的日志。日志压缩完成后，它们可以安全的删除那些被包含在日志中的记录。

但这时在日志同步上出现了新的问题，例如一台机器可能已经宕机几个月了，现在重新加入集群。举个例子，它上面可能包含了前 10 条记录的快照，随后是 5 条已提交的记录；此时 leader 可能包含了前 20 条记录的快照。此时这台机器需要与 leader 同步，你会发现由于它需要从早于 leader 日志的位置开始，而 leader 已经将它压缩成了快照，这个过程无法进行。

Raft 中为了对这种情况进行支持，它还包含了 InstallSnapshotRPC。这个调用将命令机器清空它的所有状态，然后从头加载 leader 的快照。当然这里存在的一个问题是，对于一个状态远落后于 leader 的机器，使用 Snapshot 的方式可能帮助其更快与 leader 同步；但如果这台机器仅略微落后于 leader 而触发了 InstallSnapshotPRC，这将带来巨大的性能损失，因此我们需要权衡在什么位置开始进行快照。