第7章分布式系統(tǒng)中容錯(cuò)技術(shù)1一臺(tái)計(jì)算機(jī)由各種各樣的硬件和軟件組成，這些部件時(shí)不時(shí)地會(huì)出現(xiàn)故障或錯(cuò)誤，導(dǎo)致死機(jī)或運(yùn)行失敗。

這些故障或錯(cuò)誤往往是隨機(jī)出現(xiàn)的，計(jì)算機(jī)用戶無(wú)法預(yù)料這些情況的出現(xiàn)，有時(shí)甚至察覺(jué)不到錯(cuò)誤的出現(xiàn)。如果一個(gè)計(jì)算機(jī)系統(tǒng)能夠?qū)Ψ穷A(yù)期的軟件/硬件故障有適當(dāng)?shù)膶?duì)策和應(yīng)變措施，則我們說(shuō)這個(gè)系統(tǒng)具備一定的容錯(cuò)(Faulttolerance)

能力。分布式系統(tǒng)的特殊之處在于故障的局部化，即系統(tǒng)的某個(gè)(些)

局部成份出現(xiàn)故障，這種故障可能會(huì)影響到系統(tǒng)的局部功能，而對(duì)系統(tǒng)的其它部分毫無(wú)影響。本章討論內(nèi)容包括容錯(cuò)處理的基本概念、要求和模型，如何實(shí)現(xiàn)可靠的通信，以及當(dāng)發(fā)現(xiàn)故障時(shí)如何排除并恢復(fù)運(yùn)行。27.1分布式系統(tǒng)中的故障模型

7.1.1基本概念

屬性：

可用性

可靠性

安全性可維護(hù)性

保密性完整性

后果：

失效

錯(cuò)誤

故障策略：

防止故障

故障容錯(cuò)

故障恢復(fù)

故障預(yù)報(bào)什么是“可信賴的系統(tǒng)”？如何區(qū)分各種故障？如何處理故障？3可用性：可用性反映的是系統(tǒng)隨時(shí)可被用戶使用的特性?？煽啃裕阂粋€(gè)系統(tǒng)可以無(wú)故障持續(xù)運(yùn)行的程度。與可用性相反，可靠性以時(shí)間周期為基準(zhǔn)，而不是以某個(gè)時(shí)刻為基準(zhǔn)。也就是說(shuō)，一個(gè)高度可靠的系統(tǒng)在相當(dāng)長(zhǎng)的時(shí)間周期里可以無(wú)間斷地為用戶提供服務(wù)安全性：安全性指的是在系統(tǒng)出現(xiàn)暫時(shí)錯(cuò)誤的情況下，不出現(xiàn)災(zāi)難性后果的能力?？删S護(hù)性：可維護(hù)性指的是系統(tǒng)一旦出現(xiàn)故障，系統(tǒng)易于修復(fù)的能力。保密性：保密性要求系統(tǒng)資源不被非法用戶訪問(wèn)?？尚刨囅到y(tǒng)的性質(zhì)4當(dāng)系統(tǒng)不能提供所承諾的服務(wù)時(shí)就認(rèn)為系統(tǒng)失效一個(gè)系統(tǒng)在正常工作時(shí)會(huì)在若干種運(yùn)行狀態(tài)之間變遷，一旦出現(xiàn)異常，則該系統(tǒng)進(jìn)入錯(cuò)誤(Error)

狀態(tài)。一個(gè)系統(tǒng)的錯(cuò)誤狀態(tài)可能是導(dǎo)致系統(tǒng)失效的原因造成錯(cuò)誤的原因稱為故障。歸于導(dǎo)致故障錯(cuò)誤失效故障的種類(lèi)繁多，軟件和硬件都有可能產(chǎn)生故障，而且在某些場(chǎng)合下，與系統(tǒng)無(wú)關(guān)的外部環(huán)境也可能引發(fā)故障。通常分為：暫時(shí)性的(transient)、間歇性的(intermittent)和永久性的(permanent)57.1.2基本的故障模型

拜占庭故障故障類(lèi)故障子類(lèi)故障語(yǔ)義崩潰故障

服務(wù)器崩潰(停機(jī))

，但停機(jī)前工作正常失憶型崩潰服務(wù)器只能從初始狀態(tài)啟動(dòng)，遺忘了崩潰前的狀態(tài)中頓型崩潰服務(wù)器可以從崩潰前的狀態(tài)啟動(dòng)停機(jī)型崩潰服務(wù)器完全停機(jī)失職故障（遺漏故障）

服務(wù)器對(duì)輸入的請(qǐng)求沒(méi)有響應(yīng)接收型失職服務(wù)器無(wú)法接收信件發(fā)送型失職服務(wù)器無(wú)法發(fā)送信件應(yīng)答故障

服務(wù)器對(duì)服務(wù)請(qǐng)求做出錯(cuò)誤反應(yīng)返回值故障返回值出現(xiàn)錯(cuò)誤狀態(tài)變遷故障服務(wù)器偏離正確的運(yùn)行軌跡時(shí)序故障

服務(wù)器反應(yīng)遲緩，超出規(guī)定的時(shí)間間隔隨意故障

服務(wù)器在任意時(shí)間產(chǎn)生的隨意錯(cuò)誤故障分類(lèi)

(與語(yǔ)義有關(guān))6要建立可靠系統(tǒng)就必須控制故障。對(duì)用戶來(lái)講最重要的是容錯(cuò)，即系統(tǒng)發(fā)生故障時(shí)也能提供服務(wù)（對(duì)其他進(jìn)程隱藏故障的發(fā)生）。容錯(cuò)是建立在冗余的基礎(chǔ)上的,冗余類(lèi)型有四種：哺乳動(dòng)物的兩只眼睛、兩個(gè)耳朵、兩個(gè)腎，747飛機(jī)的四個(gè)引擎只用了三個(gè)，多個(gè)體育裁判硬件冗余使用多個(gè)硬件軟件冗余使用多個(gè)軟件信息冗余

海明(Hamming)

校驗(yàn)檢查和奇偶位時(shí)間冗余

超時(shí)重發(fā)技術(shù)：如原子操作和原子事務(wù)處理重復(fù)計(jì)算物理冗余77.1.3故障的基本處理方法(進(jìn)程容錯(cuò)機(jī)制)：(1)主動(dòng)復(fù)制。所有的復(fù)制模塊協(xié)同進(jìn)行，并且它們的狀態(tài)緊密同步。用到了錯(cuò)誤屏蔽的概念——隱藏出現(xiàn)的故障或防止故障造成錯(cuò)誤。把相同進(jìn)程的集合組織到一個(gè)平等組中。在分布式系統(tǒng)中使用主動(dòng)復(fù)制相對(duì)比較昂貴。編組故障屏蔽(2)被動(dòng)復(fù)制。以等級(jí)方式組織進(jìn)程組，其中只有一個(gè)模塊（主進(jìn)程）處于動(dòng)態(tài)，其他模塊的交互狀態(tài)由這一模塊的檢查點(diǎn)定期更新。如果主進(jìn)程崩潰，后備進(jìn)程執(zhí)行選舉算法選擇一個(gè)新的主進(jìn)程。動(dòng)態(tài)方法層次故障屏蔽(3)半主動(dòng)復(fù)制。是主動(dòng)復(fù)制和被動(dòng)復(fù)制的混合方法。此種方法所需的恢復(fù)開(kāi)銷(xiāo)相對(duì)較低。失效的檢測(cè)可分為外部檢測(cè)和內(nèi)部檢測(cè)兩類(lèi)：外部檢測(cè)是指將檢測(cè)節(jié)點(diǎn)失效的職責(zé)賦予被檢測(cè)節(jié)點(diǎn)的外部附件。內(nèi)部檢測(cè)將節(jié)點(diǎn)的失效檢測(cè)機(jī)制置于該節(jié)點(diǎn)內(nèi)部，通常檢測(cè)部件被假定為一個(gè)可以完全信賴的“硬核”。

8Passive(Primary-Backup)Replication

RequestCommunication:

therequestisissuedtotheprimaryRMandcarriesauniquerequestid.Coordination:

Primarytakesrequestsatomically,inorder,checksid(resendsresponseifnotnewid.)Execution:

Primaryexecutes&storestheresponseAgreement:Ifupdate,primarysendsupdatedstate/result,req-idandresponsetoallbackupRMs.Response:

