The Design of a Parctical System
阅读论文后，请回答问题：VM-FT如何应对网络分区，是否会出现primary和backup都以为自己是主的情况？
这篇论文主要讲述了 VMware 公司如何利用一种协议来实现两个虚拟机之间的主从备份（Primary-Backup Replication）
背景
为实现可容错的服务器，主从备份是一种常用的解决方案：在开启了主动备份的系统中，备份服务器的状态需要在几乎任何时候都与主服务器保持一致，这样当主服务器失效后备份服务器才能立刻接管。实现主备间的状态同步主要包括以下两种方式：
- State Transfer（状态转移）：主服务器将状态的所有变化都传输给备份服务器。这样的方案会较为简单，但需传输的数据量较大
- Replicated State Machine（备份状态机）：将需要备份的服务器视为一个确定性状态机 —— 主备以相同的状态启动，导入相同的输入，最后它们就会进入相同的状态、给出相同的输出。这样的方案较为复杂，但需要传输的数据量会小很多
VMware 选用了状态机方法，因为对于虚拟机而言，其状态过于复杂，使用状态转移方法也不会简单多少。在虚拟机上应用备份状态机方法也会有一定的顾虑 —— 我们难以保证在虚拟机上运行的应用（即操作系统）是确定性的。实际上，在物理机上应用状态机方法是极其困难的，其所能接收到的输入很多都是不确定的（如定时器中断等），但虚拟机是运行在 Hypervisor（虚拟机管理程序）之上的抽象机器，通过 Hypervisor 这一隔离层便能很好地将非确定性的输入转变为确定性的输入。
Deterministic Replay
尽管目标很直白，但考虑到虚拟机的很多输入事件本身是不确定的，如时钟中断、网络中断和磁盘中断，这会为在虚拟机上实现状态机方法带来第一个挑战。这个问题可以被细分为三个问题：
- 正确地捕获所有的输入事件以及它们的不确定性，以确保有足够地信息能够确定性地重放这些事件
- 正确地在备份虚拟机上重放这些输入事件和不确定性
- 保证性能不会因此降级
VMware 实现的主从备份方法名为 VMware vSphere Fault Tolerance，简称 VMware FT，它是基于 VMware Deterministic Replay 实现的。Deterministic Replay 解决了上面的前两个问题，而第三个问题则会由 VMware FT 来解决。
Deterministic Replay 会以日志记录的形式记录主服务器接收到的输入，这些日志信息则会由 VMware FT 传输到备份服务器并被重放。正如上面所提到的那样，真正的麻烦实际上来源于那些会产生不确定作用的输入。对于那些不确定的输入操作，Deterministic Replay 会记录足够多的信息，确保其在备份虚拟机上重新执行能够得到相同的状态和输出；而对于那些不确定的输入事件，如定时器、IO 操作完成中断等，Deterministic Replay 则会记录这些事件发生在哪个指令之后，这样在重放时备份服务器便能在指令流中相同的位置重放这些事件。
FT（Fault-Tolerance）协议
FT 协议是应用于 logging channel 的协议，协议的基本要求为：
如果 Primary 宕机了，Backup 接替它的工作，Backup 之后向外界发出所有的 Output 要和 Primary 原本应当发送的一致。
为了保证以上的要求，设计如下系统：
image.png
如图所示，整个架构由一主一备组成，两个虚拟机运行在两个不同的物理机上，通过一个 Logging Channel 传输 Deterministic Replay 产生的日志信息，同时两个虚拟机都能访问一个 Shared Disk。
为了实现这个核心要求，最简单的解决方案就是延迟主虚拟机的输出操作，直到备份虚拟机已经接收到所有至少足以让它重放至该输出操作的所有日志信息。要做到这一点，简单地确保备份虚拟机已接收到该输出操作之前的所有日志信息是不够的，因为如果主虚拟机在完成输出操作后立刻失效的话，备份虚拟机在重放该输出操作前仍可能出现其他不确定的事件（如计时中断）导致备份虚拟机进入其它执行路径。
Primary会在所有关于本次Output 的所有信息都发送给 Backup 之后（并且要确保 Backup 收到）才会把 output 发送给外界
Primary 只是推迟将 output 发送给外界，而不会暂停执行后边的任务
流程如图所示：
image.png
由于 VMware FT 在处理与输出操作相关的日志时没有采用二阶段提交机制，VMware FT 并不保证输出是 Exactly Once 的。所幸的是，网络基础服务（如 TCP）通常能很好地处理重复的包，对磁盘同一位置的重复写入往往也不会有什么问题。
主从切换
首先，VMware FT 会使用两种不同的方式来检测虚拟机节点的失效事件：
- 两个虚拟机所寄宿的物理机会相互之间发送 UDP 心跳信息，以判断对方是否仍存活
- 持续监控 Logging Channel 上的流量：由于周期定时中断的存在，主虚拟机发往备份虚拟机的日志和备份虚拟机发往主虚拟机的 ack 应该是持续不断的，信息中断即意味着节点的失效
如果备份虚拟机失效，主虚拟机就会 go live，即退出日志记录模式，不再产生和发送日志信息，并以普通的方式继续运行；如果主虚拟机失效，备份虚拟机就会在消费完 Logging Channel 中的所有日志信息后升级为主虚拟机并 go live，开始对外界发送输出。
然而上述两种方案无法避免架构在主从虚拟机间发生网络隔离时出现 Split-Brain Syndrome（裂脑综合征，指在连接大脑左右脑的胼胝体受损到一定的程度后发生的因左右脑冲突导致的症状，在分布式系统领域指一个集群中存在多个 Master 角色所带来的问题）：主从虚拟机间的网络不通会导致备份虚拟机误以为主虚拟机已经宕机而自动升级为主虚拟机，导致集群中存在两个主虚拟机。
为了解决这个问题，无论主备，虚拟机在 go live 前首先会对存储在 Shared Disk 上的一个字段进行原子的 test-and-set 操作：如果操作成功，那么它便可以 go live；否则就意味着已经有另一个虚拟机 go live，它便会立刻关闭自己（形如因自身失效而导致另一个虚拟机 go live）。
虚拟机恢复
为了确保架构的高可用，VMware FT 在发生虚拟机失效后会自动地在另一台宿主机上启动备份虚拟机。如此便涉及到了另一个问题：如何以与主虚拟机相同的状态启动一个虚拟机。论文只中提到 VMware FT 用了 VMware VMotion 的变种来实现该功能，并未详细描述这一过程。
除外，VMware vSphere 还实现了一个可以监控并管理集群资源的服务，可用于选取适合启动新虚拟机的宿主机。
Logging Channel
首先，VMware FT 的 Logging Channel 会在发送和接收端启用 Buffer 机制来减少网络传输对虚拟机执行速度的影响。主虚拟机会在 Buffer 满时暂停运行，而备份虚拟机则会在 Buffer 空时暂停运行。
由于 Buffer 的存在，在某一时刻上，备份虚拟机有可能落后于主虚拟机。这样的延迟必然存在，但不宜过大，源于 Buffer 中堆积的数据不仅可能导致主虚拟机时常暂停运行，还会延长主虚拟机失效后备份虚拟机消费完所有日志并 go live 的耗时。要保证 Buffer 中不会产生过多的日志堆积，必须确保备份虚拟机的性能大于等于主虚拟机。为此，VMware FT 会采集每一条日志从发送到 ack 之间的延时，并动态地通过 Hypervisor 调整主虚拟机的 CPU 频率，最终确保主虚拟机以与备份虚拟机相近的速度运行。
FAQ
Q: 为什么非常困难在物理服务器上来确保确定性的执行相比虚拟机？
确保确定性在VM上更容易，因为虚拟机管理程序会仿真和控制硬件的许多方面，这些方面在primary执行和back-up执行之间可能会有所不同，例如发送中断的准确时间。
Q: 什么是hypervisor（虚拟机管理程序）？
管理程序是虚拟机系统的一部分； 它与虚拟机监视器（VMM）相同。 系统管理程序模拟计算机和guest操作系统（和应用程序）在模拟计算机内部执行。 guest运行的仿真通常称为虚拟机。 在本文中，primary和backup是在虚拟机内部运行的guest虚拟机，而FT是实现每个虚拟机的管理程序的一部分。
Q：GFS 和 VMware FT 都提供了容错性。我们该怎么比较它们呢？
FT 备份的是计算，你能用它为任何已有的网络服务器提供容错性。FT 提供了相当严谨的一致性而且对客户端和服务器都是透明的。例如，你可以将 FT 应用于一个已有的邮件服务器并为其提供容错性。
相比之下，GFS 只为存储提供容错性。因为 GFS 只针对一种简单的服务提供容错性，它的备份策略会比 FT 更为高效：例如，GFS 不需要让所有的中断都以相同的顺序应用在所有的 Replica 上。GFS 通常只会被用作一个对外提供完整容错服务的系统的一部分：例如，VMware FT 本身也依赖了一个在主备虚拟机间共享的有容错性的存储服务，而你则可以用类似于 GFS 的东西来实现这个模块（虽然从细节上来讲 GFS 不太适用于 FT）。
Q 论文3.4 反射缓冲区如何避免race?
当网络数据包或请求的磁盘块到达主要节点并需要复制到主要节点的内存中时，就会出现问题。
如果没有FT，则相关硬件将在执行软件时将数据复制到内存中。来宾指令可以在DMA期间读取该内存；根据确切的时间安排，访客可能会看到或看不到DMA的数据（这是race）。如果主数据库和备份数据库都这样做，那将是很糟糕的，但是由于时间上的微小差异，其中一个仅在DMA之后读取，而另一个仅在DMA之后读取。在那种情况下，他们会分歧。
FT通过在执行主数据库或备份数据库时不将其复制到来宾内存中来避免此问题。 FT首先将网络数据包或磁盘块复制到主要节点无法访问的专用“反弹缓冲区”中。当第一个副本完成时，FT虚拟机管理程序会中断主数据库，使其不执行。 FT记录了它中断主节点的时间（与任何中断一样）。然后，FT将反射缓冲区复制到primary的内存中，然后让primary继续执行。 FT将数据发送到日志通道上的备份。备份的FT按照与主数据库被中断相同的指令中断备份，在执行备份时将数据复制到备份的内存中，然后恢复备份。
这样做的结果是，网络数据包或磁盘块在主数据库和备份数据库中完全同时出现，因此无论何时读取内存，它们都可以看到相同的数据。
Q: 如果应用调用一个随机数生成器， 是否主和backup会得到不同的结果？
主数据库和备用数据库将从其随机数生成器中获得相同的数字。 所有随机性源均由管理程序控制。 例如，应用程序可以使用当前时间，硬件周期计数器或精确的中断时间作为随机性来源。 在所有这三种情况下，系统管理程序都会在主数据库和备份数据库上拦截相关指令，并确保它们产生相同的值。
Q：如果主虚拟机在向外界进行输出后立刻就失效了会怎么样？
这个输出可能会执行两次：主虚拟机一次，备份虚拟机一次。对于网络和磁盘 IO 来说，这个重复不会产生任何问题。如果输出的是一个网络包，那么接收端的 TCP 栈会丢弃掉这个重复的包；如果是磁盘 IO，那么磁盘 IO 实际上是幂等的（两次操作会在同一个位置写入相同的数据，这之间也不会有其他的 IO）。
Q: 论文3.4 讨论了disk io在primary没有完成在失败发生时。我们会重发这个pending io 在back up go live的进程里。 问题是pending io 存在哪，重新发需要花多久？
论文里说了disk io 当有一个log记录了io开始不过没有一个log现实io 完成。这些io操作必须被重发在back up里。 当io完成，io设备会产生一个io完成的中断。 因此，如果io完成中断在log里没有找到， backup 会重发这个io. 反之，不重发。
Q：只去解决宕机失效的场景是合理的吗？还存在其他类型的失效吗？
这是合理的，因为现实世界中的多数失效本质上来讲都是宕机失效，例如各种网络失效和电源失效。要做到更好的话就需要处理那些似乎正在正常运行但其实正在产生错误结果的计算机 —— 在最坏的情况下，这样的失效可能是来源于一个恶意的攻击者。这类非宕机失效的失效通常被称为“拜占庭”（Byzantine）。我们实际上是有方法去应对拜占庭失效的，我们会在这节课的末尾学习这些方法，但 6.824 的主要内容还是关于宕机失效。
关于更多类型的失效，可参考《Failure Modes in Distributed Systems》 一文。
我的启发和思考
- 利用某些方法使得一些不确定的指令变得确定化，然后通过同步指令来使得主备之间一致。
- 可以使用一个共享的磁盘，一个test and set操作来避免脑裂的问题。
- udp 发送心跳，和监控channel上的流量来判定health状态。
- 为了使得在一方挂掉时，原先的行为也完全一致，特别是已经交互出去的消息。我们必须要记录一条特别的special log，要让这条special log被back up记录好后，才可发送，不然会没法保证记录发出时之前走的指令一致。
- buffer的作用可以减少网络的传输对虚拟机的影响，但必须保持发送者和消费者速率尽可能相当。还可以避免race。
- 巧妙的利用tcp 网络包主动去重，和写磁盘幂等特性。可以只用at least once语义来实现一致。
