分布式系统,程序语言,算法设计

MIT 6.824 2020 视频笔记四:VM-FT

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第四节课笔记,VM-FT。

备份——容错

失败(Failue)

如何定义?在其他电脑看来,停止对外提供服务。
通过备份/副本(Replication)
可以解决:宕机(fail-stop),比如 CPU 过热而关闭、主机或者网络断电、硬盘空间耗尽等问题。
不能解决:一些相关联(correlated,主副本机器会同时存在)的问题,比如软件 Bug、人为配置问题

前提

主从备份可以工作的一个假设是,主从机器的出错概率需要时独立的。
比如说:同一批次机器、同一个机架上的机器,出错概率就存在强正相关特性。

是否值当

需要对业务场景和所需费用考量,是否真的需要进行 Replica。比如银行数据就需要多备份,而课程网站可能并不需要。

作者:青藤木鸟 https://www.qtmuniao.com/2020/04/01/6-824-video-notes-4-vm-ft/, 转载请注明出处

Primary-Backup Paper

两种进行状态备份的方式:

  • 状态转移(State transfer)
    持续增量同步 Primary 的状态到 Backup,包括CPU、内存、IO设备等等;但是这些状态通常所占带宽很大,尤其是内存变化。
  • 冗余状态机(Replicated State Machine)
    将服务器看作是一个具有确定性状态的状态机,只要给定相同初始状态和同样顺序的确定输入,就能保持同样的状态。同步的是外部的事件/操作/输入;同步的内容通常较小,但是依赖主机的一些特性:比如指令执行的确定性(deterministic)。而在物理机上保证确定性很难,但是在 VM 上就简单的多,由于 hypervisor 有对 VM 有完全的控制权,因此可以通过某些手段来额外同步某些不确定性输入(比如类似随机数、系统时钟等)。

一般来说操作会比状态小的多,因此 Replicated State Machine 被采纳。

Q&A:

  1. 如果主从备份由于某种原因不一致了会怎么样?
    可以考虑 GFS 中,由于网络分区造成两个 chunkserver 都认为自己是 Primary 的例子。
  2. 如果指令中有一些类似于依赖于随机数的指令,Replicated State Machine 如何进行同步?
    这正是之前强调的需要依赖指令的确定性的意义所在。当然,也可以在遇到这种命令时,让 Backup 去直接接受 Primary 的执行结果。

此外,Replicated State Machine 需要机器为单核,因为在多核机器上,指令的执行顺序本身是不确定的。那对于多核机器如何做同步?State Transfer 。

pb-ft-configuration.png

挑战

  1. 需要同步什么状态?
  2. Primary 需要等 Backup吗?
  3. Primary 宕机时,如何进行切换?
  4. 在 Primary/Backup 宕机时,如何进行快速恢复。

同步状态的层级:

  1. 应用层(Application state)。如 GFS,更为高效,只需要发送高维操作即可,缺点是需要在应用层进行容错。
  2. 机器层(Machine level)。可以让运行在服务器上的应用无需改动而获取容错能力。但需要细粒度的同步机器事件(中断、DMA);并且需要修改机器底层实现以发送这些事件。

而 VM-FT 选择了后者,能力更强大,但也做出了更多牺牲。

VM-FT 系统使用一个额外的虚拟层 VMMonitor( hypervisor == monitor == VMM ),当 client 请求到达 Primary 时,VMMonitor 一方面向本机转发请求、一方面向 Backup 的 VMMonitor 同步请求。处理完请求得到结果时,Primary 的 VMMonitor 会回复 Client,而 Backup 的 VMMonitor 会丢弃 Backup 产生的回复。

使用两种方法来检测 Primary 和 Backup 的健康状况:

  1. 和 Primary/Backup 进行心跳。
  2. 监控 logging channel。

主从切换

如何实现主从间的切换?在 Primary 宕机后,Backup 声称具有 Primary 的 MAC 地址,然后让 ARP 缓存表过期,就将打向某个IP的流量从 Primary 切换到了 Backup。

切换后,原先的 Backup 成为新的 Primary,对外进行回复。然后利用 VMotion 的技术在和新 Primary 共享外存的地方启动一个副本,并且建立日志通道。

不确定性事件

都有哪些不确定性(Non-deterministic)操作(operations)和事件(events)?

  • 输入的不确定性。系统中断事件。
  • 奇怪指令。比如随机数、依赖时间戳的指令。
  • 多核。不同机器可能以不同的方式在多核上交替运行指令。

对于不确定性操作,需要保留充足的信息到日志通道中,以使 Backup 可以进行同样的状态改变,并且产生同样输出。对于不确定性事件,如时钟信号中断和 IO 完成中断,不仅需要记录事件本身,也要记录下事件发生的指令序列的位置,由此才能在 Backup 上确定性复现。

Logging Channel

为了进行容错(FT),我们使用日志条目(log entry )来记录 Primary 上发生的事件;但我们并没有将这些日志写到硬盘中,而是将其通过日志通道(logging channel)传送到 Backup 上进行实时确定性的重建(deterministic replay)。每个 LogEntry 可能包含以下数据:

  1. 指令编号
  2. 指令类型
  3. 数据

DMA

DMA能够直接将数据从网口拷贝到内存,而不经过CPU。这时需要 VMM 强行中断,拷贝来到的数据,模拟一个指令,并发送给 Backup。

OutPut rule

当 Primary 宕机时,其发送给 Backup 的最后一条指令也由于网络问题丢失了。当 Backup 接手时,如何处理该条指令丢失造成的不一致?
使用 Output Rule 保证。即 Primary 仅当在收到 Backup 该条指令的 ACK 时,才会将该指令结果发送给用户。当然,为缩短响应延迟,在 Backup 上,VMM 只需要将收到的指令缓存到 Buffer 中就可以回 ACK。而且,Primary 只是会延迟将回复发送给用户,以等待 Backup 的 ACK,但在这段等待时间内并不用真停止执行,毕竟网络请求回复是异步的,Primary 可以并行的做其他事情。

pb-ft-protocol.png

在 Primary 宕机后,Backup 接管时,可能会产生重复的结果。但是由于P/B 共用 TCP channel,SEQ 也会被重用,会在 Client 端作为重复TCP 帧被忽略,从而不会暴露到用户层面。

吞吐

如果 Primary 和 Backup 不在一个城市,每次通信都需要几ms,那么久很难构建高吞吐系统。

网络分区

如果 P/B 之前的网络断了,但是同时都可以和 client 通信,就发生了 split-brain。解决办法是引入一个第三方仲裁,来保存谁可以进行应答:比如使用一个 TAS(Test-and-Set Server) 或者一个共享外存。


欢迎关注公众号木鸟杂记,获取更多分布式系统文章。

wx-distributed-system-muniao-s.jpg