前言

这个部分来自课程 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

VMware FT 是应用与虚拟机系统 VMware 中的容错体系，它通过主从复制来提供可靠的服务。

我认为在这个章节中教授的介绍与论文存在不一致，产生冲突时我将更倾向于对论文的理解。对于不一致的点我会标明它在论文的位置。

复制的基本概念 (Replicate)

其实我们在前面的 GFS 中就大量介绍了复制，同样的 VMware FT 也是通过复制来建立容错的。

用最简单的方法来描述复制可以解决的容错问题就是单台设备的 Fail-Stop。这是容错领域的通用属于，它是指当任何过程中出现了异常，我们立即停止继续执行，而不是继续返回一个错误的结果。当然复制并不能解决所有的错误，例如硬件和软件的 Bug，这导致无论如何复制和运行你的程序都无法得到正确的结果。

另一个问题是复制是否值得？复制意味着需要花费额外的计算和存储资源，例如在 GFS 中每份数据拥有 3 份副本，而在我们即将介绍的 VMware 中存在 2 台主机。复制考虑的问题就是服务的价值，你提供的服务是否值得提供额外的成本，例如银行应该提供可靠的服务，而我们的课程网站偶尔宕机并不会带来太大的损失。

确定性状态机 (Determined Status Machine)

值得注意的是，VMware FT 是以状态机（Status Machine）的形式实现复制的，它使用这种方式实现 Primer 和 Backup 两台机器的同步。如果我们需要实现两台机器完全同步，一种最简单的方法是只需在 Primer 的每次状态变化后，将它的所有内存、寄存器等信息全部复制到 Backup 上，这样显然保证了 Backup 始终是与 Primer 同步的。但是这样的问题也是严重的，全部复制的开销是巨大的，何况它通过网络传输很大程度上收到网络带宽的限制。

VMware FT 当然没有采取这样的方案，它使用状态机复制的方案。状态机复制是指，如果两台机器具有完全相同的初始状态，并且每次以相同的序列执行完全相同的操作，那么它们的内部状态始终是同步的，当下一个操作到来时，它们也将得到相同的结果。通过状态机复制的方式，Primer 每执行一条指令都会将它发送到 Backup，然后 Backup 将会执行它从而保持同步，在 Primer 宕机后可以快速的接替它的工作。显然这样的工作方式的网络开销要小得多。

当然，状态机复制的模式是理想的，它受到非常多因素的影响，这也是我们后面必须解决的问题。一个是同步频率的问题，前面讲到 Primer 通过转发指令实现机器间同步，因此 Backup 总是要比 Primer 要滞后一些，我们十分关心它们的交换频率。一个是非确定性问题，并不是所有的指令都是确定的，例如需要获取时间、IO 中断、读取未定义的内存，这是需要提供额外的信息实现同步。另一个是创建 Backup 的问题，当两台机器的其中一台宕机时，这是只有一台机器在工作，这时你不许创建一台新的机器，这里还是不可避免的需要复制大量的内存和寄存器的信息。

关于论文中讨论的还存在一个问题，我们可以发现论文中讨论的都是状态机复制，并且只涉及单核心，目前还不确定 VMware 是如何将问题拓展到多核心上的。在多核心上处理指令的顺序是更加不明确的，VMware 在之后推出了新的不同的系统，并且可以在多核上工作，这些系统在我（教授）看来都是直接复制的而非状态机复制。

一个非常有趣的点，我想说 VMware 和我们前面讲到的 MapReduce 以及 GFS 都不一样。MapReduce 在实现重复计算或者 GFS 在实现拷贝副本时，它们的工作都是应用程序层面的，也就是说它们工作在 OS 之上。而 VMware 不同，它对机器指令进行复制，它实际并不知道上次的软件具体做了什么，你可以使用 VMware FT 管理任何软件，只要它可以运行在 VMware 支持的微处理器上。VMware FT 实际上为任何软件提供了容错的魔法棒。

VMware FT 是如何工作的？

