高級操作系統(tǒng)課件-第八章容錯性

第八章容錯性容錯性簡介進程復原牢靠的C-S通信牢靠的組通信分布式提交復原容錯性簡介容錯意味著系統(tǒng)即使發(fā)生故障也能供應服務容錯與牢靠性相聯(lián)系，包含以下需求：可用性（Availability）：任何給定的時刻都能剛好工作牢靠性（Reliability）：系統(tǒng)可以無故障地持續(xù)運行平安性（Safety）：系統(tǒng)偶然出現(xiàn)故障能正常操作而不會造成任何災難可維護性（Maintainability）：發(fā)生故障的系統(tǒng)被復原的難易程度故障模型造成錯誤的緣由稱為故障故障分為短暫故障：只發(fā)生一次間歇故障：反復間隔發(fā)生（接觸不良）長久故障：持續(xù)存在的故障（軟件錯誤、磁盤頭損壞）故障模型不同類型的故障故障類型描述崩潰性故障服務器過早停機，但在之前工作正常遺漏性故障

接收故障

發(fā)送故障服務器不能響應到來的請求服務器不能接收到來的消息服務器不能發(fā)送消息定時故障服務器的響應超出了指定的實時要求響應故障

值故障

狀態(tài)轉(zhuǎn)換故障服務器的響應不正確

響應值錯誤服務器偏離了正確的控制流隨意性故障服務器可能在任意的時間產(chǎn)生任意的錯誤運用冗余來掩蓋故障三倍的模塊冗余運用冗余來掩蓋故障故障信息冗余：增加信息，如海明碼校驗時間冗余：多次執(zhí)行一個動作，如事務物理冗余：增加額外的設備或進程進程復原

同等組與等級組為防止進程失敗，把進程復制到組當消息發(fā)送到組時，組中全部成員都接收它，一個進程失敗，其他進程可以接管它進程組是動態(tài)的同等組通信：增加延遲和開銷簡潔等級組通信：單點失效組成員組通信時，須要創(chuàng)建和刪除組，以及允許進程加入和離開運用組管理器：存儲相應數(shù)據(jù)庫，干脆、有效、簡潔實現(xiàn)；單點失敗分布式的方法：加入組:發(fā)消息給全部的組成員離開組:發(fā)消息給全部的組成員，需考慮崩潰的狀況進程加入和離開必需與數(shù)據(jù)消息的發(fā)送同步重建組故障掩蓋和復制復制進程，用一個容錯的進程組來代替一個脆弱的進程須要多少復制?假如系統(tǒng)能經(jīng)受K個組件的故障而且能滿足規(guī)范的要求,被稱為K容錯的假如組件是失敗緘默的，具有K+1個組件即可假如組件發(fā)生拜占庭錯誤（Byzantinefault），接著錯誤運行，則至少須要2K+1個組件才能獲得K容錯拜占庭錯誤：在非失敗緘默模型下，一個有故障的進程可能會對其它進程發(fā)出干擾消息，從而影響這些進程的正常工作。拜占庭錯誤是全部故障類型中最嚴峻的故障系統(tǒng)的協(xié)議(1)分布式協(xié)議算法的目標是使全部的非故障進程就一些問題在有限步驟內(nèi)達成一樣通信是否牢靠：兩軍問題進程故障：拜占庭將軍問題Lamport證明在具有m個故障進程的系統(tǒng)中，只有存在2m+1的正常工作的進程才能達成協(xié)議故障系統(tǒng)的協(xié)議(2)三個忠誠將軍和一個叛徒的問題將軍宣布他們的兵力在(a)基礎上每個將軍的向量每個將軍收到的向量故障系統(tǒng)的協(xié)議(3)兩個忠誠將軍和一個叛徒的問題牢靠的C-S通信RPC系統(tǒng)失敗的五種狀況：客戶不能定位到服務器客戶到服務器的懇求消息丟失：運用定時器服務器在收到懇求后崩潰最少一次語義：再次嘗試操作，將應答傳給用戶，RPC最少執(zhí)行一次最多一次語義：放棄并報告失敗，RPC最多執(zhí)行一次從服務器到客戶的響應消息丟失：運用定時器;冪等操作；為每個懇求安排一個序列號客戶在發(fā)送懇求后崩潰：孤兒進程奢侈資源處理孤兒進程的方法殲滅：客戶重啟后依據(jù)客戶端日志清除孤兒進程再生：將時間分為依次編號的時期，客戶重啟后廣播清除孤兒進程優(yōu)雅再生：找不到擁有者，再清除孤兒進程到期：給每個RPC指定標準的執(zhí)行時間服務器崩潰

