东北大学分布式操作系统课件7

第7章分布式容错管理东北大学信息学院于戈2006年4月2006-4-18东北大学软件所于戈第七章分布式容错管理2主要内容7.1分布式容错模型7.2进程恢复能力7.3可靠的客户服务器通信7.4可靠的分组通信7.5分布式提交7.6恢复处理7.7习题2006-4-18东北大学软件所于戈第七章分布式容错管理37.1分布式容错模型可依赖性（Dependability）–可用性（availability）•在给定时刻能正确操作的概率–可靠性（Reliablity）•在给定期间能正确操作的概率–安全性（Safty）•临时失效不会造成灾难–可维护性（Maintainability）•易于对失效进行修复的系统2006-4-18东北大学软件所于戈第七章分布式容错管理4基本概念（1）失效（fail,failure）、失败–一个系统不能满足它的承诺（提供服务）差错（error）：–导致系统失效的系统状态故障（fault）：–导致差错发生的原因2006-4-18东北大学软件所于戈第七章分布式容错管理5基本概念（2）故障控制–预防–去除–预告容错（faulttolerance）–即使发生故障，系统仍能提供服务2006-4-18东北大学软件所于戈第七章分布式容错管理6基本概念（3）故障类型–短暂型（transient）:出现一次，再也不出现–间歇型(intermittent)：消失后，再重复出现–永久型(permanent)：一直存在失效时间–p为每秒失效概率–平均失效时间(MTTF)=Σ1∞kp(1-p)k-1=1/p–例：p=10-6，MTTF=106秒=11.6天2006-4-18东北大学软件所于戈第七章分布式容错管理7失效（失败）模型失效类型描述崩溃性失效服务器停止。但在停止前一直正确工作遗漏性失败接收遗漏发送遗漏服务器不能响应连入的请求服务器不能接收连入的消息服务器不能发送消息定时性失效服务器的响应超出规定的时间间隔响应性失效值失效状况变迁失效服务器的响应不正确响应的值是错误的服务器偏离正确的控制流任意性失效服务器在任意的时刻产生任意的响应2006-4-18东北大学软件所于戈第七章分布式容错管理8失效（失败）模型失败模型–失败缄默(fail-silent)。不通知失效。•失败即停(fail-stop)。良性的。易检测。•失败安全(fail-safe)。不产生恶果。–拜占庭(Byzantine)故障。恶意的。难检测。•拜占庭帝国（330-1453）系统类型–同步系统：在规定上限时间内有响应–异步系统：响应时间没有上限2006-4-18东北大学软件所于戈第七章分布式容错管理9基于冗余的失效屏蔽技术冗余类型–信息冗余：如，海明码。–时间冗余：如，重发，重做–物理冗余：•软件:如复制进程•硬件：如复制电路2006-4-18东北大学软件所于戈第七章分布式容错管理10基于冗余的失效屏蔽技术三模冗余方法(TMR,TripleModularRedundancy)–三路表决器(voter)：三路输入，一路输出–可屏蔽一路错误2006-4-18东北大学软件所于戈第七章分布式容错管理117.2进程恢复能力进程容错–进程组：具有相同功能的进程集合–组成员籍•加入：具有成员籍•脱离：注销成员籍•多成员籍：同时属于不同的组设计问题–需要复制的程度–无故障时，平均情况和最坏情况下的系统性能–有故障时，平均情况和最坏情况下的系统性能2006-4-18东北大学软件所于戈第七章分布式容错管理12复制组（1）扁平组：所有成员是同等的层次组：协调程序和工作程序2006-4-18东北大学软件所于戈第七章分布式容错管理13复制组（2）组成员籍管理–组服务器：集中式管理–多播通信：分布式管理故障后，如何脱离组–fail-stop类型：发送Goodbye信息–fail-silent类型：需其他成员发现消息同步–加入组：立刻收到所有消息–脱离组：不再受到任何消息组的重建：组崩溃后，重新恢复组2006-4-18东北大学软件所于戈第七章分布式容错管理14复制容错技术复制容错–用多个相同的进程，屏蔽个别故障进程的故障–冗余度：相同进程的个数基于主副本协议(primary-based)–分层组结构–primary-backup协议复制写协议(replicated-write)–平面组结构–基于表决数协议2006-4-18东北大学软件所于戈第七章分布式容错管理15复制容错技术k-容错度：–在有k个进程发生故障时，系统仍能正确运行Fail-stop型故障：–对k-容错度，需k+1冗余度拜占庭型故障：–对k-容错度，需2k+1冗余度容错的前提条件–所有的请求到达所有服务器的顺序应相同–原子广播问题（atomicbroadcastproblem）2006-4-18东北大学软件所于戈第七章分布式容错管理16主备份方法（primarybackup）主服务器失效，则备份服务器接替其任务接管模型客户主系统备份系统1.请求2.执行3.更新4.执行6.应答5.确认2006-4-18东北大学软件所于戈第七章分布式容错管理17故障系统的协定问题(1)协定(agreemnt)–对某些问题的一致意见。如，是否提交事务，负载划分，同步等分布式协定算法–在有限的步骤内，所有非故障进程达成协定2006-4-18东北大学软件所于戈第七章分布式容错管理18故障系统的协定问题(2)两军问题(two-army)–3000+3000〉5000–对于可靠通信，不可能达成协定3000波拿巴将军50003000亚历山大将军1232006-4-18东北大学软件所于戈第七章分布式容错管理19故障系统的协定问题(3)拜占庭将军问题–例：3个忠诚将军，1个叛变将军Lamport递归算法–共4步：(a)对外报告(b)收集向量(c)报告向量(d)生成结果向量：（1，2，未知，4）2006-4-18东北大学软件所于戈第七章分布式容错管理20故障系统的协定问题(4)若三个将军中，有两个忠诚将军，一个叛变将军，则不能判断出哪个将军叛变。若要有m个进程出错的系统实现协同一致，最少要有2m＋1个正常进程。进程总数为3m+1。需超过2/3多数，才能达成协定2006-4-18东北大学软件所于戈第七章分布式容错管理217.3可靠的客户服务器通信点到点通信–可靠通信：可靠的传输协议，如TCP协议–遗漏失效：利用TCP可屏蔽–连接崩溃失效：不能屏蔽，需重建连接RPC失效–5种失效客户服务器1.定位失败2.请求消息丢失3.服务器失败5.客户失败4.应答消息丢失2006-4-18东北大学软件所于戈第七章分布式容错管理22RPC失效(1)1、客户不能定位服务器–可能服务器被修改，客户存根（stub）与新的服务器存根不匹配–解决策略：•抛出例外信号SIG-NOSERVER，然后由编写的信号处理程序做相应处理。•没有透明性2、丢失请求消息–解决策略：•客户发现超时，重发请求2006-4-18东北大学软件所于戈第七章分布式容错管理23RPC失效(2)3、服务器崩溃–崩溃情况–解决策略：•至少一次语义•最多一次语义•听之任之•确切一次语义(a)正常情况;(b)在执行后崩溃(c)在执行前崩溃2006-4-18东北大学软件所于戈第七章分布式容错管理24RPC失效(3)举例：打印文本。在打印服务器失效时，客户和服务器的策略组合–M(发送完成消息)；P(打印)；C(崩溃)客户服务器策略M-P策略P-M重发策略MPCMC(P)C(MP)PMCPC(M)C(PM)总是重发请求DUPOKOKDUPDUPOK不重发OKOKOK当收到ACK时，重发DUPOKDUPOK当没收到ACK时，重发OKOKOKDUPOK2006-4-18东北大学软件所于戈第七章分布式容错管理25RPC失效(4)丢失应答消息–解决策略：定时器，超时监测–幂等性操作客户崩溃–孤儿进程问题–解决策略：•根除法：日志•再生法：世纪（epoch）•温和再生法：撤销无主的孤儿•过期法：时间T2006-4-18东北大学软件所于戈第七章分布式容错管理267.4可靠的分组通信假定：进程操作正确，在通信中不加入或离开分组可靠多播–将每一个消息递交给每一个当前组员不可靠多播–不能保证将一个多播消息递交给所有组员SRRRmmm2006-4-18东北大学软件所于戈第七章分布式容错管理27基本的可靠多播模式解决策略a)消息传播：记录顺序号b)报告反馈：如果丢失，返回负ACK，重新发送2006-4-18东北大学软件所于戈第七章分布式容错管理28可靠多播的可伸缩性（1）反馈爆炸问题：N→1简单解决方案：–接收者只返回NACK消息–发送者保留消息到历史缓冲区☻历史缓冲区溢出问题☻NACK反馈爆炸SRRRACKACKACK2006-4-18东北大学软件所于戈第七章分布式容错管理29可靠多播的可伸缩性（2）反馈抑制技术（SRM,可伸缩的可靠多播协议）–不返回ACK，只返回NACK–压缩NACK。随机延迟后，如果接收到重发消息，才发NACK用途：白板系统2006-4-18东北大学软件所于戈第七章分布式容错管理30可靠多播的可伸缩性（3）层次化反馈控制–一个大组划分成若干个小组，形成一个树–发送者所在的小组为树的根–每个局部协调者转发消息给它的孩子–局部协调者负责请求重发2006-4-18东北大学软件所于戈第七章分布式容错管理31原子性多播(1)原子性多播问题–消息要么递交给所有组员，要么一个也不递交–对于每个组员，所有消息的递交次序是相同的用途举例：主动式复制协议故障组员处理–出故障后，自动退出组–修复后，重新加入组组视图G（groupview）–在发送一个消息时，属于该组的所有进程的名单2006-4-18东北大学软件所于戈第七章分布式容错管理32原子性多播(2)视图变更–向所有的组员宣布加入或者脱离该组带有通信层的分布式系统结构–能区分消息接收和消息递交2006-4-18东北大学软件所于戈第七章分布式容错管理33原子性多播(3)虚拟同步性–如果发送者在多播时崩溃，消息将递交给其他所有组员，或者，被它们丢弃原理：所有多播在视图变更之间进行2006-4-18东北大学软件所于戈第七章分布式容错管理34原子性多播(4)消息递交次序1.可靠的无序多播–不保证接收到消息的递交次序是相同的–举例：ProcessP1ProcessP2ProcessP3sendsm1receivesm1receivesm2sendsm2receivesm2receivesm1时间2006-4-18东北大学软件所于戈第七章分布式容错管理35原子性多播(5)2.可靠的FIFO次序多播–从同一发送者接收到的消息的递交次序与发送次序一致–举例：发送者P1,P4；接收者P2,P3ProcessP1ProcessP2ProcessP3ProcessP4sendsm1receivesm1receivesm3sendsm3sendsm2receivesm3receivesm1sendsm4receivesm2receivesm2receivesm4receivesm4时间2006-4-18东北大学软件所于戈第七章分布式容错管理36原子性多播(6)3.可靠的因果次序多播–具有因果关系的消息的递交次序与发送次序一致，无论消息是否由同一发送者发送的–可使用时间戳向量实现4.全序递交（Total-ordereddelivery）–对于所有组员的消息递交次序，是相同的。原子性多播：–提供全序递交的虚拟同步可靠多播2006-4-18东北大学软件所于戈第七章分布式容错管理37原子性多播(7)虚拟同步的可靠多播的6个版本多播基本的消息次序全序递交?可靠多播无NoFIFO多播FIFO次序型递交No因果多播因果-次序型递交No原子性多播无YesFIFO原子性多播FIFO-次序型递交Yes因果原子性多播因果-次序型递交Yes2006-4-18东北大学软件所于戈第七章分布式容错管理