primarysendstothefrontendClientFrontEndRMRMRMClientFrontEndRMprimaryBackupBackupBackup….9FaultToleranceinPassiveReplicationThesystemimplementslinearizability,sincetheprimarysequencesoperationsinorder.Iftheprimaryfails,abackupbecomesprimarybyleaderelection,andthereplicamanagersthatsurviveagreeonwhichoperationshadbeenperformedatthepointwhenthenewprimarytakesover.Theaboverequirementismetifthereplicamanagers(primaryandbackups)areorganizedasagroupandiftheprimaryusesview-synchronousgroupcommunicationtosendupdatestobackups.Thesystemremainslinearizableaftertheprimarycrashes10ActiveReplication

RequestCommunication:

Therequestcontainsauniqueidentifierandismulticasttoallbyareliabletotallyorderedmulticast.Coordination:

Groupcomm.ensuresthatrequestsaredeliveredtoeachRMinthesameorder(butmaybeatdifferenttimes!).Execution:

Eachreplicaexecutestherequest.(Correctreplicasreturnsameresultsincetheyarerunningthesameprogram,i.e.,theyarereplicatedprotocolsorreplicatedstatemachines)Agreement:Noagreementphaseisneeded,becauseofmulticastdeliverysemanticsofrequestsResponse:

EachreplicasendsresponsedirectlytoFE,FEusestheseasbeforeClientFrontEndRMRMClientFrontEndRM….11FaultToleranceinActiveReplicationRMsworkasreplicatedstatemachines,playingequivalentroles.Thatis,eachrespondstoagivenseriesofrequestsinthesameway.ThisisachievedbyrunningthesameprogramcodeatallRMs.IfanyRMcrashes,stateismaintainedbyothercorrectRMs.ThissystemimplementssequentialconsistencyThetotalorderensuresthatallcorrectreplicamanagersprocessthesamesetofrequestsinthesameorder.Eachfrontend’srequestsareservedinFIFOorder(becausethefrontendawaitsaresponsebeforemakingthenextrequest).So,requestsareFIFO-totalordered.Butifclientsaremulti-threadedandcommunicatewithoneanotherwhilewaitingforresponsesfromtheservice,wemayneedtoincorporatecausal-totalordering127.2容錯(cuò)系統(tǒng)的基本構(gòu)件7.2.1堅(jiān)固存儲(chǔ)器（穩(wěn)定存儲(chǔ)器，Lampson提出）

堅(jiān)固存儲(chǔ)器是對(duì)一個(gè)可以經(jīng)受系統(tǒng)失效的特定存儲(chǔ)器的邏輯抽象，也就是說(shuō)，堅(jiān)固存儲(chǔ)器里的內(nèi)容不會(huì)被一個(gè)失效所毀壞。堅(jiān)固存儲(chǔ)器的實(shí)現(xiàn)技術(shù)：磁盤(pán)鏡像：堅(jiān)固存儲(chǔ)器可以用一對(duì)普通磁盤(pán)來(lái)實(shí)現(xiàn)。堅(jiān)固存儲(chǔ)器中的每一個(gè)塊由兩個(gè)獨(dú)立的磁盤(pán)塊組成，分別位于不同的驅(qū)動(dòng)器上，使得它們同時(shí)由于硬件故障受到損壞的機(jī)會(huì)最小。RAID：另一種實(shí)現(xiàn)堅(jiān)固存儲(chǔ)器的方法是使用廉價(jià)磁盤(pán)冗余陣列(RAID)。RAID是通過(guò)運(yùn)用位交錯(cuò)技術(shù)將數(shù)據(jù)分布到多個(gè)磁盤(pán)中，從而提供高I/O性能。可以用一個(gè)或幾個(gè)磁盤(pán)來(lái)檢測(cè)或屏蔽錯(cuò)誤，RAID與傳統(tǒng)磁盤(pán)相比有顯著的優(yōu)點(diǎn)，并可承受多個(gè)失效。13RecoveryStableStorageStableStorageCrashafterdrive1isupdatedBadspot147.2.2故障—停止處理器當(dāng)一個(gè)處理器失效，最可能的是它不進(jìn)行任何不正確的操作，并且簡(jiǎn)單地停止運(yùn)行，這樣的處理器被稱為故障—停止處理器，一個(gè)故障—停止處理器由多個(gè)處理器組成。失效的效果：當(dāng)出現(xiàn)一個(gè)故障時(shí)，故障—停止處理器會(huì)有以下效果：(a)處理器停止運(yùn)行；(b)易失性存儲(chǔ)器的內(nèi)容丟失，而堅(jiān)固存儲(chǔ)器不受影響；(c)任何其他處理器均可以檢測(cè)到故障—停止處理器的失效狀態(tài)。故障—停止處理器的實(shí)現(xiàn)：現(xiàn)有一個(gè)可靠的堅(jiān)固存儲(chǔ)器、一個(gè)可靠的存儲(chǔ)處理器(控制存儲(chǔ)媒介的處理器)以及k+1個(gè)處理器，將它們轉(zhuǎn)變成故障—停止處理器的方法如下：k+1個(gè)處理器中的每一個(gè)都運(yùn)行同樣的程序并通過(guò)存儲(chǔ)處理器訪問(wèn)同一個(gè)堅(jiān)固存儲(chǔ)器。如果任何一個(gè)請(qǐng)求是不同的，或者任何一個(gè)請(qǐng)求沒(méi)有在指定的期間到達(dá)，則意味著檢測(cè)到一個(gè)失效事件，因而應(yīng)該丟棄所有請(qǐng)求。因?yàn)橄到y(tǒng)表現(xiàn)為一個(gè)故障—停止處理器，這一方法產(chǎn)生一個(gè)k—故障—停止處理器，除非系統(tǒng)中k+1個(gè)或更多的部件失效。157.2.3原子操作一個(gè)原子操作就是由硬件獨(dú)立執(zhí)行的一系列動(dòng)作。也就是說(shuō)，每一個(gè)動(dòng)作或者被完全徹底地執(zhí)行，或者所有的動(dòng)作根本沒(méi)有執(zhí)行，系統(tǒng)的狀態(tài)保持不變。原子操作中的每一個(gè)動(dòng)作都是孤立的，當(dāng)執(zhí)行這一動(dòng)作時(shí)，在進(jìn)程中感覺(jué)不到外界活動(dòng)的存在，也意識(shí)不到外界狀態(tài)的變化。與此相似，任何外界的進(jìn)程均感覺(jué)不到一個(gè)孤立的原子操作的內(nèi)在狀態(tài)的變化。這就是所謂的原子操作的“全有或全無(wú)”的性質(zhì)，即一個(gè)原子操作要么全部完成，要么在執(zhí)行過(guò)程中出現(xiàn)錯(cuò)誤的時(shí)候相當(dāng)于根本沒(méi)有執(zhí)行。原子操作失效時(shí)，可以通過(guò)簡(jiǎn)單地重做來(lái)恢復(fù)。16如果由于某個(gè)故障，系統(tǒng)進(jìn)入錯(cuò)誤狀態(tài)，容錯(cuò)處理的目的是采取適當(dāng)?shù)氖侄?，把系統(tǒng)恢復(fù)(Recovery)到無(wú)錯(cuò)誤狀態(tài)。大致上我們可以把系統(tǒng)恢復(fù)技術(shù)歸納為兩類(lèi)：前向恢復(fù)(ForwardRecovery)和逆向恢復(fù)(BackwardRecovery)。前向恢復(fù)技術(shù)，采用一種樂(lè)觀的態(tài)度，當(dāng)系統(tǒng)發(fā)現(xiàn)錯(cuò)誤后，我們?cè)噲D把系統(tǒng)帶入一個(gè)新?tīng)顟B(tài)，從新?tīng)顟B(tài)開(kāi)始繼續(xù)運(yùn)行。關(guān)鍵在于必須預(yù)先知道會(huì)發(fā)生什么錯(cuò)誤。逆向恢復(fù)技術(shù)，向后式恢復(fù)（回退恢復(fù)），采用保守的態(tài)度，事先不知道會(huì)發(fā)生什么故障，在系統(tǒng)正常運(yùn)行時(shí)記錄一些狀態(tài)歷史。一旦當(dāng)失效導(dǎo)致系統(tǒng)處于不一致的狀態(tài)時(shí)，可恢復(fù)到從前沒(méi)有發(fā)生故障的狀態(tài)，重新執(zhí)行。是一種通用方法。開(kāi)銷(xiāo)較大。不能提供完全的故障透明性。需要設(shè)置檢查點(diǎn)?；謴?fù)技術(shù)

