分布式系统可靠性设计

分布式系统可靠性设计第一页，共六十页，2022年，8月28日10.1分布式容错模型可依赖系统（Dependable,Trustworthy）可用性（availability）系统可为用户服务的能力可靠性（Reliability）系统可连续工作的能力安全性（Safety）系统故障时产生危害的程度可维护性（Maintainability）系统故障修复的难度第二页，共六十页，2022年，8月28日基本概念（1）失效（fail,failure）、失灵一个系统不能满足它的承诺（提供服务）差错（error）：导致系统失效的原因故障（fault）：导致差错发生的原因第三页，共六十页，2022年，8月28日基本概念（2）平均无故障时间(MTTF)MeanTimeToFailure平均能够正常运行多长时间，才发生一次故障。用来度量可靠性p为每秒失效概率平均无故障时间(MTTF)=Σ1∞kp(1-p)k-1=1/p例：p=10-6，MTTF=106秒=11.6天平均维修时间（MTTR）MeanTimeToRepair系统发生故障后维修和重新恢复正常运行平均花费的时间用来度量可维护性可用性=(MTTF/(MTTF+MTTR))

第四页，共六十页，2022年，8月28日故障的类型按照故障出现的概率短暂型(transient):出现一次，再也不出现间歇型(intermittent)：消失后，再重复出现永久型(permanent)：一直存在按照故障产生的原因节点故障硬件故障软件故障时序故障第五页，共六十页，2022年，8月28日基本概念（2）故障控制预防去除预告容错（faulttolerance）即使发生故障，系统仍能提供服务系统的容错能力用可允许的故障节点数量来衡量。如果系统能够在k个节点出现故障的情况下仍然能够完成任务，则称该系统为k-容错系统。第六页，共六十页，2022年，8月28日失效（失败）模型失效类型描述崩溃性失效服务器停止。但在停止前一直正确工作遗漏性失败

接收遗漏

发送遗漏服务器不能响应连入的请求

服务器不能接收连入的消息

服务器不能发送消息定时性失效服务器的响应超出规定的时间间隔响应性失效

值失效

状态变迁失效服务器的响应不正确

响应的值是错误的服务器偏离正确的控制流任意性失效服务器在任意的时刻产生任意的响应第七页，共六十页，2022年，8月28日失效（失败）模型失败模型故障-沉静系统(fail-silent)。由于故障产生的系统停止不能被其他节点感知。故障-停止系统(fail-stop)。由于节点故障产生的系统停止能够被其他节点感知。故障-安全系统(fail-safe)。由于节点故障而停止服务但不会产生随机故障。拜占庭(Byzantine)故障系统（随机故障系统）。由于故障导致系统产生任意的响应。恶意的、难检测。系统类型同步系统：在规定上限时间内有响应异步系统：响应时间没有上限第八页，共六十页，2022年，8月28日基于冗余的失效屏蔽技术冗余类型信息冗余：如，海明码。时间冗余：如，重发，重做物理冗余：软件:如复制进程硬件：如复制电路信息冗余和物理冗余都属于空间冗余第九页，共六十页，2022年，8月28日基于冗余的失效屏蔽技术三模冗余方法(TMR,TripleModularRedundancy)三路表决器(voter)：三路输入，一路输出可屏蔽一路错误（任意性失效）第十页，共六十页，2022年，8月28日10.2进程的恢复进程容错进程组：具有相同功能的进程集合组成员籍加入：具有成员籍脱离：注销成员籍多组成员籍：同时属于不同的组设计问题需要复制的程度无故障时，平均情况和最坏情况下的系统性能有故障时，平均情况和最坏情况下的系统性能

第十一页，共六十页，2022年，8月28日组的管理（1）扁平组：所有成员是同等的层次组：协调程序和工作程序第十二页，共六十页，2022年，8月28日组的管理（2）组成员籍管理组服务器：集中式管理多播通信：分布式管理NN故障后，组的退出fail-stop类型：发送Goodbye信息fail-silent类型：需其他成员发现第十三页，共六十页，2022年，8月28日组的管理（3）消息同步加入组时：立刻收到所有消息退出组时：不再收到任何消息组的重建当组崩溃后，重新建立组重建协议第十四页，共六十页，2022年，8月28日复制容错技术（1）复制容错用多个相同的进程，屏蔽个别故障进程的故障冗余度：相同进程的个数基于主进程协议(primary-based)结构：分层组结构协议：primary-backup协议复制写协议(replicated-write)结构：平面组结构协议：基于表决数协议第十五页，共六十页，2022年，8月28日主-后备方法（primarybackup）主服务器失效，则后备服务器接替其任务