首先 VMware 是一家虚拟机公司，它们的主要业务是售卖虚拟机技术。它们的虚拟机基本结构是这样的：首先需要有 VMM（Virtual Machine Monitor，论文中为 Hypervisor）工作在实体机器之上，在 VMM 上工作有 OS，然后 OS 上运行了各种应用程序。对于 VMware FT 而言工作在同一台机器上毫无意义，因为容错的一方面就是要解决机器故障的问题。因此这里有 Primer 和 Backup 两台机器， 同时还有外部的 Client，当然论文中还提到 Primer 和 Backup 共享磁盘，我们称之为 Disk Server。

当 Client 发送网络数据包时，Primer 的 VMM 会将请求送到应用程序。然后，Primer 会将具体执行的指令或许一些附加信息发送给 Backup，Backup 会执行这些指令，因此两台机器同步了它们的状态。这条通道具有一个术语 Log Channel，而这里发送的每一条指令称作 Log Entry。然后两台机器内部的应用程序将给出相同的输出，这个输出会在 Primer 中穿透 VMM 到达 Client，而在 Backup 中 VMM 会抑制它的输出。

Log Entry 发送的速度非常快，Backup 会通过这种方式检测 Primer 是否仍然存活。如果超过一定的时间 Backup 没有从 Log Channel 获取到任何指令或者没有收到心跳，它会认为 Primer 挂了，Backup 会开始托管 Primer 的工作。Backup 首先会在网络中进行一些处理，让所有 Client 认为它是 Primer，因此它将接收到来自 Client 的请求，不过我并不清楚这里的网络是如何处理的。同时 Backup 的 VMM 不再抑制其输出，它实际上成为了 Primer，它将开始筹备复制一台它的 Backup。

当然同样的，Primer 也应该具有类似的机制，它需要检测 Backup 的异常。当 Primer 认为 Backup 宕机时，它不再向 Backup 发送 Log Entry，然后需要启动一台新的 Backup。

非确定性事件 (Non-determined Event)

前面讲到，我们需要处理的一个问题就是非确定性事件（Non-determined Event），例如时间、IO 中断、读取未定义的内存这些都是非确定的。两机可能因为执行时间的先后，中断发送的位置不同等产生分歧。

像时间依赖和随机数的指令处理起来相对简单，对于这类特殊指令它会直接将结果发送到 Backup 上（在论文中提到是通过附加额外信息而未表示是执行结果，但也只是简单提到，论文 1 页右栏 8 行），这类指令是极少的并且被这样特殊处理。对于未定义行为，我们同样通过附加额外信息从而做到确定性。

另一问题，多核并行也有可能导致非确定性。我们前面讲到，VMware FT 这篇论文讨论的所有话题都局限于单核心，它无法解决这个问题。目前还不确定 VMware 是如何将问题拓展到多核心上的。在多核心上处理指令的顺序是更加不明确的，VMware 在之后推出了新的不同的系统，并且可以在多核上工作，这些系统在我（教授）看来都是直接复制的而非状态机复制。

最复杂的问题就是中断。当网络数据包到达的时候，网卡会通过 DMA 的方式将网络数据拷贝到关联的计算机内存中，这时很有可能一些运行在物理机器上的操作系统会将数据拷贝到虚拟机中，这样我们就失去了对 Primer 的时序控制。我们将关联的内存设置在 VMM 中，这时网络数据会首先来到 VMM，然后由 VMM 控制拷贝到 Primer 中，最后发送一个网络中断。同时 VMM 将网络数据包发送到 Backup，最后在相同的指令序号发送网络中断。这就是论文中提到的 Bounce Buffer 机制。

输出控制 (Output Rule)

前面我们讲到，Primer 和 Backup 总是保持相同的输出，然而 Primer 的输出将穿透 VMM，Backup 的输出将被抑制。但这并不是输出控制的全部，我们还需要考虑容错的问题。

假设这样一个场景，Primer 完成一个输出，例如告诉 Client 现在的时间，然后立即崩溃了；它会向 Backup 发送数据包，但网络是不可靠的，这个数据包同时丢失了。此时 Backup 会开始接替 Primer，但它从更早的位置开始，它不知道 Primer 告知 Client 的时间是多少，于是它响应了自己当前的时间，当然这个响应很可能因为重复被过滤。这时如果 Client 再次询问刚才那个时间进行一种复杂运算的结果是什么，这时它可能发现这个运算结果显然不是从前面的时间得到的，更糟糕的是 Client 可能并不会发现这个问题而导致更加严重的系统故障。

