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