【正文】 不能檢測(cè)出錯(cuò)誤。換句話說，通過冗余的進(jìn)程可以獲得高度容錯(cuò)性。在一些組中，所有的進(jìn)程都是平等的。這個(gè)組服務(wù)器保持著所有組及其成員的完整的數(shù)據(jù)庫。 28 組成員 ?與組成員相關(guān)的最后一個(gè)問題是如果很多機(jī)器停機(jī)使得組完全不能工作時(shí)該怎么辦。如果這些組件 (進(jìn)程 )是失敗沉默的，那么具有 k+1個(gè)組件就足夠提供 k個(gè)容錯(cuò)。根據(jù)系統(tǒng)參數(shù)的不同可能有不同的情況，包括通信是否可靠或進(jìn)程崩潰性失敗的語義。 ?很容易看出，即使使者每次都能成功通過山谷，不論它們發(fā)送了多少確認(rèn)， A和 B也永遠(yuǎn)不會(huì)達(dá)成協(xié)議。假定每個(gè)將軍都知道他有多少士兵，將軍的目的是交換兵力，這樣在算法結(jié)束時(shí)每個(gè)將軍都得到一個(gè)對(duì)應(yīng)于所有軍隊(duì)的兵力情況的長(zhǎng)度為 n的向量。叛徒不能破壞忠誠(chéng)的將軍的信息，因此他也不能破壞這個(gè)工作。 45 ?容錯(cuò)性簡(jiǎn)介 ?進(jìn)程恢復(fù) ?可靠的客戶 服務(wù)器通信 ?可靠的組通信 ?分布式提交 ?恢復(fù) 46 可靠的客戶 服務(wù)器通信 ?在很多情況下，分布式系統(tǒng)中的容錯(cuò)關(guān)注的是故障進(jìn)程。 49 ?容錯(cuò)性簡(jiǎn)介 ?進(jìn)程恢復(fù) ?可靠的客戶 服務(wù)器通信 ?可靠的組通信 ?分布式提交 ?恢復(fù) 50 可靠的組通信 ?盡管大多數(shù)的傳輸層都提供了可靠的點(diǎn)到點(diǎn)通道，它們很少能提供一組進(jìn)程的可靠通信。 ?一種簡(jiǎn)單的方法如圖 。 56 原子多播 ?現(xiàn)在我們返回需要在存在進(jìn)程失敗的情況下獲得可靠多播的情況。在這種情況下，在一個(gè)副本崩潰之前發(fā)送給所有副本的更新操作或者是在所有的正常副本上都執(zhí)行，或者是一個(gè)都不執(zhí)行。即，它們都同意 m應(yīng)該被傳送給它們中的每一個(gè)而且不被傳送到別的進(jìn)程。但是在崩潰之前塔成功地將消息多播到了進(jìn)程 P2和P4，但是沒有多播到 P1。分布式提交的問題涉及到要使一個(gè)操作被進(jìn)程組中的每個(gè)成員都執(zhí)行或一個(gè)成員都不執(zhí)行。 Skeen(1981)開發(fā)了一種 2PC的變種，稱為三階段提交協(xié)議 (3PC)，它避免了在出現(xiàn)故障停機(jī)時(shí)的阻塞過程。每次記錄系統(tǒng)的當(dāng)前狀態(tài)時(shí)，就稱為設(shè)臵一個(gè)檢查點(diǎn)。回退錯(cuò)誤恢復(fù)的一個(gè)重要優(yōu)點(diǎn)在于它是一種通用的方法，不依賴于任何特定的系統(tǒng)或進(jìn)程。當(dāng)接收進(jìn)程崩潰時(shí)，需要恢復(fù)到最近的檢查點(diǎn)的狀態(tài)，并從這個(gè)狀態(tài)重放被發(fā)送的消息。 83 檢查點(diǎn) 圖 恢復(fù)線 84 獨(dú)立檢查點(diǎn) ? 不幸的是，每個(gè)進(jìn)程的檢查點(diǎn)是以一種不協(xié)調(diào)的方式來按時(shí)記錄它的本地狀態(tài)的，這種分布式本性使得找到一個(gè)恢復(fù)線很困難。但是它主要的缺點(diǎn)還是恢復(fù)線的計(jì)算。 ? 一種比較簡(jiǎn)單的方法是使用兩階段的阻塞協(xié)議。 ? 消息日志的基本思想是：如果消息的傳播可以重放，那么我們就能夠到達(dá)一個(gè)全局一致的狀態(tài)而不需要從穩(wěn)定存儲(chǔ)中恢復(fù)該狀態(tài)。但是，與其他消息不同，消息 m2沒有進(jìn)行日志記錄。 99 消息日志 ? 使用這些表示，現(xiàn)在很容易就可以準(zhǔn)確定義孤兒進(jìn)程是什么了。這種方法可以避免孤兒進(jìn)程。注意只要 m被傳送給進(jìn)程 P， P就稱為COPY(m)的成員。 ? COPY(m)進(jìn)程集由那些具有 m的拷貝，但是該拷貝不在它的本地穩(wěn)定存儲(chǔ)中的進(jìn)程組成。 Alvisi和 Marzullo(1998)介紹的方法說明，如果我們關(guān)注現(xiàn)存的消息日志方案如何處理孤兒進(jìn)程，那么可以容易地描述消息日志方案的特征。一個(gè)進(jìn)程只轉(zhuǎn)發(fā)一次請(qǐng)求。另外，它不是支配性能因素的進(jìn)程之間的協(xié)調(diào)。在這個(gè)例子中，恢復(fù)線就是系統(tǒng)的最初狀態(tài)。 ? 在回退錯(cuò)誤恢復(fù)方法中，每個(gè)進(jìn)程都按時(shí)把它的狀態(tài)保存在本地可用的穩(wěn)定存儲(chǔ)中。因此，很多容錯(cuò)的分布式系統(tǒng)把檢查點(diǎn)與消息日志相結(jié)合。典型的值為 k=16或k=32，而且 kn2k，參閱 (Rizzo 1997)。錯(cuò)誤恢復(fù)的總體想法是用正確的狀態(tài)取代錯(cuò)誤的狀態(tài)。 4. 每個(gè)提交表決的參與者都等待協(xié)調(diào)者的最后反應(yīng)。例如，在分布式事務(wù)的情況下，不可能進(jìn)行本地提交，因?yàn)檫@會(huì)破壞并發(fā)控制約束。具有這種屬性的可靠多播被稱為虛擬同步。接收到的消息在發(fā)送到高層的應(yīng)用程序之前放在通信層的本地緩存器中。 ?當(dāng)崩潰的副本恢復(fù)時(shí)，它可以恢復(fù)到它崩潰之前的狀態(tài)，但是它可能會(huì)錯(cuò)過一些更新。 55 基于組的可靠多播方法 ?只返回否定確認(rèn)理論上還存在另外一個(gè)問題，發(fā)送者不得不永遠(yuǎn)在歷史緩存器中保留消息。在最簡(jiǎn)單的情況下，不要求所有的組成員都按同樣的順序接收消息，但是有時(shí)需要這個(gè)特性。要掩蓋這樣的故障，唯一的方法就是讓分布式系統(tǒng)嘗試自動(dòng)建立一個(gè)新的連接。 Fischer等(1985)證明了在不能保證消息在已知的有限時(shí)間內(nèi)交付的分布式系統(tǒng)中，即使只有一個(gè)進(jìn)程故障 (雖然該進(jìn)程發(fā)生的是沉默性故障 )也不可能達(dá)成協(xié)議。最后在第 4步中，每個(gè)將軍都檢查新收到的向量中的第 i個(gè)元素。通信是通過電話雙向進(jìn)行的，及時(shí)而且質(zhì)量很好。 ?但是后來 A意識(shí)到 B并不知道使者是否安全返回，而不知道這一點(diǎn)可能不敢發(fā)動(dòng)攻擊。在很多情況下要求達(dá)到一致。這樣做的主要優(yōu)點(diǎn)在于這樣的組沒有單一的失敗點(diǎn)，代價(jià)是分布式的協(xié)調(diào)。 27 組成員 ?另外一個(gè)棘手的問題是進(jìn)程的離開與加入必須跟數(shù)據(jù)消息的發(fā)送同步。 ?平等組則相反。因此需要一些機(jī)制來管理組和組的成員。當(dāng)錯(cuò)誤是臨時(shí)性或間歇性時(shí)，時(shí)間冗余特別有用。例如，如果服務(wù)器接收到一個(gè)它不能識(shí)別的信息，也沒有采取措施來處理這樣的信息，那么就會(huì)發(fā)生狀態(tài)轉(zhuǎn)換故障。導(dǎo)致這種問題可能有多種原因。 ?持久故障是那些直到故障組件被修復(fù)之前持續(xù)存在的故障。例如，當(dāng)從網(wǎng)絡(luò)上傳輸數(shù)據(jù)包時(shí)，可能有一些數(shù)據(jù)包在到達(dá)接收者時(shí)已經(jīng)被破壞了。通常，它指在任何給定的時(shí)刻，系統(tǒng)都可以正確地操作，可根據(jù)用戶的行為來執(zhí)行它的功能。 4 容錯(cuò)性簡(jiǎn)介 ?要理解容錯(cuò)在分布式系統(tǒng)中的作用，首先需要深入了解分布式系統(tǒng)中的容錯(cuò)到底意味著什么。 7 容錯(cuò)性簡(jiǎn)介 ?當(dāng)一個(gè)系統(tǒng)不能兌現(xiàn)它的承諾時(shí)就被認(rèn)為是失敗的。連接器接觸不良通常會(huì)造成間歇故障。在這個(gè)意義上說，把復(fù)位按鈕從機(jī)箱背后轉(zhuǎn)移到前面是很有道理的。在值故障的情況下，服務(wù)器為請(qǐng)求提供錯(cuò)誤的響應(yīng)，例如搜索引擎系統(tǒng)返回了與使用的搜索項(xiàng)無關(guān)的 Web頁面，就是這種情況。 17 使用冗余來掩蓋故障 ?在時(shí)間冗余中，執(zhí)行一個(gè)動(dòng)作，如果需要就再次執(zhí)行?？梢詣?chuàng)建新的組也可以刪除舊的組。如果一個(gè)進(jìn)程崩潰，組只是簡(jiǎn)單地變得更小，但是還可以繼續(xù)。問題在于當(dāng)一個(gè)進(jìn)程崩潰時(shí)不能像一個(gè)進(jìn)程自動(dòng)離開那樣進(jìn)行通知。實(shí)際上，如果主進(jìn)程崩潰，后備進(jìn)程執(zhí)行一些選舉算法來選擇一個(gè)新的主進(jìn)程。正如我們提到的那樣，如果客戶可以根據(jù)它的表決機(jī)制做出決定，我們甚至可以容忍 2k+1個(gè)進(jìn)程中的 k個(gè)進(jìn)程得出錯(cuò)誤的結(jié)果。 34 故障系統(tǒng)的協(xié)議 ?假定藍(lán)軍 1的司令 A發(fā)送一個(gè)消息給藍(lán)軍 2的司令官 B：“ 我有一個(gè)計(jì)劃 —— 我們?cè)诿魈炝璩堪l(fā)起攻擊 ” 。 37 故障系統(tǒng)的協(xié)議 ?現(xiàn)在我們假定通信良好，但是進(jìn)程卻并不好。每個(gè)將軍都得到來自其他三個(gè)將軍的三個(gè)向量。具有 2m+1個(gè)忠誠(chéng)者，就可以達(dá)到這一點(diǎn)，因?yàn)橹挥挟?dāng)三分之二以上的選票相同才能達(dá)成協(xié)議。 ?但是通常不能掩蓋連接的崩潰性故障。我們?cè)谙旅嬗懻撛佣嗖?，然后再回到這個(gè)問題上來。另外，我們也需要考慮接收者可能發(fā)布在關(guān)于網(wǎng)上的情況。換句話說，我們假定使用的是活動(dòng)的復(fù)制協(xié)議。下面來區(qū)分一下接收消息和發(fā)送消息。作為選擇， m可以被每個(gè)成員忽略，這對(duì)應(yīng)于在發(fā)送 m之前發(fā)送者崩潰的情況。在簡(jiǎn)單的方案中，協(xié)調(diào)者通知所有涉及到的稱為參與者的其他進(jìn)程是否 (本地 )按要求執(zhí)行操作。如果所有的參與者都表決要提交事務(wù)，那么協(xié)調(diào)者就進(jìn)行提交。因此存活進(jìn)程總是可以做出的最后決定。 ? 還有一種可供選擇的方式是使用一種稱為擦除修正 (erasure correction)的方法。例如，如果一個(gè)人從柜員機(jī)取走了 1000美元時(shí)，那么即使自動(dòng)柜員機(jī)立即回退這些錢也很難追回。著重強(qiáng)調(diào)了記錄一致全局狀態(tài)的必要性，稱為分布式快照。因此，P2需要回退到更早的狀態(tài)。如果 CP[j](m1)導(dǎo)致了不一致的全局狀態(tài)，那么還需要進(jìn)行更多的回退。這稱為增量快照。 ? 實(shí)際上，如果以相同的非確定性事件作為開始進(jìn)行重放，那么一個(gè)間隔的重放可以具有已知的結(jié)果，也就是說，以一種完全確定的方式進(jìn)行重放。特別是， DEP(m)由那些接收 m的進(jìn)程組成。第一種方法稱為悲觀日志協(xié)議。在樂觀的方法中， DEP(m)中的任何孤兒進(jìn)程都被回退到一個(gè)不再屬于 DEP(m)的狀態(tài)。即，如果一個(gè)依賴于 m，但是沒有辦法來重放 m的傳輸時(shí)它就是一個(gè)孤兒進(jìn)程。認(rèn)為每個(gè)消息 m都具有頭部，頭部中包含了重發(fā) m并正確處理它所需的所有信息。在這種模式中，假定每個(gè)進(jìn)程的執(zhí)行者都有一連串的間隔，事件是在這些間隔中發(fā)生的。當(dāng)協(xié)調(diào)者接收到所有進(jìn)程的確認(rèn)時(shí)，它就多播一個(gè) Checkpoint_Done消息讓 (阻塞的 )進(jìn)程繼續(xù)執(zhí)行。 88 獨(dú)立檢查點(diǎn) ? 當(dāng)進(jìn)程 Pi按 Int[i](m)的間隔發(fā)送消息時(shí)，它就在接收進(jìn)程中加入 (i, m)對(duì)。下面要說明一種尋找恢復(fù)線的方法。在只使用檢查點(diǎn)的系統(tǒng)中，進(jìn)程將被恢復(fù)到設(shè)臵檢查點(diǎn)時(shí)的狀態(tài)，它們的行為將與發(fā)生故障之前不同。首先，把一個(gè)系統(tǒng)或進(jìn)程恢復(fù)到原先的狀態(tài)通常是一個(gè)相對(duì)開銷較大的操作。前向錯(cuò)誤恢復(fù)機(jī)制的關(guān)鍵在于它必須預(yù)先知道會(huì)發(fā)生什么錯(cuò)誤。它們各自的狀態(tài)機(jī)如圖 。 69 兩階段提交 ? 兩階段提交協(xié)議 (2PC)是由 Gray(1978)提出的。后來 P3恢復(fù)了，它可以在它的狀態(tài)進(jìn)行更新之后再次加入該組。組成員關(guān)系的這個(gè)改變被宣告給 G中的所有進(jìn)程。 ?當(dāng)崩潰的副本恢復(fù)時(shí)，它就被強(qiáng)迫再次加入該組。這種方式稱為原子多播。在這種方式中，接收者很容易探測(cè)到消息接收者，那么發(fā)送者就簡(jiǎn)單地在每個(gè)接收者都返回一個(gè)確認(rèn)之前在歷史緩存器中保留消息。不過，如果進(jìn)程數(shù)目較少，通過多個(gè)可靠的點(diǎn)到點(diǎn)通道來獲得可靠性是一種簡(jiǎn)單而直接的方法。特別是，通信通道也可能出現(xiàn)崩潰性故障、遺漏性故障、定時(shí)故障和隨意性故障。算法無法達(dá)成一致。在圖 n=4而 m=1的情況下這種算法的工作情況。如果這個(gè)消息沒有到達(dá)，行動(dòng)就被取消。紅軍具有 5000個(gè)士兵，在一個(gè)山谷中扎營(yíng)。在最壞的情況下， k個(gè)失敗的進(jìn)程可以意外地產(chǎn)生同樣的回答，這樣，客戶或表決電路還可以相信多數(shù)進(jìn)程的回答。 29 故障掩蓋和復(fù)制 ?進(jìn)程組是建立容錯(cuò)系統(tǒng)方法的一部分，特別是在有一組相同的進(jìn)程允許我們掩蓋組中的一個(gè)或多個(gè)發(fā)生故障的進(jìn)程的情況下。所有組服務(wù)器崩潰、組管理就不再存在。例如，一個(gè)進(jìn)程是協(xié)調(diào)者而其他進(jìn)程都是工作者。在下面的內(nèi)容中，