分布式系統(tǒng)可靠性設計

分布式系統(tǒng)可靠性設計第一頁，共六十頁，2022年，8月28日10.1分布式容錯模型可依賴系統(tǒng)（Dependable,Trustworthy）可用性（availability）系統(tǒng)可為用戶服務的能力可靠性（Reliability）系統(tǒng)可連續(xù)工作的能力安全性（Safety）系統(tǒng)故障時產生危害的程度可維護性（Maintainability）系統(tǒng)故障修復的難度第二頁，共六十頁，2022年，8月28日基本概念（1）失效（fail,failure）、失靈一個系統(tǒng)不能滿足它的承諾（提供服務）差錯（error）：導致系統(tǒng)失效的原因故障（fault）：導致差錯發(fā)生的原因第三頁，共六十頁，2022年，8月28日基本概念（2）平均無故障時間(MTTF)MeanTimeToFailure平均能夠正常運行多長時間，才發(fā)生一次故障。用來度量可靠性p為每秒失效概率平均無故障時間(MTTF)=Σ1∞kp(1-p)k-1=1/p例：p=10-6，MTTF=106秒=11.6天平均維修時間（MTTR）MeanTimeToRepair系統(tǒng)發(fā)生故障后維修和重新恢復正常運行平均花費的時間用來度量可維護性可用性=(MTTF/(MTTF+MTTR))

第四頁，共六十頁，2022年，8月28日故障的類型按照故障出現(xiàn)的概率短暫型(transient):出現(xiàn)一次，再也不出現(xiàn)間歇型(intermittent)：消失后，再重復出現(xiàn)永久型(permanent)：一直存在按照故障產生的原因節(jié)點故障硬件故障軟件故障時序故障第五頁，共六十頁，2022年，8月28日基本概念（2）故障控制預防去除預告容錯（faulttolerance）即使發(fā)生故障，系統(tǒng)仍能提供服務系統(tǒng)的容錯能力用可允許的故障節(jié)點數(shù)量來衡量。如果系統(tǒng)能夠在k個節(jié)點出現(xiàn)故障的情況下仍然能夠完成任務，則稱該系統(tǒng)為k-容錯系統(tǒng)。第六頁，共六十頁，2022年，8月28日失效（失?。┠Ｐ褪ь愋兔枋霰罎⑿允Х掌魍Ｖ埂５谕Ｖ骨耙恢闭_工作遺漏性失敗

接收遺漏

發(fā)送遺漏服務器不能響應連入的請求

服務器不能接收連入的消息

服務器不能發(fā)送消息定時性失效服務器的響應超出規(guī)定的時間間隔響應性失效

值失效

狀態(tài)變遷失效服務器的響應不正確

響應的值是錯誤的服務器偏離正確的控制流任意性失效服務器在任意的時刻產生任意的響應第七頁，共六十頁，2022年，8月28日失效（失敗）模型失敗模型故障-沉靜系統(tǒng)(fail-silent)。由于故障產生的系統(tǒng)停止不能被其他節(jié)點感知。故障-停止系統(tǒng)(fail-stop)。由于節(jié)點故障產生的系統(tǒng)停止能夠被其他節(jié)點感知。故障-安全系統(tǒng)(fail-safe)。由于節(jié)點故障而停止服務但不會產生隨機故障。拜占庭(Byzantine)故障系統(tǒng)（隨機故障系統(tǒng)）。由于故障導致系統(tǒng)產生任意的響應。惡意的、難檢測。系統(tǒng)類型同步系統(tǒng)：在規(guī)定上限時間內有響應異步系統(tǒng)：響應時間沒有上限第八頁，共六十頁，2022年，8月28日基于冗余的失效屏蔽技術冗余類型信息冗余：如，海明碼。時間冗余：如，重發(fā)，重做物理冗余：軟件:如復制進程硬件：如復制電路信息冗余和物理冗余都屬于空間冗余第九頁，共六十頁，2022年，8月28日基于冗余的失效屏蔽技術三模冗余方法(TMR,TripleModularRedundancy)三路表決器(voter)：三路輸入，一路輸出可屏蔽一路錯誤（任意性失效）第十頁，共六十頁，2022年，8月28日10.2進程的恢復進程容錯進程組：具有相同功能的進程集合組成員籍加入：具有成員籍脫離：注銷成員籍多組成員籍：同時屬于不同的組設計問題需要復制的程度無故障時，平均情況和最壞情況下的系統(tǒng)性能有故障時，平均情況和最壞情況下的系統(tǒng)性能

