虚拟机主从复制-MIT 6.824 lec4
顶顶大名的6.824上了第四节, 感觉还是有很大收获的. 这门课给我感觉还是偏实践的方式来教学, 给的论文和上课的例子都是工业界著名的实现. 从实现中看到分布式系统的设计思想还是蛮容易接受的, 风格和之前看 NA Lynch的 Distributed algorithms, 前者具体而实践化, 后者抽象且理论, 非常烧脑: IO automata的模型看得我怀疑人生… 不过我感觉理论的学习至少能让我知其所以然, 而且我个人感觉可靠的分布式系统不是靠复杂的, 方方面面的测试来保证质量, 而是严谨的数学推导.
今天记录和归纳下我肤浅的理解吧, 作为一个巩固, 也希望我过一阵子在看我这篇文章觉得我是个傻逼
论文是
Scales, D. J., Nelson, M., & Venkitachalam, G. (2010). The design of a practical system for fault-tolerant virtual machines. ACM SIGOPS Operating Systems Review, 44(4), 30-39.
系统模型
讨论一个具体的分布式系统前我们必须明确下这个系统的模型. 特别是通信模型:
- 消息channel是异步的
- 消息是有序的
- 消息不会丢
- Fail-Stop model
今天讨论的是replication 解决的是Fail-Stop的错误模型 Fail Stop:
- 当一个机器出错了, 那么他停止执行
- 当一个Failure终究会被其他机器所发现
- 其他机器不会错误地以为某个机器挂了(其实没挂)
怎样让其他机器知道某个机器挂了呢? Heartbeat + timeout, 但是这个并不能百分百可靠, 网络可以暂时不通, 超时了, 这时候就错误认为对方挂掉…设置一个超大的timeout或许能保证99.99999的情况是对的 但不是绝对正确. 这就是分布式系统的难点所在了, 你需要时间来做一些判断, 而时间又不是可靠的衡量标准. 所以我们现实生活中并没有完美的Fail-Stop Failure, 但是在理论中我们不妨假设有某种神秘力量告诉其他节点: Something is wrong. 除开fail-stop模型, 可能还有的是byzantine fault, 就是假设当机器出错后, 它可能作出任意的行为, 甚至不排除这个机器会做malicious的行为来破坏整个系统的一致性, 这种错误一般就是硬件层次上的错误…虽说是小概率事件, 但是之前看到一篇论文说出现过 在ecc内存中出现两个bit flip导致系统崩溃的案例… 针对于没有完美的fail stop情况, 还有一种模型Crash Failure: 这里允许机器错误地认为对方挂掉..具体我就不懂了 以后碰到再看
这篇文章解决的问题是单线程的虚拟机的primary backup replication, 就是beckup被动地接受primary送来的更新状态信息, 与之相对的还有 state machine replication, 其中client的消息会被发到每个replica上. 我们希望当primary挂掉时候, backup能无缝地接过重担, 并且外部系统并不能区分 是否primary有改变. 不能区分变化这种思想在分布式系统里还挺常见的 在分布式snapshot算法里, 合法的一个瞬时全局状态就是属于一个等价类 这个等价类里所有的瞬时全局状态, 对于后边的执行, 都不能被区分开来…
Deterministic Replay
在IO automata模型里 一个io automata的状态改变当且仅当它接受了输入. 同理primary在运行的同时, 它的输入是决定它状态改变的最基本的触发点, 这里输入回到论文应用中就是收到网络packet, 这些packets会被hypervisor给捕获并且原封不动地丢给backup. 除了这些, 所有non-deterministic操作都会被记录, 让backup能够正确的重播. non-deterministic操作可能是观看当前时间, 生成一个随机数啥的. 除此之外, 系统中断发生的时间点也会影响虚拟机的状态 因此它会记录: When the 12341st instruction is executed, the system trapped by xxx. 在xxx时候中断这种事情需要cpu微架构的支持, Intel支持这种事情. 教授说了 在xxx时候中断也是profiling程序时候经常做的事情.
主从同步
primary做的所有Non-Determinsic 的操作都会被hypervisor所记录并且送给backup, 来保证backup最终会达到primary当前的状态. 万一没有啥记录要送给backup, backup执行速度一不小心比primary快, 然后执行到指令X了, 但是primary在执行到X前被中断了咋办, 这样的话二者被中断的地方不一样, 状态同步就失败了. 论文给的解决方法是, 如果channel里没有primary送来的记录, 那就暂停backup的执行. 这样保证backup执行时候至少有一个primary送来的记录, 保证了backup执行一定会慢于primary
Disk IO
论文中primary和backup连接到同一个storage, backup所有的输出都会被hypervisor给拦截并且丢弃 包括写硬盘和发网络包. primary对于disk的同一块地方做non blocking io, 多次并行地读写, 这个时候读写操作可能互相交叉 因此结果是不确定的, 这种不确定必须被消除. 解决方法就是监测到这种race, 把操作变成序列执行, 搞定
现代架构io通过DMA来直接从设备传入内存, 传输是不会打断cpu的执行的. 问题就处在独立于CPU进行DMA传输. DMA传输改变了虚拟机的状态, 并且独立于CPU, 所以CPU执行某到个指令时候, 内存的状态是不确定的, 可能DMA多传一点, 可能DMA少传一点. 这就带来了不确定性. 如果这个CPU从头到尾都不看DMA的那块内存, 那么这样的流程下来, primary和backup终究会再次达到相同状态. 但是万一CPU访问了, GG. MIT教授原话是: “The operating system may actually see the data is copied from the device to memory”. 虽然这个很少见, 但是不代表不会发生. 解决方法就是当数据到来时候hypervisor, 把它暂停:
ザワールド!
然后直接把数据拷贝到vm的内存里, 所以这样VM看起来DMA是“瞬间完成”, 没错, 是替身攻击! 原文hypervisor创建了一个和目标内存区域大小一样的Bounce Buffer, 读和写都是通过这个buffer
Primary可能随时挂掉
课堂中教授给了个例子: 就是当primary接收到请求, 改变处理完之后改变自己状态, 发送了个输出(发出数据包)之后, 这个发数据包的操作被记录下来, 但是这些操作记录还没来得及送达backup, 保洁大妈过来做卫生把插头拔了插上吸尘器(真实事件), hyepervisor连带着primary挂了. 这个时候, 网络包已经发出去了, 也就是说primary在死的前一瞬间, 用它最后的波纹 改变了外部世界. 这个时候backup就需要继承primary的意志来完成他生前未完成的任务, 但是呢因为操作记录丢失了, backup根本不知道有这个client请求, 也不知道现在这个世界是咋样的, 并且内部状态也和primary临终前不一致, 系统一致性就被破坏了. 咋办?
Output Rule: the primary VM may not send an output to the external world, until the backup VM has received and acknowledged the log entry associated with the operation producing the output
这就保证所有改变外部世界的行为在发生前, 都保证backup已经收到所需要的状态更新信息了. 为什么Output这么重要? 上述的规则并不能阻止下面的情况发生: primary跑了一大堆non-deterministic操作挂掉, 并且这些non-deterministic并没来得及送给backup, 此时backup状态大概率不能达到primary临死前的状态. 但是这种情况是ok的, 因为整个系统的一致性没有破坏: 外部世界并不能区分primary临终前的状态和backup后来达到的状态. Output之所以重要是因为Output是改变外部世界状态的一种方式, 处理消息并生成Output是因, 状态改变是果. 外部系统都看到了果, 他们就知道必有因存在, 而在之前的例子里, backup却不知道有因.
Primary挂掉之后
Primary挂掉之后backup就把控制权拿过来了. 在遵循Output Rule:的情况下, 假设primary死之前发送了最后一个数据包, 此时backup能够达到primary死前的状态, 但是却并不能知道这个Output是不是已经被成功发送. 因为如果primary在发output前的一瞬间死掉, backup所获取的信息也是这样. 此时backup的行为就是重新发送数据包. 这就有可能带来重复数据包的问题, 幸运的是, 这个重复的数据包能被TCP/IP协议给发现并且正确的丢弃.
MIT一个老哥在课上问了一个问题, 万一primary临死前连接关闭了, 但是backup并不知道连接是不是真的在死前关闭, 或者是关闭前死掉, 这个时候会不会有问题? 教授的回答是, 这种情况下, TCP保证了 如果backup对一个已经关闭的连接发数据包, 将会收到rst消息, backup就会中断. 这是一种方式, 但是这个回答没有解释, 万一新的backup需要知道这个数据包是否被client正确接收, 并且以此来进行接下来的逻辑处理咋办. 我个人感觉“需要知道这个数据包是否被client正确接收”这个要求可在client的应用逻辑里实现, 如果看到这样重复的消息, 就跟新的primary说, 我已经知道这件事了, 你别在烦我了.
另外值得一说的是教授说, primary backup replication这种模型是没有办法杜绝重复信息的存在的. 这个有空我去查查论文, 肯定是有理论的证明的.
虚假的Fail-Stop Model
之前已经讨论过, 真正的fail-stop model在我们这个宇宙里是不存在的. 因此很有可能因为连接Primary和backup之间的网络暂时不可用, Primary和backup都互相以为对方挂掉, 然后两个人一起处理请求, 这就“Brain Split”了. 论文里解决Brain Split是请求第三个实体的帮助, 每当发现对方挂的时候, 先问一问第三个实体. 第三个实体这里就是shared storage, 假设primary 和backup互相以为对方死掉, 他们分别在shared storeage上做一个TST(Test-and-Set)操作就能避免脑裂了. 那万一这个第三方不可访问呢? 我们这里就假设第三方也是高可用并且replicated.
总结
本文就是很肤浅地记录了主从复制的一个虚拟机实现. 真实实践里这样的主从复制逻辑常见是在应用层逻辑里搞定的. 这个就具有极其的挑战性了. 这篇文章至少给我们一些启发, 来实现应用层的主从复制…不得不说, MIT 6.824的课程安排真是巧妙. 关于replication的研究已经有非常多, 有更深入的topic和相关理论. 以后有空我也读一读: 相关高引用论文
Schneider, Fred B. “Implementing fault-tolerant services using the state machine approach: A tutorial.” ACM Computing Surveys (CSUR) 22.4 (1990): 299-319.
教科书
Charron-Bost, Bernadette, Fernando Pedone, and André Schiper. “Replication.” LNCS 5959 (2010): 19-40.
最后, MIT的学生真牛逼!