7.3節(jié)點(diǎn)故障的處理177.3.1向前式恢復(fù)：例外處理技術(shù)過(guò)程：一個(gè)進(jìn)程或任務(wù)的初始拷貝由不同的處理器來(lái)運(yùn)行。這些版本的結(jié)果在檢查點(diǎn)進(jìn)行表決或比較，如果表決結(jié)果是成功的，則可以獲得一個(gè)儲(chǔ)存在堅(jiān)固存儲(chǔ)器中的正確結(jié)果。在此結(jié)果的基礎(chǔ)上，再執(zhí)行下一項(xiàng)任務(wù)的拷貝。如果表決結(jié)果是失敗的，對(duì)以前的任務(wù)進(jìn)行一次回退執(zhí)行。也就是說(shuō)，在后備處理器上再運(yùn)行以前的任務(wù)，目的是獲得正確的結(jié)果。盡管在所有版本都失效(所有結(jié)果都不正確)或者表決也不能獲得正確結(jié)果的情況下，回退運(yùn)行是不可避免的，但由于利用了現(xiàn)存的正確結(jié)果而不必從頭重新開(kāi)始，還是節(jié)省了回退時(shí)間。前向恢復(fù)技術(shù)的關(guān)鍵是要事先掌握可能出現(xiàn)的故障，并且為每一種故障定義了相應(yīng)的恢復(fù)操作，于是才能在故障出現(xiàn)時(shí)把系統(tǒng)切換到一個(gè)新的狀態(tài)。前向恢復(fù)技術(shù)的要求過(guò)于苛刻，我們無(wú)法預(yù)先估計(jì)到所有可能發(fā)生的故障。18向前式恢復(fù)方案的實(shí)例：其中Ii，Ii+1和Ii+2是檢查點(diǎn)間隔。兩個(gè)進(jìn)程X和Y均運(yùn)行一個(gè)進(jìn)程的同一個(gè)版本。在每一個(gè)檢查點(diǎn)之前，需要對(duì)它們的結(jié)果進(jìn)行比較并確認(rèn)是否正確。S是一個(gè)后備處理器，對(duì)兩個(gè)間隔Ii和Ii+1進(jìn)行驗(yàn)證。有以下四種可能的情況：(1)沒(méi)有并發(fā)重試。如果X和Y都在間隔Ii正確運(yùn)行，那么X和Y在間隔Ii所得的結(jié)果是相同的，S不進(jìn)行并發(fā)重試。Pradhan、Vaidya提出19(2)有非回退的并發(fā)重試。在Ii中出現(xiàn)了錯(cuò)誤，但在兩個(gè)合法的檢查點(diǎn)間隔Ii+1和Ii+2中間沒(méi)有錯(cuò)誤。如果我們用(Xi,Yi,Si)代表在間隔Ii之中X、Y和S的狀態(tài)，并且用0代表錯(cuò)誤，1代表正確，d代表沒(méi)有關(guān)系(或者錯(cuò)誤或者正常)。(Xi,Yi,Si)就有兩種情況：(1,0,1)和(0,1,1)，無(wú)論哪種情況，系統(tǒng)都可以判斷哪個(gè)進(jìn)程是正確的，所以不用回退。(3)在一次并發(fā)重試的間隔后進(jìn)行回退。對(duì)應(yīng)于在Ii中有兩個(gè)進(jìn)程(X、Y和S中的兩個(gè))有錯(cuò)誤的情況。若用(Xi,Yi,Si)代表在間隔Ii之中X、Y和S的狀態(tài)，可得到三種情況：(1,0,0)，(0,1,0)，(0,0,d)。這三種情況是在一次并發(fā)重試的間隔后進(jìn)行回退。系統(tǒng)回退到Ii的開(kāi)始處。20(4)在并發(fā)重試的兩次間隔之后回退。該情況下在檢查點(diǎn)間隔Ii+1處出現(xiàn)了一個(gè)額外的錯(cuò)誤，如果我們用(Xi,Yi,Si,Xi+1,Yi+1,Si+1)代表在間隔Ii和Ii+1中X、Y和S的狀態(tài)，這種情況對(duì)應(yīng)于以下描述的四種情形：(1,0,1,d,d,0)，(1,0,1,0,d,d)，(0,1,1,d,d,0)，(0,1,1,d,0,d)。可以確定間隔Ii中哪個(gè)進(jìn)程是正確的，但是不能確定間隔Ii+1中哪個(gè)進(jìn)程是正確的。系統(tǒng)回退到間隔Ii+1的起始處。217.3.2向后式恢復(fù)：檢查點(diǎn)技術(shù)檢查點(diǎn)：在向后式恢復(fù)中進(jìn)程被恢復(fù)到一個(gè)先前的正確的狀態(tài)。進(jìn)程執(zhí)行中的一些點(diǎn)被稱為“檢查點(diǎn)”(checkpoint)，在以后發(fā)生錯(cuò)誤的情況下，進(jìn)程可以被恢復(fù)到這些點(diǎn)。在檢查點(diǎn)的實(shí)現(xiàn)過(guò)程中，需要考慮兩個(gè)主要問(wèn)題：檢查點(diǎn)的存儲(chǔ)和檢查點(diǎn)的更新。局部快照合法恢復(fù)線非法恢復(fù)線22有兩種方法來(lái)保存檢查點(diǎn)：(1)每個(gè)檢查點(diǎn)被組播到每一個(gè)備份模塊；(2)每個(gè)檢查點(diǎn)被存儲(chǔ)在其本地堅(jiān)固存儲(chǔ)器中。當(dāng)進(jìn)程正確地從一個(gè)舊的檢查點(diǎn)運(yùn)行到一個(gè)新的檢查點(diǎn)時(shí)，舊的檢查點(diǎn)就要被新的檢查點(diǎn)替換。當(dāng)進(jìn)程執(zhí)行到兩個(gè)檢查點(diǎn)之間時(shí)發(fā)生錯(cuò)誤，那么進(jìn)程應(yīng)該卷回到舊的檢查點(diǎn)處重新執(zhí)行。檢查點(diǎn)的原子更新：當(dāng)使用新的檢查點(diǎn)替換舊的檢查點(diǎn)的過(guò)程中，系統(tǒng)也會(huì)發(fā)生失效。這可以通過(guò)檢查點(diǎn)的原子更新過(guò)程來(lái)解決，也就是說(shuō)，在檢查點(diǎn)的更新中，要么舊的檢查點(diǎn)被新的檢查點(diǎn)替換，要么舊的檢查點(diǎn)被完整地保留。檢查點(diǎn)原子更新的實(shí)現(xiàn)：假設(shè)庫(kù)A和庫(kù)B現(xiàn)在保存的檢查點(diǎn)是C1，現(xiàn)在要用檢查點(diǎn)C2取代庫(kù)A和庫(kù)B的內(nèi)容。在取代前，假設(shè)Ta1=Ta2=Tb1=Tb2=1，檢查點(diǎn)的更新過(guò)程如下：(1)為了更新庫(kù)A，先置Ta1=2；(2)將庫(kù)A的內(nèi)容用檢查點(diǎn)C2取代；(3)庫(kù)A更新完畢，置Ta2=2；(4)為了更新庫(kù)B，先置Tb1=2；(5)將庫(kù)B的內(nèi)容用檢查點(diǎn)C2取代；(6)庫(kù)B更新完畢，置Tb2=2；23識(shí)別在檢查點(diǎn)更新過(guò)程中發(fā)生的失效：基于影像頁(yè)面技術(shù)的恢復(fù)方案：在基于影像頁(yè)面技術(shù)的方案中，當(dāng)進(jìn)程需要修改一個(gè)頁(yè)面時(shí)，系統(tǒng)復(fù)制該頁(yè)并保留在堅(jiān)固存儲(chǔ)器中。系統(tǒng)中每個(gè)頁(yè)面都有兩個(gè)拷貝，當(dāng)進(jìn)程在執(zhí)行的過(guò)程中，只有其中的一個(gè)拷貝被進(jìn)程修改，另一個(gè)拷貝就作為影像頁(yè)面。如果進(jìn)程失效，則丟棄被修改的拷貝，系統(tǒng)根據(jù)影像頁(yè)面進(jìn)行恢復(fù)。如果進(jìn)程成功運(yùn)行，則每一份影像頁(yè)面被相應(yīng)的修改后的頁(yè)面替換。247.4分布式檢查點(diǎn)算法7.4.1一致性檢查點(diǎn)全局狀態(tài)：一種全局狀態(tài)的定義是一系列局部狀態(tài)的集合，代表系統(tǒng)曾經(jīng)歷過(guò)的某個(gè)狀態(tài)。這里的局部狀態(tài)就是一個(gè)進(jìn)程的檢查點(diǎn)，每個(gè)局部進(jìn)程有一個(gè)局部狀態(tài)。可利用分布式快照算法保證系統(tǒng)的全局一致性。即系統(tǒng)中每一個(gè)進(jìn)程周期地“快照”自身的狀態(tài)，并把狀態(tài)數(shù)據(jù)存放在局部堅(jiān)固存儲(chǔ)器中。當(dāng)某個(gè)進(jìn)程或系統(tǒng)發(fā)生故障需要恢復(fù)以前的狀態(tài)時(shí)，就利用這些局部快照構(gòu)造出一個(gè)全局一致的狀態(tài)，令整個(gè)系統(tǒng)根據(jù)這個(gè)全局狀態(tài)恢復(fù)運(yùn)行。25恢復(fù)線和切割線：一個(gè)分布式快照對(duì)應(yīng)一個(gè)全局一致的狀態(tài)，該全局狀態(tài)是離故障點(diǎn)最近的系統(tǒng)快照。這個(gè)分布式快照可以作為一個(gè)恢復(fù)線(recoveryline)用于恢復(fù)。恢復(fù)線在每一進(jìn)程的快照上必須選擇一致的切入點(diǎn)。即，一個(gè)恢復(fù)線對(duì)應(yīng)于最近的一個(gè)一致性切割線262）局部檢查點(diǎn)可能組成如下兩種不一致的全局狀態(tài)：丟失報(bào)文。進(jìn)程Pi的檢查點(diǎn)狀態(tài)顯示它給進(jìn)程Pj發(fā)送了報(bào)文m，但是進(jìn)程Pj并沒(méi)有關(guān)于該報(bào)文的紀(jì)錄。孤兒報(bào)文。進(jìn)程Pj的檢查點(diǎn)狀態(tài)顯示它收到了一個(gè)來(lái)自進(jìn)程Pi的報(bào)文m，但是進(jìn)程Pi的狀態(tài)顯示它沒(méi)有向進(jìn)程Pj發(fā)送過(guò)報(bào)文m。不一致全局狀態(tài)實(shí)例：27一個(gè)強(qiáng)一致(stronglyconsistent)的檢查點(diǎn)集合是由一系列的沒(méi)有孤兒報(bào)文和沒(méi)有丟失報(bào)文局部檢查點(diǎn)組成。一個(gè)一致的檢查點(diǎn)集合是由一系列沒(méi)有孤兒報(bào)文的局部檢查點(diǎn)組成。顯然一個(gè)強(qiáng)一致的檢查點(diǎn)集合包括一系列局部檢查點(diǎn)，在這些檢查點(diǎn)之間，進(jìn)程之間沒(méi)有報(bào)文傳送。如果每個(gè)進(jìn)程都在發(fā)送一個(gè)報(bào)文之后生成一個(gè)檢查點(diǎn)，那么最近的檢查點(diǎn)集合將永遠(yuǎn)是一致的。3）檢查點(diǎn)的設(shè)置可以是同步的，或異步的，也可以是兩者的混合。287.4.2異步檢查點(diǎn)異步檢查點(diǎn)算法中，程序中各進(jìn)程周期性地相互獨(dú)立地保存自己的運(yùn)行狀態(tài)，程序各進(jìn)程之間不需要相互協(xié)商。在恢復(fù)過(guò)程中，各進(jìn)程之間則需要相互協(xié)商通過(guò)復(fù)雜的回退算法各自回退到合適的檢查點(diǎn)時(shí)刻以使整個(gè)程序的各個(gè)進(jìn)程恢復(fù)到最近的一個(gè)一致的全局狀態(tài)。一致檢查點(diǎn)的檢測(cè)方法：比較發(fā)送的和接收的報(bào)文數(shù)量來(lái)檢測(cè)孤兒報(bào)文的存在。如果接收到的報(bào)文數(shù)目和任何發(fā)送報(bào)文的進(jìn)程發(fā)送的報(bào)文的數(shù)目是一致的，那么就可以認(rèn)為找到了一個(gè)局部檢查點(diǎn)的一致集合。使用間隔依賴圖來(lái)進(jìn)行檢測(cè)。如果每個(gè)進(jìn)程i的向量時(shí)鐘是LCi，一個(gè)檢查點(diǎn)集合是一致的，當(dāng)且僅當(dāng)不存在i和j滿足LCi＜LCj，即不存在孤兒報(bào)文。