第十一頁，共六十頁，2022年，8月28日組的管理（1）扁平組：所有成員是同等的層次組：協(xié)調程序和工作程序第十二頁，共六十頁，2022年，8月28日組的管理（2）組成員籍管理組服務器：集中式管理多播通信：分布式管理NN故障后，組的退出fail-stop類型：發(fā)送Goodbye信息fail-silent類型：需其他成員發(fā)現(xiàn)第十三頁，共六十頁，2022年，8月28日組的管理（3）消息同步加入組時：立刻收到所有消息退出組時：不再收到任何消息組的重建當組崩潰后，重新建立組重建協(xié)議第十四頁，共六十頁，2022年，8月28日復制容錯技術（1）復制容錯用多個相同的進程，屏蔽個別故障進程的故障冗余度：相同進程的個數(shù)基于主進程協(xié)議(primary-based)結構：分層組結構協(xié)議：primary-backup協(xié)議復制寫協(xié)議(replicated-write)結構：平面組結構協(xié)議：基于表決數(shù)協(xié)議第十五頁，共六十頁，2022年，8月28日主-后備方法（primarybackup）主服務器失效，則后備服務器接替其任務

接管模型客戶主進程后備進程1.請求2.執(zhí)行3.更新4.執(zhí)行

6.應答5.確認第十六頁，共六十頁，2022年，8月28日復制容錯技術（2）k-容錯度：在有k個進程發(fā)生故障時，系統(tǒng)仍能正確運行Fail-stop型故障：對k-容錯度，需k+1冗余度拜占庭型故障：對k-容錯度，需2k+1冗余度容錯的前提條件

所有的請求到達所有服務器的順序應相同原子廣播問題（atomicbroadcastproblem）