ServerCrashes(1)client-server通信中的服務器通常狀況執(zhí)行后崩潰執(zhí)行前崩潰牢靠的組通信牢靠多播:發(fā)送到一個進程組的消息被傳遞到該組的每個成員問題:假如通信期間有進程加入假如通信期間一個（發(fā)送）進程崩潰基本的牢靠多播方法：假定全部的接收者已知而且假定不會失敗的簡潔牢靠多播方法牢靠多播的可擴展性原子多播：實現(xiàn)存在進程失敗的狀況下的牢靠多播牢靠的組通信--基本的牢靠多播方法當全部的接收者已知而且假定不會失敗的簡潔的牢靠多播方法消息傳遞反饋牢靠多播的可擴展性上面介紹的牢靠多播方法不能支持過多的接收者：反饋擁塞解決方法：接收者不反饋，只有通知消息丟失時反饋一消息不能保證恒久不發(fā)生反饋擁塞發(fā)送者須要始終在緩存器中保留消息無等級的反饋限制分等級的反饋限制無等級的反饋限制

NonhierarchicalFeedbackControl反饋抑制：幾個接收者要發(fā)送重發(fā)懇求，但是第一個重發(fā)懇求抑制了其他的懇求。具有很好的可擴展性問題：須要每個接收者對反饋消息進行精確的調(diào)度，否則還會有多個接收者同時反饋中斷其他成功接收消息的進程分等級的反饋限制

HierarchicalFeedbackControl在特別大的接收組中獲得擴展性多等級的牢靠多播：每個本地協(xié)調(diào)者都把消息轉(zhuǎn)發(fā)給它的孩子然后再處理重發(fā)懇求每個子組內(nèi)可運用適合小組的牢靠多播方式協(xié)調(diào)者有自己的緩存器，假如自身丟失消息，則懇求父組的協(xié)調(diào)者重發(fā)消息在基于確認的方法中，假如收到消息，協(xié)調(diào)者向父親發(fā)送確認。假如協(xié)調(diào)者從子組的全部成員和它的孩子得到對消息m的確認，則刪除消息m原子多播須要在存在進程失敗的狀況下獲得牢靠多播的狀況原子多播:消息要么發(fā)送給全部進程，要么一個也不發(fā)送通常須要全部的消息都按相同的依次發(fā)送給全部的進程分布式系統(tǒng)中的復制數(shù)據(jù)庫原子多播確保沒有故障的進程對數(shù)據(jù)庫保持一樣；當一個副本從故障中復原并重新加入組時，原子多播強制它與其他組成員按保持一樣虛擬同步消息排序?qū)崿F(xiàn)虛擬同步虛擬同步

