准备工作
阅读：Fault-Tolerant Virtual Machines
为什么要阅读这篇文章
了解分布式系统的容错机制
本文是对于容错机制的比较特殊的实现，其并不是要设计一个应用程序级别的容错系统，而是一个系统级别的。需要处理CPU中断，能够为了实现一个容错的虚拟机系统（VM-FT），难度更大。
容错（Fault tolerance）
容错是即使发生故障也会继续提供服务的能力
一些理想的属性：可用性：尽管[某些故障]仍然可用
一致性：正确性的保证，对于客户端来说就像是面对一台服务器
对用户和软件透明（内部运行机制透明）
高效
论文尝试解决哪些失败？
断电等突然停止的错误
网络丢包
网络分区
核心思想
容错的核心思想是建立副本，需要两个以上的服务器。
每一个副本都维持相同的状态，如果一个服务器失败,其他服务器可以继续进行。
-
需要思考的重要问题：
什么状态需要去复制？
primary（主服务器）需要等待副本服务器复制完成吗？
什么时候需要切换到副本服务器？
切换到副本时是否可能发生异常？
切换到副本时能否加速？
两种主要的方式
-
状态转移
primary执行操作
primary将状态转移到副本
状态转移虽然简单，但是状态可能很大，转移可能很慢
论文中的虚拟机使用了复制状态机。
-
复制状态机
所有副本执行所有操作
相同的开始状态
相同的操作
相同的顺序
确定性的操作
则具有相同的最终状态
更有效率，但是更复杂
本论文的目标
构建复制状态机
Primary和副本具有相同的初始状态（内存，磁盘文件）
primary通过日志通道（logging channel）传递给副本服务器
使主从具有相同的指令、相同的输入、相同的执行
什么时候在主数据库上执行与备份上可能不同？
来自外部的输入（网络）
从存储服务器读取的数据
定时器中断（Timing of interrupts）。 参考：wikibook
一些特殊的指令：如cpu周期计数
冲突
不一致的原因
锁定服务器将lock授予客户端C1，拒绝来自C2的后续请求
锁定服务器在一分钟后撤消lock
假设C1持有lock并且，1分钟马上就要到时，c2请求锁。这时，Primary可能会在定时器1分钟发送中断之前立即看到C2的请求，拒绝其请求。副本可能会在定时器1分钟发送中断之后看到C2的请求，同意请求。
因此：副本必须在指令流中的同一点以相同的顺序看到相同的事件。
解决定时器中断的解决方案
-
primary
FT 收到定时器中断信号
FT从CPU读取指令
FT在日志通道（logging channel）上发送 "在指令x处触发计时器中断”
FT给primary发送中断信号，然后恢复。
-
Backup
忽略自己的定时器硬件
在副本执行指令X之前，观察是否日志中有需要在这之前执行的日志。
FT告诉CPU在指令X处中断
FT模拟计时器中断，然后恢复。
解决磁盘、网络数据输入可能不一致的问题
FT拦截，只能够让primary能够访问硬件。
Primary:
FT通知硬件通过方式将数据存入FT的私有缓存中
在某一时刻，硬件执行DMA，然后中断
FT收到中断信号
FT暂停primary
FT复制缓冲区数据到primary内存中。
FT为primary模拟中断，稍后恢复。
-
FT将数据和指令发送到备份 Backup:
FT从日志流中获取数据和指令
FT告诉CPU在指令X处中断
FT在中断期间复制数据
缓冲区（bounce buffer）的目的就是为了在内存的同一个时间点执行相同的操作，读取相同的数据。
解决特殊的指令
-
Primary:
如果primary执行了特殊的指令，FT会通知CPU中断
FT执行指令并记录结果
将结果和指令发送到备份
-
Backup:
副本在执行此指令时也会中断
副本应用从primary中得到的值
Output Ruler
primary必须在副本收到此输出指令的日志后，才能够输出。
此规则是必要的，因为我们的服务是为了在奔溃时让用户是无感知的。
有了此规则，即便pimary奔溃了，副本也能够和primary一样，对于之前的请求返回相同的数据。
假设primary收到请求I1 I2 I3 并输出, 这时primary奔溃，副本只能看到I1，I2。这时 一个之前收到I1，I2，I3的客户端由于切换到副本后，相同的请求就只能看到I1，I2。
增加了延迟，限制了性能。
问 & 答
如果primary收到副本对于I3 ack确认后奔溃，会发生什么？
这时会切换到副本运行，而副本会执行I3命令，并返回给客户端。
如果primary在发出输出之后崩溃了怎么办？
副本会立即接管。
对于TCP传输：接收者将忽略重复的序列号。
对于磁盘：副本将相同的数据写入相同的块。
如果网络分区，primary和副本都认为彼此失活？
共享磁盘只允许唯一的一个primary。
为什么确定性的操作，在物理硬件上比虚拟机上更难？
虚拟机管理程序（hypervisor）模拟和控制硬件的许多操作，这些操作可能会导致primary和副本执行不同。例如定时中断(timing interrupts)
什么是虚拟机管理程序 (hypervisor) ?
管理程序是虚拟机系统的一部分，和虚拟机监视器（VMM）一样。
系统管理程序模拟计算机以及在其中运行的操作系统和程序。
在本文中，primary和副本是运行在虚拟机中的guest操作系统。而FT是实现每个虚拟机管理程序的一部分。
GFS和VMware FT均提供容错功能，谁更好？
FT更底层强大，对内存,网络包和磁盘提供了一种容错能力。可以使用它为所有运行在其上的服务透明地提供容错功能。
GFS仅提供存储容错功能。 由于GFS专用于特定的简单服务（存储），因此其复制比FT更有效。 例如，GFS不需要使中断在所有副本上的完全相同的指令处发生。
GFS是应用程序级别的具有容错能力的大型应用程序之一。
缓冲区如何帮助避免冲突
网络数据包或请求的磁盘块到达primary并且要复制到primary的内存时，
没有FT，相关硬件将数据复制到内存中，同时 软件正在执行。操作系统指令可以在DMA期间读取该内存。
由于冲突，在某一时刻，可能无法看到DMA的数据。因此可能出现由于primary与副本的时间不同，一个能看到，一个不能看到这个数据。
表现
logging带宽
直接反应磁盘读取率 + 网络输入率
大约18 Mbit/s for my-sql
比较慢,应用程序可以至少400 Mbps的速度读取磁盘
用途
关键但强度较低的服务，例如 名称服务器。
适用于软件行为不常发生改变的服务。
高吞吐量服务的主从复制
将应用程序主从状态机用于数据库等高吞吐量服。
状态只是DB，而不是全部的内存和磁盘。
事件是数据库命令（put或get），而不是数据包和中断。
更少的细粒度同步，更少的开销。
GFS使用应用程序级复制，与lab2相似。