VMware FT

Replication

复制能够处理单台计算机的fail-stop故障；复制不能处理软件中的bug和硬件设计中的缺陷 ps: 当计算机任何地方出现故障时，就停止运行，而不是运算出错误结果。对于复制的限制有：如果有两个副本（primary和backup），我们总是假设两个副本中的错误是相互独立的，否则错误有关联，则复制对我们没有帮助。

State transfer and replicated state machine

状态转移：主机(primary)将自己所有的状态拷贝并发送给备份机(backup)，一般是增量备份

复制状态机（VMware FT使用的方法）：将备份机视为一个确定的状态机——client发送操作到主机，主机按顺序发送到备份机，所有备份机执行所有的操作，如果从同一起始状态，以相同的顺序输入相同的操作，它们的输出将是相同的（互为副本，并一直保持一致）

PS：状态转移传输的是可能是内存，而复制状态机会将来自客户端的操作或者其他外部事件，从Primary传输到Backup。人们倾向于使用复制状态机的原因是，通常来说，外部操作或事件通常比服务的内存状态要小。例如，如果是一个数据库，它的内存状态可能达到 GB 级别。 复制状态机的缺点：它会更复杂一些，并且对于计算机的运行做了更多的假设

VMware FT论文讨论的都是复制状态机，并且只涉及了单核CPU，目前还不确定论文中的方案如何扩展到多核处理器的机器中。在多核的机器中，两个核交互处理指令的行为是不确定的，所以就算Primary和Backup执行相同的指令，在多核的机器中，它们也不一定产生相同的结果。 面对多核和并行计算，状态转移更加健壮。因此VMware之后推出的可在多核处理器上工作的复制系统是使用了状态转移（但是多核方案的代价更高一些）。

这些方法有什么问题？

学生提问：如果这里的方法出现了问题，导致Primary和Backup并不完全一样，会有什么问题？

Robert教授：假设我们对GFS的Master节点做了多副本，其中的Primary对Chunk服务器1分发了一个租约。但是因为我们这里可能会出现多副本不一致，所以Backup并没有向任何人发出租约，它甚至都不知道任何人请求了租约，现在Primary认为Chunk服务器1对于某些Chunk有租约，而Backup不这么认为。当Primary挂了，Backup接手，Chunk服务器1会认为它对某些Chunk有租约，而当前的Primary（也就是之前的Backup）却不这么认为。当前的Primary会将租约分发给其他的Chunk服务器。现在我们就有两个Chunk服务器有着相同的租约。这只是一个非常现实的例子，基于不同的副本不一致，你可以构造出任何坏的场景和任何服务器运算出错误结果的情形。我之后会介绍VMware的方案是如何避免这一点的。

学生提问：随机操作在复制状态机会怎么处理？

Robert教授：我待会会再说这个问题，但是这是个好问题。只有当没有外部的事件时，Primary和Backup都执行相同的指令，得到相同的结果，复制状态机才有意义。对于ADD这样的指令来说，这是正确的。如果寄存器和内存都是相同的，那么两个副本执行一条ADD指令，这条指令有相同的输入，也必然会有相同的输出。但是，如你指出的一样，有一些指令，或许是获取当前的时间，因为执行时间的略微不同，会产生不同的结果。又或者是获取当前CPU的唯一ID和序列号，也会产生不同的结果。对于这一类问题的统一答案是，Primary会执行这些指令，并将结果发送给Backup。Backup不会执行这些指令，而是在应该执行指令的地方，等着Primary告诉它，正确的答案是什么，并将监听到的答案返回给软件。