4）算法的優(yōu)缺點(diǎn)：允許分布式程序的各個(gè)進(jìn)程擁有最大程度的自治性，算法的延遲較小。但由于每個(gè)進(jìn)程需要保存若干時(shí)刻的檢查點(diǎn)信息，空間開(kāi)銷(xiāo)較大；其次，在恢復(fù)過(guò)程中可能會(huì)重復(fù)回退，甚至出現(xiàn)多米諾效應(yīng)，使程序一直回退到初始狀態(tài)。29多米諾效應(yīng)(dominoeffect)由于進(jìn)程的分布式特性，要找到一個(gè)恢復(fù)線較困難。需要每個(gè)進(jìn)程都回退到它最近保存的狀態(tài)。每個(gè)進(jìn)程都定期地對(duì)狀態(tài)設(shè)置檢查點(diǎn)，各進(jìn)程之間設(shè)置檢查點(diǎn)的過(guò)程是獨(dú)立的，與系統(tǒng)中其他進(jìn)程毫無(wú)協(xié)調(diào)。一旦需要形成一條恢復(fù)線，每個(gè)進(jìn)程只能回溯到它最近保存的那個(gè)局部快照，然后通過(guò)一個(gè)檢驗(yàn)算法來(lái)核對(duì)一致性。如果檢驗(yàn)成功，則皆大歡喜；反之，就必須令所有進(jìn)程進(jìn)一步回退，一直到形成一條合法恢復(fù)線為止。這種折疊回退的過(guò)程可能會(huì)導(dǎo)致多米諾效應(yīng)。例如，為解決孤兒報(bào)文的問(wèn)題，由于一個(gè)進(jìn)程的回退導(dǎo)致另外一個(gè)或多個(gè)進(jìn)程的回退的效應(yīng)，即多米諾效應(yīng)。

Thedominoeffect307.4.3同步檢查點(diǎn)（協(xié)調(diào)檢查點(diǎn)）在同步檢查點(diǎn)算法中，各相關(guān)進(jìn)程協(xié)調(diào)它們的局部檢查點(diǎn)的建立行為，以保證所有的最近的檢查點(diǎn)都是一致的。在同步檢查點(diǎn)中，只有最近的一致的檢查點(diǎn)集合才需要被維護(hù)和保存。即所有進(jìn)程都同步地把它們的狀態(tài)寫(xiě)到本地穩(wěn)定存儲(chǔ)器中。算法的優(yōu)缺點(diǎn)：由于使用同步檢查點(diǎn)算法，各進(jìn)程的局部檢查點(diǎn)組成的集合是一個(gè)全局一致的狀態(tài)，所以在恢復(fù)時(shí)各個(gè)進(jìn)程只需要簡(jiǎn)單地從檢查點(diǎn)處重新開(kāi)始執(zhí)行。優(yōu)點(diǎn)是每個(gè)進(jìn)程只需保存最近時(shí)刻的檢查點(diǎn)信息，空間開(kāi)銷(xiāo)較小，且在恢復(fù)的時(shí)候沒(méi)有多米諾效應(yīng)。其缺點(diǎn)是，在建立檢查點(diǎn)時(shí)，各進(jìn)程間的同步使程序運(yùn)行中止時(shí)間較長(zhǎng)，且中央?yún)f(xié)調(diào)者是系統(tǒng)瓶頸。Sync-and-Stop(SNS)算法中有一個(gè)進(jìn)程pc負(fù)責(zé)管理全局檢查點(diǎn)建立過(guò)程。各進(jìn)程的檢查點(diǎn)建立過(guò)程如下：pc向所有進(jìn)程廣播檢查點(diǎn)開(kāi)始報(bào)文Mb(第一次同步開(kāi)始)；任一個(gè)進(jìn)程接收到報(bào)文Mb后停止運(yùn)行，并在自己所發(fā)送的報(bào)文全部到達(dá)接收者后向pc進(jìn)程發(fā)送報(bào)文Ms1；31pc接收到所有進(jìn)程發(fā)送的報(bào)文Ms2后，意味著第二次同步結(jié)束。pc向所有進(jìn)程廣播報(bào)文Me；各進(jìn)程接收到報(bào)文Me后，刪除舊的檢查點(diǎn)，僅保留新的檢查點(diǎn)，然后繼續(xù)執(zhí)行。SNS算法的恢復(fù)過(guò)程十分簡(jiǎn)單，只需回退到檢查點(diǎn)處繼續(xù)執(zhí)行。