VirtualSynchrony(2)虛擬同步多播的原理虛擬同步：保證多播到組視圖的消息被傳送給組中的每個正常進程假如發(fā)送消息的進程在多播期間失敗，則消息或者傳遞給剩余的全部進程，或者被每個進程忽視全部多播都在視圖變更之間進行消息排序牢靠不排序的多播：對接收不同進程發(fā)送的消息的次序不做任何保證FIFO依次的多播：依據(jù)消息發(fā)送的依次傳送同一進程的消息，對不同進程發(fā)送的消息的傳送依次沒有約束按因果關系排序的多播：按因果關系排序多播來保留消息間的因果關系全序多播：無論消息傳送是無序、FIFO依次還是按因果關系排序，對全部的組成員按相同的次序傳送消息排序(1)--不排序的多播同組中的三個通信進程，每個進程中時間的依次按垂直依次排列ProcessP1ProcessP2ProcessP3sendsm1receivesm1receivesm2sendsm2receivesm2receivesm1消息排序(2)--FIFO依次的多播同組中的四個通信進程，具有兩個不同的發(fā)送者，在FIFO多播下可能的消息傳送依次ProcessP1ProcessP2ProcessP3ProcessP4sendsm1receivesm1receivesm3sendsm3sendsm2receivesm3receivesm1sendsm4receivesm2receivesm2receivesm4receivesm4消息排序(3)--全序多播對全部的組成員按相同的次序傳送ProcessP1ProcessP2ProcessP3ProcessP4sendsm1receivesm1receivesm1sendsm3sendsm2receivesm3receivesm3sendsm4receivesm2receivesm2receivesm4receivesm4消息排序(4)六種不同的虛擬同步牢靠傳播供應了全序的消息傳送的虛擬同步牢靠多播稱為原子多播多播基本的消息排序完全排序傳送可靠多播無不FIFO多播FIFO排序傳送不按因果關系多播按因果關系傳送不原子多播無是FIFO原子多播FIFO排序傳送是按因果關系的原子多播按因果關系傳送是實現(xiàn)虛擬同步保證發(fā)送到組視圖G的全部消息在組成員關系變更之前發(fā)送到G中的全部正常進程進程4留意到進程7已經(jīng)崩潰,發(fā)送一個視圖變更進程6發(fā)送全部的不穩(wěn)定消息（全部進程都收到的消息稱為穩(wěn)定消息），然后發(fā)送一個flush消息當進程6從其他每個進程收到flush消息后，建立一個新的視圖分布式提交—單階段提交分布式提交：具有原子性：要使一個操作被進程組中每一個進程都執(zhí)行或都不執(zhí)行。通常運用協(xié)調(diào)者。協(xié)調(diào)者向事務全部的參與者發(fā)出提交或者中止懇求，并不斷重復該懇求，直到全部參與者報告它們執(zhí)行了該懇求。問題：假如遇到某一問題，導致某一參與者無法完成提交，本協(xié)議就無法實現(xiàn)。NoYes向所有參與者發(fā)“提交”/“中止”請求獲得所有參與者的肯定回答？向未完成者再發(fā)請求分布式提交—兩階段提交(1)簡潔、好用、牢靠，成為事實上的工業(yè)標準。在兩段提交協(xié)議中，將提交分成兩個階段，第一階段（表決階段），事務的協(xié)調(diào)者詢問各個參與者是否可以提交，此時，各個參與者將回答消息發(fā)給協(xié)調(diào)者。協(xié)調(diào)者依據(jù)收到的消息，看是否可以真正提交。其次階段（完成階段），假如可以提交，則通知各參與者馬上執(zhí)行提交，否則，通知它們中止此事務。NoYes向所有參與者發(fā)詢問CanCommit?可以提交？向所有參與者發(fā)立即提交請求DoCommit接受參與者的回答：GetDecision中止本次提交AbortCommit接受參與者的完成回答Havecommited/Haveaborted兩階段提交(2)2PC中的協(xié)調(diào)者的有限狀態(tài)機2PC中的參與者的有限狀態(tài)機參與者一旦投票，則失去自主實力，必需等待協(xié)調(diào)者的最終確定，可能造成堵塞可能的堵塞狀態(tài)：參與者在INIT狀態(tài)等待協(xié)調(diào)者的VOTE_REQUEST消息協(xié)調(diào)者在WAIT狀態(tài)等待來自每個參與者的表決參與者在READY狀態(tài)等待協(xié)調(diào)者發(fā)送的全局表決消息兩階段提交(3)參與者P在READY狀態(tài)下與另一個參與者Q聯(lián)系時實行的行動當全部運行的參與者都處于READY狀態(tài)時，盡管都已同意提交，但可能有崩潰的參與者（不確定同意提交），因而無法做出確定（即使選舉出新的協(xié)調(diào)者），只能等待原協(xié)調(diào)者復原StateofQActionbyPCOMMIT轉(zhuǎn)換到COMMITABORT轉(zhuǎn)換到ABORTINIT轉(zhuǎn)換到ABORTREADY與其他參與者聯(lián)系兩階段提交(4)2PC中協(xié)調(diào)者實行的操作whileSTART_2PCtolocallog;