复制状态机的挑战（担心的问题）

  • 我们要复制哪些状态？
    • VMWare FT会复制机器的完整状态，包括所有的内存，所有的机器。（一种非常详细的复制方案）primary和backup在最底层也是完全一样的。总的来说，大部分复制方案都跟GFS(应用程序级别的状态复制，这更高效)更像。这种类型的复制方案是非常少见的。
    • VMware FT的独特之处在于，它从机器级别实现复制，因此它不关心你在机器上运行什么样的软件，它就是复制底层的寄存器和内存。你可以在VMware FT管理的机器上运行任何软件，只要你的软件可以运行在VMware FT支持的微处理器上。
      • 优点：可以将现有的软件甚至不需要这些软件的源代码，也不需要理解这些软件是如何运行的，在某些限制条件下，可以将这些软件运行在VMware FT的这套方案上。
      • 缺点：没那么高效
  • primary必须等待Backup机备份完吗？
  • 什么时候切换到Backup？
  • 切换时能否看到异常情况？
  • 如果有个副本故障了，我们需要重新添加一个新的副本，这可能是一个代价很高的行为，因为副本可能非常大，如何提升添加新副本的速度？

VMware FT工作原理

VMware FT需要两台物理服务器（分别运行一个虚拟机模拟器VMM，virtual machine monitor），primary与backup保持同步，虚拟机的虚拟磁盘在共享存储上。

所有的输入（如网络、鼠标、键盘等）都会输入到primary，然后通过Logging channel转发到backup，对于 非确定性的操作，还将发送额外的信息，以确保backup以 确定性的方式执行这些操作。 PS：两台虚拟机都会执行输入操作，但是只有primary的输出返回客户端，backup的输出会被管理程序丢弃。 （从primary发送到backup的事件被称为 Log channel上的Log Event/Entry）

更具体的基本工作流程是：假设两个虚拟机：primary和backup（互为副本）。client向primary发送一个请求，请求以网络数据包的形式（这里会产生一个中断，之后这个中断发送到了VMM。VMM发现这是发给多副本服务的一个输入，VMM做两件事：1）在虚拟机的guest操作系统中，模拟网络数据包到达的中断，将相应的数据送给应用程序的primary副本；2）VMM将网络数据包拷贝一份，通过网络送给backup虚拟机所在的VMM）

backup VM所在的VMM直到这是发送给个backup VM的网络数据包，它也会在backup VM中模拟网络数据包到达的终端，以将数据发送给应用程序backup。现在primary和backup都有这个网络数据包，他们都有相同的输入，再加上许多细节，都将会以相同的方式处理这个输入，并保持同步。

当Primary因为故障停止运行时，FT（Fault-Tolerance）就开始工作了。从Backup的角度来说，它将不再收到来自于Log Channel上的Log条目。实际中，Backup每秒可以收到很多条Log，其中一个来源就是来自于Primary的定时器中断。每个Primary的定时器中断都会生成一条Log条目并发送给Backup，这些定时器中断每秒大概会有100次。所以，如果Primary虚机还在运行，Backup必然可以期望从Log Channel收到很多消息。如果Primary虚机停止运行了，那么Backup的VMM就会说：天，我都有1秒没有从Log Channel收到任何消息了，Primary一定是挂了或者出什么问题了。当Backup不再从Primary收到消息，VMware FT论文的描述是，Backup虚机会上线（Go Alive）。这意味着，Backup不会再等待来自于Primary的Log Channel的事件，Backup的VMM会让Backup自由执行，而不是受来自于Primary的事件驱动。Backup的VMM会在网络中做一些处理（猜测是发GARP），让后续的客户端请求发往Backup虚机，而不是Primary虚机。同时，Backup的VMM不再会丢弃Backup虚机的输出。当然，它现在已经不再是Backup，而是Primary。所以现在，左边的虚机直接接收输入，直接产生输出。到此为止，Backup虚机接管了服务。

学生提问：Backup怎么让其他客户端向自己发送请求？