接管模型客户主进程后备进程1.请求2.执行3.更新4.执行

6.应答5.确认第十六页，共六十页，2022年，8月28日复制容错技术（2）k-容错度：在有k个进程发生故障时，系统仍能正确运行Fail-stop型故障：对k-容错度，需k+1冗余度拜占庭型故障：对k-容错度，需2k+1冗余度容错的前提条件

所有的请求到达所有服务器的顺序应相同原子广播问题（atomicbroadcastproblem）

第十七页，共六十页，2022年，8月28日故障检测进程故障检测主动式方法，发送“Areyoualive?”消息常用方法，ping操作被动式方法，等待发来的故障消息超时机制，在规定时间内作出响应，否则，为故障第十八页，共六十页，2022年，8月28日10.3可靠的客户服务器通信点到点通信可靠通信：防止通信失效遗漏型失效：消息丢失解决策略：利用可靠的传输协议，如TCP协议。确认和重新传输连接崩溃失效：连接中断不能屏蔽，需重建连接解决策略：抛出例外，通知客户进程第十九页，共六十页，2022年，8月28日RPC失效(1)RPC失效5种失效情况客户服务器1.定位失败2.请求消息丢失3.服务器失败5.客户失败4.应答消息丢失第二十页，共六十页，2022年，8月28日RPC失效(2)1、客户不能定位服务器可能服务器被修改，客户存根（stub）与新的服务器存根不匹配解决策略：抛出例外信号SIG-NOSERVER，然后由编写的信号处理程序做相应处理。没有透明性2、丢失请求消息解决策略：客户发现超时，重发请求第二十一页，共六十页，2022年，8月28日RPC失效(3)3、服务器崩溃崩溃情况解决策略：至少一次语义最多一次语义听之任之确切一次语义(a)正常情况;(b)在执行后崩溃(c)在执行前崩溃第二十二页，共六十页，2022年，8月28日RPC失效(4)举例：打印文本。在打印服务器失效时，客户和服务器的策略组合M(发送完成消息)；P(打印)；C(崩溃)客户服务器策略M->P策略P->M重发策略MPCMC(P)C(MP)PMCPC(M)C(PM)总是重发请求DUPOKOKDUPDUPOK不重发OKOKOK当收到ACK时，重发DUPOKDUPOK当没收到ACK时，重发OKOKOKDUPOK第二十三页，共六十页，2022年，8月28日RPC失效(5)4.丢失应答消息解决策略定时器，超时检测，重发请求问题：重复操作解决策略构造幂等性操作（idempotent）顺序号标志：区分原始消息和重发消息第二十四页，共六十页，2022年，8月28日RPC失效(6)5.客户崩溃孤儿进程问题解决策略：根除法：利用日志，撤销孤儿进程再生法：设置时期（epoch）。到达epoch时，重新创建客户进程温和再生法：撤销无主的孤儿过期法：设置时间量T。如果超过T，则撤销客户的请求（不一定是孤儿）。第二十五页，共六十页，2022年，8月28日10.4可靠的分组通信假定：进程操作正确，在通信中不加入或退出分组可靠多播将每一个消息递交给每一个当前组员不可靠多播不能保证将一个多播消息递交给所有组员SRRRmmm第二十六页，共六十页，2022年，8月28日基本的可靠多播模式解决策略消息传播：记录顺序号报告反馈：如果丢失，返回负ACK，重新发送第二十七页，共六十页，2022年，8月28日可靠多播的可伸缩性（1）反馈爆炸问题：N→1简单解决方案：接收者只返回NACK消息发送者保留消息到历史缓冲区历史缓冲区溢出问题NACK反馈爆炸SRRRACKACKACK第二十八页，共六十页，2022年，8月28日可靠多播的可伸缩性（2）反馈抑制技术（SRM,可伸缩的可靠多播协议）不返回ACK，只返回NACK压缩NACK。随机延迟后，如果接收到重发消息，才发NACK用途：例，白板系统第二十九页，共六十页，2022年，8月28日可靠多播的可伸缩性（3）层次化反馈控制一个大组划分成若干个小组，形成一个树发送者所在的小组为树的根每个局部协调者转发消息给它的孩子局部协调者负责请求重发第三十页，共六十页，2022年，8月28日原子性多播(1)原子性多播问题消息要么递交给所有组员，要么一个也不递交对于每个组员，所有消息的递交次序是相同的用途举例：主动式复制协议故障组员处理出故障后，自动退出组修复后，重新加入组组视图G（groupview）在发送一个消息时，属于该组的所有进程的名单第三十一页，共六十页，2022年，8月28日原子性多播(2)视图变更向所有的组员宣布加入或者退出该组带有通信层的分布式系统结构能区分消息接收和消息递交第三十二页，共六十页，2022年，8月28日原子性多播(3)虚拟同步(virtuallysynchronous)的可靠多播如果发送者在多播时崩溃，消息将递交给其他所有组员，或者，被它们丢弃原理：所有多播在视图变更之间进行第三十三页，共六十页，2022年，8月28日原子性多播(4)消息递交次序1.可靠的无序多播不保证接收到消息的递交次序是相同的举例：ProcessP1ProcessP2ProcessP3sendsm1receivesm1receivesm2sendsm2receivesm2receivesm1时间第三十四页，共六十页，2022年，8月28日原子性多播(5)2.可靠的FIFO次序多播从同一发送者接收到的消息的递交次序与发送次序一致举例：发送者P1,P4；接收者P2,P3ProcessP1ProcessP2ProcessP3ProcessP4sendsm1receivesm1receivesm3sendsm3sendsm2receivesm3receivesm1sendsm4receivesm2receivesm2receivesm4receivesm4时间第三十五页，共六十页，2022年，8月28日原子性多播(6)3.可靠的因果次序多播具有因果关系的消息的递交次序与发送次序一致，无论消息是否由同一发送者发送的可使用时间戳向量实现第三十六页，共六十页，2022年，8月28日原子性多播(7)4.全序递交（Total-ordereddelivery）对于所有组员的消息递交次序，是相同的。原子性多播：提供全序递交的虚拟同步可靠多播第三十七页，共六十页，2022年，8月28日原子性多播(10)虚拟同步的可靠多播的6个版本多播基本的消息次序全序递交?可靠多播无NoFIFO多播FIFO次序型递交No因果多播因果-次序型递交No原子性多播无YesFIFO原子性多播FIFO-次序型递交Yes因果原子性多播因果-次序型递交Yes第三十八页，共六十页，2022年，8月28日原子性多播(10)虚拟同步性的实现举例：ISIS系统P4发现P7崩溃，多播视图变更消息(vc)P6发送所有不稳定消息，后跟flush（刷新）消息P6接收到所有返回的flush消息后，确定新的视图Gi+1第三十九页，共六十页，2022年，8月28日10.5分布式提交两阶段提交协议

