【正文】 有單一的失敗點(diǎn)，代價是分布式的協(xié)調(diào)。 ?當(dāng)然，說一個系統(tǒng)是 k容錯的，讓 k+1相同的進(jìn)程以票數(shù)勝過 k個相同的應(yīng)答在理論上是好的，但是在實(shí)踐中很難想象這樣的情況，即 k個進(jìn)程失敗了，但是k+1個進(jìn)程沒有失敗。在很多情況下要求達(dá)到一致。兩支藍(lán)軍各有 3000人，分別在山谷兩邊的山坡上扎營。 ?但是后來 A意識到 B并不知道使者是否安全返回，而不知道這一點(diǎn)可能不敢發(fā)動攻擊。 36 故障系統(tǒng)的協(xié)議 ?但是，最后一個消息的發(fā)送者并不知道消息是否到達(dá)。通信是通過電話雙向進(jìn)行的，及時而且質(zhì)量很好。對這樣的參數(shù)來說，這個算法需要進(jìn)行 4步操作。最后在第 4步中，每個將軍都檢查新收到的向量中的第 i個元素。 ? Lamport等（ 1982）在他的論文中證明在具有 m個故障進(jìn)程的系統(tǒng)中，只有存在 2m+1個正確工作的進(jìn)程才能達(dá)成協(xié)議，這樣總共就有 3m+1個進(jìn)程。 Fischer等(1985)證明了在不能保證消息在已知的有限時間內(nèi)交付的分布式系統(tǒng)中，即使只有一個進(jìn)程故障 (雖然該進(jìn)程發(fā)生的是沉默性故障 )也不可能達(dá)成協(xié)議。在實(shí)踐中建立可靠的通信通道時，焦點(diǎn)應(yīng)該放在掩蓋崩潰性故障與遺漏性故障上。要掩蓋這樣的故障，唯一的方法就是讓分布式系統(tǒng)嘗試自動建立一個新的連接。 ?要做到這一點(diǎn)，我們需要準(zhǔn)確地定義什么是可靠多播。在最簡單的情況下，不要求所有的組成員都按同樣的順序接收消息，但是有時需要這個特性。如果接收者探測到它丟失了一個消息，那么就返回一個否定確認(rèn)，請求發(fā)送者重發(fā)。 55 基于組的可靠多播方法 ?只返回否定確認(rèn)理論上還存在另外一個問題，發(fā)送者不得不永遠(yuǎn)在歷史緩存器中保留消息。 ?為了理解原子多播的重要性，我們來考慮一個作為在分布式系統(tǒng)上建立的應(yīng)用程序基礎(chǔ)的復(fù)制數(shù)據(jù)庫。 ?當(dāng)崩潰的副本恢復(fù)時，它可以恢復(fù)到它崩潰之前的狀態(tài)，但是它可能會錯過一些更新。在它重新注冊為組成員之前沒有更新操作轉(zhuǎn)發(fā)給它。接收到的消息在發(fā)送到高層的應(yīng)用程序之前放在通信層的本地緩存器中。即，通過多播一個 vc消息宣布一個進(jìn)程加入或離開，視圖的改變就發(fā)生了。具有這種屬性的可靠多播被稱為虛擬同步。 64 虛擬同步 圖 虛擬同步多播的原理 65 虛擬同步 ?虛擬同步的原理是所有的多播都在視圖改變之間進(jìn)行 。例如，在分布式事務(wù)的情況下，不可能進(jìn)行本地提交，因為這會破壞并發(fā)控制約束?？紤]一個分布式事務(wù)中有很多進(jìn)程作為參與者，每個進(jìn)程都運(yùn)行在不同的機(jī)器上。 4. 每個提交表決的參與者都等待協(xié)調(diào)者的最后反應(yīng)。該協(xié)議的本質(zhì)在于協(xié)調(diào)者和每個參與者都滿足以下兩個條件： ? 沒有一個可以直接轉(zhuǎn)換到 Commit或者 Abort狀態(tài)的單獨(dú)狀態(tài)。錯誤恢復(fù)的總體想法是用正確的狀態(tài)取代錯誤的狀態(tài)。只有在這樣的情況下才可能糾正錯誤并轉(zhuǎn)到新的狀態(tài)。典型的值為 k=16或k=32，而且 kn2k，參閱 (Rizzo 1997)。例如，如接下來的部分講述的那樣，要從進(jìn)程崩潰或站點(diǎn)失敗中恢復(fù)通常需要做很多工作。因此，很多容錯的分布式系統(tǒng)把檢查點(diǎn)與消息日志相結(jié)合。例如，因為通信時間是不確定的，消息可能以不同的次序發(fā)送，而導(dǎo)致接收者的不同響應(yīng)。 ? 在回退錯誤恢復(fù)方法中，每個進(jìn)程都按時把它的狀態(tài)保存在本地可用的穩(wěn)定存儲中。這種折疊回退的過程可能會導(dǎo)致多米諾效應(yīng)。在這個例子中，恢復(fù)線就是系統(tǒng)的最初狀態(tài)。當(dāng)進(jìn)程 Pi按 Int[j](n)的間隔接收消息時，就使用 (i, m)是索引對，它記錄了Int[i](m)?Int[j](n)的依賴關(guān)系。另外，它不是支配性能因素的進(jìn)程之間的協(xié)調(diào)。 91 協(xié)調(diào)檢查點(diǎn) ? 很容易看出這個方法可以使全局狀態(tài)一致，因為沒有即將近來的消息注冊為檢查點(diǎn)的一部分。一個進(jìn)程只轉(zhuǎn)發(fā)一次請求。這些事件與第 5章中討論過的 Lamport的先發(fā)生關(guān)系的事件相同。 Alvisi和 Marzullo(1998)介紹的方法說明，如果我們關(guān)注現(xiàn)存的消息日志方案如何處理孤兒進(jìn)程，那么可以容易地描述消息日志方案的特征。例如，每個頭部都包含了發(fā)送者和接收者的標(biāo)識符以及一個用來識別它的序列號。 ? COPY(m)進(jìn)程集由那些具有 m的拷貝，但是該拷貝不在它的本地穩(wěn)定存儲中的進(jìn)程組成。 ? 要避免產(chǎn)生孤兒進(jìn)程，需要確認(rèn)：如果 COPY(m)中的每個進(jìn)程都崩潰了，在 DEP(m)中沒有幸存的進(jìn)程。注意只要 m被傳送給進(jìn)程 P， P就稱為COPY(m)的成員。很明顯，樂觀日志協(xié)議需要跟蹤依賴關(guān)系，這使它們的實(shí)現(xiàn)變得更復(fù)雜。這種方法可以避免孤兒進(jìn)程。 100 消息日志 ? 可以使用兩種方法來做到這一點(diǎn)。 99 消息日志 ? 使用這些表示，現(xiàn)在很容易就可以準(zhǔn)確定義孤兒進(jìn)程是什么了。 98 消息日志 ? 每個消息 m都導(dǎo)致產(chǎn)生一個進(jìn)程組 DEP (m)，它依賴于 m的傳送。但是，與其他消息不同，消息 m2沒有進(jìn)行日志記錄。一個時間間隔以發(fā)生非確定性的事件之前的最后一個事件結(jié)束。 ? 消息日志的基本思想是：如果消息的傳播可以重放，那么我們就能夠到達(dá)一個全局一致的狀態(tài)而不需要從穩(wěn)定存儲中恢復(fù)該狀態(tài)。如果一個進(jìn)程在設(shè)臵了上個檢查點(diǎn)之后接收到了與協(xié)調(diào)者發(fā)送的消息直接或間接相關(guān)的消息，那么這個進(jìn)程就是依賴于協(xié)調(diào)者的。 ? 一種比較簡單的方法是使用兩階段的阻塞協(xié)議。特別是，在我們的例子中，進(jìn)程至少需要回退到檢查點(diǎn)CP[j](m1)。但是它主要的缺點(diǎn)還是恢復(fù)線的計算。不幸的是，這兩個最近保存的本地狀態(tài)不能組成一個一致的全局狀態(tài)， P2保存的狀態(tài)表明了消息 m的接收，但是沒有其他進(jìn)程說明其為發(fā)送者。 83 檢查點(diǎn) 圖 恢復(fù)線 84 獨(dú)立檢查點(diǎn) ? 不幸的是，每個進(jìn)程的檢查點(diǎn)是以一種不協(xié)調(diào)的方式來按時記錄它的本地狀態(tài)的，這種分布式本性使得找到一個恢復(fù)線很困難。分布式系統(tǒng)的狀態(tài)已經(jīng)在第 5章中進(jìn)行了討論。當(dāng)接收進(jìn)程崩潰時，需要恢復(fù)到最近的檢查點(diǎn)的狀態(tài)，并從這個狀態(tài)重放被發(fā)送的消息。 ? 最后，盡管回退錯誤恢復(fù)需要設(shè)臵檢查點(diǎn)，但也決不會回退到某些狀態(tài)?；赝隋e誤恢復(fù)的一個重要優(yōu)點(diǎn)在于它是一種通用的方法，不依賴于任何特定的系統(tǒng)或進(jìn)程。因此，通過分組重發(fā)獲得的可靠通信就是應(yīng)用回退錯誤恢復(fù)技術(shù)的一個例子。每次記錄系統(tǒng)的當(dāng)前狀態(tài)時，就稱為設(shè)臵一個檢查點(diǎn)。在 3PC中，只要有可操作的進(jìn)程處于Ready狀態(tài)，就沒有崩潰的進(jìn)程可以恢復(fù)達(dá) Init、Abort或 Premit之外的狀態(tài)。 Skeen(1981)開發(fā)了一種 2PC的變種，稱為三階段提交協(xié)議 (3PC)，它避免了在出現(xiàn)故障停機(jī)時的阻塞過程。 3. 協(xié)調(diào)者收集來自參與者的所有選票。分布式提交的問題涉及到要使一個操作被進(jìn)程組中的每個成員都執(zhí)行或一個成員都不執(zhí)行。 66 ?容錯性簡介 ?進(jìn)程恢復(fù) ?可靠的客戶 服務(wù)器通信 ?可靠的組通信 ?分布式提交 ?恢復(fù) 67 分布式提交 ?分布式提交通常以設(shè)立協(xié)調(diào)者方式建立。但是在崩潰之前塔成功地將消息多播到了進(jìn)程 P2和P4，但是沒有多播到 P1。在這種情況下，或者是 G里的所有成員都知道這個新成員的異常結(jié)束，或者沒有一個成員知道。即，它們都同意 m應(yīng)該被傳送給它們中的每一個而且不被傳送到別的進(jìn)程。 59 虛擬同步 ?存在失敗時的可靠多播可以根據(jù)進(jìn)程組和組成員關(guān)系的變化進(jìn)行準(zhǔn)確的定義。在這種情況下，在一個副本崩潰之前發(fā)送給所有副本的更新操作或者是在所有的正常副本上都執(zhí)行，或者是一個都不執(zhí)行。更新操作總是向所有副本進(jìn)行多播，然后在本地進(jìn)行。 56 原子多播 ?現(xiàn)在我們返回需要在存在進(jìn)程失敗的情況下獲得可靠多播的情況。如果有很多的接收者，那么發(fā)送者可能被大量的反饋消息淹沒，這被稱為反饋擁塞。 ?一種簡單的方法如圖 。其中的竅門在于除了不同的次序約束之外，還應(yīng)該就在傳遞消息之前組看上去是什么樣達(dá)成協(xié)議。 49 ?容錯性簡介 ?進(jìn)程恢復(fù) ?可靠的客戶 服務(wù)器通信 ?可靠的組通信 ?分布式提交 ?恢復(fù) 50 可靠的組通信 ?盡管大多數(shù)的傳輸層都提供了可靠的點(diǎn)到點(diǎn)通道，它們很少能提供一組進(jìn)程的可靠通信。這樣的故障對 TCP客戶是完全隱藏的。 45 ?容錯性簡介 ?進(jìn)程恢復(fù) ?可靠的客戶 服務(wù)器通信 ?可靠的組通信 ?分布式提交 ?恢復(fù) 46 可靠的客戶 服務(wù)器通信 ?在很多情況下，分布式系統(tǒng)中的容錯關(guān)注的是故障進(jìn)程。即使有 m個叛徒，他們與那些已經(jīng)被叛徒誤導(dǎo)的忠誠者在一起表決，我們也需要確保表決的結(jié)果是忠誠者的票數(shù)占多數(shù)。叛徒不能破壞忠誠的將軍的信息，因此他也不能破壞這個工作。 39 故障系統(tǒng)的協(xié)議 ?第 3步，每個將軍把他從圖 其他所有將軍。假定每個將軍都知道他有多少士兵，將軍的目的是交換兵力，這樣在算法結(jié)束時每個將軍都得到一個對應(yīng)于所有軍隊的兵力情況的長度為 n的向量。在不可靠傳輸?shù)臈l件下，即使是無錯誤的進(jìn)程，在兩個進(jìn)程之間達(dá)成協(xié)議也是不可能的。 ?很容易看出，即使使者每次都能成功通過山谷，不論它們發(fā)送了多少確認(rèn)， A和 B也永遠(yuǎn)不會達(dá)成協(xié)議。他們只能使用不可靠的方法進(jìn)行通信：派一個可能會被紅軍抓獲的使者。根據(jù)系統(tǒng)參數(shù)的不同可能有不同的情況，包括通信是否可靠或進(jìn)程崩潰性失敗的語義。 32 故障系統(tǒng)的協(xié)議 ?把復(fù)制的進(jìn)程組織在一個組中有助于提供容錯性。如果這些組件 (進(jìn)程 )是失敗沉默的，那么具有 k+1個組件就足夠提供 k個容錯。在實(shí)踐中，這個主進(jìn)程是固定的，盡管如果需要可以用一個后備進(jìn)程來接管它。 28 組成員 ?與組成員相關(guān)的最后一個問題是如果很多機(jī)器停機(jī)使得組完全不能工作時該怎么辦。在容錯環(huán)境中，故障停機(jī)的語義一般并不確切。這個組服務(wù)器保持著所有組及其成員的完整的數(shù)據(jù)庫。平等組是對稱的，沒有單獨(dú)的失敗點(diǎn)。在一些組中，所有的進(jìn)程都是平等的。 ?進(jìn)程組可以是動態(tài)的。換句話說，通過冗余的進(jìn)程可以獲得高度容錯性。例如可以在傳輸?shù)臄?shù)據(jù)中添加一段 Hamming碼來從傳輸線路上的噪聲中恢復(fù)數(shù)據(jù)。特別是，服務(wù)器可能產(chǎn)生它從來沒有產(chǎn)生過的輸出，但是又不能檢測出錯誤。可能發(fā)生兩種響應(yīng)故障。 13 典型故障 ?與此類似，如果服務(wù)器能正常工作，但是在發(fā)送響應(yīng)時失敗，則產(chǎn)生發(fā)送遺漏性故障。雖然人們期望個人計算機(jī)系統(tǒng)能正常運(yùn)行，但它經(jīng)常遭遇崩潰性故障。但是，出現(xiàn)故障的服務(wù)器本身并不總是我們應(yīng)該查找錯誤的地方。 ?間歇故障發(fā)生，消失不見，然后再次發(fā)生，如此反