Robert教授：魔法。。。取决于是哪种网络技术。从论文中看，一种可能是，所有这些都运行在以太网上。每个以太网的物理计算机，或者说网卡有一个48bit的唯一ID（MAC地址）。下面这些都是我（Robert教授）编的。每个虚拟机也有一个唯一的MAC地址，当Backup虚机接手时，它会宣称它有Primary的MAC地址，并向外通告说，我是那个MAC地址的主人。这样，以太网上的其他人就会向它发送网络数据包。不过这只是我（Robert教授）的解读。

学生提问：随机数生成器这种操作怎么在Primary和Backup做同步？

Robert教授：VMware FT的设计者认为他们找到了所有类似的操作，对于每一个操作，Primary执行随机数生成，或者某个时间点生成的中断（依赖于执行时间点的中断）。而Backup虚机不会执行这些操作，Backup的VMM会探测这些指令，拦截并且不执行它们。VMM会让Backup虚机等待来自Log Channel的有关这些指令的指示，比如随机数生成器这样的指令，之后VMM会将Primary生成的随机数发送给Backup。

论文有暗示说他们让Intel向处理器加了一些特性来支持这里的操作，但是论文没有具体说是什么特性。

Non-Deterministic Events

不由当前内存直接决定的指令，在primary和backup的运行结果可能不一样，这些指令即为 非确定性事件。

非确定性事件分为：

  • 客户端输入。当说输入的时候，实际上是指接受到一个网络数据包（包含两部分：数据、提示数据包送达的中断）。对于primary和backup来说，中断在什么时候，具体在指令流的哪个位置触发？如果执行过程是不一样的，会导致他们的状态不一致。因此，我们关心网络数据包的内容与中断的时间。

  • 有一些指令在不同计算机上的行为是不一样的，这一类指令成为 怪异指令，如1）随机数生成器；2）获取当前事件的指令，在不同时间调用会得到不同的结果；3）获取计算机的唯一ID。

  • 多CPU的并发（VMware FT论文中没有讨论的）

    之所以多核会导致非确定性事件，是因为当服务运行在多CPU上时，指令在不同的CPU上会交织在一起运行，进而产生的指令顺序是不可预期的。所以如果我们在Backup上运行相同的代码，并且代码并行运行在多核CPU上，硬件会使得指令以不同（于Primary）的方式交织在一起，而这会引起不同的运行结果。假设两个核同时向同一份数据请求锁，在Primary上，核1得到了锁；在Backup上，由于细微的时间差别核2得到了锁，那么执行结果极有可能完全不一样，这里其实说的就是（在两个副本上）不同的线程获得了锁。所以，多核是一个巨大的非确定性事件来源

学生提问：如何确保VMware FT管理的服务只使用单核？

Robert教授：服务不能使用多核并行计算。硬件几乎可以肯定是多核并行的，但是这些硬件在VMM之下。在这篇论文中，VMM暴露给运行了Primary和Backup虚机操作系统的硬件是单核的。我猜他们也没有一种简单的方法可以将这里的内容应用到一个多核的虚拟机中。

日志条目的三样东西（论文中没有描述，Robert教授猜测）：

  • 事件发生时的指令序号。因为如果要同步中断或者客户端输入数据，最好是Primary和Backup在相同的指令位置看到数据，所以我们需要知道指令序号。这里的指令号是自机器启动以来指令的相对序号，而不是指令在内存中的地址。比如说，我们正在执行第40亿零79条指令。所以日志条目需要有指令序号。对于中断和输入来说，指令序号就是指令或者中断在Primary中执行的位置。对于怪异的指令（Weird instructions），比如说获取当前的时间来说，这个序号就是获取时间这条指令执行的序号。这样，Backup虚机就知道在哪个指令位置让相应的事件发生。
  • 日志条目的类型，可能是普通的网络数据输入，也可能是怪异指令。
  • 最后是数据。如果是一个网络数据包，那么数据就是网络数据包的内容。如果是一个怪异指令，数据将会是这些怪异指令在Primary上执行的结果。这样Backup虚机就可以伪造指令，并提供与Primary相同的结果

Output Rule

Duplicated Output

Test-and-Set Service

References