【正文】 特別是，假定對某個消息 m， COPY(m)中的每個進(jìn)程都崩潰了。這個協(xié)議認(rèn)為對于每個非穩(wěn)定的消息 m，都最多有一個進(jìn)程依賴它。如果 Q包含在 DEP(m)中，在 COPY(m)中的每個進(jìn)程都崩潰了的同時存在消息 m，那么 Q就是一個孤兒進(jìn)程。另外，如果另一個消息 m’由于因果關(guān)系也要依賴 m的傳送，而且 m’被傳送給進(jìn)程 Q，那么 Q也包含在 DEP(m)中。 96 消息日志 圖 在恢復(fù)之后不正確的重放導(dǎo)致孤兒進(jìn)程 97 消息日志 ? 為了描述不同的消息日志方案的特征，我們使用文獻(xiàn) (Alvisi, Marzullo 1998)中說明的方法。因此，如果我們在這樣的模式中記錄下所有的非確定性事件，就有可能以一種確定的方式完全重放整個進(jìn)程的執(zhí)行。 94 消息日志 ? 假定采用分段確定模式 (piecewise deterministic model)，這種方法可以很好地工作。 ? 要設(shè)臵一個增量快照，協(xié)調(diào)者只對那些在上次設(shè)臵檢查點(diǎn)之后對之發(fā)送了消息的進(jìn)程多播檢查點(diǎn)請求。當(dāng)進(jìn)程接收到這樣的消息時就設(shè)臵一個本地檢查點(diǎn)，通過它正在執(zhí)行的應(yīng)用程序?qū)㈦S后傳遞給它的消息進(jìn)行排隊(duì)，然后向協(xié)調(diào)者確認(rèn)它已經(jīng)設(shè)臵了檢查點(diǎn)。 89 獨(dú)立檢查點(diǎn) ? 計算恢復(fù)線需要對每個進(jìn)程設(shè)臵檢查點(diǎn)時記錄的時間間隔依賴關(guān)系進(jìn)行分析。用 CP[i](m)來表示進(jìn)程 Pi采用的第 m個檢查點(diǎn)，用 Int[i](m)來表示檢查點(diǎn) CP[i](m1)與 CP[i](m)之間的間隔。 ? 但是， P2要回退到的下一個狀態(tài)不能用作分布式快照的一部分。如果這些本地狀態(tài)不能組成一個分布式快照，那么就需要進(jìn)一步的回退。在分布式快照中，如果進(jìn)程 P記錄了一條消息的接收，那么就應(yīng)該有一個進(jìn)程 Q記錄了該消息的發(fā)送。 81 恢復(fù) ? 在僅使用檢查點(diǎn)方法與另外還使用日志的方法之間還有另一個重要的不同。 80 恢復(fù) ? 通過檢查點(diǎn)可使系統(tǒng)恢復(fù)到先前的正確狀態(tài)。 ? 但是，回退錯誤恢復(fù)也有一些問題。這種方法是從其他成功傳送的分組中建立丟失的分組。在這種情況下，當(dāng)系統(tǒng)進(jìn)入錯誤狀態(tài)時，不是回退到以前的檢查點(diǎn)處的狀態(tài)，而是嘗試從可以繼續(xù)執(zhí)行某點(diǎn)開始把系統(tǒng)帶入一個正確的新狀態(tài)。 75 ?容錯性簡介 ?進(jìn)程恢復(fù) ?可靠的客戶 服務(wù)器通信 ?可靠的組通信 ?分布式提交 ?恢復(fù) 76 恢復(fù) ? 容錯的基本要求是從錯誤中恢復(fù)。 72 三階段提交 ? 像 2PC一樣， 3PC也可以用一個協(xié)調(diào)者和一些參與者來進(jìn)行說明。在這種情況下它向所有的參與者發(fā)送一個 Global_Commit消息。在分布式事務(wù)中，操作可能是單個站點(diǎn)上事務(wù)的提交，它是整個事務(wù)的一部分。這種方法稱為單階段提交協(xié)議。 ?在從組中刪除 P3之后，通信在剩余的組成員之間進(jìn)行。 ?這種更強(qiáng)的可靠多播保證多播到組視圖 G的消息被傳送給 G中的每個正常進(jìn)程。此外，假定在發(fā)生多播時另一個進(jìn)程加入或離開了組。特別指出的是，采用圖 ，其中的分布式系統(tǒng)由通信層組成。換句話說，如果其余的副本達(dá)成一致，認(rèn)為崩潰的副本不再屬于該組，那么更新就可以執(zhí)行。 57 原子多播 ?假定現(xiàn)在要執(zhí)行一系列的更新，但是在一個更新執(zhí)行期間，一個副本崩潰了，于是該副本上的更新就丟失了。另外，如果傳送的化，通常還需要所有的消息都按相同的順序發(fā)送給所有的進(jìn)程。 ?解決這個問題的方法是：接收者不對消息接收者進(jìn)行反饋，而是只在通知發(fā)送者消息丟失時才返回一個反饋消息。假定消息按它們被發(fā)送的次序進(jìn)行接收。 ?如果假定存在一個協(xié)議說明誰是組的成員，那么問題就會簡單一些。顯然，這樣的組織不是有效的，因?yàn)樗速M(fèi)了網(wǎng)絡(luò)帶寬。崩潰性故障發(fā)生在不論什么原因 TCP連接突然中斷時，這時就不能再通過該通道傳輸更多的消息了。前面討論的大多數(shù)故障模型都很好地應(yīng)用導(dǎo)通信通道上。換句話說，如果三分之二以上的將軍做出同樣的決定，那么這個決定就符合在忠誠將軍組的表決中占多數(shù)的原則。我們在圖 到占多數(shù)的元素 元素 2和元素 3，所以它們都被標(biāo)記為 unknown。將軍 3在這里還是說了謊，編造了 12個新的值。 38 故障系統(tǒng)的協(xié)議 ? Lamport等 (1992)建議使用一種遞歸算法，這種算法可以在一定條件下解決這個問題。這里也有一個經(jīng)典的軍事問題稱為拜占庭將軍問題(Byzantine generals problem)。現(xiàn)在某個消息是最后的消息，它對達(dá)成協(xié)議是關(guān)鍵性的 (因?yàn)檫@是最小的協(xié)議 )。試著到達(dá)藍(lán)軍 2， B讓它帶回一個消息： “ 好主意，明天凌晨見 ” 。有一個稱為兩軍問題 (twoarmy problem)的著名問題，它說明了在兩個運(yùn)行良好的進(jìn)程之間即使只就 1位信息達(dá)成協(xié)議也是非常困難的。但是，我們做出的假定是這些進(jìn)程沒有組合成團(tuán)隊(duì)來共同產(chǎn)生錯誤的結(jié)果。 31 故障掩蓋和復(fù)制 ?另一方面，如果進(jìn)程發(fā)生拜占庭失敗，繼續(xù)錯誤運(yùn)行并發(fā)送出錯誤或隨機(jī)的應(yīng)答，那么最少需要 2k+1個進(jìn)程才能獲得 k容錯。 30 故障掩蓋和復(fù)制 ?與基于團(tuán)體的協(xié)議相同，復(fù)制寫協(xié)議以主動復(fù)制的形式使用。一些進(jìn)程不得不進(jìn)行初始化來重新啟動，但是如果有兩個或三個進(jìn)程同時進(jìn)行嘗試會發(fā)生什么？協(xié)議必須能夠處理這些問題。其他成員不得不通過注意到崩潰的成員不再進(jìn)行響應(yīng)來發(fā)現(xiàn)這一點(diǎn)。不幸的是它具有所有集中式技術(shù)的缺點(diǎn)：單一的失敗點(diǎn)。它的缺點(diǎn)在于做出決定比較復(fù)雜。在其他的組中存在一些等級關(guān)系。在系統(tǒng)操作過程中，一個進(jìn)程可以加入一個組也可以離開一個組。首先要討論的主題是防止進(jìn)程失敗，這是通過把進(jìn)程復(fù)制到組中來獲得的。使用事務(wù)是這種方法的例子。這種情況說明了為什么談到可靠系統(tǒng)時安全被認(rèn)為是一個重要的需求。 ?另外一種故障稱為狀態(tài)轉(zhuǎn)換故障。注意，與接收遺漏性故障，服務(wù)器現(xiàn)在的狀態(tài)可能說明它已經(jīng)完成了對客戶的服務(wù)。可能有一天還會把它移到背后，甚至完全去掉。 ?這樣的依賴關(guān)系大量出項(xiàng)在分布式系統(tǒng)中。間歇故障會造成情況的惡化，因?yàn)樗鼈兒茈y診斷。要改變天氣來減少或防止錯誤是不可能的。尤其是，如果一個分布式系統(tǒng)被設(shè)計為它為為它的用戶提供大量的服務(wù)，當(dāng)這些服務(wù)中的一個或多個不能被 (完整地 )提供時，系統(tǒng)就發(fā)生故障了。 6 容錯性簡介 ?安全性 是指明在系統(tǒng)偶然出故障的情況下正確操作而不會造成任何災(zāi)難。容錯與被稱為可靠的系統(tǒng) (dependable system)緊密相關(guān)。1 Fault Tolerance Chapter 7 2 ?容錯性簡介 ?進(jìn)程恢復(fù) ?可靠的客戶 服務(wù)器通信 ?可靠的組通信 ?分布式提交 ?恢復(fù) 3 容錯性簡介 ?分布式系統(tǒng)區(qū)別于單機(jī)系統(tǒng)的一個特性是它可能部分失效。可靠性是一個術(shù)語，它包含了分布式系統(tǒng)中很多有用的需求，列舉以下： ?可用性 ?可靠性 ?安全性 ?可維護(hù)性 5 容錯性簡介 ?可用性被定義為系統(tǒng)的一個屬性，它說明系統(tǒng)已準(zhǔn)備好，馬上就可以使用。例如，很多進(jìn)程控制系統(tǒng)，比如那些用來控制核電站或把人送入太空的控制系統(tǒng)，就必須提供高度的安全性。而錯誤是系統(tǒng)狀態(tài)的一部分，它可能會導(dǎo)致故障發(fā)生。 ?建立一個可靠的系統(tǒng)與控制故障緊密相關(guān)。通常當(dāng)解決故障的人到來時系統(tǒng)工作良好。如果一個文件服務(wù)器的設(shè)計目的是提供高度可用的文件系統(tǒng)，那么失效的磁盤會使該服務(wù)器運(yùn)行困難。 ?當(dāng)服務(wù)器不能對請求進(jìn)行響應(yīng)時就發(fā)生遺漏性故障。因此，如果響應(yīng)發(fā)送失敗，那么服務(wù)器可能需要為客戶重新發(fā)送先前的請求而做好準(zhǔn)備。當(dāng)服務(wù)器對到來的請求做出意想不到的響應(yīng)時就發(fā)生這種故障。 16 使用冗余來掩蓋故障 ?如果系統(tǒng)是容錯的，那么它能做的最好的事情就是對其他進(jìn)程隱藏故障的發(fā)生。如果一個事務(wù)中止，那么它就可以無害地重新執(zhí)行。在下面的內(nèi)容中，我們考慮進(jìn)程組中的一般設(shè)計問題，并討論容錯組到底是什么。一個進(jìn)程可以同時是多個組的成員。例如，一個進(jìn)程是協(xié)調(diào)者而其他進(jìn)程都是工作者。例如，要決定某事常常需要進(jìn)行表決，這導(dǎo)致了一些延遲和開銷。所有組服務(wù)器崩潰、組管理就不再存在。一旦確定崩潰的成員是真正的崩潰 (而不是速度慢 )，就從組中刪除它。 29 故障掩蓋和復(fù)制 ?進(jìn)程組是建立容錯系統(tǒng)方法的一部分，特別是在有一組相同的進(jìn)程允許我們掩蓋組中的一個或多個發(fā)生故障的進(jìn)程的情況下。這些解決方法把相同進(jìn)程的集合組織到一個平等組中。在最壞的情況下， k個失敗的進(jìn)程可以意外地產(chǎn)生同樣的回答，這樣，客戶或表決電路還可以相信多數(shù)進(jìn)程的回答。 ?通常，如果要求進(jìn)程組達(dá)成一致，事情會變得更復(fù)雜。紅軍具有 5000個士兵，在一個山谷中扎營。使者安全回到它的基地傳達(dá)了這個消息，A通知它的士兵準(zhǔn)備在凌晨進(jìn)行戰(zhàn)斗。如果這個消息沒有到達(dá)，行動就被取消。在這個問題中，紅軍還是在山谷中扎營，但是在附近的山上有 n個帶領(lǐng)部隊(duì)的藍(lán)軍將領(lǐng)。在圖 n=4而 m=1的情況下這種算法的工作情況。第 3步的結(jié)果在圖 。算法無法達(dá)成一致。 44 故障系統(tǒng)的協(xié)議 ?不幸的是，達(dá)成協(xié)議的情況甚至?xí)鼔摹Ｌ貏e是，通信通道也可能出現(xiàn)崩潰性故障、遺漏性故障、定時故障和隨意性故障。在大多數(shù)情況下，可通過拋出一個異常信號來通知客戶通道已經(jīng)崩潰。不過，如果進(jìn)程數(shù)目較少，通過多個可靠的點(diǎn)到點(diǎn)通道來獲得可靠性是一種簡單而直接的方法。特別是，如果我們假定進(jìn)程不會失敗，而且在通信進(jìn)行期間不會有進(jìn)程加入或離開組，那么可靠多播就簡單地意味著每個消息都應(yīng)該被傳遞到組的每個當(dāng)前成員處。在這種方式中，接收者很容易探測到消息接收者，那么發(fā)送者就簡單地在每個接收者都返回一個確認(rèn)之前在歷史緩存器中保留消息。只返回否定確認(rèn)通?？梢詼p少反饋的規(guī)模(例如， Towsley等 1997)，但是并不能保證不會發(fā)生反饋擁塞。這種方式稱為原子多播。但是另一方面，在其他的副本上的更新被正確執(zhí)行了。 ?當(dāng)崩潰的副本恢復(fù)時，它就被強(qiáng)迫再次加入該組。消息在這個通信層中進(jìn)行發(fā)送和接收。組成員關(guān)系的這個改變被宣告給 G中的所有進(jìn)程。如果消息的發(fā)送者在多播期間崩潰，那么消息或者被投遞給所有剩余的進(jìn)程或者被每個進(jìn)程忽略。后來 P3恢復(fù)了，它可以在它的狀態(tài)進(jìn)行更新之后再次加入該組。如果有一個參與者不能真正執(zhí)行該操作，那么就說明它存在著明顯的缺陷，因?yàn)樗鼪]有辦法來通知協(xié)調(diào)者。 69 兩階段提交 ? 兩階段提交協(xié)議 (2PC)是由 Gray(1978)提出的。但是，如果有一個參與者表決要取消事務(wù)，那么協(xié)調(diào)者就決定取消事務(wù)并多播一個 Global