經(jīng)過(guò)第一次同步之后，任何進(jìn)程所發(fā)送的報(bào)文都已經(jīng)被對(duì)應(yīng)的接收進(jìn)程接收到，任何進(jìn)程之間不會(huì)存在孤兒報(bào)文，滿足一致性的要求。pc接收到所有進(jìn)程發(fā)送的報(bào)文Ms1后，即意味著第一次同步結(jié)束。pc向各進(jìn)程廣播報(bào)文Mchk，第二次同步開(kāi)始；任一個(gè)進(jìn)程接收到報(bào)文Mchk后，立即作局部檢查點(diǎn)，檢查點(diǎn)建立完成之后向pc發(fā)送報(bào)文Ms2；32Chandy-Lamport(CL)算法：機(jī)器mc與m1之間有通道直接相連，可直接相互發(fā)送報(bào)文，機(jī)器mc與m1稱為直接相連；機(jī)器mc與m2之間沒(méi)有直接通道相連，它們間相互發(fā)送的報(bào)文要通過(guò)m1轉(zhuǎn)發(fā)，機(jī)器mc與m2稱為間接相連。建立檢查點(diǎn)的過(guò)程可由任一個(gè)進(jìn)程pc發(fā)起，pc進(jìn)程停止運(yùn)行，并向與其所在機(jī)器直接相連的機(jī)器上的進(jìn)程廣播報(bào)文Mb，然后進(jìn)程pc建立局部檢查點(diǎn)；進(jìn)程p接收到報(bào)文Mb后，若進(jìn)程p還未開(kāi)始建立檢查點(diǎn)，則進(jìn)程p停止運(yùn)行并立即向與其所在機(jī)器直接相連的機(jī)器上的進(jìn)程廣播報(bào)文Mb，然后進(jìn)程p建立局部檢查點(diǎn)；進(jìn)程p開(kāi)始建立檢查點(diǎn)后，若接收到其他進(jìn)程發(fā)送的非檢查點(diǎn)控制報(bào)文m，則保存報(bào)文m；33當(dāng)進(jìn)程p完成局部檢查點(diǎn)的建立，并且接收到與其所在機(jī)器直接相連的機(jī)器上的所有進(jìn)程發(fā)送的報(bào)文Mb后，進(jìn)程p向pc進(jìn)程發(fā)送報(bào)文Ms；當(dāng)進(jìn)程pc接收到所有進(jìn)程發(fā)送的報(bào)文Ms后，pc進(jìn)程向所有進(jìn)程發(fā)送報(bào)文Me，并刪除本進(jìn)程舊的檢查點(diǎn)，進(jìn)程pc繼續(xù)執(zhí)行；其他進(jìn)程p接收到報(bào)文Me后，刪除本進(jìn)程舊的檢查點(diǎn)，繼續(xù)執(zhí)行。在恢復(fù)過(guò)程中，CL算法在回退到當(dāng)前檢查點(diǎn)重新執(zhí)行的同時(shí)還必須重發(fā)過(guò)程(c)中保存的報(bào)文m。與SNS算法相比，CL算法減少了兩次全局同步的開(kāi)銷(xiāo)。CL算法的缺點(diǎn)是其控制報(bào)文的數(shù)目與機(jī)器間的拓?fù)浣Y(jié)構(gòu)有關(guān)。347.4.4混合檢查點(diǎn)其基本思想是在一個(gè)較長(zhǎng)的時(shí)間段中使用同步檢查點(diǎn)，而在較短的時(shí)間段內(nèi)使用異步檢查點(diǎn)。也就是說(shuō)，在一個(gè)同步時(shí)間段里，會(huì)有若干個(gè)異步時(shí)間段。因此，我們可以有一個(gè)可以控制的回退，從而保證不會(huì)在建立檢查點(diǎn)的過(guò)程中引入過(guò)多的開(kāi)銷(xiāo)。

例如：準(zhǔn)同步檢查點(diǎn)。這個(gè)方法允許每個(gè)進(jìn)程異步地設(shè)置檢查點(diǎn)，從而保證了進(jìn)程的獨(dú)立性。同時(shí)，對(duì)恢復(fù)線的擴(kuò)展采用發(fā)起通信的檢查點(diǎn)協(xié)調(diào)方法，從而可以限制恢復(fù)過(guò)程中回退的傳播。7.4.5報(bào)文日志：日志技術(shù)日志技術(shù)不僅用于故障恢復(fù)，也常常用于故障收集、故障報(bào)告、以及故障診斷等方面。與保存系統(tǒng)狀態(tài)相比，記錄日志不但節(jié)省時(shí)間，也節(jié)省存儲(chǔ)空間，因?yàn)楸４嫦到y(tǒng)快照要求面面俱到，而保存日志只需要少許的關(guān)鍵信息。不同層次、不同應(yīng)用領(lǐng)域中的故障恢復(fù)系統(tǒng)對(duì)日志的觀點(diǎn)亦不相同。例如，在分布式數(shù)據(jù)庫(kù)系統(tǒng)中，日志記錄以事務(wù)為單位，記載各事務(wù)對(duì)數(shù)據(jù)的更新操作和狀態(tài)。其典型格式為〈事務(wù)標(biāo)識(shí)，數(shù)據(jù)項(xiàng)，老值，新值〉，以及執(zhí)行2PC的有關(guān)信息。35報(bào)文日志：為了減少回退時(shí)撤銷(xiāo)的計(jì)算工作量，所有接收的和發(fā)送的報(bào)文都可以記錄下來(lái)。前者叫做接收者日志，后者叫做發(fā)送者日志。它使用一個(gè)檢查點(diǎn)狀態(tài)作為開(kāi)始點(diǎn)，然后簡(jiǎn)單地把從該點(diǎn)以后發(fā)送的所有消息都重發(fā)并進(jìn)行處理。當(dāng)Pj的檢查點(diǎn)被恢復(fù)到一個(gè)沒(méi)有孤兒報(bào)文，而且所有要發(fā)送的報(bào)文都已經(jīng)發(fā)送的一致?tīng)顟B(tài)的時(shí)候，可以用Pj的接收者日志減少回退工作量，即只需要將Pj所收到的報(bào)文重新向Pj發(fā)送一遍即可。

如果進(jìn)程Pj記錄了報(bào)文m的接收者日志，那么Pi和Pj的當(dāng)前檢查點(diǎn)集合就可以看作是一致的。一旦Pj由于失效回退到當(dāng)前檢查點(diǎn)重新執(zhí)行的時(shí)候，報(bào)文m就可以通過(guò)Pj的接收者日志重新發(fā)送給進(jìn)程Pj，不會(huì)引起進(jìn)程Pi的任何回退。36如果Pi在發(fā)送完報(bào)文m后失效，那么當(dāng)進(jìn)程Pi恢復(fù)到當(dāng)前檢查點(diǎn)后，它會(huì)根據(jù)發(fā)送者日志的紀(jì)錄知道曾經(jīng)發(fā)送過(guò)報(bào)文m，這樣就沒(méi)有必要再發(fā)送一次了。如果接收者Pj失效，而且沒(méi)有接收者日志，它仍然可以根據(jù)從發(fā)送者日志中得到的報(bào)文正確恢復(fù)。37Alvisi和Marzullo的報(bào)文日志方案報(bào)文格式：每個(gè)報(bào)文m包含有一個(gè)報(bào)文頭用于存放重發(fā)這個(gè)報(bào)文和正確處理這個(gè)報(bào)文所必需的一些信息，例如，該報(bào)文的發(fā)送者和接收者，用于識(shí)別報(bào)文重復(fù)的序列號(hào)，另外還有一個(gè)傳輸號(hào)用于決定何時(shí)該報(bào)文需要傳遞給接收進(jìn)程。

