1、主要内容10.1 分布式容错模型10.2 进程的恢复10.3 可靠的客户服务器通信10.4 可靠的分组通信10.5 分布式提交 10.6 恢复处理10.7 习题2009-11-10110.1 分布式容错模型n可依赖系统（Dependable,Trustworthy）n可用性（availability）n系统可为用户服务的能力n可靠性（Reliability）n系统可连续工作的能力n安全性（Safety）n系统故障时产生危害的程度n可维护性（Maintainability）n系统故障修复的难度2009-11-102基本概念（1）n失效（fail,failure）、失灵n一个系统不能满足它的承诺（
2、提供服务）n差错（error）：n导致系统失效的原因n故障（fault）：n导致差错发生的原因2009-11-103基本概念（2）n平均无故障时间(MTTF)Mean Time To Failuren平均能够正常运行多长时间，才发生一次故障。用来度量可靠性np为每秒失效概率n平均无故障时间(MTTF)=1kp(1-p)k-1=1/pn例：p=10-6，MTTF=106秒=11.6天n平均维修时间（MTTR）Mean Time To Repair n系统发生故障后维修和重新恢复正常运行平均花费的时间 n用来度量可维护性n可用性=(MTTF/(MTTF+MTTR)2009-11-104故障的类型n
3、按照故障出现的概率n短暂型(transient):出现一次，再也不出现n间歇型(intermittent)：消失后，再重复出现n永久型(permanent)：一直存在n按照故障产生的原因n节点故障n硬件故障n软件故障n时序故障2009-11-105基本概念（2）n故障控制n预防n去除n预告n容错（fault tolerance）n即使发生故障，系统仍能提供服务n系统的容错能力用可允许的故障节点数量来衡量。n如果系统能够在k个节点出现故障的情况下仍然能够完成任务，则称该系统为k-容错系统。2009-11-106失效（失败）模型失失效类型效类型描述描述崩溃性失效服务器停止。但在停止前一直正确工作遗
4、漏性失败 接收遗漏 发送遗漏服务器不能响应连入的请求服务器不能接收连入的消息服务器不能发送消息定时性失效服务器的响应超出规定的时间间隔响应性失效 值失效 状态变迁失效服务器的响应不正确响应的值是错误的服务器偏离正确的控制流任意性失效服务器在任意的时刻产生任意的响应2009-11-107失效（失败）模型n失败模型n故障-沉静系统(fail-silent)。由于故障产生的系统停止不能被其他节点感知。n故障-停止系统(fail-stop)。由于节点故障产生的系统停止能够被其他节点感知。n故障-安全系统(fail-safe)。由于节点故障而停止服务但不会产生随机故障。n拜占庭(Byzantine)故障
5、系统（随机故障系统）。由于故障导致系统产生任意的响应。恶意的、难检测。n系统类型n同步系统：在规定上限时间内有响应n异步系统：响应时间没有上限2009-11-108基于冗余的失效屏蔽技术n冗余类型n信息冗余：如，海明码。n时间冗余：如，重发，重做n物理冗余：n软件:如复制进程n硬件：如复制电路n信息冗余和物理冗余都属于空间冗余2009-11-109基于冗余的失效屏蔽技术n三模冗余方法(TMR,Triple Modular Redundancy)n三路表决器(voter)：三路输入，一路输出n可屏蔽一路错误（任意性失效）2009-11-101010.2 进程的恢复n进程容错n进程组：具有相同功能
6、的进程集合n组成员籍n加入：具有成员籍n脱离：注销成员籍n多组成员籍：同时属于不同的组n设计问题n需要复制的程度n无故障时，平均情况和最坏情况下的系统性能n有故障时，平均情况和最坏情况下的系统性能 2009-11-1011组的管理（1）n扁平组：所有成员是同等的n层次组：协调程序和工作程序2009-11-1012组的管理（2）n组成员籍管理n组服务器：集中式管理n多播通信：分布式管理NNn故障后，组的退出nfail-stop类型：发送Goodbye信息nfail-silent类型：需其他成员发现2009-11-1013组的管理（3）n消息同步n加入组时：立刻收到所有消息n退出组时：不再收到任何
7、消息n组的重建n当组崩溃后，重新建立组n重建协议2009-11-1014复制容错技术（1）n复制容错n用多个相同的进程，屏蔽个别故障进程的故障n冗余度：相同进程的个数n 基于主进程协议(primary-based)n结构：分层组结构n协议：primary-backup协议n复制写协议(replicated-write)n结构：平面组结构n协议：基于表决数协议2009-11-1015主-后备方法（primary backup）n主服务器失效，则后备服务器接替其任务 n接管模型客户主进程后备进程1.请求 2.执行 3.更新 4.执行 6.应答 5.确认2009-11-1016复制容错技术（2）nk
8、-容错度：n在有k个进程发生故障时，系统仍能正确运行nFail-stop型故障：n对k-容错度，需k+1冗余度n拜占庭型故障：n对k-容错度，需2k+1冗余度n容错的前提条件 n所有的请求到达所有服务器的顺序应相同 n原子广播问题（atomic broadcast problem）2009-11-1017故障检测n进程故障检测n主动式方法，发送“Are you alive?”消息n常用方法，ping操作n被动式方法，等待发来的故障消息n超时机制，在规定时间内作出响应，否则，为故障2009-11-101810.3 可靠的客户服务器通信n点到点通信n可靠通信：防止通信失效n遗漏型失效：消息丢失n解
9、决策略：利用可靠的传输协议，如TCP协议。确认和重新传输n连接崩溃失效：连接中断n不能屏蔽，需重建连接n解决策略：抛出例外，通知客户进程2009-11-1019RPC失效(1)nRPC失效n5种失效情况客户服务器1.定位失败2.请求消息丢失3.服务器失败5.客户失败4.应答消息丢失2009-11-1020RPC失效(2)n1、客户不能定位服务器n可能服务器被修改，客户存根（stub）与新的服务器存根不匹配n解决策略：n抛出例外信号SIG-NOSERVER，然后由编写的信号处理程序做相应处理。n没有透明性n2、丢失请求消息n解决策略：n客户发现超时，重发请求2009-11-1021RPC失效(3
10、)n3、服务器崩溃n崩溃情况n解决策略：n至少一次语义n最多一次语义n听之任之n确切一次语义(a)正常情况;(b)在执行后崩溃 (c)在执行前崩溃2009-11-1022RPC失效(4)n举例：打印文本。在打印服务器失效时，客户和服务器的策略组合nM(发送完成消息)；P(打印)；C(崩溃)客户客户服务器服务器策略策略 M-P策略策略 P-M重发策略重发策略MPCMC(P)C(MP)PMCPC(M)C(PM)总是重发请求DUPOKOKDUPDUPOK不重发OKOKOK当收到ACK时，重发DUPOKDUPOK当没收到ACK时，重发OKOKOKDUPOK2009-11-1023RPC失效(5)n4.
11、丢失应答消息n解决策略n定时器，超时检测，重发请求n问题：重复操作n解决策略n构造幂等性操作（idempotent）n顺序号n标志：区分原始消息和重发消息2009-11-1024RPC失效(6)n5.客户崩溃n孤儿进程问题n解决策略：n根除法：利用日志，撤销孤儿进程n再生法：设置时期（epoch）。到达epoch时，重新创建客户进程n温和再生法：撤销无主的孤儿n过期法：设置时间量T。如果超过T，则撤销客户的请求（不一定是孤儿）。2009-11-102510.4 可靠的分组通信n假定：进程操作正确，在通信中不加入或退出分组n可靠多播n将每一个消息递交给每一个当前组员n不可靠多播n不能保证将一个多
12、播消息递交给所有组员SRRRmmm2009-11-1026基本的可靠多播模式n解决策略a)消息传播：记录顺序号b)报告反馈：如果丢失，返回负ACK，重新发送2009-11-1027可靠多播的可伸缩性（1）n反馈爆炸问题：N1n简单解决方案：n接收者只返回NACK消息n发送者保留消息到历史缓冲区历史缓冲区溢出问题NACK反馈爆炸SRRRACKACKACK2009-11-1028可靠多播的可伸缩性（2）n反馈抑制技术（SRM,可伸缩的可靠多播协议）n不返回ACK，只返回NACKn压缩NACK。随机延迟后，如果接收到重发消息，才发NACKn用途：例，白板系统2009-11-1029可靠多播的可伸缩性
13、（3）n层次化反馈控制n一个大组划分成若干个小组，形成一个树n发送者所在的小组为树的根n每个局部协调者转发消息给它的孩子n局部协调者负责请求重发2009-11-1030原子性多播(1)n原子性多播问题n消息要么递交给所有组员，要么一个也不递交n对于每个组员，所有消息的递交次序是相同的n用途举例：主动式复制协议 n故障组员处理n出故障后，自动退出组n修复后，重新加入组n 组视图G（group view）n在发送一个消息时，属于该组的所有进程的名单2009-11-1031原子性多播(2)n视图变更n向所有的组员宣布加入或者退出该组n带有通信层的分布式系统结构n能区分消息接收和消息递交2009-11
14、-1032原子性多播(3)n虚拟同步(virtually synchronous)的可靠多播n如果发送者在多播时崩溃，消息将递交给其他所有组员，或者，被它们丢弃n原理：所有多播在视图变更之间进行2009-11-1033原子性多播(4)n消息递交次序n1.可靠的无序多播n不保证接收到消息的递交次序是相同的n举例：Process P1Process P2Process P3sends m1receives m1receives m2sends m2receives m2receives m1时间2009-11-1034原子性多播(5)n2.可靠的FIFO次序多播n从同一发送者接收到的消息的递交次序
15、与发送次序一致n举例：发送者P1,P4；接收者P2,P3Process P1Process P2Process P3Process P4sends m1receives m1receives m3sends m3sends m2receives m3receives m1sends m4receives m2receives m2receives m4receives m4时间2009-11-1035原子性多播(6)n3.可靠的因果次序多播n具有因果关系的消息的递交次序与发送次序一致，无论消息是否由同一发送者发送的n可使用时间戳向量实现2009-11-1036原子性多播(7)n4.全序递交（T
16、otal-ordered delivery）n对于所有组员的消息递交次序，是相同的。n原子性多播：n提供全序递交的虚拟同步可靠多播2009-11-1037原子性多播(10)n虚拟同步的可靠多播的6个版本多播基本的消息次序全序递交?可靠多播无NoFIFO多播FIFO次序型递交No因果多播因果-次序型递交No原子性多播无YesFIFO原子性多播FIFO-次序型递交Yes因果原子性多播因果-次序型递交Yes2009-11-1038原子性多播(10)n虚拟同步性的实现n举例：ISIS系统P4发现P7崩溃，多播视图变更消息(vc)P6发送所有不稳定消息，后跟 flush（刷新）消息P6 接收到所有返回的
17、flush消息后，确定新的视图Gi+12009-11-103910.5 分布式提交n两阶段提交协议 (a)协调者的有限状态机 (b)参与者的有限状态机2009-11-1040两阶段提交协议n当参与者P处于READY状态，并已与另一参与者Q通信之后，可能采取的动作.进程进程 Q状态状态进程进程 P动作动作COMMIT变迁到 COMMITABORT变迁到ABORTINIT变迁到ABORTREADY与其他参与者联络2009-11-1041两阶段提交协议n协调者执行步骤write START _2PC to local log;multicast VOTE_REQUEST to all partici
18、pants;while not all votes have been collected wait for any incoming vote;if timeout write GLOBAL_ABORT to local log;multicast GLOBAL_ABORT to all participants;exit;record vote;if all participants sent VOTE_COMMIT and coordinator votes COMMIT write GLOBAL_COMMIT to local log;multicast GLOBAL_COMMIT t
19、o all participants;else write GLOBAL_ABORT to local log;multicast GLOBAL_ABORT to all participants;2009-11-1042两阶段提交协议n参与者执行步骤write INIT to local log;wait for VOTE_REQUEST from coordinator;if timeout write VOTE_ABORT to local log;exit;if participant votes COMMIT write VOTE_COMMIT to local log;send V
20、OTE_COMMIT to coordinator;wait for DECISION from coordinator;if timeout multicast DECISION_REQUEST to other participants;wait until DECISION is received;/*remain blocked*/write DECISION to local log;if DECISION=GLOBAL_COMMIT write GLOBAL_COMMIT to local log;else if DECISION=GLOBAL_ABORT write GLOBAL
21、_ABORT to local log;else write VOTE_ABORT to local log;send VOTE ABORT to coordinator;2009-11-1043两阶段提交协议n对来自其他参入者的决策请求的处理步骤/*executed by separate thread*/while true wait until any incoming DECISION_REQUEST is received;/*remain blocked*/read most recently recorded STATE from the local log;if STATE=G
22、LOBAL_COMMIT send GLOBAL_COMMIT to requesting participant;else if STATE=INIT or STATE=GLOBAL_ABORT send GLOBAL_ABORT to requesting participant;else skip;/*participant remains blocked*/2009-11-1044三阶段提交协议n目的：n在失败即停故障情况下，避免进程阻塞 (a)协调者的有限状态机 (b)参与者的有限状态机2009-11-1045三阶段提交协议n协调者（WAIT）：发现超时,则abortn协调者(PRE
23、COMMIT)：发现超时,继续commitn参与者(INIT)：发现超时,则abortn参与者(READY)：n发现超时，询问其他参与者n如果有COMIT/ABORT,则执行n如果都为PRECOMMIT,则commitn如果有INIT，则abortn如果都为READY，则abortn参与者(PRECOMMIT)：发现超时,继续commit2009-11-104610.6 恢复处理n目的:使系统从错误状态到正确状态n类型：n向后恢复(backward recovery)：使系统返回到上一个正确状态n向前恢复(forward recovery)：使系统前进到一个正确的新状态n检查点技术(check
24、point)n消息日志技术（logging）n基于发送者的写日志n基于接受者的写日志2009-11-1047可恢复的稳定存储器n稳定存储器状态a)稳定存储状态b)崩溃状态：在更新驱动器1后发生c)坏点状态：出现坏扇区2009-11-1048检查点n分布式快照（snapshot）n一致的全局状态n恢复线n最近的分布式快照，最近的一致性割集n举例2009-11-1049独立检查点（1）n独立检查点n每个进程的检查点是相互独立的n问题：多米诺效应n局部状态没有形成分布式快照，导致级联回滚（cascaded rollback）过程n举例：只有m,m的接受记录，没有发送记录2009-11-1050独立检
25、查点（2）n解决方法n设CPi(m)表示Pi的第m个检查点n设INTi(m)表示CPi(m)和CPi(m-1)之间的间隔n当Pi在INTi(m)中发送消息x时，带上(i,m)n当Pj在INTj(n)收到x后，记录依赖关系INTi(m)INTj(n)nPj在CPj(n)中加入该依赖关系n当Pi需要回滚到CPi(m-1)时，则Pj需要回滚到CPj(n-1)2009-11-1051协作式检查点（2）n同步写检查点n所有进程同步地在本地稳存中写检查点，使保存的状态自动地保持全局一致。n非阻塞式算法n分布式快照算法n两阶段阻塞式算法nCHECKPOINT_REQUEST：n协调者发送命令，所有进程写局部
26、检查点，将要发送消息插入队列，向协调者返回ACK消息。nCHECKPOINT_DONE：n当协调者收到所有的ACK后，发送命令，所有进程继续2009-11-1052协作式检查点（2）n改进算法-增量快照算法n最近发送进程：n进程P在上一个检查点向其发送过请求的进程。n协调者恢复依赖进程：n在上一个检查点，直接或间接收到协调者消息的进程。因此，由最近发送进程的闭包集组成。n协调者只向其最近发送进程多播命令。n当进程P收到写检查点请求时，仅向P的最近发送进程，转发该请求。每个进程仅转发该请求一次。n当所有进程被确认后，协调者发送第二个多播命令，开始实际写检查点2009-11-1053消息日志（1）
27、n基本思想n减少检查点的个数n如果消息的传送可以重放(replay)，则可取得全局一致性状态，而不必从稳存恢复。n分段确定性模型(piecewise deterministic model)，假定：n每个进程在一序列的间隔中执行，有先后次序，是确定性的。每个间隔是可重放的。n每个间隔以一个非确定性事件开始，以下一个非确定形式件发生而结束。n如果记录所有非确定性事件，则全部执行可重放。2009-11-1054消息日志（2）n孤儿进程n在进程P崩溃后，仍然存活的进程。但在P恢复后，其状态与P不一致n举例：n进程Q崩溃，消息m2没有写日志nQ恢复后，m2,m3消息没有重放，导致R为孤儿进程2009-
28、11-1055消息日志（3）n消息n消息头：发送者、接受者、顺序号、递交号n稳定消息：已记入稳存，不会丢失nDEP(m)：n依赖于消息m递交的进程集合。n与m有因果关系的进程集合nCOPY(m)：n拥有m的副本，但未将m写入稳存的进程集合.n孤儿进程nQ存在于DEP(m)，而COPY(m)中的所有进程崩溃2009-11-1056消息日志（4）n避免孤儿进程n如果QDEP(m)，则保证QCOPY(m)n悲观型(pessimistic logging)日志协议n保证每个不稳定的消息m最多提交到一个进程n不可能出现孤儿进程n乐观型(optimistic logging)日志协议n在崩溃后处理，将DE
29、P(m)中的孤儿进程都回滚到不再属于DEP(m)的状态2009-11-1057小小 结结1.故障模型：故障类型、三模容错2.进程容错技术：冗余容错、两军问题、拜占庭将军问题3.客户服务器容错问题4.组通信容错问题：原子多播、全局有序5.事务容错技术：两段提交、三段提交6.恢复方法：分布式日志、消息日志2009-11-105810.7 习习 题题1.在崩溃失败的情况下，是什么使得fail-stop模型难以实现？2.如果一个Web浏览器返回一个过期的缓存的网页，而不是服务器上的最新网页。这是失败吗？如果是，属于何种失败？3.以下TMR系统可应付多少个故障元件（设备和表决器）？举例说明可屏蔽掉的最坏的情况。2009-11-1059习习 题题(续续)4.对以下应用讨论是最少一次语义还是最多一次语义合适：从文件服务器读写文件 编译程序 远程银行付款5.举例说明不需要消息顺序的分组通信6.虚拟同步性类似于分布式数据存储器的弱一致性，它是以组视图的变化作为同步点。那么，给出对应于强一致性的同步性。2009-11-1060
