分布式系统学习4
用了很长的时间来读《The Design of a Practical System for Fault-Tolerant Virtual Machines》（Fault-Tolerant Virtual Machines-VMware容错虚拟机设计）这篇论文，整体读下来感觉还是不求甚解，或许可能需要在实践的过程中多沉淀，才能有进一步的体会。
在前面我们关于MapReduce和GFS的学习中，我们都是默认通过复制这一手段来达成分布式系统的高可用目的，但我们都没涉及到复制的具体实现，GFS中或许涉及到了一点，但也只是略微提起，并不作为主要论述的点。而在今天这篇中就要详细探讨一下分布式系统中具体实现复制的技术之一：VMware容错虚拟机设计
一说到给服务器做备份的复制，我们的第一印象往往是“状态转移”，即把主服务器上的所有东西全都复制一份到备份服务器上，但如果仔细想想，这样做的代价简直高得离谱，你不可能通过使用移动硬盘来向备份服务器拷贝东西，你需要使用网络通信，而状态转移所需要的带宽似乎有点惊人。
还有一种复制方法是采用复制状态机。
我们先来说说状态机，我们都知道状态机（这里指确定状态机），对于状态机来说，如果两个确定性状态机以相同的初始状态启动，并以相同的顺序提供完全相同的输入，那么它们将经历相同的状态序列并产生相同的输出。
所以回到复制这里，我们就可以采用复制状态机的方式来进行复制操作，我们可以把主服务器和备份服务器建模为两台状态机，我们想复制的大部分的服务或者计算机软件都有一些确定的内部操作，不确定的部分是外部的输入。所以我们只需要给予主服务器和备份服务器以相同的输入，在没有外界影响的前提下，它们都会产生相同的输出，即一直保持相同的状态。通常来说，如果有两台计算机，如果它们从相同的状态开始，并且它们以相同的顺序，在相同的时间，看到了相同的输入，那么它们会一直互为副本，并且一直保持一致。
我们可以来对比一下状态转移和复制状态机，很显然，人们更倾向于使用复制状态机的原因是，通常来说，外部操作或者事件比整个服务的状态要小。如果是一个数据库的话，它的状态可能是整个数据库，可能到达GB这个级别，而操作只是一些客户端发起的请求，例如读磁盘上的一些数据。所以操作通常来说比较小，而状态通常比较大。所以复制状态机通常来说更吸引人一些。复制状态机的缺点是，它会更复杂一些，并且对于计算机的运行做了更多的假设。而状态转移就比较简单粗暴，我就是将我整个状态发送给你，你不需要再考虑别的东西。
很显然，如果计算机只是单纯按顺序执行确定的指令，那这种方案确实相对比较完美了，但很可惜在实际情况中会有很多非确定性的发生。在论文中，将它们归类为非确定性操作和非确定性事件。
非确定性事件
这类事件主要由外部输入或异步信号触发，其发生的时间和内容无法由虚拟机当前状态预测。
- 客户端输入：所有来自外部的输入，如网络数据包、鼠标和键盘操作。网络数据包何时到达、其内容是什么，均不取决于虚拟机内部状态。
- 硬件中断：例如虚拟中断、I/O完成中断。这些事件会异步地改变指令的执行路径。
- 磁盘I/O完成事件：磁盘操作可以是异步的，对同一磁盘位置的I/O操作顺序可能不确定，从而引发竞争
非确定性操作
这类操作通常由特定CPU指令执行，其输出结果不完全由输入和当前架构状态决定。
- 读取CPU时钟计数器：如
RDTSC指令，读取处理器的时间戳计数器。主备虚拟机在不同时间点执行，会得到不同的值。 - 随机数生成器：执行随机数生成指令，主备虚拟机会产生不同的随机序列。
- 获取当前时间：读取系统时间的指令，在不同时刻调用会返回不同结果。
- 获取计算机唯一ID：读取硬件标识符（如CPU ID、序列号）的指令，在不同物理机上执行可能返回不同值。
我们必须要采取措施来应对这些非确定性的因素，从而使得我们主服务器和备份服务器的状态保持一致。
如果在物理机上应对这些非确定性的因素是极其困难的，因为我们很难重放相同的操作。但如果主服务器和备份服务器都部署在虚拟化平台上，那解决问题就会变得相对容易。我们知道虚拟机上发生的大多数事情都可以被虚拟化软件监控，基于此，就可以在虚拟化平台上实现复制状态机方案的服务器主副备份。
我们先来看看在不发生非确定性事件的时候，要如何使用虚拟机来构建我们的容错系统
很多人接触虚拟机都是一台物理机上运行多个操作系统，但今天我们所讨论的显然是要将主服务器和备份服务器所在的虚拟机放在不同的物理机上，因为我们最开始采用复制的目的就是应对硬件故障，所以将Primary和Backup运行在一台服务器的两个虚拟机里面毫无意义。所以，你至少需要两个物理服务器运行VMM（VMM，Virtual Machine Monitor，一种虚拟机监控器），Primary虚机在其中一个物理服务器上，Backup在另一个物理服务器上。在其中一个物理服务器上，我们有一个虚拟机，这个物理服务器或许运行了很多虚拟机，但是我们只关心其中一个。这个虚拟机跑了某个操作系统，和一种服务器应用程序，或许是个数据库，或许是MapReduce master或者其他的，我们将之指定为Primary。在第二个物理服务器上，运行了相同的VMM，和一个相同的虚拟机作为Backup。它与Primary有着一样的操作系统。
所以现在我们有了运行在不同物理机上的两台虚拟机做主副备份，它们之间通过网络进行连接
然后有一些客户端来与服务器进行交互，具体的交互形式会在后面提到。需要注意的是，在VMware FT中是主副服务器和同一块虚拟硬盘进行交互，而不是各有硬盘。同时，其多副本服务没有使用本地盘，而是使用了一些Disk Server（远程盘）。这里可以将远程盘服务器也看做是一个外部收发数据包的源，与客户端的区别不大。
所以，基本的工作流程是，我们假设这两个副本，或者说这两个虚拟机：Primary和Backup，互为副本。某些我们服务的客户端，向Primary发送了一个请求，这个请求以网络数据包的形式发出。
这个网络数据包产生一个中断，之后这个中断送到了VMM。VMM可以发现这是一个发给我们的多副本服务的一个输入，所以这里VMM会做两件事情：
- 在虚拟机的guest操作系统中，模拟网络数据包到达的中断，以将相应的数据送给应用程序的Primary副本。
- 除此之外，因为这是一个多副本虚拟机的输入，VMM会将网络数据包拷贝一份，并通过网络送给Backup虚机所在的VMM。
Backup虚机所在的VMM知道这是发送给Backup虚机的网络数据包，它也会在Backup虚机中模拟网络数据包到达的中断，以将数据发送给应用程序的Backup。所以现在，Primary和Backup都有了这个网络数据包，它们有了相同的输入，再加上许多细节，它们将会以相同的方式处理这个输入，并保持同步。
当然，虚机内的服务会回复客户端的请求。在Primary虚机里面，服务会生成一个回复报文，并通过VMM在虚机内模拟的虚拟网卡发出。之后VMM可以看到这个报文，它会实际的将这个报文发送给客户端。
另一方面，由于Backup虚机运行了相同顺序的指令，它也会生成一个回复报文给客户端，并将这个报文通过它的VMM模拟出来的虚拟网卡发出。但是它的VMM知道这是Backup虚机，会丢弃这里的回复报文。所以这里，Primary和Backup都看见了相同的输入，但是只有Primary虚机实际生成了回复报文给客户端。
这里有一个术语，VMware FT论文中将Primary到Backup之间同步的数据流的通道称之为Log Channel。虽然都运行在一个网络上，但是这些从Primary发往Backup的事件被称为Log Channel上的Log Event/Entry。
当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虚机接管了服务。
关于日志通道，FT实现了一个日志缓冲区，当Primary执行时，它产生日志条目到日志缓冲区，然后备份虚拟机从日志缓冲区消耗这些日志条目。
上面都是不涉及到非确定性事件的情况，下面我们看看当发生非确定性事件时会发生什么，我们需要做哪些预案
由于一些指令在不同计算机上的行为是不一样的，会造成非确定性操作，在MIT6.824课程中，将这一类指令称为怪异指令，我们也沿用这个称呼。
为了解决非确定性事件和非确定性操作可能造成的不一致，VMware使用了“确定性重放”这一技术来解决这些不一致。
FT记录足够的信息以允许以相同的状态变化和输出来重现该操作，对于怪异指令，事件发生的确切指令也被记录下来。在重放过程中，该事件在指令流中的同一位置被传递。
举个例子，Primary和Backup两个虚机内部的guest操作系统需要在模拟的硬件里有一个定时器，能够每秒触发100次中断，这样操作系统才可以通过对这些中断进行计数来跟踪时间。因此，这里的定时器必须在Primary和Backup虚机的完全相同位置产生中断，否则这两个虚机不会以相同的顺序执行指令，进而可能会产生分歧。所以，在运行了Primary虚机的物理服务器上，有一个定时器，这个定时器会计时，生成定时器中断并发送给VMM。在适当的时候，VMM会停止Primary虚机的指令执行，并记下当前的指令序号，然后在指令序号的位置插入伪造的模拟定时器中断，并恢复Primary虚机的运行。之后，VMM将指令序号和定时器中断再发送给Backup虚机。虽然Backup虚机的VMM也可以从自己的物理定时器接收中断，但是它并没有将这些物理定时器中断传递给Backup虚机的guest操作系统，而是直接忽略它们。当来自于Primary虚机的Log条目到达时，Backup虚机的VMM配合特殊的CPU特性支持，会使得物理服务器在相同的指令序号处产生一个定时器中断，之后VMM获取到这个中断，并伪造一个假的定时器中断，并将其送入Backup虚机的guest操作系统，并且这个定时器中断会出现在与Primary相同的指令序号位置。
现在关于这个系统我们已经有了一个大致的框架，但细节上还不是很完美，现在要再给它加上一些限制，首先是输出规则
假设在故障发生时，大多数情况下主服务器发生故障，备份服务器顶上，在这个过程中发生的给客户端发出多次输出或许是可以忍受的，但设想这样一种极端情况：
一个客户端发送了一个自增的请求给Primary，这个请求在Primary虚机的软件中执行，Primary会发现，现在的数据是10，我要将它变成11，并回复客户端说，现在的数值是11。这个请求也会发送给Backup虚机，并将它的数值从10改到11。Backup也会产生一个回复，但是这个回复会被丢弃，这是我们期望发生的。
但极端情况是：假设Primary确实生成了回复给客户端，但是之后立马崩溃了。更糟糕的是，现在网络不可靠，Primary发送给Backup的Log条目在Primary崩溃时也丢包了。那么现在的状态是，客户端收到了回复说现在的数据是11，但是Backup虚机因为没有看到客户端请求，所以它保存的数据还是10。现在，因为察觉到Primary崩溃了，Backup接管服务。这时，客户端再次发送一个自增的请求，这个请求发送到了原来的Backup虚机，它会将自身的数值从10增加到11，并产生第二个数据是11的回复给客户端。如果客户端比较前后两次的回复，会发现一个明显不可能的场景（两次自增的结果都是11）。
论文里给出的解决方法是控制输出。简单来说就是，Primary在每次向客户端输出前，都要先收到Backup的确认。
让我们回到Primary崩溃前，并且计数器的内容还是10，Primary上的正确的流程是这样的：
- 客户端输入到达Primary。
- Primary的VMM将输入的拷贝发送给Backup虚机的VMM。所以有关输入的Log条目在Primary虚机生成输出之前，就发往了Backup。之后，这条Log条目通过网络发往Backup，但是过程中有可能丢失。
- Primary的VMM将输入发送给Primary虚机，Primary虚机生成了输出。现在Primary虚机的里的数据已经变成了11，生成的输出也包含了11。但是VMM不会无条件转发这个输出给客户端。
- Primary的VMM会等到之前的Log条目都被Backup虚机确认收到了才将输出转发给客户端。所以，包含了客户端输入的Log条目，会从Primary的VMM送到Backup的VMM，Backup的VMM不用等到Backup虚机实际执行这个输入，就会发送一个表明收到了这条Log的ACK报文给Primary的VMM。当Primary的VMM收到了这个ACK，才会将Primary虚机生成的输出转发到网络中。
但很显然，这样会有一些性能问题，Primary必须等待Backup的回应，及时每次等待的时间只有0.几毫秒，在高并发或者距离较远的时候对性能来说同样是不小的影响。
对于我们一开始提到的重复输出的问题，虽然这是一种异常行为，但其实无意识中这种异常其实已经被解决了。因为客户端使用TCP与服务进行交互，也就是说客户端请求和回复都通过TCP Channel收发。当Backup接管服务时，因为它的状态与Primary相同，所以它知道TCP连接的状态和TCP传输的序列号。当Backup生成回复报文时，这个报文的TCP序列号与之前Primary生成报文的TCP序列号是一样的，这样客户端的TCP栈会发现这是一个重复的报文，它会在TCP层面丢弃这个重复的报文，用户层的软件永远也看不到这里的重复。
最后我们要说一下分布式系统经典的脑裂问题，看看FT是如何解决网络分区的
在实际应用中我们还会遇到这种情况，Primary和Backup都在运行，但由于网络问题，他们会以为对方挂了。VMware FT解决这个问题的方案是由想要上线的服务器（大多情况下是Backup）对虚拟磁盘进行原子操作，如果成功了，那就可以上线接管，如果失败，就放弃尝试，而如果虚拟机在试图进行原子操作时无法访问共享存储，那么它就会等待，直到它能够访问。
这也是为什么我们要在最开始强调VMware FT采用了共享磁盘的设计，但VMware FT同时也在论文后面提供了非共享磁盘的解决方案，首先使用非共享磁盘要保持不同磁盘间的数据备份，同时这种情况下解决脑裂的方案是引入第三方权威机构来决定Primary还是Backup允许上线。这里的第三方就是Test-and-Set服务。
Test-and-Set服务不运行在Primary和Backup的物理服务器上，VMware FT需要通过网络支持Test-and-Set服务。这个服务会在内存中保留一些标志位，当你向它发送一个Test-and-Set请求，它会设置标志位，并且返回旧的值。Primary和Backup都需要获取Test-and-Set标志位，这有点像一个锁。为了能够上线，它们或许会同时发送一个Test-and-Set请求，给Test-and-Set服务。当第一个请求送达时，Test-and-Set服务会说，这个标志位之前是0，现在是1。第二个请求送达时，Test-and-Set服务会说，标志位已经是1了，你不允许成为Primary。对于这个Test-and-Set服务，我们可以认为运行在单台服务器。当网络出现故障，并且两个副本都认为对方已经挂了时，Test-and-Set服务就是一个仲裁官，决定了两个副本中哪一个应该上线。
参考
The Design of a Practical System for Fault-Tolerant Virtual Machines
Fault-Tolerant Virtual Machines-VMware vSphere容错虚拟机设计 (1)
Fault-Tolerant Virtual Machines-VMware容错虚拟机设计 (2)