(a)协调者的有限状态机(b)参与者的有限状态机第四十页，共六十页，2022年，8月28日两阶段提交协议当参与者P处于READY状态，并已与另一参与者Q通信之后，可能采取的动作.进程Q状态进程P动作COMMIT变迁到COMMITABORT变迁到ABORTINIT变迁到ABORTREADY与其他参与者联络第四十一页，共六十页，2022年，8月28日两阶段提交协议协调者执行步骤writeSTART_2PCtolocallog;

multicastVOTE_REQUESTtoallparticipants;

whilenotallvoteshavebeencollected{

waitforanyincomingvote;

iftimeout{

writeGLOBAL_ABORTtolocallog;

multicastGLOBAL_ABORTtoallparticipants;

exit;

}

recordvote;

}

ifallparticipantssentVOTE_COMMITandcoordinatorvotesCOMMIT{

writeGLOBAL_COMMITtolocallog;

multicastGLOBAL_COMMITtoallparticipants;

}else{

writeGLOBAL_ABORTtolocallog;

multicastGLOBAL_ABORTtoallparticipants;

}第四十二页，共六十页，2022年，8月28日两阶段提交协议参与者执行步骤writeINITtolocallog;

waitforVOTE_REQUESTfromcoordinator;

iftimeout{

writeVOTE_ABORTtolocallog;

exit;}

