MIT 6.824 2018 Lec 4: Primary/Backup Replication

本篇文章主要是对阅读《The Design of a Practical System for Fault-Tolerant Virtual Machines》论文后做一个总结.

Primary/Backup Replication

这篇论文主要介绍了 VMware 实现的能提供容错虚拟机的企业级商用系统所涉及的技术和原理。所谓容错性,就是在出现故障时,服务能继续运行,用户不会感知到故障的存在,理想的容错服务有以下几个特性:

  • 可用性,在(某些)故障发生后,服务仍可用
  • 强一致性:对客户端来说,服务就好像运行在一台服务器上,不会有数据不一致的情况
  • 服务容错能力的实现对客户端和服务器上其他软件都是透明的
  • 高效


当然,分布式系统的容错性是相对而言的,不可能应对所有类型的错误,我们主要关注这几类故障的处理:

  • Fail-stop 故障,某个节点发生故障后,就停止运行,其他节点都能感知到这个节点的故障
  • Independent 故障
  • 网络传输丢失了一些/全部数据包
  • 网络分区(个人觉得翻译成“分裂”更好)


提高容错能力的核心思想:复制(Replication)

  • 每台服务器至少有一个副本
  • 每个副本都保持着能够运行服务的状态
  • 如果一个副本失败了,另一个副本继续工作


实现复制又需要考虑很多问题:

  • 服务器的哪些状态信息需要复制?
  • 在复制过程中,主服务器是否需要等待复制的完成?
  • 什么时候从主服务器切换到副本?
  • 在切换过程中异常是否可见?
  • 如何快速完成切换过程?


实现复制主要有两种方法:

  • 状态传输,主服务器执行服务任务,将最新状态传输给其他副本
  • 复制状态机,所有副本执行都执行所有操作,如果起始状态相同,所有操作相同,执行顺序相同,操作的结果是确定的,那么所有副本最终能保持在相同的状态


状态传输相对简单,但是需要传输的状态信息量可能很大,导致传输速度慢。

复制状态机较为复杂,但更高效,适合执行操作付出的代价小于传输大量状态数据的场景,论文中实现的 VMware vSphere Fault Tolerance (以下简称 VM-FT)就是采用的这个方法。

VM-FT 系统

VM-FT 的实现目标主要有三个:

  • 为服务器上的软件提供容错能力
  • 客户端不会感知到故障的存在
  • 不需要修改客户端或服务端的软件


主服务器(primary)和其他副本(backup)产生分歧(divergence)的意思就是,如果主服务器发生故障,客户端会从其他副本那里得到和主服务器上不一样的响应结果。

如果主服务器被客户端A锁定,那么服务器就会拒绝客户端B的请求,但是如果副本不知道主服务器被客户端A锁定了,那么当主服务器发生故障后,副本会允许被客户端B锁定,从而拒绝客户端A的请求(客户端A:???)

如果服务器被锁定的时限为一分钟,假设一分钟的锁定时间快到了,此时是客户端A锁定了主服务器,主服务器可能在时钟中断前收到客户端B的请求,于是拒绝了该请求,而其他副本可能在时钟中断后收到客户端B的请求,于是接收了该请求。

以上是两种产生分歧的情况,因此要想不产生分歧,副本必须在指令流相同的位置以相同的顺序观察到相同的事件才行。

中断

VM-FT 为了保证主服务器和副本在执行过程中相同的位置得到中断,处理流程如下,以时钟中断为例:

主服务器:

  • FT 暂时保留时钟中断
  • FT 从 CPU 读取指令编号,设为 X
  • FT 发送“时钟中断在指令X处”的信息到 logging channel
  • FT 将时钟中断分发给主服务器


副本:

  • 忽略自己本地的定时器
  • FT 在副本执行指令X之前得到 log entry
  • FT 在指令X处模拟一个时钟中断

磁盘/网络输入

主服务器:

  • FT 告诉硬件直接从内存中将数据读取到 FT 的 “bounce buffer”
  • 硬件要执行 DMA 命令后,产生中断
  • FT 得到中断
  • FT 暂停主服务器
  • FT 将 “bounce buffer” 拷贝到主服务器的内存中
  • FT 在主服务器中模拟一个中断
  • FT 将数据和指令编号发送到副本


副本:

  • FT 从日志流中得到数据和指令编号
  • FT 告诉 CPU 在指令X处产生中断
  • FT 在中断期间拷贝数据


为什么要使用 bounce buffer 呢?因为我们希望在主服务器和副本的执行过程中,数据载入到内存的时间点是相同的,否则可能会产生分歧。

这里还要注意,副本必须在得到第一个 log entry 后才能开始执行命令,这样就能保证副本的执行过程始终比主服务器要慢一个事件,同理,在重启副本前也要先得到下一个 log entry 才能重启。如果不这样做,假设主服务器在指令X后得到中断或者输入,而副本在得到输入时已经执行完指令X(正在执行指令X后的指令),这样副本就不能正确地处理输入。

磁盘/网络输出

主服务器和副本执行指令后有相同的结果,但是只有主服务器的结果会输出,副本的结果会被丢弃。

根据 Output Rule,主服务器在输出结果前,必须先告知副本,并且要等到副本返回确认已收到 log entry 的消息后,再输出结果。

如果没有 Output Rule,假设主服务器在得到输入I1 I2 I3后,直接输出结果,此时,副本只收到了I1 I2I3在网络传输过程中丢失了,主服务器又碰巧发生故障不能再重新发送I3,那么副本就没有机会得到输入I3,但主服务器已经输出了I1 I2 I3的执行结果,某些客户端得到了这个输出结果,当再次请求该服务时,由于副本没有收到I3,不能输出相同的结果,导致异常。

总结

VM-FT 是 Primary-backup replication 的一个很好的范例,是系统层面的复制状态机,开销较大,适合重要但低强度的服务,比如域名服务器。

而数据库则是应用层面的复制状态机,开销较小,适合高吞吐量的应用,复制到状态仅仅是数据库,不用涉及内存和磁盘,关心的事件仅仅是数据库命令,不需要关心数据包和中断,GFS 也是应用层面的复制。


版权声明

作者:萝卜姓胡
许可协议:Creative Commons Attribution-ShareAlike 4.0 International License
本文永久链接:http://hw2007.com/2018/11/29/MIT-6-824-2018-Lec-4-Primary-Backup-Replication/