因此正确的做法是，对于需要输出的指令，Primer 执行后不会立即回复，而是发送一条提示 Backup 回复的指令，然后等待 Backup 回复。当 Backup 执行这条指令时会回复 Primer，Primer 收到回复后才会进行输出。这样 Primer 和 Backup 就做到了输出时的同步，当然这也提醒我们两机时差太大可能产生较大的延迟。当然，此时 Primer 并未完全停止，等待过程它可以进行一些并发操作。

教授解释进行输出控制的原因是可能发生包丢失，然后此时 Backup 接替工作就无法获取这些数据包，这里就不再展开教授的举例。然而论文认为进行输出控制的原因是非确定性事件（论文 3 页左栏倒数 7 行）。论文提到外围设施会解决包丢失的问题，因此 Backup 只会丢失 Primer 附加的信息，也就是决定非确定性事件的关键因素（论文 4 页左栏 8 行）。

Primer 和 Backup 只需在输出时同步，这是因为 Primer 如果在输出前崩溃，那么它与 Backup 可能在更早的指令序号因为非确定性事件出现分歧，但这个指令序号不会早于上一次输出。Primer 事实上与 Backup 出现了分歧，但因为 Primer 此时并未向 Client 输出，Client 拿到这个分歧的任意一个版本并且继续执行都是正确的（论文 3 页左栏 Output Requirement 及下面一段）。教授没有解释这个问题，我认为他的解释无法解释这个问题，因此我认为他是错的。

重复输出

一种需要讨论的情况是，在主从切换时，出现了重复输出。例如 Primer 在输出控制后实际向 Client 发送了响应，而这时 Primer 立即奔溃了；这时 Backup 认为 Primer 可能在向其发送最近一条指令后立即奔溃了，也可能收到了 Backup 的输出控制回复并完成了输出。Backup 无法与 Primer 确认这点，因此它会选择重复输出。

有趣的是，输出控制这个问题无需被 VMware FT 处理，网络协议例如 TCP 具备处理这些问题的能力。Primer 和 Backup 虚拟机具有完全相同的物理状态，它们具有相同的 TCP 序列号，当然 IP 和 MAC 地址也是相同的。TCP 协议在收到相同序列号的数据包时会丢弃它，因此在用户层永远看不到它。

这里可以认为是异常的场景，并且被意外的解决了。事实上，所有系统都存在这样的问题，它们无法避免包重复的问题，因此所有的系统都需要重复检测机制，这里我们使用 TCP 解决了这个问题。另一种思路是都不输出，这意味着 Client 不会收到响应而进行重试，这可能是一种糟糕的思路。

脑裂 (Split Brain)

最后一个问题，对于所有不存在 master 的系统都必须考虑脑裂。脑裂是指 Primer 和 Backup 之间可能失去网络连接了，但是它们都可以与 Client 连接，于是它们都会向 Client 输出。

VMware FT 使用了 Test-and-Set 服务。前面提到两机使用了共享磁盘，在这个共享磁盘上有一个标志位用于 Test-and-Set。当任意一台机器需要进行主从切换时，都会检查这个标志位。如果这个标志位已经置位说明另一台机器现在是 Primer，如果未置位则置位并升级为 Primer，这种方法类似于两机在竞争分布式锁。当然，最糟糕的情况是这个共享磁盘如果失联了，那两机都必须等待，无法进行任何操作。

总的来说，Test and Set 看起来像是个单点故障。虽然 VMware FT 尝试构建一个复制的容错系统，但是最后，主从切换还是依赖于 Test and Set 服务，这有点让人失望。我强烈的认为，Test and Set 服务本身也是个复制的服务，并且是容错的。几乎可以肯定的是，VMware 非常乐意向你售卖价值百万的高可用存储系统，系统内使用大量的复制服务。因为这里用到了 Test and Set服务，我猜它也是复制的。