1. Introduction

传统实现容错集群的方法：

主/从服务器法：主失效，从接管
- 从需要持续和主同步状态，需要很大的带宽
（确定）状态机法：让其它节点和主节点的初始状态一样，并接收一致的输入（顺序和内容一样），如共识算法：Paxos, Raft等
- 一般对非确定的操作不适用（在VM中大量出现这类操作）
- 实现很难

本文讨论使用虚拟机主从法实现状态机法：

由一个顶层的管理程序（嵌入在VM进程中）记录主虚拟机的操作，然后在从虚拟机上重放，重放是确定的
操作完全虚拟化，虚拟机支持非确定操作，且可被管理程序记录
系统完全可容错（仅在fail-stop假设下），且能自动恢复和冗余
记录和重放可同时进行

2. 基本容错设计

架构图如下：

ftdesign

包含：

主VM
从VM：与主VM保持同步，执行相同的输入序列；主VM和从VM会相互心跳；
共享存储：主VM和从VM共享这些存储，但只有主VM公布其存在；

所以所有的输入都只经过主
日志通道：主VM将输入通过该通道传给从VM，并需要传输一些额外信息，保证非确定性操作在从VM的行为和主VM一样。通道遵循一个协议，防止数据丢失。

从VM的输出会被管理程序丢弃，真正返回给客户端的是主VM的输出

2.1. 实现确定性重放

3个挑战：

正确捕捉所有的输入以及非确定性的操作，保证从VM的执行序列是确定性的
正确将这些输入和非确定性操作应用到从VM中
不会降低性能

实现：

确定事件和非确定事件都要记录到日志中，通过日志通道传给从VM
对于非确定操作：
- 需要额外信息，保证重放时，状态变化和输出一样
- 对于时钟或者I/O完成的操作，还记录了事件发生时的指令

优化：分epoch，并且把非确定性事件放在每个epoch最后发出。（参照了批处理系统的做法）

2.2. FT协议（容错协议）

协议要求：

输出要求：由于主VM失效，若从VM接管成为主VM，则它之后给外界的输出要与之前失效的主VM一致。

实现需要应用下面的规则：

输出规则：主VM直到从VM收到并回应了日志项（与当前操作相关的）时，才能把输出返回给外界

这不代表“停止”执行，而只是延迟返回，等待过程中，其它请求依旧可以处理

如图：

特殊情况——主VM输出output前后宕机，从VM不知道它是否已经发送：

使用如类似TCP的协议，它会去重
网络架构，操作系统和上层应用来进行补偿

2.3. 检测和响应失效

响应失效（go live操作）：

若从VM失效，主VM关闭日志传输，正常执行
若主VM失效，从VM先重放完最后一条日志，然后接管成为主VM，正常执行

检测：使用UDP心跳以及日志流，互相检测服务器是否失效（超时机制）

问题——脑裂（当主从VM间网络较差时，彼此认为对方挂掉，实际并没有）：

使用共享存储，当节点想要go live，则在上面进行原子test-and-set操作
- 若成功，则go live
- 否则，必然有其它VM已经go live，自己就停机（自杀）
若VM不能访问共享存储，等待直到可以访问
当一台VM已经go live，会自动启动新的从VM，实现冗余

3. FT实现

3.1. 启动一个和主VM一样的从VM

VMware VMotion能将一个VM从一台服务器迁移到另一台服务器，时间很短。

FT VMotion这里的设计不是迁移，而是直接克隆。

3.2. 管理日志通道

类似流量控制，主VM和从VM都有自己的缓冲队列：

若主VM的缓冲满，则会等待，直到有空间（主快从慢）
若从VM的缓冲空，则会等待新的日志项（主慢从快）

回应发生在从VM从缓冲读取日志项且应用操作后

若主VM和从VM执行速度不同，产生执行延后（即第一种情况），会造成明显的停顿，解决方法是：

请求和回应中捎带实际的执行延后时长
主VM根据时长，更改CPU的分配

这种方法也能减少第二种情况的发生，尽管它不会影响整体性能。

3.3. 对VM的操作

绝大部分操作都应该由主VM发起（如关机），然后通过日志通道传给从VM。

只有一种操作可以在主和从VM上操作：VMotion。

VMotion，需要所有的磁盘I/O已完成：

对于主VM，直接等待物理I/O完成即可
对于备I/O，VMware FT使用一个特殊的方法：
- 备VM通过日志通道请求主VM，临时完成/停顿自己的磁盘I/O
- 这样备VM也会在某个时间点完成所有的I/O

3.4. 实现磁盘I/O的问题

1. 磁盘操作非阻塞且可并行，导致操作结果不确定

由于磁盘I/O实现使用了DMA（会访问VM的内存），同时会访问相同内存页的磁盘操作也会造成结果不确定。

检测I/O竞争，强制其串行执行。

2. 磁盘操作可能和应用的内存操作竞争（因为使用DMA）

设置临时的页保护，这会引发一个trap，VM会等待磁盘操作完毕后再操作该页的内存。

设置页保护不修改MMU的保护（因为开销太大），而是额外使用弹性缓冲（bounce buffer）。它是一个临时的缓冲，大小和磁盘操作所访问的一样：

磁盘读：将数据读入弹性缓冲，然后当I/O完成后拷贝到对应地方
磁盘写：将数据先拷贝到弹性缓冲，写数据的时候从该缓冲中写

3. 主VM未完成I/O时挂掉，从VM接管

从VM不知道主VM的I/O是否已经完成。

不过由于所有的竞争都被消除，因此操作是幂等的，新主VM（原从VM）直接重试I/O操作即可。

3.5. 实现网络I/O的问题

关闭异步网络优化

异步会带来不确定性。但是关闭它会带来网络性能问题，用以下方法解决：

使用聚合优化（批量处理）来减少VM的trap和中断数量
减少数据包的延迟
- 发送和回应日志时，没有线程上下文切换（允许将函数注册到TCP协议栈上，函数会在“延迟执行上下文”中执行，类似于中断的下半部，如tasklet）
- 当数据包发出后，强制刷新相关日志项（通过“调度延迟执行上下文”）

4. 其它的设计方案

4.1. 使用非共享存储

每个VM独立写到自己的虚拟磁盘，因此各个VM的磁盘内容需要保持与主VM的一致。

优点：当共享存储不可用，或过于昂贵，或主从VM距离过远时，比较有用

缺点：FT打开时，主从VM的磁盘必须保持实时同步，同步失败时必须重试，从VM重启后也必须先同步，带来额外开销（不仅保持VM运行状态一致，且要保证磁盘存储一致）

防止脑裂：由于没有共享存储的test-and-set，需要第三方节点作为仲裁，当集群割裂时，取大多数的一方

4.2. 在从VM上进行磁盘读

当在主VM执行读操作时，同时也在从VM上读，不进行日志传输：

优点：减少日志通道的负载；
缺点：减慢从VM的执行速度（因为在从VM读时，需要等待主VM也要同样完成后才能返回）。

还有一些额外的工作：

若主VM的读成功，对应的从VM的读需要重试直到成功
若主VM的读失败，对应的从VM的读需要回滚，这通过传输日志实现
若主VM执行同一位置的read-write操作，主的write必须等到从的read结束后才能进行

测试：吞吐量减少1%~4%，但日志通道的带宽被限制了

论文阅读-容错虚拟机分布式系统的设计