Readings - Practical System for Fault-Tolerant Virtual Machines Fault-Tolerant Virtual Machines论文

这篇论文讨论的主从复制与常见的相比，非常极端和雄心勃勃，论文基于vm构建了一个os级别的主从复制系统，较为细致的讨论了主从复制的设计和实现。

介绍

主从复制是实现server容错的常用方法，如果primary挂了，backup可以继续提供服务。将primary的全量数据同步到backup是比较耗费带宽的操作。更好的方法是将server视为确定状态机，基本思路是把primary和backup置为相同的初始状态，并保证二者都能以相同的顺序收到相同的输入。由于存在某些操作是非确定的（如：中断和获得当前时间），因此还需要额外的协同。

FT协议

Deterministic Replay

为了实现在backup进行replay，需要保证：

1. 正确的捕获所有输入和非确定的操作，以保证backup的确定性执行。
2. 在backup上正确的replay。
3. 对性能没有影响。

论文中关于非确定的操作，零零散散在不少地方提到，不过总结下来其实就是，这个操作不是pure function，结果受除输入的外部状态影响。更具体的就是，非确定操作使用到的资源是与其他（来自vm或hypervisor）的进程共享的，竞争导致了非确定的结果。

在多核系统上，上述的竞争会更复杂，这也是为什么论文没有在多核系统上实现的原因。

FT协议

primary的日志实时的通过logging channel发送到backup。为了保证在切换的时候，backup能够以与primary相同状态进行服务，需要满足：

Output Requirement：如果primary失败，backup接替了primary，backup的执行需要保证所有的输出都与primary的一致。

只要满足Output Requirement，在发生主从切换的时候，client就感知不到打断和不一致。为了保证Output Requirement，需要backup在收到能够产生那个output的input之前，primary推迟输出，也就是下面的规则：

Output Rule：只有当backup收到能够产生一个output的log，并返回ack（表示已经存入log buffer）给primary，primary才能输出。

除了VM-FT有，在其他的多副本系统上都以某种形式出现着。

primary等待ack不必阻塞系统当前的执行。

检测和响应失败

检测失败：

• server之间的heartbeat
• logging channel的traffic是否一直存在

如何避免split-brain：

• 共享磁盘存储，原子的检测标志位

实现

FT VM启动

• 使用基于VMware VMotion实现的FT VMotion完成clone，primary的中断小于1s。
• 使用VMware vShpere实现的集群服务来选择最佳server创建backup。

logging channel管理

log buffer的局限： primary（或backup）的log buffer满了（或空了），primary（或backup）需要等待至log buffer可用为止，此时会暂停对client的服务。

主从切换的时间=检测primary失败的时间+backup消费log buffer的时间，为了减少切换的时间，在backup无法及时消费log的时候，会减慢primary的速度（限制CPU）。

FT VM上的操作

除VMotion外的所有运维操作（例如：调整cpu限制），都必须在primary上完成，然后通过特殊的日志项目发送到backup。

关于磁盘io的实现问题

1. 磁盘访问时的竞争会导致非确定的操作。
   • 检测这样的io竞争，并在primary和backup上以相同顺序执行。
2. 使用DMA时，对磁盘和内存的访问会导致非确定的操作。
   • 对磁盘的读写，改为读写bounce buffer。
   • 只有当数据全部读到buffer以后，FT才会从读指令处恢复primary/backup的执行，避免二者出现差异（如果直接依赖DMA读取，primary和backup可能会在不可预知的时间点发生缺页中断，从而导致不一致）。
3. primary在磁盘io完成前就挂了。
   • backup切换为primary以后，无从得知io是否已经完成。FT会在backup上重试（前两点已经消除了导致非确定结果的操作）未完成的io操作。
   • 那么如何判断未完成的io操作是哪些？io完成以后，设备会产生一个中断，如果某个io log缺少相应的中断，那么就需要重试。
4. primary在磁盘io完成后挂了
   • backup同样无从得知io是否已经完成。此时重新执行写磁盘是幂等的（而对于网络io，tcp会忽略重复的包）。

关于网络io的实现问题

hypervisor对vm buffer的更新导致了非确定操作，改为由vm触发hypervisor的中断，并记录到log。

其他设计

非共享磁盘

优势：

• 磁盘作为vm的内部状态，primary写磁盘时不必等待backup的ack。

缺点：

• backup失败、执行FT VMotion时，需要同步磁盘数据。
• 需要使用其他方法来解决split-brain，例如：另外一个server作为共享存储；多个机器进行投票选主。

backup上执行read

在从执行read，论文考虑的点并不是可以增加系统的read上限，而是考虑不发送read log可以减少logging channel的带宽。

具体看在backup上执行read，需要注意的点是：

• 如果primary成功，backup失败，backup需要重试，直到成功。
• 如果primary失败，那么尝试读取的内存必须发送到backup。
• 如果primary执行了读，然后是写，那么在backup也必须按照这个顺序来执行。

Lecture

Fault tolerance

理想的特性

• 可用性
• 强一致性
• 对client和server software透明
• 高效

容错，容什么错？

• Fail-stop failures
• Independent failures
• Network drops some/all packets
• Network partition

不包括：

• Incorrect execution
• Correlated failures
• Configuration errors
• Malice

Fault tolerant MapReduce master

lab 1中的woker由于是无状态的，且mapper和reducer执行的都是pure function，因此实现容错很简单。

master实现容错，需要考虑：

• 需要复制什么状态？应用程序级？指令级？（woker list、完成的job、空闲的worker、tcp连接状态、程序memory和stack、cpu寄存器？）
• primary是否需要等待backup？
• 什么时候切换到backup？
• 切换时是否能被观察到？
• 如何快速的切换？

主要方法有

1. State transfer，简单，但是state可能会很大，传输很慢
   • 主副本执行服务
   • primary把新状态发送到backup
2. Replicated state machine，高效但复杂
   • 所有副本执行所有的操作
   • 如果所有副本有相同的起始状态、相同的操作、相同的顺序、deterministic，那么就会有相同的最终状态
   • 例如：VM-FT，GFS

VM-FT

VM-FT是一个replicated state machine。

为了避免primary和backup出现差异，backup必须在指令流的相同位置、以相同的顺序看到相同事件。对于普通的指令，这个是比较容易实现的。FT对中断和磁盘/网络io会做特殊的处理。

例如：时钟中断

FT的有缺点

适用场景

1. 重要且低延迟的服务，例如：name server。
2. 不便于修改的服务。

不适用的情况

1. 高吞吐量的服务
   • state仅仅是应用程序级别的，降低了开销，实现更高的性能。
   • 例如：GFS适用应用程序级别的state。

Reference

1. FAILURE MODES IN DISTRIBUTED SYSTEMS