堅(jiān)固的報(bào)文：如果一個(gè)報(bào)文不再會(huì)丟失，則稱這個(gè)報(bào)文是堅(jiān)固的，例如當(dāng)一個(gè)報(bào)文已經(jīng)被寫(xiě)入到堅(jiān)固存儲(chǔ)器中，就可以說(shuō)這個(gè)報(bào)文是堅(jiān)固的。堅(jiān)固的報(bào)文可以重新發(fā)送給失效后重新恢復(fù)的進(jìn)程。進(jìn)程集合DEP(m)的組成：一個(gè)報(bào)文m對(duì)應(yīng)于一個(gè)進(jìn)程集合DEP(m)，該集合包含了與報(bào)文m傳輸有關(guān)的所有進(jìn)程。DEP(m)包含了所有接收該報(bào)文m的進(jìn)程；

如果另外一個(gè)報(bào)文m’和報(bào)文m有因果依賴性關(guān)系，并且m’是傳遞給進(jìn)程Q的，那么DEP(m)集合中應(yīng)該包含進(jìn)程Q。因果依賴性關(guān)系：如果m’和m是由同一個(gè)進(jìn)程發(fā)送的，并且m的發(fā)送先于m’的發(fā)送，則說(shuō)m’和報(bào)文m的傳輸有因果依賴性關(guān)系。同樣地，如果m”和m’有因果依賴性關(guān)系，m’和m有因果依賴性關(guān)系，則說(shuō)m”和m有因果依賴性關(guān)系。38進(jìn)程集合COPY(m)的組成：如果一個(gè)進(jìn)程有報(bào)文m的一個(gè)拷貝，但是這個(gè)拷貝還沒(méi)有寫(xiě)入到它的局部堅(jiān)固存儲(chǔ)器中的話，該進(jìn)程就屬于集合COPY(m)。當(dāng)一個(gè)進(jìn)程發(fā)送了報(bào)文m，它也屬于集合COPY(m)。值得注意的是COPY(m)集合中所包含的進(jìn)程是那些擁有報(bào)文m的拷貝，并且在出現(xiàn)失效的時(shí)候，能夠重新傳輸報(bào)文m的進(jìn)程。當(dāng)COPY(m)中的所有進(jìn)程都失效時(shí)，顯然報(bào)文m就不能被重新傳輸。

孤兒進(jìn)程：假設(shè)在一個(gè)分布式系統(tǒng)中，某個(gè)或某些進(jìn)程失效了，Q是一個(gè)存活下來(lái)的進(jìn)程。有一個(gè)報(bào)文m，如果進(jìn)程Q是集合DEP(m)中的一個(gè)元素，而集合COPY(m)中的所有進(jìn)程都失效了，那么Q就是一個(gè)孤兒進(jìn)程。也就是說(shuō)，當(dāng)一個(gè)進(jìn)程依賴于報(bào)文m，但是無(wú)法向該進(jìn)程重發(fā)報(bào)文m，該進(jìn)程就是一個(gè)孤兒進(jìn)程。

避免孤兒進(jìn)程的出現(xiàn)：需要確保當(dāng)集合COPY(m)中的進(jìn)程都失效的時(shí)候，DEP(m)中沒(méi)有存活的進(jìn)程。也就是說(shuō)，DEP(m)中的進(jìn)程也必須全部失效。這可以通過(guò)如下的強(qiáng)制方式得以實(shí)現(xiàn)，當(dāng)一個(gè)進(jìn)程成為DEP(m)中的一個(gè)成員的時(shí)候，我們強(qiáng)制它也成為COPY(m)的一個(gè)成員。也就是說(shuō)，當(dāng)一個(gè)進(jìn)程依賴于報(bào)文m的傳輸?shù)臅r(shí)候，它將保持報(bào)文m的一個(gè)副本。39悲觀的日志協(xié)議：每一個(gè)非堅(jiān)固的報(bào)文m，確保最多只有一個(gè)進(jìn)程依賴于報(bào)文m。也就是說(shuō)，對(duì)于每一個(gè)非堅(jiān)定的報(bào)文m，悲觀的日志協(xié)議確保該報(bào)文最多只傳給了一個(gè)進(jìn)程。值得注意的是，一旦一個(gè)非堅(jiān)定的報(bào)文m傳遞給了進(jìn)程P，P就成為集合COPY(m)的一個(gè)成員。最壞的情況是在報(bào)文m寫(xiě)入到堅(jiān)固存儲(chǔ)器之前，進(jìn)程P失效了。因?yàn)樵诒^的日志協(xié)議下，在報(bào)文m寫(xiě)入到堅(jiān)固存儲(chǔ)器之前，不允許P發(fā)送任何報(bào)文，所以不會(huì)有其他進(jìn)程依賴于報(bào)文m，也就不會(huì)有重發(fā)報(bào)文m的可能性。所以，使用悲觀的日志協(xié)議避免了孤兒進(jìn)程的問(wèn)題。樂(lè)觀的日志協(xié)議：在樂(lè)觀的日志協(xié)議下，實(shí)際的工作是在失效發(fā)生之后進(jìn)行的。假定對(duì)某個(gè)報(bào)文m來(lái)說(shuō)，如果集合COPY(m)中的每個(gè)進(jìn)程都失效了，DEP(m)中的每個(gè)孤兒進(jìn)程一直要回退到以前的某個(gè)狀態(tài)，在這個(gè)狀態(tài)下，該進(jìn)程不再是集合DEP(m)中的一個(gè)成員。很明顯，樂(lè)觀的日志協(xié)議需要保持追蹤依賴性關(guān)系，從而使得它的實(shí)現(xiàn)變得復(fù)雜。407.5拜占庭故障的恢復(fù)故障-停止型故障與拜占庭式故障：在故障-停止模型中，我們假定一個(gè)處理器將停止工作并且不再恢復(fù)運(yùn)轉(zhuǎn)。在其他情況下，一個(gè)故障可能做出破壞性的行為。例如，一個(gè)有故障的處理器可能會(huì)向不同的處理器發(fā)送不同的令它們費(fèi)解的報(bào)文，這種故障叫做隨意性故障(arbitraryfault)，或拜占庭式故障(Byzantinefault)。由Pease(1980)和Lamport(1982)進(jìn)行了分析。

處理這類(lèi)故障的一個(gè)主要方案是將多個(gè)完全相同的進(jìn)程設(shè)置成為一個(gè)進(jìn)程組，當(dāng)消息發(fā)送到組本身時(shí)，組中所有成員都接收它，從而達(dá)到容錯(cuò)的目的。7.1.3進(jìn)程容錯(cuò)機(jī)制－主動(dòng)復(fù)制（層次故障屏蔽）、被動(dòng)復(fù)制（編組故障屏蔽）417.5.1恢復(fù)中的設(shè)計(jì)問(wèn)題進(jìn)程組的內(nèi)部結(jié)構(gòu)：編組目的是把若干等同的進(jìn)程抽象成一個(gè)具備容錯(cuò)能力的虛進(jìn)程。組內(nèi)成員具備彼此通信的能力平面結(jié)構(gòu)(Flatgroup)

：在這種結(jié)構(gòu)中，所有的進(jìn)程都是等價(jià)的，要通過(guò)彼此協(xié)商才能做出決定。層次結(jié)構(gòu)(Hierarchicalgroup)

：在最簡(jiǎn)單的層次結(jié)構(gòu)的進(jìn)程組中，一個(gè)進(jìn)程是協(xié)調(diào)者，其他所有的進(jìn)程為工作者。無(wú)論是進(jìn)程組外的一個(gè)顧客，還是進(jìn)程組中的一個(gè)工作者向進(jìn)程組發(fā)出一個(gè)工作請(qǐng)求，由協(xié)調(diào)者決定哪一個(gè)工作者最適合這項(xiàng)工作，并且將此工作請(qǐng)求轉(zhuǎn)交給它42進(jìn)程組管理：對(duì)于進(jìn)程組通信來(lái)說(shuō)，需要一定的辦法進(jìn)行進(jìn)程組的管理，如組播通信、組創(chuàng)建及刪除，同時(shí)還要允許進(jìn)程能加入到一個(gè)進(jìn)程組中去以及允許一個(gè)進(jìn)程離開(kāi)一個(gè)進(jìn)程組。實(shí)現(xiàn)方式：

集中式管理：設(shè)置一個(gè)進(jìn)程組服務(wù)員(GroupServer)

，所有的服務(wù)請(qǐng)求都發(fā)送給進(jìn)程組服務(wù)員。進(jìn)程組服務(wù)員使用一個(gè)數(shù)據(jù)庫(kù)來(lái)保存所有進(jìn)程組的信息和一個(gè)進(jìn)程組中所有成員的有關(guān)信息