第十七頁，共六十頁，2022年，8月28日故障檢測進程故障檢測主動式方法，發(fā)送“Areyoualive?”消息常用方法，ping操作被動式方法，等待發(fā)來的故障消息超時機制，在規(guī)定時間內作出響應，否則，為故障第十八頁，共六十頁，2022年，8月28日10.3可靠的客戶服務器通信點到點通信可靠通信：防止通信失效遺漏型失效：消息丟失解決策略：利用可靠的傳輸協(xié)議，如TCP協(xié)議。確認和重新傳輸連接崩潰失效：連接中斷不能屏蔽，需重建連接解決策略：拋出例外，通知客戶進程第十九頁，共六十頁，2022年，8月28日RPC失效(1)RPC失效5種失效情況客戶服務器1.定位失敗2.請求消息丟失3.服務器失敗5.客戶失敗4.應答消息丟失第二十頁，共六十頁，2022年，8月28日RPC失效(2)1、客戶不能定位服務器可能服務器被修改，客戶存根（stub）與新的服務器存根不匹配解決策略：拋出例外信號SIG-NOSERVER，然后由編寫的信號處理程序做相應處理。沒有透明性2、丟失請求消息解決策略：客戶發(fā)現(xiàn)超時，重發(fā)請求第二十一頁，共六十頁，2022年，8月28日RPC失效(3)3、服務器崩潰崩潰情況解決策略：至少一次語義最多一次語義聽之任之確切一次語義(a)正常情況;(b)在執(zhí)行后崩潰(c)在執(zhí)行前崩潰第二十二頁，共六十頁，2022年，8月28日RPC失效(4)舉例：打印文本。在打印服務器失效時，客戶和服務器的策略組合M(發(fā)送完成消息)；P(打印)；C(崩潰)客戶服務器策略M->P策略P->M重發(fā)策略MPCMC(P)C(MP)PMCPC(M)C(PM)總是重發(fā)請求DUPOKOKDUPDUPOK不重發(fā)OKOKOK當收到ACK時，重發(fā)DUPOKDUPOK當沒收到ACK時，重發(fā)OKOKOKDUPOK第二十三頁，共六十頁，2022年，8月28日RPC失效(5)4.丟失應答消息解決策略定時器，超時檢測，重發(fā)請求問題：重復操作解決策略構造冪等性操作（idempotent）順序號標志：區(qū)分原始消息和重發(fā)消息第二十四頁，共六十頁，2022年，8月28日RPC失效(6)5.客戶崩潰孤兒進程問題解決策略：根除法：利用日志，撤銷孤兒進程再生法：設置時期（epoch）。到達epoch時，重新創(chuàng)建客戶進程溫和再生法：撤銷無主的孤兒過期法：設置時間量T。如果超過T，則撤銷客戶的請求（不一定是孤兒）。第二十五頁，共六十頁，2022年，8月28日10.4可靠的分組通信假定：進程操作正確，在通信中不加入或退出分組可靠多播將每一個消息遞交給每一個當前組員不可靠多播不能保證將一個多播消息遞交給所有組員SRRRmmm第二十六頁，共六十頁，2022年，8月28日基本的可靠多播模式解決策略消息傳播：記錄順序號報告反饋：如果丟失，返回負ACK，重新發(fā)送第二十七頁，共六十頁，2022年，8月28日可靠多播的可伸縮性（1）反饋爆炸問題：N→1簡單解決方案：接收者只返回NACK消息發(fā)送者保留消息到歷史緩沖區(qū)歷史緩沖區(qū)溢出問題NACK反饋爆炸SRRRACKACKACK第二十八頁，共六十頁，2022年，8月28日可靠多播的可伸縮性（2）反饋抑制技術（SRM,可伸縮的可靠多播協(xié)議）不返回ACK，只返回NACK壓縮NACK。隨機延遲后，如果接收到重發(fā)消息，才發(fā)NACK用途：例，白板系統(tǒng)第二十九頁，共六十頁，2022年，8月28日可靠多播的可伸縮性（3）層次化反饋控制一個大組劃分成若干個小組，形成一個樹發(fā)送者所在的小組為樹的根每個局部協(xié)調者轉發(fā)消息給它的孩子局部協(xié)調者負責請求重發(fā)第三十頁，共六十頁，2022年，8月28日原子性多播(1)原子性多播問題消息要么遞交給所有組員，要么一個也不遞交對于每個組員，所有消息的遞交次序是相同的用途舉例：主動式復制協(xié)議故障組員處理出故障后，自動退出組修復后，重新加入組組視圖G（groupview）在發(fā)送一個消息時，屬于該組的所有進程的名單第三十一頁，共六十頁，2022年，8月28日原子性多播(2)視圖變更向所有的組員宣布加入或者退出該組帶有通信層的分布式系統(tǒng)結構能區(qū)分消息接收和消息遞交第三十二頁，共六十頁，2022年，8月28日原子性多播(3)虛擬同步(virtuallysynchronous)的可靠多播如果發(fā)送者在多播時崩潰，消息將遞交給其他所有組員，或者，被它們丟棄原理：所有多播在視圖變更之間進行第三十三頁，共六十頁，2022年，8月28日原子性多播(4)消息遞交次序1.可靠的無序多播不保證接收到消息的遞交次序是相同的舉例：ProcessP1ProcessP2ProcessP3sendsm1receivesm1receivesm2sendsm2receivesm2receivesm1時間第三十四頁，共六十頁，2022年，8月28日原子性多播(5)2.可靠的FIFO次序多播從同一發(fā)送者接收到的消息的遞交次序與發(fā)送次序一致舉例：發(fā)送者P1,P4；接收者P2,P3ProcessP1ProcessP2ProcessP3ProcessP4sendsm1receivesm1receivesm3sendsm3sendsm2receivesm3receivesm1sendsm4receivesm2receivesm2receivesm4receivesm4時間第三十五頁，共六十頁，2022年，8月28日原子性多播(6)3.可靠的因果次序多播具有因果關系的消息的遞交次序與發(fā)送次序一致，無論消息是否由同一發(fā)送者發(fā)送的可使用時間戳向量實現(xiàn)第三十六頁，共六十頁，2022年，8月28日原子性多播(7)4.全序遞交（Total-ordereddelivery）對于所有組員的消息遞交次序，是相同的。原子性多播：提供全序遞交的虛擬同步可靠多播第三十七頁，共六十頁，2022年，8月28日原子性多播(10)虛擬同步的可靠多播的6個版本多播基本的消息次序全序遞交?可靠多播無NoFIFO多播FIFO次序型遞交No因果多播因果-次序型遞交No原子性多播無YesFIFO原子性多播FIFO-次序型遞交Yes因果原子性多播因果-次序型遞交Yes第三十八頁，共六十頁，2022年，8月28日原子性多播(10)虛擬同步性的實現(xiàn)舉例：ISIS系統(tǒng)P4發(fā)現(xiàn)P7崩潰，多播視圖變更消息(vc)P6發(fā)送所有不穩(wěn)定消息，后跟flush（刷新）消息P6接收到所有返回的flush消息后，確定新的視圖Gi+1第三十九頁，共六十頁，2022年，8月28日10.5分布式提交兩階段提交協(xié)議

