【正文】 _Abort消息。它們各自的狀態(tài)機如圖 。錯誤是系統(tǒng)中可能導致失敗的部分。前向錯誤恢復機制的關鍵在于它必須預先知道會發(fā)生什么錯誤。例如，在一個 (n, k)塊的擦除碼中，一組 k個源分組被編碼為一組 n個已編碼的分組，這樣任意 k個已編碼的分組都可以重建出原來的 k個源分組。首先，把一個系統(tǒng)或進程恢復到原先的狀態(tài)通常是一個相對開銷較大的操作。但是，設臵檢查點通常是一個開銷很大的操作，可能引起嚴重的性能問題。在只使用檢查點的系統(tǒng)中，進程將被恢復到設臵檢查點時的狀態(tài)，它們的行為將與發(fā)生故障之前不同。畢竟消息必須是來自某個地方的。下面要說明一種尋找恢復線的方法。在這種情況下， P1將記錄消息 m’ 的接收，但是沒有這一消息被發(fā)送的記錄事件，因此，有必要把 P1回退到以前的狀態(tài)。 88 獨立檢查點 ? 當進程 Pi按 Int[i](m)的間隔發(fā)送消息時，它就在接收進程中加入 (i, m)對。我們不討論更多的細節(jié)，可以證明：這樣的計算是相當復雜的，與協(xié)調檢查點相比，獨立檢查點對這些計算的需求也是不盡合理的。當協(xié)調者接收到所有進程的確認時，它就多播一個 Checkpoint_Done消息讓 (阻塞的 )進程繼續(xù)執(zhí)行。當進程 P接收到這樣的請求時，它就把請求轉發(fā)給那些在上次檢查點之后 P本身向之發(fā)送了消息的所有進程，等等。在這種模式中，假定每個進程的執(zhí)行者都有一連串的間隔，事件是在這些間隔中發(fā)生的。 95 消息日志 ? 考慮到要從進程崩潰中恢復到一個全局一致的狀態(tài)時消息日志是必需的，準確地知道什么時候對消息進行記錄是很重要的。認為每個消息 m都具有頭部，頭部中包含了重發(fā) m并正確處理它所需的所有信息。注意 m’是按因果關系依賴于 m的傳送的，如果它由先前傳送 m的同一個進程發(fā)送，或者它傳送了另一個按因果關系依賴于 m的傳送的消息。即，如果一個依賴于 m，但是沒有辦法來重放 m的傳輸時它就是一個孤兒進程。換句話說，悲觀日志協(xié)議確保每個非穩(wěn)定的消息 m都最多被傳送給一個進程。在樂觀的方法中， DEP(m)中的任何孤兒進程都被回退到一個不再屬于 DEP(m)的狀態(tài)。 101 消息日志 ? 相反，在樂觀日志協(xié)議中，在發(fā)生崩潰之后才進行實際的工作。第一種方法稱為悲觀日志協(xié)議。假定一些進程在分布式系統(tǒng)中崩潰了， Q是幸存的進程之一。特別是， DEP(m)由那些接收 m的進程組成。如果進程 Q崩潰然后恢復，那么要恢復 Q只需要重放記錄了的消息，在我們的例子中就是 m1，因為m2沒有進行記錄，它的傳輸也就不會被重放，這意味著 m2的傳輸不會發(fā)生。 ? 實際上，如果以相同的非確定性事件作為開始進行重放，那么一個間隔的重放可以具有已知的結果，也就是說，以一種完全確定的方式進行重放。它使用一個檢查點狀態(tài)作為開始點，然后簡單地把從該點以后發(fā)送的所有消息都重發(fā)并執(zhí)行處理。這稱為增量快照。首先協(xié)調者向所有進程多播一個 Checkpoint_Request消息。如果 CP[j](m1)導致了不一致的全局狀態(tài)，那么還需要進行更多的回退。 ? 實現(xiàn)獨立的檢查點需要記錄依賴關系，應按照進程可以共同回退到一個一致的全局狀態(tài)的方法來進行記錄。因此，P2需要回退到更早的狀態(tài)。要找到恢復線需要每個進程都回退到它最近保存的狀態(tài)。著重強調了記錄一致全局狀態(tài)的必要性，稱為分布式快照。把檢查點與消息日志相結合使得有可能恢復到最近檢查點的狀態(tài)而無需付出設臵檢查點的代價。例如，如果一個人從柜員機取走了 1000美元時，那么即使自動柜員機立即回退這些錢也很難追回。換句話說，它可以作為一項通用的服務集成到分布式系統(tǒng)的中間層中。 ? 還有一種可供選擇的方式是使用一種稱為擦除修正 (erasure correction)的方法。 ? 另一種是前向恢復 (forward recovery)。因此存活進程總是可以做出的最后決定。盡管 3PC在文章中廣泛出現(xiàn)，但是它在實際中用得并不多，因為在 2PC中阻塞的情況很少發(fā)生。如果所有的參與者都表決要提交事務，那么協(xié)調者就進行提交。在可靠多播的情況下，操作就是消息的傳遞。在簡單的方案中，協(xié)調者通知所有涉及到的稱為參與者的其他進程是否 (本地 )按要求執(zhí)行操作。但是，虛擬同步保證這個消息根本不會被傳送，這就有效地建立起一種情況，使得在 P3崩潰之前消息從來沒有被發(fā)送。作為選擇， m可以被每個成員忽略，這對應于在發(fā)送 m之前發(fā)送者崩潰的情況。 60 虛擬同步 The logical anization of a distributed system to distinguish between message receipt and message delivery 61 虛擬同步 ?現(xiàn)在假定 m在發(fā)送者具有組視圖 G時進行多播。下面來區(qū)分一下接收消息和發(fā)送消息。特別是，在使用原子多播的情況下，只有在所有正確操作的副本就組成員關系達成一致時，操作才能執(zhí)行。換句話說，我們假定使用的是活動的復制協(xié)議。特別是，在分布式中經常需要保證消息要么發(fā)送給所有的進程，要么就不向任何進程一個也不發(fā)送。另外，我們也需要考慮接收者可能發(fā)布在關于網(wǎng)上的情況。發(fā)送進程為它發(fā)送的每個多播分配一個序列號。我們在下面討論原子多播，然后再回到這個問題上來。最好的也只是讓每個進程建立在想要與之通信的每個其他進程的點到點連接。 ?但是通常不能掩蓋連接的崩潰性故障。但是我們也需要考慮通信故障。具有 2m+1個忠誠者，就可以達到這一點，因為只有當三分之二以上的選票相同才能達成協(xié)議。 40 故障系統(tǒng)的協(xié)議 The Byzantine generals problem for 3 loyal generals and1 traitor. a) The generals announce their troop strengths (in units of 1 kilosoldiers). b) The vectors that each general assembles based on (a) c) The vectors that each general receives in step 3. 41 故障系統(tǒng)的協(xié)議 ?現(xiàn)在讓 n=3, m=1，來重新看一下這個問題，也就是說只有兩個忠誠的將軍和一個叛徒，像圖 那樣。每個將軍都得到來自其他三個將軍的三個向量。如果將軍 i是忠誠的，那么他的兵力中的元素就為 i，否則就是未定義的。 37 故障系統(tǒng)的協(xié)議 ?現(xiàn)在我們假定通信良好，但是進程卻并不好。假定有某個可以在有限步驟內結束的協(xié)議，這是一種結尾去掉任何額外的步驟而得到的可以工作的最小協(xié)議。 34 故障系統(tǒng)的協(xié)議 ?假定藍軍 1的司令 A發(fā)送一個消息給藍軍 2的司令官 B：“ 我有一個計劃 —— 我們在明天凌晨發(fā)起攻擊 ” 。 33 故障系統(tǒng)的協(xié)議 ?在考慮故障進程的情況之前，我們先看簡單的情況：進程運行很好但是通信線路丟失消息。正如我們提到的那樣，如果客戶可以根據(jù)它的表決機制做出決定，我們甚至可以容忍 2k+1個進程中的 k個進程得出錯誤的結果。如果 k個組件停止工作，還可以用剩下的一個組件來得到響應。實際上，如果主進程崩潰，后備進程執(zhí)行一些選舉算法來選擇一個新的主進程。這時需要通過一些協(xié)議來重建組。問題在于當一個進程崩潰時不能像一個進程自動離開那樣進行通知。這種方法直接、有效、容易實現(xiàn)。如果一個進程崩潰，組只是簡單地變得更小，但是還可以繼續(xù)。沒有指揮，所有的決定都是共同做出的?？梢詣?chuàng)建新的組也可以刪除舊的組。 18 使用冗余來掩蓋故障 三倍的模塊冗余 19 ?容錯性簡介 ?進程恢復 ?可靠的客戶 服務器通信 ?可靠的組通信 ?分布式提交 ?恢復 20 進程恢復 ?已經討論了容錯的基本問題，現(xiàn)在我們集中討論在分布式系統(tǒng)中如何獲得容錯性的問題。 17 使用冗余來掩蓋故障 ?在時間冗余中，執(zhí)行一個動作，如果需要就再次執(zhí)行。更壞的情況是發(fā)生故障的服務器惡意地與其他服務器共同工作來產生惡意的錯誤結果。在值故障的情況下，服務器為請求提供錯誤的響應，例如搜索引擎系統(tǒng)返回了與使用的搜索項無關的 Web頁面，就是這種情況。例如，當發(fā)送緩沖區(qū)溢出而服務器又沒有為這樣的情況做好準備時就發(fā)生此類故障。在這個意義上說，把復位按鈕從機箱背后轉移到前面是很有道理的。如果這樣的服務器要依賴其他服務器才能充分提供它的服務，那么錯誤的原因就可能需要到別的地方去尋找。連接器接觸不良通常會造成間歇故障。在這種情況下要解決故障是相對容易的，但是無線網(wǎng)絡中的傳輸錯誤可能是由惡劣的天氣條件引起的。 7 容錯性簡介 ?當一個系統(tǒng)不能兌現(xiàn)它的承諾時就被認為是失敗的。這很微妙，但是與可用性相比，這是一個重要的不同。 4 容錯性簡介 ?要理解容錯在分布式系統(tǒng)中的作用，首先需要深入了解分布式系統(tǒng)中的容錯到底意味著什么。當分布式系統(tǒng)中的一個組件發(fā)生故障時就可能產生部分失效。通常，它指在任何給定的時刻，系統(tǒng)都可以正確地操作，可根據(jù)用戶的行為來執(zhí)行它的功能。這樣的控制系統(tǒng)即使只是非常短時間瞬時故障，結果也將是災難性的。例如，當從網(wǎng)絡上傳輸數(shù)據(jù)包時，可能有一些數(shù)據(jù)包在到達接收者時已經被破壞了。防止、解決和預報故障三者之間是有差別的 (Lapire 1995)。 ?持久故障是那些直到故障組件被修復之前持續(xù)存在的故障。如果這樣的文件服務器是分布式數(shù)據(jù)庫的一部分，那么整個數(shù)據(jù)庫的正常工作都將被打亂，因為只有一部分數(shù)據(jù)真正可以訪問。導致這種問題可能有多種原因。 ?另外一種遺漏性故障與通信無關，可能由諸如無限循環(huán)或不正確的內存管理的軟件錯誤引起，這時服務器的狀態(tài)被稱為 “ 掛起 ” 。例如，如果服務器接收到一個它不能識別的信息，也沒有采取措施來處理這樣的信息，那么就會發(fā)生狀態(tài)轉換故障。關鍵技術是使用冗余來掩蓋故障。當錯誤是臨時性或間歇性時，時間冗余特別有用。我們也將討論當一個或多個程度不能給出正確的回答時，如何在進程組中達到一致。因此需要一些機制來管理組和組的成員。在這種模式中，當外部客戶或一個工作者產生一個工作請求時，請求被發(fā)送給協(xié)調者。 ?平等組則相反?？赡艽蠖鄶?shù)或所有組都不得不從頭開始重建，所有組都不得不從頭開始重建，所有正在進行的工作都可能終止。 27 組成員 ?另外一個棘手的問題是進程的離開與加入必須跟數(shù)據(jù)消息的發(fā)送同步。即，我們可以復制進程并把它們組織在一個組中來用一個容錯的組取代一個脆弱的進程。這樣做的主要優(yōu)點在于這樣的組沒