ifparticipantvotesCOMMIT{

writeVOTE_COMMITtolocallog;

sendVOTE_COMMITtocoordinator;

waitforDECISIONfromcoordinator;

iftimeout{

multicastDECISION_REQUESTtootherparticipants;

waituntilDECISIONisreceived;/*remainblocked*/

writeDECISIONtolocallog;}ifDECISION==GLOBAL_COMMIT

writeGLOBAL_COMMITtolocallog;

elseifDECISION==GLOBAL_ABORT

writeGLOBAL_ABORTtolocallog;

}else{

writeVOTE_ABORTtolocallog;

sendVOTEABORTtocoordinator;

}第四十三页，共六十页，2022年，8月28日两阶段提交协议对来自其他参入者的决策请求的处理步骤/*executedbyseparatethread*/whiletrue{

waituntilanyincomingDECISION_REQUESTisreceived;/*remainblocked*/

readmostrecentlyrecordedSTATEfromthelocallog;

ifSTATE==GLOBAL_COMMIT

sendGLOBAL_COMMITtorequestingparticipant;

elseifSTATE==INITorSTATE==GLOBAL_ABORT

sendGLOBAL_ABORTtorequestingparticipant;

else

skip;/*participantremainsblocked*/第四十四页，共六十页，2022年，8月28日三阶段提交协议目的：在失败即停故障情况下，避免进程阻塞

(a)协调者的有限状态机(b)参与者的有限状态机第四十五页，共六十页，2022年，8月28日三阶段提交协议协调者（WAIT）：发现超时,则abort协调者(PRECOMMIT)：发现超时,继续commit参与者(INIT)：发现超时,则abort参与者(READY)：发现超时，询问其他参与者如果有COMIT/ABORT,则执行如果都为PRECOMMIT,则commit如果有INIT，则abort如果都为READY，则abort参与者(PRECOMMIT)：发现超时,继续commit第四十六页，共六十页，2022年，8月28日10.6恢复处理目的:使系统从错误状态到正确状态类型：向后恢复(backwardrecovery)：使系统返回到上一个正确状态向前恢复(forwardrecovery)：使系统前进到一个正确的新状态检查点技术(checkpoint)消息日志技术（logging）基于发送者的写日志基于接受者的写日志第四十七页，共六十页，2022年，8月28日可恢复的稳定存储器稳定存储器状态稳定存储状态崩溃状态：在更新驱动器1后发生坏点状态：出现坏扇区第四十八页，共六十页，2022年，8月28日检查点分布式快照（snapshot）一致的全局状态恢复线最近的分布式快照，最近的一致性割集举例第四十九页，共六十页，2022年，8月28日独立检查点（1）独立检查点每个进程的检查点是相互独立的问题：多米诺效应局部状态没有形成分布式快照，导致级联回滚（cascadedrollback）过程举例：只有m,m'的接受记录，没有发送记录第五十页，共六十页，2022年，8月28日独立检查点（2）解决方法设CP[i](m)表示Pi的第m个检查点设INT[i](m)表示CP[i](m)和CP[i](m-1)之间的间隔当Pi在INT[i](m)中发送消息x时，带上(i,m)当Pj在INT[j](n)收到x后，记录依赖关系INT[i](m)→INT[j](n)Pj在CP[j](n)中加入该依赖关系当Pi需要回滚到CP[i](m-1)时，则Pj需要回滚到CP[j](n-1)第五十一页，共六十页，2022年，8月28日协作式检查点（2）同步写检查点所有进程同步地在本地稳存中写检查点，使保存的状态自动地保持全局一致。非阻塞式算法分布式快照算法两阶段阻塞式算法CHECKPOINT_REQUEST：协调者发送命令，所有进程写局部检查点，将要发送消息插入队列，向协调者返回ACK消息。CHECKPOINT_DONE：当协调者收到所有的ACK后，发送命令，所有进程继续第五十二页，共六十页，2022年，8月28日协作式检查点（2）改进算法--增量快照算法最近发送进程：进程P在上一个检查点向其发送过请求的进程。协调者恢复依赖进程：在上一个检查点，直接或间接收到协调者消息的进程。因此，由最近发送进程的闭包集组成。协调者只向其最近发送进程多播命令。当进程P收到写检查点请求时，仅向P的最近发送进程，转发该请求。每个进程仅转发该请求一次。当所有进程被确认后，协调者发送第二个多播命令，开始实际写检查点第五十三页，共六十页，2022年，8月28日消息日志（1）基本思想减少检查点的个数如果消息的传送可以重放(replay)，则可取得全局一致性状态，而不必从稳存恢复。分段确定性模型(piecewisedeterministicmodel)，假定：每个进程在一序列的间隔中执行，有先后次序，是确定性的。每个间隔是可重放