(a)協(xié)調者的有限狀態(tài)機(b)參與者的有限狀態(tài)機第四十頁，共六十頁，2022年，8月28日兩階段提交協(xié)議當參與者P處于READY狀態(tài)，并已與另一參與者Q通信之后，可能采取的動作.進程Q狀態(tài)進程P動作COMMIT變遷到COMMITABORT變遷到ABORTINIT變遷到ABORTREADY與其他參與者聯(lián)絡第四十一頁，共六十頁，2022年，8月28日兩階段提交協(xié)議協(xié)調者執(zhí)行步驟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日兩階段提交協(xié)議參與者執(zhí)行步驟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日兩階段提交協(xié)議對來自其他參入者的決策請求的處理步驟/*executedbyseparatethread*/whiletrue{

waituntilanyincomingDECISION_REQUESTisreceived;/*remainblocked*/

readmostrecentlyrecordedSTATEfromthelocallog;

ifSTATE==GLOBAL_COMMIT

sendGLOBAL_COMMITtorequestingparticipant;

elseifSTATE==INITorSTATE==GLOBAL_ABORT

sendGLOBAL_ABORTtorequestingparticipant;

else

skip;/*participantremainsblocked*/第四十四頁，共六十頁，2022年，8月28日三階段提交協(xié)議目的：在失敗即停故障情況下，避免進程阻塞

(a)協(xié)調者的有限狀態(tài)機(b)參與者的有限狀態(tài)機第四十五頁，共六十頁，2022年，8月28日三階段提交協(xié)議協(xié)調者（WAIT）：發(fā)現(xiàn)超時,則abort協(xié)調者(PRECOMMIT)：發(fā)現(xiàn)超時,繼續(xù)commit參與者(INIT)：發(fā)現(xiàn)超時,則abort參與者(READY)：發(fā)現(xiàn)超時，詢問其他參與者如果有COMIT/ABORT,則執(zhí)行如果都為PRECOMMIT,則commit如果有INIT，則abort如果都為READY，則abort參與者(PRECOMMIT)：發(fā)現(xiàn)超時,繼續(xù)commit第四十六頁，共六十頁，2022年，8月28日10.6恢復處理目的:使系統(tǒng)從錯誤狀態(tài)到正確狀態(tài)類型：向后恢復(backwardrecovery)：使系統(tǒng)返回到上一個正確狀態(tài)向前恢復(forwardrecovery)：使系統(tǒng)前進到一個正確的新狀態(tài)檢查點技術(checkpoint)消息日志技術（logging）基于發(fā)送者的寫日志基于接受者的寫日志第四十七頁，共六十頁，2022年，8月28日可恢復的穩(wěn)定存儲器穩(wěn)定存儲器狀態(tài)穩(wěn)定存儲狀態(tài)崩潰狀態(tài)：在更新驅動器1后發(fā)生壞點狀態(tài)：出現(xiàn)壞扇區(qū)第四十八頁，共六十頁，2022年，8月28日檢查點分布式快照（snapshot）一致的全局狀態(tài)恢復線最近的分布式快照，最近的一致性割集舉例第四十九頁，共六十頁，2022年，8月28日獨立檢查點（1）獨立檢查點每個進程的檢查點是相互獨立的問題：多米諾效應局部狀態(tài)沒有形成分布式快照，導致級聯(lián)回滾（cascadedrollback）過程舉例：只有m,m'的接受記錄，沒有發(fā)送記錄第五十頁，共六十頁，2022年，8月28日獨立檢查點（2）解決方法設CP[i](m)表示Pi的第m個檢查點設INT[i](m)表示CP[i](m)和CP[i](m-1)之間的間隔當Pi在INT[i](m)中發(fā)送消息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日協(xié)作式檢查點（2）同步寫檢查點所有進程同步地在本地穩(wěn)存中寫檢查點，使保存的狀態(tài)自動地保持全局一致。非阻塞式算法分布式快照算法兩階段阻塞式算法CHECKPOINT_REQUEST：協(xié)調者發(fā)送命令，所有進程寫局部檢查點，將要發(fā)送消息插入隊列，向協(xié)調者返回ACK消息。CHECKPOINT_DONE：當協(xié)調者收到所有的ACK后，發(fā)送命令，所有進程繼續(xù)第五十二頁，共六十頁，2022年，8月28日協(xié)作式檢查點（2）改進算法--增量快照算法最近發(fā)送進程：進程P在上一個檢查點向其發(fā)送過請求的進程。協(xié)調者恢復依賴進程：在上一個檢查點，直接或間接收到協(xié)調者消息的進程。因此，由最近發(fā)送進程的閉包集組成。協(xié)調者只向其最近發(fā)送進程多播命令。當進程P收到寫檢查點請求時，僅向P的最近發(fā)送進程，轉發(fā)該請求。每個進程僅轉發(fā)該請求一次。當所有進程被確認后，協(xié)調者發(fā)送第二個多播命令，開始實際寫檢查點第五十三頁，共六十頁，2022年，8月28日消息日志（1）基本思想減少檢查點的個數(shù)如果消息的傳送可以重放(replay)，則可取得全局一致性狀態(tài)，而不必從穩(wěn)存恢復。分段確定性模型(piecewisedeterministicmodel)，假定：每個進程在一序列的間隔中執(zhí)行，有先后次序，是確定性的。每個間隔是可重放