这节课看 VMWare 的一篇文章，讲的是如何给用户提供可靠的虚拟机。采用的方式是主备切换。

我们讨论的主题仍然是容错，通过复制的手段提供可靠性，在服务器或者网络可能出错的情况下。

我们考虑的错误

错误有很多种：

  • fail-stop 错误，很多论文都会出现这个关键词，它的含义是，只要出错了，机器就停止运转，而不是继续产生错误结果，比如， CPU 过热、断网断电等；
  • 逻辑错误、配置错误、恶意软件这类可能不是 fail-stop 的错误；
  • 其他可能发生的极端情况，如地震。

我们考虑的错误是 fail-stop 这类。

容错有一些挑战：

  • 主服务真的失效了吗？如果只是短暂的网络丢包，备份错误上台，可能会有脑裂问题；
  • 主备同步。怎样确保主备之间的状态是同步、一致的？应该按顺序应用变化，同时考虑不确定性的处理办法；
  • fail over，即主服务失效备份上台时，怎样确保安全过渡。

实现主备同步

为了实现主备同步，有两种方式，想想也比较自然。

  1. 把主服务的状态完整复制给备份，类似于 GFS 里定期保存的快照；
  2. 采用复制状态机 (Replicated State Machine) 的方式，不传送状态，而是传送使得状态改变的动作。

完整传送状态的方式，可能因为状态的体积太大，导致通过网络传递的速度很慢，那么，状态机的方式看上去更加自然。

观察一个机器从状态 A 变成状态 B，可能内存、CPU 等各个组件都大变样，完全没有头绪实现增量更新。但是，所谓「牵一发而动全身」，只需要把重点放在引入变化的动作就好了！

这是一个思维上的转变！我们现在把机器当作黑盒子，不考虑怎样把黑盒子里面的状态复制一份，而是考虑对另一个初始化的黑盒子施加相同的一串动作。前提是，动作是确定性的。

当然了，完整复制状态并不是一无是处。如果能获得一份检查点状态作为初始状态，可以加快初始化的速度，毕竟执行指令还是要花很多时间的，而且确定性很难保证。

顺带一提，实现操作的复制，有两种级别：

  1. 高层是应用级别，就像 GFS 那样，需要持久化的操作必须写入日志，这是在应用级别进行维护的，转发的是高级操作，例如新文件创建；
  2. 底层是机器级别，寄存器、内存等，hypervisor 可以捕获虚拟机的所有外部交互，对应用程序透明，转发的是底层操作，例如中断信号。

今天的论文聚焦后者。

论文

总览

仿照讲义的框架图

总的来说，这篇论文给我的初次印象是，读起来并不是很复杂——没有涉及大量的工程取舍，也没有很艰深的启发式算法。大概做的内容是在现有的虚拟机软件上做一些小修改。

我们工作的重点是 VM FT，也就是 hypervisor。操作系统和应用软件是虚拟机中的所谓客户。在主备两个机器之间，主机器需要把所有必要的事件发给备份，这之间的逻辑通道是 logging channel。一般来讲，备份的输出被 FT 抑制，毕竟只有主机器需要响应客户请求。

如果主备有一个挂掉了，活着的那个会开启 live 模式，我管它叫直播模式，也就是不必再发送日志给后备了。

这个日志通道很有意思，有点像 Go 的 channel，毕竟我是先学的 Go，再学的这篇论文，所以形成了这个类比。后面还会仔细展开，主备是如何通过通道实现同步的，很巧妙。

分歧

为什么主机器必须给后备机器发信息呢？因为并不是所有操作都是确定性的，当分歧发生的时候，就需要记录主机器的当前状态和操作，发送给后备机器。

绝大多数的指令是确定性的，比如算数运算，这也是这篇工作成功的基础，如果所有操作都要同步，那流量可太大了。只有小部分需要同步，这个开销可以接受。

具体来说，需要考虑的分歧有：

  • 外部世界的输入，比如网络包；
  • 时钟中断；
  • 不是 $f(状态)$ 的指令，换句话说，不由当前状态确定取值的指令，比如获取时间；

PS：不考虑多核。

其实这篇文章加深了在操作系统课程中对计算机的建模。如果一个计算机无法接收外部中断，那它的状态建模很简单，确定性的状态机。而且不能和外部交互，一条路走到黑，批处理嘛，没啥用。

外部中断让我们可以和计算机交互的同时，也引入了不确定性。计算机不知道我们什么时候按下键盘，所以必须引入一个接口，嗯，键盘这个外设和计算机也通过某种接口交互嘛！

扯远了，总而言之，计算机要和外部交互，引入了中断，也引入了不确定性，FT 必须处理这个不确定性。

凭什么？因为不确定性会引入很大的问题。讲义以 GFS 为例：

  1. 假如我们复制的是 GFS 的 master；
  2. Primary chunkserver 在 60s 的租约过期之前，给 master 发送了一条续约请求；
  3. 在主服务器上，意味着租约已发放 60s 的时钟中断在请求到达后发生，那么，master 认为租约在期限内，同意续约；
  4. 在后备服务器上，可能由于传播时延，请求在时钟中断后才发生，后备服务器会选择不续约，准备选一个新的 primary；
  5. 此时主备状态已经不一致了，如果主服务器挂掉，后备服务器上来，会选择新的 primary，那么就有 2 个 primary，导致脑裂。

注意喔，应用程序的代码完全没有问题，而是底层基础设施坏掉了！所以最难排查的 BUG 是什么？是你信赖的底层服务没有按预期运行。

