Introduction
实现容错服务器的通常方法是primary/backup机制，当primary server出错时，backup server可以作为primary server推动系统继续向前运行。backup server的状态必须在任何时候都与primary server保持一致，因此在primary出错时backup可以立即接替，并且这种机制将错误对外部的客户端隐藏，并且不会出现数据丢失。一种在backup上复制primary的状态的方式是不断将primary所有的状态变化都发送到backup，包括CPU，内存，I/O设备。但是这一方式受到带宽的限制。
状态机方法可以使用更少的带宽来复制服务器状态。将服务器抽象成确定性状态机，使不同的服务器从相同的初始状态启动，并且确保按照相同的顺序收到相同的输入请求。因为大部分服务器或服务具有某些非确定性的状态，因此需要额外的协调操作来保证primary和backup同步。但是保持primary和backup同步所需的额外信息的数量远小于primary中正在改变的状态（主要是内存更新）的数量。
在hypervisor上运行的VM是非常适合用于实现状态机方法。VM可以被看作定义好的状态机，其操作是被定义的虚拟机的操作。与物理机相同，VM同样有某些非确定性的操作，例如读取时间时钟或传递中断，因此额外的信息必须发送到backUp以保持primary和backup之间的同步。因为hypervisor具有对于VM的执行具有完全的控制权，包括传递输入，因此hypervisor能够获取primary VM的非确定性操作的所有必要的信息，因此能够在backup VM上正确地重放这些操作。因此能够在商用硬件上为VM实现状态机方法，而不需要额外的硬件修改，因此能够为最新地微处理器实现容错。另外，状态机方法所需的低带宽也为primary和backup在物理上分离提供了可能。
作者在VMware vSphere 4.0平台上使用primary/backup approach实现了fault-tolerant VMs，其中以高性能方式运行了完全虚拟化的x86虚拟机。由于VMware vSphere实现了完全的x86虚拟机，因此能够为任何x86操作系统和应用程序提供容错机制。VMware vSphere Fault Tolerance基于确定性重放，并添加了必要的额外协议和功能来构建完整的容错系统。除了提供硬件容错之外，还通过在出现服务器错误后在本地集群中的任何空闲的服务器中启动新的backup虚拟机来恢复冗余。作者构建的容错系统用于处理fail-stop错误，这种服务器错误能够在出错的服务器造成不正确的额外操作前被检测出。
BASIC FT DESIGN
Figure 1展示了系统基本设置。对于一台给定的希望提供容错的服务器（这台服务器作为primary），在不同的物理服务器上运行backup VM，使backup与primary始终同步并且与primary执行相同的操作，二者之间仅有微小的时间延迟。我们称这两台VM是virtual lock-step的。VM的虚拟磁盘在共享存储器上，因此可以访问primary和backup的输入和输出。只有primary VM在网络中宣告其自身存在时，所有的网络输入才能够到达primary VM。类似地，所有地输入都会输入到primary VM中。
primary VM接收到的所有的输入通过称为logging channel网络连接发送到backup VM。对于服务器负载，决定性的输入流量是网络和磁盘。在必要时传输额外信息以保证backup VM与primary VM执行相同的非确定性操作，结果是backup VM总是与primary VM的执行保持一致。不同的是backup的输出被hypervisor丢弃，因此只有primary产生的真实输出会被返回给客户端。primary和backup会遵守特定的协议，其中包括来自backup VM的显式确认，以保证在primary出错时不会出现数据丢失。
系统通过在相邻的服务器之间发送heartbeat和监视logging channel上的流量来检测是否存在primary或backup VM出错。此外，即使出现primary和backup之间丢失通信（称为splitbrain），也必须确保只有一个primary或backup VM接替primary执行。
Deterministic Replay Implementation
复制服务器或VM的执行可以被抽象为确定性状态机的复制。如果两个确定性状态机在同样的初始状态执行，并且按照相同的顺序读取输入 ，那么将会具有相同的状态迁移序列并产生完全一致的输出。虚拟机具有多种不同的输入，包括输入的网络分组，硬盘读，键盘和鼠标操作。非确定性的事件（例如虚拟中断）和非确定性的操作（例如读处理器的时钟周期计数器）同样会影响VM的状态。因此对于复制在任何操作系统上运行的任何VM的执行和工作负载提出了三个挑战：（1）必须正确地捕获必要的所有的输入和非确定性事件来确保backup VM的确定性执行。（2）正确地将输入和非确定性事件应用到backup VM中。（3）在不影响性能的情况下完成上述要求。此外，x86位处理器中的许多复杂操作是未定义的并且具有非确定性的副作用。捕获这些副作用并且重放来产生相同的状态提出了另一项挑战。
VMware确定性的重放为VMware vSphere平台上的x86虚拟机提供了此种功能。确定性的重放将VM的输入以及所有与VM的执行相关的可能的不确定性事件记录在日志记录流中，并将其写入到日志文件中。通过从日志文件中读取日志记录来重放VM执行过程。对于非确定性的操作，记录足够的信息来使VM重放相同的状态改变和输出。对于非确定性的事件，例如定时器或IO完成中断，事件发生时执行的指令也同样被记录。在重放时，the event is delivered at the same point inthe instruction stream（我的理解是事件按照primary中发生的顺序进行重放，例如在primary中，首先执行指令A，然后触发事件B，然后执行指令C，在重放时也要按照相同的顺序依次执行ABC），VMware确定性重放实现了一个高效的事件记录和事件传递机制，每个中断在发生时被记录，并在重放过程中在合适的指令处被传递给VM。
FT Protocol
作者使用确定性的重放来产生必要的日志记录以记录primary VM的执行过程，但是并不需要将记录写在磁盘上，而是通过logging channel将日志发送给backup VM.backup VM实时重放记录，因此执行过程与primary完全一致。但是为了实现这一目的，必须在严格的FT protocol上按照递增序在logging channel上发送日志。基本的输出要求(Output Requirement)是：如果backup VM在primary出错后接管了primary，backup VM必须继续执行，并且与primary VM已经发送到外部客户端的输出完全一致（我的理解是要求backup VM和primary VM过去的执行和输出完全一致，并在primary出错时接续执行，而不会出现服务中断或不一致的现象，从而对客户端隐藏）。
在failover发生后，backup VM开始执行的方式可能与primary VM继续执行的方式完全不同，因为在执行期间可能会产生许多非确定性的事件。但是只要backup VM满足上面说的输出要求，在failover期间没有外部的可见状态和数据丢失，客户端就不会注意到服务中的中断或不一致现象出现。
可以通过推迟外部输出（尤其是网络包）直到backup VM收到了能够使其重放这一输出操作的所有必要信息时来保证输出要求。一个必要条件是backup VM必须接收到所有输出操作之前的的日志记录。这些日志记录将会使backup能够执行到上一个日志记录点。但是如果primary执行完输出操作之后立即出错，backup VM将会知道自己必须重放primary的输出操作没并且只能go live（停止重放并且接替primary VM的工作），如果backup在执行完输出操作前的最后一条日志后接替primary，某些非确定性的事件可能在新的primary执行输出操作前改变其执行路径。
解决上述问题的最简单的方式是在每个输出操作处创建一个特殊的日志记录，于是有了能够强制保证输出要求(Output Requirement)的输出规则：primary VM可能不会向外部世界发送输出，直到backup已经接收并确认与产生输出相关的操作的日志记录。
如果backup VM收到了包括产生输出在内的所有的日志记录，backup VM将会能够重新产生primary VM在输出时的状态，因此当primary出错时，backup将会到达与输出一致的状态。反过来讲，如果backup VM没有收到所有必要的日志记录，并且接替了primary VM，那么其状态可能很快与primary出现不一致，因此也就会产生与primary不一致的输出。
输出规则并没有说需要停止primary VM执行。只需要推迟向客户端发送输出，而VM自身是可以继续往下推进的。因为操作系统使用异步中断来通知非阻塞的网络和磁盘输出完成，因此VM可以继续执行而不会被输出延迟影响。
Figure 2中展示了primary和backup VM上事件发生的时间线。primary指向backUp的箭头代表从primary向backup转发日志记录，而backup从primary的箭头代表了backup对日志的确认。异步事件、输入和输出操作的信息必须作为日志被发送到backup并确认。对外部世界的输出必须被推迟到收到来自backup的对于输出操作的日志的确认后。只要输出规则得到满足，backup VM将能够以与primary的上一个输出相一致的状态接管primary.
无法保证failover中所有的输出都被执行一次。primary发送输出时，如果不采用两阶段提交的事务，backup无法确认primary是在发送最后一个输出之前还是之后崩溃。但是由于网络协议如TCP存在处理丢包和重复的机制，因此重复的响应将会被忽略。并且如果在切换时出现丢包，客户端超时没有收到来自服务端的响应，也将会重发，因此丢包也可以被网络协议自身解决。
Detecting and Responding to Failure
如果另一个VM出错，primary和backup VM必须能够快速响应。如果backup出错，primary将会go live，即离开记录模式，并且停止在logging channel上发送日志记录，开始正常执行。如果primary VM出错，backup将会go live。由于backup在时间上相对于primary的执行略有延迟，backup VM可能有一些日志记录已经收到但是由于自身还没有执行到对应的状态，因此尚未执行。backup VM将会持续重放日志中记录的执行过程，直到没有收到新的日志。此时，backup VM将会停止重放模式，并且开始作为一个正常的VM执行。也就是说，backupVM被提升为primary VM，并且没有backup VM存在。由于此时不再存在backup VM，因此当客户端执行输出操作时，新的primary VM将会直接输出到外部。在转换到正常模式的过程中，可能需要某些设备相关的操作来使输出正常完成。VMware FT自动在网络中广播新的primary VM的MAC地址，因此物理网络交换机将会知道新的primary VM在哪台服务器上。另外新的primary VM可能需要重新执行某些磁盘I/O
检测primary和backup VM错误的方法：VMware FT使用服务器间的UDP heartbeat来检测服务器的状态。VMware FT监视器检测从primary发送到backup的日志流量以及从backup发送给primary的响应流量。由于定期的时间中断，日志流量也应该是定期的，并且一个正在工作的guest OS日志流量从不中断。因此，日志流或确认流的中断标志着VM出错。如果heartbeat或日志流量停止的事件超出指定的timeout事件，就可以认为VM出错。
上述错误检测方法存在的缺陷：无法解决split-brain问题。如果backup服务器停止接收来自primary的heartbeat，可能说明1.primary服务器出错。2.两台服务器仍然在工作，但是二者之间的网络连接丢失。如果primary VM仍然在运行时，backup提升为primary，那么正在与服务器通信的客户端可能会出现数据污染的问题。因此必须确保当检测到错误时只有一台服务器在运行。利用保存VM的虚拟磁盘的共享存储来避免split-brain问题。当primary或backup想要go live时，首先在贡献存储上执行一个test-and-set操作。如果操作成功，则说明此时只有一台服务器在运行，可以go live。如果使用原子操作时无法访问共享存储，那么将会等待直到可以访问为止。如果共享存储是因为本身的故障导致无法访问，那么VM将会无法正常工作，因为VM的虚拟磁盘也保存在共享存储中。因此使用共享存储来解决split-brain不会影响可用性。
当错误发生并且VM go live后，VMware FT将会自动在另一台host上启动新的backup VM来恢复冗余。
PRACTICAL IMPLEMENTION OF FT
Starting and Restarting FT VMs
作者采用了VMware vSphere的VMotion机制来实现保持backup与primary相同的状态，以及在backup出错时重启一台新的backup，并且不会影响primary的执行。
VMware VMotion允许以最小的代价将正在运行的VM从一台服务器迁移到另一台服务器，VM暂停的时间通常小于1秒。作者创建了修改版的VMotion，从远程服务器上创建了一个正在运行的VM的副本，但是并没有销毁本地服务器上的VM。也就是说，修改过的FT VMotion在远程服务器上克隆了VM而没有迁移。FT VMotion同样创建了一个logging channel，并且使源VM作为VM进入了logging模式，目标VM作为新的primary进入了重放模式。与VMware VMotion相同，FT VMotion使VM被打断的时间小于1秒。
启动一个backup VM的另一个问题是选择一台合适的可以用于运行VM的服务器。Fault-tolerant VM在拥有共享内存的服务器集群中运行，因此所有的VM通常可以运行在集群中的任何一台服务器上。因此VMware vSphere能够在一台或多台服务器出错时恢复冗余性。VMware vSphere实现了一个集群服务来维护管理和资源信息。当错误发生并且primary VM需要新的backup VM来重建冗余时，primary VM通知集群服务需要新的backup。集群服务根据资源使用和其他的限制条件来选择最合适的服务器运行backup VM，然后调用FT VMotion来创建新的backup。通过这一机制可以在出错后的几分钟内完成重建，并且对fault-tolerant VM的执行不会产生太大的影响。
Managing the Logging Channel
实现中hypervisor维护一个buffer用于primary和backupVM的日志记录。当primary VM执行时，primary将日志写入buffer，backup VM从buffer中读出。primary的日志缓冲尽可能快的刷新到logging channel，并且一旦日志被写入到channel中，backup就从中读取日志到自己的缓冲区。backup每次从网络中读入一批日志到自己的日志缓冲区后向primary发送响应，响应使VMware FT决定根据Output Rule被推迟的输出何时被发送给backup。如图3所示。
如果backup VM在读取时发现日志缓冲区是空的，则将被阻塞直到新的日志到来。因为backup VM不与外部通信，因此将不会影响VM的客户端。类似地，如果primary VM发现日志缓冲区满了，则会停止执行直到缓冲区被刷新。primary的停止是一个天然的流控制机制，使primary在产生日志过快时暂停执行。但是primary的暂停会影响外部的客户端，因为primary VM将会完全停止执行并直到可以向缓冲区写入日志记录和继续执行时才能响应客户端。因此需要尽可能降低将缓冲区填满的可能性。
缓冲区可能填满的一个原因是backup执行过慢因此读取日志的速度太慢。通常backup必须能够以与primary大概相同的速度重放primary的执行过程。但是如果backup所在的服务器负载过多，则backup可能被不会得到足够的CPU和内存资源来快速执行。
除了避免缓冲区被填满造成primary阻塞之外，另一个不能让backup和primary之间差距太大的原因是，当primary出错时，backup VM必须在go live并与外部通信之前通过重放所有已经确认的日志记录来使自己达到primary出错时的状态。重放日志记录所需的时间至少是backup落后于primary的时间，因此backup go live所需的时间通常等于检测时间+重放时间。因此，如果backup落后于primary的时间过长，那么对应的failover时间也会延长。
Operations on FT VMs
另一个问题是如何处理可能应用在primary VM上的各种控制操作。例如，如果primary显式的断电，backup VM也会停止，而不会尝试go live。同理，任何primary上的管理操作例如提高CPU共享也同样应该应用到backup上。
通常，VM上的大部分操作仅应该在priamry VM上使用，随后VMware FT将所有必要的控制记录发送给backup以在backup上执行对应的操作。唯一的能够在primary和backup上独立执行的是VMotion。也就是说，primary和backup VM可以被独立地VMotioned到其他的主机上（前面提到了， VMotion的作用是将一台主机以最小的代价迁移到另一台主机，作者修改的FT VMotion是克隆到另一台主机）。VMware FT确保没有VM会被迁移到存在VM的服务器上，因为这种情况下服务器宕机会导致两台VM同时出错，从而不再具有容错能力。
因为backup VM必须从源primary断连，并且在合适的时候重新连接到目标primary，因此primary的VMotion在正常的VMotion上添加了一些额外的复杂度。对于正常的VMotion，需要所有未完成的磁盘IO在VMotion最终切换执行时完成。对于primary VM，可以通过使primary等待直到物理IO完成并将完成发送到VM来实现。对于backup，没办法在需要时让所有的IO完成，因为backup VM必须重放primary VM的执行并在相同的执行点处完成IO。primary VM可能一直在执行磁盘IO，而backup VM又必须与primary保持一致，所以backup也就无法使IO在给定的某一点处完成。VMware FT提供了一个解决方案：当backup VM在VMotion的最终执行点处时，通过logging channel来使primary暂停所有的IO，backup VM因此能够在重放primary VM执行暂停操作时自然结束所有的IO。（简单来讲，因为primary能够随时停止IO而backup依赖于primary的执行，并且backup与primary存在通信机制，因此backup通过logging channel通知primary先暂停一下，因为backup重放primary的执行过程，因此自然也就会重放primary的暂停，从而使backup的IO全部结束）
Implementation Issues for Disk IOs
磁盘IO存在一些问题需要解决。
首先，假设磁盘操作是非阻塞的，因而也就可以并行执行，那么同时访问同一磁盘位置的操作将会导致非确定性。同时，磁盘IO的实现使用DMA来直接与虚拟内存通信，因此同时访问同一内存页的操作也会导致不确定性。作者的解决方式是检测这种IO竞争，并且强迫这些竞争性的磁盘IO在backup和primary上以相同的顺序串行。
第二，磁盘操作可能与VM中的应用或OS的内存访问相冲突，因为磁盘操作通过DMA来直接访问VM的内存。例如，如果VM中的应用或OS正在读某个内存块，同时这个块正在发生磁盘读，则会产生不确定性结果。一种解决方式是对磁盘操作的目标内存页启用页保护，当VM正好需要访问的页是磁盘操作的目标页时，页保护将会产生trap，使VM等待直到磁盘操作完成。由于修改页的MMU保护的开销很大，因此使用bounce buffer来实现保护。bounce buffer是一个临时的buffer，与正在被磁盘操作访问的内存块大小相同，磁盘读操作被修改为将数据读取到bounce buffer，并在IO结束后将数据拷贝到guest的内存。类似地，对于磁盘写操作，数据首先被拷贝到bounce buffer，然后磁盘写被修改为写来自bounce buffer的数据。对bounce buffer的使用可能会使磁盘操作减慢，但并没有造成任何可见的性能损失。
第三，在primary出错时，可能会有一些尚未完成的磁盘IO，此时backup成为primary。新的primary没有办法确定磁盘IO是否开始或完成。并且因为磁盘IO不是在backup VM上从外部发出的，因此当新的primary继续运行时也不会有显式的磁盘IO完成通知，最终会造成VM中的guest OS中断或重置进程。因为即使在IO成功完成时返回一个错误是可以接受的，因此可以发送一个错误完成来通知每个IO出错。但是guest OS可能不会从自己的本地磁盘中响应这些错误，因此作者重新启动backup VM go live过程中挂起的IO。因为消除了所有的竞争，并且所有的IO直接指明了访问的是哪个磁盘块或内存块，因此即使这些磁盘操作已经成功完成了也是可以进行重复的。
为什么新的primary没法确认磁盘IO是否完成？backup与primary的状态应该是一致的，primary自身也无法确认磁盘IO是否完成？来自FAQ的答案：这些无法确认是否完成的IO指的backup收到了启动IO的日志，但没有收到IO结束的日志。因此这部分需要重新开始。
Implementation Issues for Network IO
VMware vSphere为VM网络通信提供了多种性能优化。某些优化基于hypervisor异步更新虚拟网络设备的状态。例如，接收缓冲在VM执行时可以直接被hypervisor更新。但是除非能够保证状态更新发生在backup和primary指令流的同一点，否则会导致不确定性，因而backup的执行就可能与primary出现分歧。
FT网络仿真代码最大的变化是禁用了异步的网络优化。使用输入网络包异步更新VM的ring buffer的代码被修改为强制guest陷入到hypervisor，因此能够记录这一更新并将其应用到VM。类似地，从发送队列中异步的取出网络报文的代码也被禁用，并且也是通过trap来完成。
作者采用了两种方式来提高运行FT时VM的网络性能。首先，实现了集群优化来减少VM的陷入和中断。当VM在以足够的速率发送流式数据时，hypervisor可以每一组报文执行一次陷入，最好情况下是不执行陷入，因为可以将传输报文作为接收新报文的一部分（我的理解是类似于TCP，在发送时捎带确认？），类似地，hypervisor可以通过仅发布一组网络报文的中断来减少VM中断的数量。
第二个性能优化包括减少传输报文的延迟。前面提到，hypervisor必须延迟所有的传输报文直到接收到来自backup对于日志的确认。因此降低延迟的关键是降低发送日志消息和接收来自backup确认的时间。作者主要的优化是确保发送和接收日志记录和确认不需要任何线程上下文的切换。VMware vSphere hypervisor允许函数在TCP协议栈注册，并在收到TCP数据时在推迟的执行上下文调用（类似tasklet）tasklet是这样的，将中断服务程序分为上半部和下半部，上半部要求立刻完成，而下半部的优先级较低，因此可以推迟到以后来完成，先对中断响应，然后把所有并不要求立刻完成的中断服务程序放到之后完成。类比一下，对于收到的TCP数据立刻响应，然后等到空闲后再处理TCP数据。因此能够迅速处理backup收到的日志消息和primary收到的确认而不需要上下文切换。
FAQ from 6.824
为什么在VM上实现确定性比物理服务器更加容易？
因为VM存在hypervisor模拟和控制硬件，从而消除primary和backup之间的不同。例如可以通过hypervisor来精确控制时钟中断。hypervisor是VM的一部分，与Virtual Machine Monitor相同。hypervisor模拟了一台计算机，guest OS在上面运行。论文中的FT作为hypervisor的一部分，primary和backup是guest OS.
GFS和FT都提供了一致性，二者的区别和优劣？
FT提供了强一致性，并且backup复制了primary的计算过程，并且只有primary与client进行通信，因此对于client是透明的。GFS只为存储提供了容错，因此复制过程比FT更加高效。例如GFS不需要处理中断来让所有的副本保持完全一致，因而提供的是弱一致性。GFS通常作为一个大型容错服务的一部分，例如VMware FT依赖于primary和backup之间共享存储，因此需要一个容错存储服务，GFS可以提供此功能。
bounce buffer是如何避免竞争的？
考虑这种情况：通过DMA从磁盘拷贝数据到内存，同时有个应用程序正在读取这一内存，那么应用读到的数据有两种可能：一种是读到旧的，一种是读到来自DMA的数据，具体取决于CPU的调度。如果primary和backup上同时遇到了这种情况，并且做出了不同的选择，即primary可以读到DMA的数据，backup读不到DMA的数据，就无法再保持二者的状态完全一致。
在backup和primary同时执行时，数据不会直接拷贝到内存中。首先将磁盘块拷贝到私有的bounce buffer中，此时primary无法访问，因而也就不会出现与应用程序的竞争。当拷贝完成时，FT hypervisor中断primary，然后将bounce buffer拷贝到primary的内存中，然后允许primary继续执行。FT在logging channel上将数据发送给backup。backup的FT在同一指令处中断backup将数据拷贝到相同的为止，然后返回给backup继续执行。这样做的效果是对于primary和backup来说，二者看到的来自磁盘和网络的数据始终保持一致，因此不会出现状态不一致的情况发生。