分布式管理：另一種辦法是采用分布方式管理進(jìn)程組。借助于一種可靠的組播通信協(xié)議，各編組自行管理，同時(shí)成員的進(jìn)入與退出也通過(guò)組播通信進(jìn)行。例如當(dāng)一個(gè)組外的進(jìn)程要加入到這個(gè)進(jìn)程組時(shí)，它向這個(gè)進(jìn)程組中的所有成員發(fā)送一個(gè)報(bào)文，申明自己要加入到這個(gè)進(jìn)程組。存在的問(wèn)題…437.5.2故障屏蔽和進(jìn)程復(fù)制

利用進(jìn)程組屏蔽故障：進(jìn)程組是構(gòu)造容錯(cuò)系統(tǒng)問(wèn)題的一部分。特別是，如果用相同的進(jìn)程來(lái)構(gòu)成一個(gè)進(jìn)程組，那么就能夠屏蔽進(jìn)程組中一個(gè)或多個(gè)出錯(cuò)的進(jìn)程?；蛘哒f(shuō)，我們可以用多個(gè)相同的進(jìn)程構(gòu)造一個(gè)進(jìn)程組，用這個(gè)容錯(cuò)的進(jìn)程組取代相對(duì)脆弱的單個(gè)進(jìn)程。利用進(jìn)程組進(jìn)行容錯(cuò)需要多少個(gè)進(jìn)程副本：

令G為一個(gè)進(jìn)程編組，如果在G的成員中，只要不多于K個(gè)成員同時(shí)發(fā)生故障，G可以一直正常運(yùn)行，則G被稱為K容錯(cuò)故障—停止型故障：如果進(jìn)程組中有k+1個(gè)進(jìn)程，那么就足以提供k故障容錯(cuò)。拜占庭式故障：此時(shí)，每個(gè)編組至少需要2k+1個(gè)進(jìn)程，才能屏蔽K個(gè)成員同時(shí)發(fā)生的故障，即達(dá)到K容錯(cuò)能力。447.5.3容錯(cuò)系統(tǒng)中的一致性算法（分布式協(xié)定算法）分布式協(xié)定算法的目標(biāo)：使得所有無(wú)故障進(jìn)程在有限步驟里對(duì)某個(gè)問(wèn)題達(dá)成一致性結(jié)論。如下：進(jìn)程組中的每個(gè)參加者都將自己的局部決策（布爾值）發(fā)給進(jìn)程組中所有的其他參加者每個(gè)參加者根據(jù)自己的局部決策值和收到的其他參加者的局部決策值做出決策（如少數(shù)服從多數(shù)）故障—停止型故障拜占庭式故障45分布式一致算法的正確性條件：(1)一致性。所有正確的進(jìn)程取得一致的結(jié)果，而且是最后的結(jié)果；(2)合法性。所有進(jìn)程同意的結(jié)果必須來(lái)自某個(gè)正確的進(jìn)程的輸入；(3)有限性。每個(gè)進(jìn)程在有限的步驟內(nèi)取得一致的結(jié)果。交互一致性算法交互一致性：系統(tǒng)中的每個(gè)非出錯(cuò)進(jìn)程都使用來(lái)自進(jìn)程Pi的同樣的值來(lái)進(jìn)行決策。這樣，一般的一致性問(wèn)題就變?yōu)橄到y(tǒng)中的進(jìn)程都同意一個(gè)特殊的進(jìn)程(比如P0)的值。確切地說(shuō)：所有非出錯(cuò)進(jìn)程都使用進(jìn)程P0的同樣的值v0若發(fā)送進(jìn)程P0是非出錯(cuò)的，那么所有非出錯(cuò)進(jìn)程都使用P0發(fā)送的值。結(jié)論：在有k個(gè)出錯(cuò)節(jié)點(diǎn)的情況下，只有進(jìn)程的總數(shù)至少為3k+1時(shí)才能獲得一致。因?yàn)橹挥写嬖?k+1個(gè)正確工作的進(jìn)程才能達(dá)成協(xié)議，即只有當(dāng)三分之二以上的進(jìn)程正常工作時(shí)才能達(dá)成一致，所以總共有3k+1個(gè)進(jìn)程46拜占庭將軍問(wèn)題

假設(shè)有N支拜占庭部隊(duì)包圍了敵軍，每支部隊(duì)都由一位將軍統(tǒng)領(lǐng)，將軍與將軍之間由信使傳遞信息。將軍之中可能有通敵者，這個(gè)(些)通敵者試圖用矛盾的信件來(lái)混淆視線，破壞將軍們之間可能達(dá)成的協(xié)定。

假定發(fā)布命令（廣播通信）的將軍是司令，而其他將軍都是軍長(zhǎng)，要想達(dá)成一致協(xié)定，所有的軍長(zhǎng)都必須“同意”司令發(fā)出的命令。

當(dāng)然，要解決拜占庭將軍問(wèn)題，每一位將軍都要扮演一次司令的角色，向其他將軍廣播消息。更確切地說(shuō)，每一位將軍pi都必須把自己的初始值Vi發(fā)送給其他將軍，并滿足下述兩個(gè)條件（稱為相互一致性）：

(1)如果發(fā)送者ps是忠誠(chéng)的，則所有忠誠(chéng)的將軍都要同意Vs； (2)如果發(fā)送者ps是通敵的，則所有忠誠(chéng)的將軍都對(duì)Vs有一致的看法。

47三位拜占庭將軍問(wèn)題

（1）首先，我們假定司令通敵。于是他向軍長(zhǎng)A發(fā)出“進(jìn)攻”而向軍長(zhǎng)B發(fā)出“撤退”的相互矛盾的命令。當(dāng)兩位軍長(zhǎng)互相驗(yàn)證所得到的命令時(shí)，發(fā)現(xiàn)無(wú)法得到一致的結(jié)論?？瓷先ナ撬玖畛隽藛?wèn)題，但問(wèn)題并非如此簡(jiǎn)單。在(2)中，假定司令發(fā)出正確的命令，而軍長(zhǎng)B通敵。當(dāng)兩位軍長(zhǎng)驗(yàn)證來(lái)自司令的命令時(shí)，軍長(zhǎng)B把“進(jìn)攻”篡改為“撤退”。對(duì)軍長(zhǎng)A來(lái)說(shuō)，(1)和(2)并無(wú)區(qū)別，他在這兩種情況下都收到相互矛盾的消息（一封“進(jìn)攻”，一封“撤退”）。顯然，軍長(zhǎng)A不能服從來(lái)自司令的命令，因?yàn)槿绻玖钔〝车脑挘瑑晌恢艺\(chéng)的將軍就不可能一致行動(dòng)，而是背道而馳；可是，如果司令是忠誠(chéng)的，軍長(zhǎng)A又不能違抗來(lái)自司令的命令，如果違抗，將受到軍法從事。于是，軍長(zhǎng)A陷入兩難境地，無(wú)法做出決定。撤退進(jìn)攻司令進(jìn)攻(1)司令通敵(2)軍長(zhǎng)B通敵軍長(zhǎng)A軍長(zhǎng)B撤退司令進(jìn)攻軍長(zhǎng)A軍長(zhǎng)B進(jìn)攻撤退進(jìn)攻48（1）我們?nèi)匀患僭O(shè)司令通敵，也就是說(shuō)，司令向軍長(zhǎng)們發(fā)出兩種不同的命令。然而，三位忠誠(chéng)的軍長(zhǎng)在隨后的通信中，都得到一組相同的命令，即（進(jìn)攻，進(jìn)攻，撤退），根據(jù)多數(shù)原則，三位軍長(zhǎng)便采取一致的行動(dòng)，同時(shí)發(fā)起進(jìn)攻。而(2)中，軍長(zhǎng)C通敵，盡管他篡改了來(lái)自司令的命令，軍長(zhǎng)A和軍長(zhǎng)B還是能夠通過(guò)多數(shù)原則做出決定，即執(zhí)行來(lái)自司令的正確命令。Lamport等人文章把這個(gè)原則推廣到一般情況：在一可能具有拜占庭故障的系統(tǒng)中，我們需要至少3K+1個(gè)服務(wù)器才能具備K-容錯(cuò)的能力

四位拜占庭將軍問(wèn)題

