Abstract
想要让应用能够躲过硬件故障是一项非常昂贵的任务，因为这通常意味着对软件进行重构，使它包含复杂的恢复逻辑的同时需要部署专用的硬件，而这些对于提升大型的或者遗留的应用的可靠性是巨大的障碍。我们接下来将描述一个通用的高可用服务，它能够为那些已经存在并且未经修改的软件，在其运行的物理机故障的时候，提供保护。Remus提供了非常强的容错能力，它可以在发生故障的时候，让一个正在运行的系统无缝迁移到另一台物理机上，只需要短暂的停机时间，并且完全保留所有的主机状态，例如网络连接等等。我们采用的方法是将被保护的软件封装在一台虚拟机中，同时以高达每秒四次的频率将改变的状态异步地传送到backup上，并且让当前虚拟机的运行稍稍领先于备份的系统状态。
1 Introduction
高可用系统是一个非常宽泛的概念。但是对于可靠性的要求是非常普遍的，即使是对于那些只有适度资源的系统设计者。不幸的是，想达到高可用是非常困难的----因为这要求系统维护冗余组件并且在出现故障的时候切换到backup中。那些用于保护现代服务器的商业的高可用系统一般都会使用特殊的硬件，或者订制的软件，或者两者都有。不论哪种方案，想要让普通的服务器透明地渡过故障都太过复杂和昂贵了。
本篇论文介绍的Remus软件系统，在普通硬件上提供了操作系统以及应用无关的高可用性。我们利用了虚拟化当中的虚拟机热迁移技术，并且对它进行了扩展，从而能在两台物理机之间以非常高的频率复制整个操作系统的快照，通常能达到每25ms一次。通过这种技术，我们的系统将虚拟机的运行离散化为一系列的快照。外部的输出，特指网络包的发送在制造它的系统状态还没有被复制之前是不能发出去的。
虚拟化技术让创建整个运行时机器的拷贝成为可能，但是它并没有保证整个过程是高效的。同步地传输每一次状态的改变是不现实的；因为复制操作会占用网络设备大量的带宽。事实上，我们允许先运行，并且异步地做checkpoint和replicate，而在checkpoint被提交之前，系统的状态对于外部是不可见的。我们通过只让系统运行数十毫秒来实现高速的复制操作。
本篇论文的贡献主要是提供了一个实例。复制整个系统是一个提供高可用性的众所周知的方法。但是相比较之下，针对应用的checkpoint操作只需要复制一些相关的数据。我们的方法可能将HA带给大众，作为一个提供虚拟机的平台服务。该系统可以提供和商用解决方案同样甚至更好的保护，并且没有硬件和软件的约束。很多现有的系统只对持久化的存储做镜像，并且要求应用从crash-consistent persistent 状态下恢复。相反，Remus能够保证，除了在primary崩溃的那个时刻，没有其他任何的可见状态会丢失。
1.1 Goals
Remus的目标是希望能在中低端系统上获得mission-cirtical availability。通过简化配置并且让许多的服务器合并到少数的物理机中，虚拟化让这些系统前所未有的流行。然而，在合并带来好处的同时，也增加了硬件故障带来的隐患。Remus通过商品化高可用性来解决这个问题作为由虚拟化平台本身提供的服务，为各个虚拟机的管理员提供工具，以减轻与虚拟化相关的风险。
Remus的实现是基于以下几个高水平的目标：
Generality：定制化一个软件来支持高可用的昂贵程度是不能接受的，更不用说一个组织可能需要依赖各种各样的软件。为了解决这个问题，高可用必须作为一种底层的服务，以一种通用的机制出现，而不用关注被保护的应用以及在何种硬件上运行。
Transparency：在大多数现实情况下，操作系统和应用的源码是不能获取并修改的。为了对各种应用实现最大程度的支持，高可用不能要求通过修改操作系统或者应用的源码来提供一些功能，例如故障检测或状态恢复。
Seamless failure recovery：当发生单机故障的时候，任何外部可见的状态都不能丢失。另外，故障恢复必须非常快，从外界用户的角度来看好像仅仅只是发生了短暂的丢包。已经建立的TCP连接不能丢失或重置。
这都是非常崇高的目标，需要提供远远高于普通HA系统的保护。普通的HA系统仅仅只是基于异步的存储镜像以及特定于某些应用的恢复代码。同时，希望实现这种级别的可用性并且不能修改虚拟机中的代码，需要非常粗粒度的方式来解决问题。该系统最终以及普标的一个目标是，在实现上述目标的同时，能够提供可部署级别的性能，即使是在面对当今服务器硬件中非常普遍的SMP的时候。
1.2 Approach
Remus运行以active-passive模式运行的成对的服务器中。我们利用三种技术来解决这种方法固有的问题。首先，我们将系统构建在虚拟化基础设置之上，从而能实现整个系统的复制。接着，我们通过speculative execution来提高系统的性能，将外部输出从同步点中解耦出来。这让primary server依然保持可用状态，而与replicated server的同步则异步执行。Remus基本的执行步骤如Figure1 所示。
VM-based whole-system replication.Hypervisor之前就已经在HA系统中使用了。在那里，虚拟化用于以lock-step的方式运行系统对，并且还提供了一些额外的支持使得在一对物理机上运行的虚拟机会沿着相同的路径执行：外部的事件会被同时插入到primary和fallback虚拟机中，从而让它们处于完全一致的状态。强制实现这样的确定性执行会有两个问题。首先，这要求高度特定的架构，从而让系统能对被执行的指令集和外部事件的来源有完全的理解。其次，当在多处理器系统上执行的时候会产生无法接受的开销，因为其中处理器通过共享内存的交互必须被精确地处理和传播。
Speculative execution.复制可以通过复制系统的状态或者确定性地重复输入来实现。我们认为后者对于实时的操作是不现实的，特别在多处理器环境下。因此，Remus并不尝试让计算确定化----还有一种真实存在的可能是系统在给定checkpoint产生的输出，会和系统回滚会checkpoint，然后再重复输入再产生的输出不同。然而，replica的状态必须和primary同步只有当primary的输出已经在外部可见的时候。与其让正常输出流导致同步必须进行，我们还不如对输出进行缓存直到一个合适的时间点，并且在同步点之前先进行一些计算。这事实上是在输出延迟和运行开销之间做了一次权衡，而中间的度则要靠管理员来控制了。
Asychronous replication.通过在primary server上缓存输出让复制操作得以异步执行。primary能够在机器状态被获取之后继续执行，而不用等待获得另一端的确认。将正常的执行和复制操作重叠在一起会大大提高性能。这保证了在每个数十毫秒就执行一次checkpoint的情况下，依然保持非常高效的操作。
2 Design and Implementation
Figure 2显示了我们系统的架构图。我们在开始的时候先将机器封装在一个受保护的虚拟机中。我们的实现基于Xen Virtual machine monitor并且对它的热迁移部分进行了扩展从而支持更佳粒度的checkpoints。我们的checkpoint的初始的一部分子集已经被并入Xen的源代码了。
Remus通过将频繁地对active VM做checkpoints并将它传送到作为backup的物理机来实现高可用。在backup中，VM镜像被存储在内存中，一旦检测到active host发生了故障就马上开始执行。因为backup只是和primary阶段性一致，因此所有的网络输出都必须 缓存起来，直到和backup进行了同步为止。当一个完整的，一致的镜像被backup host接收之后，缓存中的数据才能被发送给外部的客户端。checkpoint，buffer再release这整个周期运行地非常快。我们的基准测试结果在40次每秒，每25毫秒就对整个机器进行了checkpoint包括网络和磁盘状态的变化。
和对网络进行传输不同，磁盘的状态对外是不可见的。但是同样，它必须作为一个完整的，一致的快照被发送到远端的host。为了对磁盘进行备份，对primary磁盘所有的写操作都必须异步地发送到backup，但是它们会被缓存在RAM中，直到内存的checkpoint到达。当primary确认发出了完整的镜像之后，它就会释放缓存的网络包，并将缓存的磁盘内容写入backup磁盘。
值得注意的是虚拟机在没有发生故障之前是不会在backup host上运行的。backup只是简单地作为存放active VM快照的容器。这对于backup host资源的消耗是相对较小的，这允许它以N-to-1的形式并行地保护运行在多个physical hosts上的虚拟机。这样的配置方式给了管理员更多的自由去平衡冗余备份和资源消耗之间的关系。
2.1 Failure model
Remus 提供了以下的特性：
1、单个host的fail-stop故障都是可以忍受的
2、假如primary和backup同时发生了故障，那么受保护系统的数据将会处于crash-consistent状态
3、在相关系统的状态没有被提交到备份之前，不会有任何外部可见的输出
我们的目标是实现单个physical host从fail-stop故障的完全透明恢复。该系统一个吸引人的特点是它的高可用性能轻易地改装适配到现有的运行在商用机器上的软件。通过使用一对商用主机，通过千兆以太网相连，并且能从任何组件的故障中恢复过来。通过结合块设备的状态复制协议，避免了使用昂贵的，基于共享网络的磁盘镜像。
我们并不追求从软件错误或者非fail-stop的状态中恢复。因为这种方法对完整的系统状态进行了备份，所以应用的错误同样会备份到backup中。这是提供透明性和通用性的必然结果。
我们的failure model和现在商用HA对虚拟机提供的保护相同。但是相比于Remus提供的保护度，这些产品还是要差很多：现有的商业产品对于physical host的故障，仅仅只是基于crash-consistent的磁盘状态在另一个host上重启一个虚拟机。我们从故障中恢复的时间尺度和热迁移是相同的，并且能让虚拟机继续运行，网络保持连接。对外暴露的状态不会丢失并且磁盘不会损坏。
2.2 Pipelined Checkpoints
对运行的虚拟机每秒做几次checkpoint会对系统造成非常大的压力。Remus通过流水化checkpoint操作来解决。我们使用epoch-based系统，对正在执行的虚拟机做短暂的暂停，原子的捕获状态的改变，当状态被传送到backup之后在释放外部输出。回到Figure 1，整个过程可以被分割成四个阶段：（1）暂停正在运行的虚拟机并且将所有的状态变化拷贝到缓存中。这其实就是热迁移中的stop-and-copy的过程。不过正如后文中会描述的那样，它需要针对高频率的checkpoint的优化。随着状态的改变被保存在缓存中，虚拟机开始继续往前执行。（2）缓存的状态被传送并且存放在backup host的内存中。（3）直到所有的状态数据被接收，primary确认checkpoint完成。最后（4）缓存的网络输出被释放。
这种方法的结果是在checkpoint的边界对执行进行了有效的离散化。backup对于完整的快照的确认出发了被缓存的网络输出的释放并且代表了进入新的epoch的完整过渡。
2.3 Memory and CPU
checkpoint是在Xen已有的热迁移机制上实现的。通过热迁移，虚拟机可以被移动到另一台物理主机上，并且中间只有非常短暂的服务中断。为了实现这个目标，内存不断被拷贝到新的主机上，而虚拟机依然在旧的主机上运行。在热迁移期间，对内存的写操作会被截获，脏页会被不断地循环拷贝到新的主机上。经过一定数目的间隔之后，或者在虚拟机写内存的速度和迁移进程拷贝发送的速度差不多时，虚拟机就被挂起了，之后剩余的脏内存连带当前的CPU状态都被拷贝转发了。这时，目的主机的镜像将被激活。而总的停机时间决定于在虚拟机停机时拷贝的内存数量，一般总是小于100ms。总的热迁移时间和虚拟机总的内存和它的可写工作集（指在虚拟机运行期间频繁更改的那些页）有关。
Xen通过一种叫影子页表（shadow page table）的技术来追踪虚拟机写内存的情况。当该模式可用的时候，VMM会维护一个虚拟机页表的私有版并将它暴露给硬件MMU。页保护是用于获取虚拟机对它内部页表的访问操作，从而能让hypervisor获取这些更新，在适当的时候将这些信息传递给shadow page table。
对于热迁移，这项技术被扩展到透明地将所有虚拟机的内存标记为只读，从而hypervisor能记录虚拟机对内存的所有写操作，并且维护了一张从上一轮以来所有被弄脏的页的映射表。在每一轮中，迁移进程原子地对这种映射表进行读取和重置，迭代的迁移进程的工作包括追踪脏页，直到它不再产生。如上所述，迁移进程最终会停止虚拟机的执行并且进入最终的"stop-and-copy"轮，在该轮中所有剩余的页都会被传送并且虚拟机会在目的主机继续执行。
Remus通过重复执行热迁移的最后阶段来实现checkpoint：每个epoch,虚拟机都会被暂停，同时内存和CPU状态的改变会被拷贝到缓存中。之后，虚拟机继续在当前主机执行，而不是在目的主机。为了提供足够好的性能并且确保在远端主机上始终有一个一致的镜像，我们需要对迁移进程做一些修改。
Migration enhancements.在热迁移中，虚拟机内存需要被迭代拷贝很多轮，可能会消耗几分钟的执行时间；而由stop-and-copy造成的服务中断造成的损耗则不是很大。但在频繁地进行checkpoint的时候却不是这样的，每次的checkpoint仅仅只是迁移过程中最后的stop-and-copy，所以对于减少checkpoint的损耗来说，这是关键。从对Xen的checkpoint代码的测试来看，虚拟机在停机时损耗的时间主要是不被调度，主要原因是用于给虚拟机和domain 0提供交互的xenstore daemon的实现不够高效。
Remus从两方面对checkpoint进行了优化：首先，减少了挂起和重新执行虚拟机的进程间请求数目。二、将xenstore在挂起/恢复过程中彻底移除。在原始的代码中，当迁移进程想要暂停虚拟机时，它要给xend（VM management daemon）发送一个信息。Xend转而给xenstore写了一个信息，xenstore又通过一个event channel(一个虚拟中断)进行停机操作。虚拟机在停机之前做的最后一个操作是做一个hypercall，它对domain进行了重新的调度，从而让Xen给xenstore发送了一个信息，之后，xen又给xend发送了一个中断，最后控制权被转交回迁移进程。整个过程的执行时间并不确定——一般延时在30到40ms，但是在有些时候，我们发现延时会长达500ms。
Remus通过在虚拟机中专门创建一个event channel用于接受停机请求，从而让迁移进程能直接调用来简化流程。另外，还创建了一个新的hypercall，它能够让进程注册一个event channel用于提醒它们虚拟机停机完成。这两种通信机制大概减少了100微秒的停机时间——相比于之前的实现提高了两个数量级。
除了这些交互方式的改变，我们还提高了内存拷贝进程的效率。首先，我们快速筛选出干净的页面，因为在高速的checkpoint操作中，多数的内存是不变的。二、我们将虚拟机所有的物理内存都映射到备份进程中，而不是在每个epoch进行映射或者解除映射的操作——我们发现对foreign pages进行映射和拷贝的时间是基本相等的。
Checkpoint support.在Xen实现对checkpoint的支持需要对已有的suspend-to-disk和热迁移代码做两个主要的修改。首先，在被暂停之后需要添加对domain重新执行的支持。Xen之前不允许"live checkpoints"而是会在状态写出之后就销毁虚拟机。第二、停机程序从之前的one-shot procedure变成了一个daemon process。这允许checkpoint在第一次操作之后，只需要对新的脏的内存进行拷贝。
另外还需要两个基本的改变来支持虚拟机的恢复执行。首先，新建一个hypercall，重新标记该domain为可调度的（Xen会将暂停的domain从调度集合中删除，因为之前它们在状态被备份之后会删除掉）。为了能重新监视xenstore，另外一个相似的操作也是必要的。
Asychronous transmission.为了让虚拟机能尽快恢复执行，需要修改迁移进程在domain暂停的时候，将脏页写入staging buffer而不是直接将它们写向网络。这直接导致了吞吐量的提升，在每秒20次checkpoint的情况下，Section 3.3中的核心基准测试所需的时间大概减少了10%。
Guest modifications.如上所述，Xen中的半虚拟化的虚拟机会包含一个suspend handler，它会在接收一个suspend request之后清除设备状态。除了在本节之前部分描述的对于notification的优化，suspend request handler同样需要被修改从而减少停机操作之前的工作量。在之前的代码中，停机会引起所有设备的断开操作，并且会拔下除了CPU以外的所有设备。而在修改之后，这项工作将推迟到domain在其他主机重新运行之后执行。这些修改在Xen版本3.1.0之后可用。
对于正确性来说，这些改变都不像必要的，但是却能极大地提高checkpoint的性能，包括对一些guest kernel的修改。对于半虚拟化的suspend handler，总共的修改不到100行代码。如上所述，这些修改对于非半虚拟化的虚拟机都不是必要的。
2.4 Networking buffering
大多数网络对于可靠的数据传输都是不可靠的。因此基于网络的应用要么能忍受网络包的丢失，重复以及乱序，或者能够使用更高层的协议，例如像TCP那样能提供很强的服务可靠性。这一事实简化了网络缓存的问题：输出的网络包并不需要备份，因为它们的丢失会被认为是传输网络的故障并且不会影响protected state的正确性。然而将输出的网络包缓存起来直到checkpoint state被提交为backup是非常重要的；如果primary故障了，这些代表speculative state的包就全都丢失了。
Figure 3描述了我们延阻speculative network state的机制。Inbound traffic会立即传送给protected host，但是从上次checkpoint以来产生的outbound packets会进入缓存，直到当前的状态被checkpoint并且该checkpoint已经被backup端接受。我们在domain 0中的guest's domain的网卡以linux queue disciplines的形式实现缓存。在guest运行在checkpoint之后重新开始执行之前，network buffer会收到一个CHECKPOINT message，它会在outbound queue中插入一个barrier，从而防止它之后的包被发送出去，直到接收到相应的release message为止。当guest checkpoint已经被backup接收之后，缓存会收到一个RELEASE message，直到这时，缓存的网络包才会被发出。
但是该实现存在两个问题。一、在linux中，queueing disciplines只处理outgoing traffic。在Xen中，guest的网络接口由在guest中的frontend device和在domain 0中相应的backend device组成。在guest中的outbound traffic在domain 0中就变成了inbound traffic。因此，为了缓存traffic，我们通过一个叫intermediate queueing device将inbound traffic转换为outbound traffic。该模块一开始是设计成通过iptables工作在IP层的，但是把它扩展成工作在briding layer并不是一件困难的事情，之后我们就能使用它来提供虚拟机的网络。
第二个问题是由于Xen虚拟网络设备的实现。出于性能的考虑，outbound networking traffic使用的内存并不会在guest domain和domain 0之间拷贝，而是两者共享的。但是在任意时刻，只有一小部分页能够被共享。如果在guest和domain 0传输数据只需要很短的时间，那么造成的限制是观察不到的。不幸的是，network output buffer会导致信息被延时很长时间，这会导致guest的网络设备在传输了非常小的traffic之后就会被阻塞。所以在缓存message的时候，我们先将它们存入本地内存，然后再将它映射到共享数据中。
2.5 Disk buffering
磁盘代表了一种和网卡截然不同的挑战，主要是因为通常它们被预期要提供更高的可用性。当一次写操作被磁盘接收之后，应用或者文件系统就希望能对该数据进行恢复，即使在写操作完成之后马上就发生了电源故障。尽管Remus被设计为能从单机故障中恢复，但是它必须要提供crash consistency即使primary和backup都发生了故障。另外，既然是提供通用的系统，那么就不能使用专为HA应用设计的昂贵的镜像存储硬件。因此，Remus在backup host中维护了完整的当前虚拟机磁盘的镜像。在认可来自priamry的checkpoint之前，primary当前磁盘的状态就已经被镜像到backup host了。一旦checkpoint被acknowledged之后，就将缓存在backup host内存中的primary的磁盘状态就被写入磁盘。Figure 4显示了磁盘备份机制的高层视图。
和Section 2.3中描述的内存备份子系统类似，当前运行的虚拟机写磁盘的方式是write-through：它们直接被写入primary磁盘镜像中，并且被异步地映射到backup的内存缓存中。这种方法会带来以下两种好处。首先，这保证了当前运行虚拟机的磁盘镜像始终处于crash consistent的状态。该磁盘在发生故障时将反映外部可见的虚拟机的crashed state。（外部可见的虚拟机存放在primary host中，如果primary host没有发生故障或者backup在激活前就发生了故障，否则存放在backup中）二、直接写磁盘准确地显示了物理设备的延时和吞吐量特性。这显而易见的特性具有相当的价值：准确地描述磁盘的响应是一个非常微妙的问题。正如我们在早期版本中遇到的，先将primary虚拟机的内存写请求先存放在磁盘缓存中直到checkpoint提交。这样的方法不管是缓冲区写，低于将数据写入磁盘的表示时间并且允许speculating虚拟机竞争执行，还是保守地高估写延时导致性能的损失。模型化磁盘访问时间是一个巨大的挑战，我们的实现通过保留磁盘到它客户端虚拟机的直接反馈来避免这个问题。
当backup确认收到了checkpoint之后，磁盘的更新就完全存放在内存中了。在完整的checkpoint接收到之前，磁盘的状态是不能被改变的，因为这会对backup回滚到上一个完整的checkpoint造成影响。一旦checkpoint被确认以后，缓存的磁盘请求就会写入磁盘。当发生故障时，Remus会等待直到所有缓存的写请求被执行，然后在恢复执行。虽然backup可以直接开始执行通过将request buffer作为物理磁盘的一个覆盖，但这将违反提交给protected VM的磁盘语义。如果backup在激活之后故障了，但是数据还没有完全写入磁盘，那么磁盘的状态就不是crash consistent的。
在任意时刻，Remus管理的两个磁盘镜像都只有一个是真正正确的。而这对于从多主机的崩溃中恢复是非常重要的。这一特性是通过backup磁盘中的activation record实现的，它会在最近的磁盘缓存都完全写入磁盘并且在backup虚拟机开始执行之前被写入。当从多主机故障中恢复时，这个record可以被用来识别正确的并且crash consistent的磁盘。
磁盘缓存是通过Xen的block tap模块实现的。block tap允许处于privileged domain中的进程将自己插入guest虚拟机中的front disk device和真正处理请求的backend device之间。该缓存模块来自protected VM的写请求，并且将它们映射到backup相应的模块中。该模块执行上文所描述的checkpoint协议，之后如果primary发生故障，它会在backup执行前将自己从磁盘的请求路径上清除。
2.6 Detecting Failure
Remus的目标是在普通硬件和不修改受保护应用的前提下，使用通用和透明的方法提供高可用性。我们现在只是在checkpoint流程中简单地插入一个故障检测器：如果backup对于提交请求的响应延时了，那么primary就会认为backup已经崩溃了并且不能提供保护了。同样，来自primary的checkpoint发生超时会让backup认为primary已经崩溃了并且会从最近的checkpoint开始重新执行。
整个系统被配置成使用一对bonded network interface，并且两台物理主机在保护的NIC中，使用一对Ethernet crossover cables(或者switches)连接在一起。假如这两个网络路径都故障了，Remus目前不提供机制来屏蔽执行。传统的用于解决隔离的技术是难以运用到双主机的配置中的。在这个例子中我们感觉到了这一点，我们已经将Remus设计到了普通商用硬件的边缘了。
![[翻译]LSP程序的分类](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