multicastVOTE_REQUESTtoallparticipants;

whilenotallvoteshavebeencollected{

waitforanyincomingvote;

iftimeout{

whileGLOBAL_ABORTtolocallog;

multicastGLOBAL_ABORTtoallparticipants;

exit;

}

recordvote;

}

ifallparticipantssentVOTE_COMMITandcoordinatorvotesCOMMIT{

writeGLOBAL_COMMITtolocallog;

multicastGLOBAL_COMMITtoallparticipants;

}else{

writeGLOBAL_ABORTtolocallog;

multicastGLOBAL_ABORTtoallparticipants;

}兩階段提交(5)2PC中參與者實行的操作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;

}兩階段提交(6)處理（來自其他READY進程）確定懇求的步驟actionsforhandlingdecisionrequests:/*executedbyseparate

thread*/whiletrue{

waituntilanyincomingDECISION_REQUESTisreceived;/*remainblocked*/

readmostrecentlyrecordedSTATEfromthelocallog;

ifSTATE==GLOBAL_COMMIT

sendGLOBAL_COMMITtorequestingparticipant;

elseifSTATE==INITorSTATE==GLOBAL_ABORT

sendGLOBAL_ABORTtorequestingparticipant;

else

skip;/*participantremainsblocked*/三階段提交三階段提交階段1同兩階段方式階段2收到有一個abortT,則abortT收到全部readyT,則precommitT節(jié)點precommitT之后，寫Log，發(fā)出acknowledgeT階段3收到全部ack，則commitT節(jié)點commit后，發(fā)出ackT收到全部ackT后，completeT三階段提交3PC中的協(xié)調(diào)者的有限狀態(tài)機3PC中的參與者的有限狀態(tài)機沒有一個干脆轉(zhuǎn)換到COMMIT和ABORT的狀態(tài)不存在這樣的狀態(tài)：它不能做出最終確定，而且可以干脆轉(zhuǎn)換到COMMIT狀態(tài)可能的堵塞狀態(tài)：參與者在INIT狀態(tài)等待協(xié)調(diào)者的VOTE_REQUEST消息協(xié)調(diào)者在WAIT狀態(tài)等待來自每個參與者的表決協(xié)調(diào)者在PRECOMMIT狀態(tài)等待來自每個參與者的表決:超時時，認為參與者已崩潰，但已投票參與事務，所以可以多播提交參與者在READY狀態(tài)等待協(xié)調(diào)者發(fā)送的全局消息：超時時，認為協(xié)調(diào)者已崩潰，聯(lián)系其他參與者的狀態(tài)ABORT-〉ABORT；PRECOMMIT-〉PRECOMMIT；都處于READY-〉事務可以被平安中止（因為出故障的參與者還未作出提交的確定），選舉出新的協(xié)調(diào)者接著執(zhí)行參與者在PRECOMMIT狀態(tài)等待協(xié)調(diào)者發(fā)送的全局消息：超時時，認為協(xié)調(diào)者已崩潰，聯(lián)系其他參與者的狀態(tài)COMMIT-〉COMMIT；都處于PRECOMMIT-〉事務平安提交恢復復原：用正確的狀態(tài)代替錯誤的狀態(tài)回退復原（backwardrecovery）:從當前錯誤的狀態(tài)回到從前正確的狀態(tài)須要記錄系統(tǒng)的狀態(tài)（檢查點）通用的技術，不依靠特定的系統(tǒng)或進程向前復原（forwardrecovery）:嘗試從可以接著進行的某點起先把系統(tǒng)帶入一個正確的狀態(tài)須要預先知道會發(fā)生什么錯誤回退復原技術存在的問題開銷較大還可能發(fā)生相同的錯誤有些狀態(tài)無法回退恢復--穩(wěn)定存儲要復原到從前的狀態(tài)，須要存儲所需的信息存儲分類：RAM、磁盤和穩(wěn)定