司令進(jìn)攻軍長(zhǎng)C軍長(zhǎng)A進(jìn)攻撤退進(jìn)攻進(jìn)攻進(jìn)攻撤退進(jìn)攻軍長(zhǎng)B司令軍長(zhǎng)A軍長(zhǎng)B軍長(zhǎng)C進(jìn)攻進(jìn)攻撤退進(jìn)攻進(jìn)攻進(jìn)攻進(jìn)攻1）司令通敵(2)軍長(zhǎng)C通敵撤退撤退進(jìn)攻49TheByzantinegeneralsproblemfor3loyalgeneralsand1traitor.Thegeneralsannouncetheirtroopstrengths(inunitsof1kilosoldiers).Thevectorsthateachgeneralassemblesbasedon(a)Thevectorsthateachgeneralreceivesinstep3.AgreementinFaultySystems50AgreementinFaultySystemsThesameasinpreviousslide,exceptnowwith2loyalgeneralsandonetraitor.51

LAMPORT交互一致性算法IC：IC(m)，m<k，開(kāi)始時(shí)m=0，S={}。發(fā)送者將其值和發(fā)送者列表S發(fā)送給其他進(jìn)程，共(n-1-m)個(gè)；設(shè)vi是進(jìn)程Pi從發(fā)送者接收到的值或者是如果沒(méi)有收到值時(shí)使用的缺省值。在IC(m+1≠k)時(shí)進(jìn)程Pi作為發(fā)送者，將結(jié)果vi和發(fā)送者列表S∪{Pi}發(fā)送給其他不在發(fā)送者列表中的n-2-m個(gè)進(jìn)程。如果m+1=k，則調(diào)用IC(k)；對(duì)每個(gè)進(jìn)程Pi，設(shè)vj是進(jìn)程Pj接收到的值(但是由Pj轉(zhuǎn)發(fā)給Pi)。節(jié)點(diǎn)使用值majority(vj)，jS；其中，IC(k)：a.發(fā)送者將它的值發(fā)送給其他n-k-1個(gè)進(jìn)程；b.每個(gè)進(jìn)程使用從接收者收到的值，或者，如果它沒(méi)有收到任何值，就使用缺省值。結(jié)論：上述算法中，被交換的報(bào)文總數(shù)為(n-1)(n-2)…(n-k-1)，其復(fù)雜度為O(nk)，k可以是(n-1)/3。52實(shí)例：具有7個(gè)進(jìn)程的例子，Pi，0≤i≤6。假定k=2，即最多有2個(gè)故障，n=7。設(shè)P0是初始發(fā)送者，發(fā)送值為1。不妨設(shè)P5和P6是出錯(cuò)進(jìn)程，它向其他進(jìn)程發(fā)送不確定的值。在這個(gè)例子中共需要k+1=3輪信息交換：P0將{V0,S}={1,{P0}}發(fā)送給進(jìn)程P1，P2，…，P6。P1至P6中每個(gè)進(jìn)程都接收到報(bào)文{1,{P0}}，它們將所收到的報(bào)文轉(zhuǎn)發(fā)給除了開(kāi)始的發(fā)送者和它本身之外的所有其他的進(jìn)程。例如P1向P2至P6發(fā)送報(bào)文{1,{P0,P1}}。它分別從P2至P6處接收到報(bào)文{1,{P0,P2}}、{1,{P0,P3}}、{1,{P0,P4}}、{d,{P0,P5}}、{d,{P0,P6}}。53在第三輪中，P1將報(bào)文{1,{P0,P2}}以{1,{P0,P2,P1}}的形式分別發(fā)送給進(jìn)程P3、P4、P5、P6，將報(bào)文{1,{P0,P3}}以{1,{P0,P3,P1}}的形式分別發(fā)送給進(jìn)程P2、P4、P5、P6，將報(bào)文{1,{P0,P4}}以{1,{P0,P4,P1}}的形式分別發(fā)送給進(jìn)程P2、P3、P5、P6，將報(bào)文{d,{P0,P5}}以{d,{P0,P5,P1}}的形式分別發(fā)送給進(jìn)程P2、P3、P4、P6，將報(bào)文{d,{P0,P6}}以{d,{P0,P6,P1}}的形式分別發(fā)送給進(jìn)程P2、P3、P4、P5。第三輪遞歸結(jié)束，返回第二輪。進(jìn)程P1收到報(bào)文{1,{P0,P2,P3}}、{1,{P0,P2,P4}}、{d,{P0,P2,P5}}、{d,{P0,P2,P6}}，連同在第二輪中收到的報(bào)文{1,{P0,P2}}，將這5個(gè)報(bào)文中的值執(zhí)行majority(1,1,d,d,1)=1，得到的這個(gè)新值1作為報(bào)文{1,{P0,P2}}的新值，記為新報(bào)文{1,{P0,P2}}’。同樣的道理，得到新報(bào)文{1,{P0,P3}}’、{1,{P0,P4}}’、{1,{P0,P5}}’、{1,{P0,P6}}’。第二輪遞歸結(jié)束，返回第1輪。P1對(duì)6個(gè)報(bào)文{1,{P0}}、{1,{P0,P2}}’、{1,{P0,P3}}’、{1,{P0,P4}}’、{1,{P0,P5}}’、{1,{P0,P6}}’中的值執(zhí)行majority(1,1,1,1,1,1)=1，這個(gè)新值是P1所確信的最終值。54交互一致性算法的擴(kuò)展

：可以通過(guò)對(duì)每個(gè)發(fā)送者都重復(fù)同樣的協(xié)議將交互一致性擴(kuò)展到多個(gè)發(fā)送者的情況。擴(kuò)展的方法：在第k輪收到的值將被發(fā)送到所有的其他節(jié)點(diǎn)，而不僅僅是那些沒(méi)有被發(fā)送過(guò)的節(jié)點(diǎn)。一致性協(xié)議對(duì)系統(tǒng)的要求：同步系統(tǒng)與異步系統(tǒng)：如果所有的處理器都是在可以預(yù)料的速度下運(yùn)行，那么這個(gè)系統(tǒng)就是同步的。確切地說(shuō)，處理器是同步的當(dāng)且僅當(dāng)存在一個(gè)常量s≥1，每當(dāng)任何一個(gè)處理器運(yùn)行了s+1步，其他的所有處理器都至少運(yùn)行了1步；否則這個(gè)系統(tǒng)就是異步的。

55可以得到一致性對(duì)系統(tǒng)的要求為：AB+AC+CD=True即在下面三種情況下，系統(tǒng)滿足一致性協(xié)議的要求：(1)(AB=1)，處理器是同步的，通信延遲是有限的；(2)(AC=1)，處理器是同步的，報(bào)文是有序的；(3)(CD=1)，報(bào)文是有序的，傳輸機(jī)制是廣播。用卡諾圖描述一致性對(duì)系統(tǒng)的要求：定義布爾變量(1)系統(tǒng)是同步的(A=1)還是異步的(A=0)。(2)通信延遲是有限的(B=1)還是無(wú)限的(B=0)。(3)報(bào)文是有序的(C=1)還是無(wú)序的(C=0)。(4)傳輸機(jī)制是廣播的(D=1)還是點(diǎn)到點(diǎn)的(D=0)。CD00011110AB000010010010111111100011一致性協(xié)議對(duì)系統(tǒng)的要求：567.6可靠的組通信

7.6.1基本的可靠組播方案

所謂可靠的組播通信，就是要求發(fā)送給某個(gè)進(jìn)程組的報(bào)文必須確保傳送到進(jìn)程組中的每一個(gè)成員。577.6.2可靠組播通信中的可擴(kuò)充性

簡(jiǎn)單方案：接收者收到組播報(bào)文后不向發(fā)送者發(fā)送應(yīng)答報(bào)文，只有在接收者發(fā)現(xiàn)丟失一個(gè)報(bào)文后，才向發(fā)送者發(fā)送一個(gè)反饋報(bào)文，指出某個(gè)報(bào)文丟失了。問(wèn)題1：多個(gè)接收者丟失報(bào)文時(shí)，仍然會(huì)出現(xiàn)反饋報(bào)文擁塞的情況；問(wèn)題2：在理論上講，發(fā)送者必須在其歷史緩沖區(qū)中長(zhǎng)時(shí)間保存它發(fā)送的每一個(gè)廣播報(bào)文。無(wú)等級(jí)的反饋控制，F(xiàn)loyd1997成功接收到組播報(bào)文的接收者不向發(fā)送者發(fā)送反饋報(bào)文，只有在接收者