为了避免上述情况，在发送日志的时候，必须保证日志按顺序到达后备服务器，而且在相同时间点运行。每个日志包含指令编号，类型，数据。

输入的例子

FT 处理时钟中断，目标是在指令执行流中，主备的中断在同一个位置发生。

主 FT 从硬件侧捕获时钟中断，暂停操作系统，从 CPU 读取执行的指令数量，通过日志通道发送一份「在指令 X 发生时钟中断」的消息，随后把时钟中断给操作系统并恢复操作系统运行。

后备 FT 需要忽略自身硬件的时钟中断，而且需要保证在执行到 X 号指令前就看到日志，接收到日志后告知 CPU 在指令 X 时中断，随后模拟一个时钟中断给操作系统。

总而言之，确保时钟中断在相同的指令位置发生。

FT 处理网络包到达，需要启动一个额外的区域用来存储数据。

主 FT 让网卡把数据通过 DMA 发送给它，随后，FT 暂停 OS，把数据拷贝到 OS 内存中，模拟一个网卡中断给 OS，并通过日志把数据发送给后备。

后备 FT 通过日志获得数据和指令号，告诉 CPU 在 X 号指令中断，随后把数据拷贝到后备的内存中，并模拟网卡中断。

之所以要有一个额外的存储区，是因为，不能直接就把数据传给主 OS，否则后备 OS 怎么获得这份数据呢？

处理不确定的指令，比如获取当前时间，主 FT 需要把主服务器的运行结果复制给后备服务器，狸猫换太子。

上面的具体例子，讲义讲的比原文细节得多，可能有一些教授自行蔓延出去的部分。总而言之，我们发现 FT 需要有两个 The World 时停技能，一方面是让 CPU 停在某个指令编号，另一方面是让 OS 暂停，从而自己能够进行一些内存修改等。

在 hypervisor 的角度，操作系统也是一个完全受控的对象。就好像应用程序在操作系统的角度来看完全受控一样。此一时彼一时啊！

最后做个总结，注意到后备总是比主服务器慢了一条消息。假如主服务器执行到 X 指令，有了一个不确定的动作，此时如果后备已经过了 X，那就于事无补了。

那么，总体的执行流程是，在第一条消息发出之前，后备服务器阻塞。第一条消息发出，执行到第一条消息指定的指令位置，继续阻塞。语义是，在这条指令之前都可以“安全”执行，但是此后的任何时刻都可能中断，无法确定。

这有点类似于 Go 的通道，如果接收方在通道一端没有内容可读，会保持阻塞。

安全输出

输出和输入截然不同，就像是读和写截然不同一样。这里的不同，不只是字面意思，而是整个处理逻辑完全不同。

我们还是从黑盒的角度出发，有点像薛定谔的猫。如果主备两个黑盒子不输出，我们可以假定它们完全一样。但要是输出了，哈哈，黑盒子就部分可观测了，到底是不是一样就可以判断出来。

什么意思？就是，必须在输出时，确保主备达到一致的状态，防止外界接收到错误的内容。

讲义用了一个数据库的例子。本来某个字段的值是 10，现在客户端要修改它为 11。正常执行流就不说了，看看异常可能在哪里。

当主服务器接收到客户端的请求后，开始执行，并把结果返回给客户端，一边把日志传给后备，一边崩溃。好了，现在后备没有接收到输出的日志。

因为主服务器已经死了，后备服务器要 go live，重放到它接收到的最后一条日志，而我们在意的字段的值还是 10。客户端下次再发送自增命令，得到的是 11，而不是 12。

解决的办法是输出规则，在主服务器发送任何输出之前，必须等待后备即诶搜到了所有过去的日志，也就是人为的同步，当然了，主服务器还可以继续执行，只是这个输出被暂时放在缓存区中。换句话说，不能让用户察觉。

这样可以解决问题吗？还是上述情景，分类讨论：

  • 如果主服务器在崩溃前没有接收到后备的 ACK，那客户端没接收到输出，可能会在未来重试（TCP 当作丢包？）；
  • 如果主服务器崩溃前接收到了 ACK，请求被发送给客户端，客户端 go live 后会重放，这条记录可能在 go live 前被处理，那输出会被 FT 抑制，如果在 go live 后，那只是重复的包，TCP 会处理的。

输出规则是一个很重要的事情，在各种各样多副本的系统中都以某种形式出现。比如下节课要学到的 Raft，leader 什么时候才能提交一个 entry？本任期的 entry 被大多数 follower 记录！

性能对比

实验场景

论文里的 Table 2 可以展开聊聊。

Table 2

为什么 Receive 和 Transmit 的 FT 带宽不对等？因为接收到一个包，按照前文的分析，需要把数据通过日志通道传递给后备。而发送一个包，只需要把输出指令发送给后备并等待 ACK。

前两行对比，FT Receive 带宽更小，因为每接收到一个包，需要

  1. 数据通过日志发给后备；
  2. 等待其 ACK 到达，随后给客户端返回 TCP ACK，之后客户端才能发下一块数据。

而 FT Transmit 需要：

  1. 把指令发给后备，没有数据；
  2. 等待其 ACK 到达，给客户端发送数据。

第二步都是一样的，只有第一步的差别。这就是为什么 Receive 的日志带宽高得多，这带来的时延减小了接收带宽。

后两行的对比类似，不必赘述。对比一下 1、3 行，第 3 行日志的带宽更高，意味着数据传输更快，后备 ACK 返回的时延更低，因而同步带来的时延更小，从而吞吐率更高。

如果从更高的视角来看，本质上还是因为同步带来的等待时延，这和条件变量、信号量什么的没什么区别。