【正文】 復(fù)進(jìn)行。例如，不好的傳輸介質(zhì)可能很容易使得數(shù)據(jù)包被破壞。但是，像我們?cè)诒菊潞竺鎸⒖吹降哪菢?，從故障中自?dòng)恢復(fù)說(shuō)起來(lái)簡(jiǎn)單，做起來(lái)就難了。高度可靠的系統(tǒng)可以在一個(gè)相對(duì)較長(zhǎng)的時(shí)間內(nèi)持續(xù)工作而不被中斷。特別是，當(dāng)故障發(fā)生時(shí)，分布式系統(tǒng)應(yīng)該在進(jìn)行恢復(fù)的同時(shí)繼續(xù)以可接受的方式進(jìn)行操作，也就是說(shuō)，它應(yīng)該能容忍錯(cuò)誤，在發(fā)生錯(cuò)誤時(shí)某種程度上可以繼續(xù)操作。這個(gè)故障也許會(huì)影響到其他組件的正確操作，但同時(shí)也有可能完全不影響其他組件。換句話說(shuō)，高度可用的系統(tǒng)在任何給定的時(shí)刻都能及時(shí)地工作。過(guò)去的很多例子 (以后也還會(huì)有更多的例子 )都說(shuō)明了要建立安全的系統(tǒng)是多么困難。在這種環(huán)境下，被破壞了意味著接收者可能錯(cuò)誤地得到某位的值 (例如把 0讀成 1)，甚至無(wú)法探測(cè)到有什么東西到達(dá)了。對(duì)我們來(lái)說(shuō)最重要的問(wèn)題是容錯(cuò) (fault tolerance)，它意味著系統(tǒng)即使在發(fā)生故障時(shí)也能提供服務(wù)。芯片燃燒、軟件錯(cuò)誤和磁盤(pán)頭損壞都是持久性故障的例子。 11 典型故障 圖 不同類型的故障 故障類型 說(shuō)明 崩潰性故障 服務(wù)器停機(jī)，但是在停機(jī)之前工作正常 遺漏性故障 接收故障 發(fā)送故障 服務(wù)器不能響應(yīng)到來(lái)的請(qǐng)求 服務(wù)器不能接收到來(lái)的消息 服務(wù)器不能發(fā)送消息 定時(shí)故障 服務(wù)器的響應(yīng)在指定的時(shí)間間隔之外 響應(yīng)故障 值故障 狀態(tài)轉(zhuǎn)換故障 服務(wù)器的響應(yīng)不正確 響應(yīng)的值錯(cuò)誤 服務(wù)器偏離了正確的控制流 隨意性故障 服務(wù)器可能在隨意的時(shí)間產(chǎn)生隨意的響應(yīng) 12 典型故障 ?如果服務(wù)器過(guò)早停機(jī)但在停止之前工作正常，就發(fā)生了崩潰性故障。在發(fā)生接收遺漏性故障的情況下，首先服務(wù)器可能永遠(yuǎn)不會(huì)接收到請(qǐng)求。 ?另外一種故障類型與時(shí)間有關(guān)。特別是，發(fā)生故障的服務(wù)器可能會(huì)錯(cuò)誤地采取一種從來(lái)沒(méi)有初始化的默認(rèn)行為來(lái)進(jìn)行處理，此時(shí)就發(fā)生這種故障。有三種可能：信息冗余、時(shí)間冗余和物理冗余。 ?在物理冗余中，通過(guò)添加額外的裝備或進(jìn)程使系統(tǒng)作為一個(gè)整體來(lái)容忍部分組件的失效或故障成為可能。 21 進(jìn)程恢復(fù) ?容忍失敗進(jìn)程的關(guān)鍵方法是把多個(gè)同樣的進(jìn)程組織到一個(gè)組中。 ?引入組的目的在于允許把進(jìn)程的集合作為單一的抽象概念來(lái)處理。協(xié)調(diào)者決定哪個(gè)工作者最適合，然后把請(qǐng)求轉(zhuǎn)發(fā)給它。協(xié)調(diào)者的故障會(huì)使整個(gè)組崩潰，但是只要它保持運(yùn)行，就可以獨(dú)自做出決定，不需要其他進(jìn)程參加。 ?與之相反的方法是以分布式的方法來(lái)管理組成員。即，從進(jìn)程加入一個(gè)組開(kāi)始，它就必須接收發(fā)送給該組的所有消息。像前面討論過(guò)的那樣，有兩種方法來(lái)進(jìn)行復(fù)制：通過(guò)基于主進(jìn)程的協(xié)議或通過(guò)復(fù)制寫(xiě)協(xié)議。 ?使用進(jìn)程組進(jìn)行容錯(cuò)中一個(gè)重要的問(wèn)題是需要多少?gòu)?fù)制。這樣，即使在容錯(cuò)系統(tǒng)中也需要某種統(tǒng)計(jì)分析。例如，選擇一個(gè)協(xié)調(diào)者，決定是否提交一個(gè)事務(wù)，在工作者之間劃分任務(wù)以及同步。如果兩支藍(lán)軍可以協(xié)調(diào)他們對(duì)紅軍的攻擊，那么他們就能獲得勝利。然后 A讓使者去告訴 B他 (B)的消息已經(jīng)到達(dá)，可以進(jìn)行戰(zhàn)斗。如果沒(méi)有到達(dá)，就沒(méi)有完成協(xié)議，其他的司令官也不會(huì)發(fā)起攻擊。但是有 n個(gè)將軍是叛徒 (故障 )，他們通過(guò)給忠誠(chéng)的將軍發(fā)送錯(cuò)誤的和矛盾的信息 (模擬故障進(jìn)程 )來(lái)阻止他們達(dá)成協(xié)議。在第 1步中，每個(gè)將軍發(fā)送一個(gè) (可靠的 )消息給其他所有將軍以宣布他的兵力，忠誠(chéng)的將軍說(shuō)的是實(shí)話；而叛徒則向別的將軍說(shuō)謊。如果哪個(gè)值為多數(shù)，就把它放到結(jié)果向量中。換句話說(shuō)，只有當(dāng)三分之二以上的進(jìn)程正常工作時(shí)才可能達(dá)成協(xié)議。這種系統(tǒng)中的問(wèn)題在于無(wú)法區(qū)分任意慢的進(jìn)程與崩潰的進(jìn)程。隨意性故障可能以重復(fù)消息的形式發(fā)生，造成他的原因是在計(jì)算機(jī)網(wǎng)絡(luò)中可能把消息緩沖一個(gè)相對(duì)較長(zhǎng)的時(shí)間，然后在原始發(fā)送者發(fā)出重新傳送命令時(shí)把消息重新發(fā)到網(wǎng)絡(luò)中。 48 可靠的客戶 服務(wù)器通信 ?RPC的目標(biāo)是通過(guò)使遠(yuǎn)程過(guò)程調(diào)用與本地調(diào)用看上去相同來(lái)隱藏通信。直觀地說(shuō)，它意味著發(fā)送到一個(gè)進(jìn)程組的消息被傳遞給該組中的每個(gè)成員。 52 基于組的可靠多播方法 ?只要接收者的數(shù)目有限，那么這種較弱形式的可靠多播實(shí)現(xiàn)起來(lái)相對(duì)容易。作為選擇，發(fā)送者可以在某個(gè)時(shí)間內(nèi)沒(méi)有接收到所有確認(rèn)的情況下自動(dòng)重發(fā)消息。因?yàn)榘l(fā)送者永遠(yuǎn)不會(huì)知道消息是否已被傳送到所有的接收者，它應(yīng)該總是準(zhǔn)備處理來(lái)自接收者的要求重發(fā)舊消息的請(qǐng)求。分布式提供了可靠的多播功能。在這一點(diǎn)上，讓它與其他副本保持狀態(tài)一致是基本的要求。加入一個(gè)組需要使它的狀態(tài)與其他的組成員保持一致。 ?原子多播的總體思想是多播消息 m應(yīng)該唯一地跟它應(yīng)該傳送到的一個(gè)進(jìn)程表相關(guān)聯(lián)?，F(xiàn)在有兩個(gè)多播消息在同時(shí)進(jìn)行傳輸：m和 vc。 63 虛擬同步 ?考慮圖 4個(gè)進(jìn)程。即 ， 視圖改變作為一個(gè)屏障 ， 不能跨越它進(jìn)行多播 。 ?在實(shí)踐中需要更復(fù)雜的方法，最常用的是兩階段提交協(xié)議，但它的缺點(diǎn)是不能有效地處理協(xié)調(diào)者失敗的情況。假定沒(méi)有故障發(fā)生，協(xié)議就由以下兩個(gè)階段組成，每個(gè)階段又由兩步組成。如果參與者接收到一個(gè) Global_Commit消息，那么它就在本地提交事務(wù)，否則接收到一個(gè) Global_Abort消息時(shí)，就在本地取消事務(wù)。 ? 沒(méi)有一個(gè)這樣的狀態(tài)：它不能做出最后決定，而且可以從它直接轉(zhuǎn)換到 Commit狀態(tài)。從本質(zhì)上說(shuō)，有兩種形式的錯(cuò)誤恢復(fù)。 77 恢復(fù) ? 考慮一下可靠通信的實(shí)現(xiàn)，很容易解釋前向錯(cuò)誤恢復(fù)與回退錯(cuò)誤恢復(fù)之間的區(qū)別。如果沒(méi)有足夠的分組被傳送，發(fā)送者就不得不繼續(xù)發(fā)送分組直到先前丟失的分組可以被重建為止。 79 恢復(fù) ? 第二，因?yàn)榛赝隋e(cuò)誤恢復(fù)機(jī)制不依賴于實(shí)際使用的分布式應(yīng)用程序，不能保證一旦進(jìn)行了恢復(fù)就不再發(fā)生相同或類似的失敗。在這種情況下，在沒(méi)有設(shè)臵檢查點(diǎn)后，一個(gè)進(jìn)程在發(fā)送消息之前對(duì)它進(jìn)行記錄 (稱為基于發(fā)送者的日志 )。但是，如果使用了消息日志，那么就會(huì)發(fā)生從上次檢查點(diǎn)之后事件的真實(shí)重放。要在進(jìn)程或系統(tǒng)失敗之后進(jìn)行恢復(fù)，就需要我們從這些局部狀態(tài)中建立一致的全局狀態(tài)。圖 。 87 獨(dú)立檢查點(diǎn) ? 由于進(jìn)程獨(dú)立地設(shè)臵本地檢查點(diǎn)，所以這種方法也被稱為獨(dú)立的檢查點(diǎn)方法。然后，當(dāng) Pj采用檢查點(diǎn) CP[j](n)時(shí)，它就把這個(gè)依賴關(guān)系與恢復(fù)信息的其他部分一起寫(xiě)入它的本地穩(wěn)定存儲(chǔ)中。相反，需要把狀態(tài)保存到本地穩(wěn)定存儲(chǔ)中，它還造成一些額外開(kāi)銷，因此，協(xié)調(diào)檢查點(diǎn)使用得更為普遍，它也比獨(dú)立檢查點(diǎn)更為簡(jiǎn)單。其原因在于任何跟隨在設(shè)臵檢查點(diǎn)的請(qǐng)求之后的消息都不被認(rèn)為是本地檢查點(diǎn)的一部分。當(dāng)確認(rèn)所有的進(jìn)程之后，使用第二次多播來(lái)引發(fā)實(shí)際的檢查點(diǎn)，然后所有的進(jìn)程繼續(xù)執(zhí)行。假如，一個(gè)事件可能是一條指令的執(zhí)行、一條消息的發(fā)送等。 ? 孤兒進(jìn)程就是在其他進(jìn)程崩潰之后還存在的進(jìn)程，但是它的狀態(tài)與恢復(fù)之后的崩潰進(jìn)程不一致。另外還有一個(gè)傳送號(hào)碼用來(lái)確定它應(yīng)該在何時(shí)被傳送給接收應(yīng)用程序。當(dāng)一個(gè)進(jìn)程傳送消息 m時(shí)，它就也成為 COPY(m)的成員。即， DEP(m)中的所有進(jìn)程都應(yīng)該已經(jīng)崩潰了。 ? 最壞的情況就是 P在 m還沒(méi)有被記錄的時(shí)候就崩潰了。 ? 像在 (Einozahy等 1996)中指出的那樣，悲觀日志要比樂(lè)觀的方法簡(jiǎn)單得多，所以在實(shí)際的分布式設(shè)計(jì)中它是消息日志的首選方法。因此，沒(méi)有其他進(jìn)程會(huì)依賴于 m的傳送，就沒(méi)有了重放 m的傳輸?shù)目赡苄?。即，不論何時(shí)一個(gè)進(jìn)程要依賴于m的傳送，那么它就總要保持 m的一份拷貝。如果所有這些進(jìn)程都崩潰了，那么重放 m的傳輸顯然就是不可能的。因此可以使用重放穩(wěn)定消息的傳輸來(lái)進(jìn)行恢復(fù)。進(jìn)程 Q從進(jìn)程 P與 R那里分別接收到消息 m1和 m2，然后把消息 m2發(fā)送給 R。但是，這個(gè)時(shí)刻之后進(jìn)程的執(zhí)行就是完全確定的。在分布式系統(tǒng)中有一種重要的技術(shù)消息日志。 92 協(xié)調(diào)檢查點(diǎn) ? 對(duì)這種算法的一種改進(jìn)是只對(duì)那些依賴協(xié)調(diào)者的恢復(fù)的進(jìn)程多播檢查點(diǎn)請(qǐng)求而忽略其他進(jìn)程。協(xié)調(diào)檢查點(diǎn)的主要優(yōu)點(diǎn)是所保存的狀態(tài)自動(dòng)保持全局一致，這樣就可以避免導(dǎo)致多米諾效應(yīng)的折疊回退。要確保全局一致性，我們需要確保所有從 Pi那里接收到了按間隔 Int[i](m)發(fā)送的消息的進(jìn)程都回退到在接收這個(gè)消息之前的檢查點(diǎn)狀態(tài)。獨(dú)立檢查點(diǎn)的另一個(gè)缺點(diǎn)是每個(gè)本地存儲(chǔ)都需要按時(shí)清理，例如通過(guò)運(yùn)行一個(gè)特定的分布式垃圾收集器來(lái)進(jìn)行清理。與此類似，進(jìn)程 P1也需要進(jìn)行回退。即，恢復(fù)線就對(duì)應(yīng)于最近的一致性切面，圖 。 82 檢查點(diǎn) ? 在容錯(cuò)的分布式系統(tǒng)中，回退錯(cuò)誤恢復(fù)需要系統(tǒng)把它的狀態(tài)有規(guī)律地保存到穩(wěn)定存儲(chǔ)中。這種方法也稱為接收者的日志。即，回退錯(cuò)誤恢復(fù)機(jī)制通常不能提供完全的故障透明性。 78 恢復(fù) ? 一般來(lái)說(shuō)，回退錯(cuò)誤恢復(fù)技術(shù)作為一種從分布式系統(tǒng)故障中恢復(fù)的機(jī)制被廣泛應(yīng)用。實(shí)際上，分組重發(fā)就是嘗試著回退到以前的正確狀態(tài)，也就是發(fā)送丟失的分組時(shí)的狀態(tài)。要做到這一點(diǎn)，必須定時(shí)記錄系統(tǒng)的狀態(tài)，以便當(dāng)發(fā)生錯(cuò)誤時(shí)恢復(fù)到記錄的狀態(tài)。在這種情況下，其余的可能操作進(jìn)程不能做出最后的決定，不得不在崩潰的進(jìn)程恢復(fù)之前阻塞。因此參與者可能在協(xié)調(diào)者恢復(fù)之前保持阻塞。 2. 當(dāng)參與者接收到 Vote_Request消息時(shí)，就向協(xié)調(diào)者返回一個(gè)Vote_Commit消息通知協(xié)調(diào)者它已經(jīng)準(zhǔn)備好本地提交事務(wù)中屬于它的部分，否則就返回一個(gè) Vote_Abort消息。 68 分布式提交 ?前面討論的原子多播問(wèn)題是一個(gè)稱為分布式提交的更一般化問(wèn)題中一個(gè)例子。 在視圖改變時(shí)進(jìn)行的所有多播都在視圖改變生效之前完成 。在多播了一些消息之后，進(jìn)程 P3崩潰了。 62 虛擬同步 ?這里出現(xiàn)了一個(gè)問(wèn)題，如果 m沒(méi)有被傳送到任何一個(gè)進(jìn)程，怎么能說(shuō)這種協(xié)議是可靠的多播協(xié)議呢 ?原則上，只有一種情況下 m的傳送允許失?。寒?dāng)組成員關(guān)系的改變是由于 m的發(fā)送者崩潰造成的結(jié)果時(shí)。很重要的一點(diǎn)是列表中的每個(gè)進(jìn)程都具有相同的視圖。當(dāng)一個(gè)副本從故障中恢復(fù)并重復(fù)加入組時(shí)，原子多播強(qiáng)制它與組的其他成員一致。 58 原子多播 ?現(xiàn)在假定底層的分布式系統(tǒng)支持原子多播。因此，復(fù)制的數(shù)據(jù)庫(kù)作為一組進(jìn)程被建立，每個(gè)進(jìn)程用于一個(gè)副本。但是，刪除一條消息是在冒險(xiǎn)，因?yàn)橹匕l(fā)的請(qǐng)求有可能不能得到響應(yīng)。如果有 N個(gè)接收者，那么發(fā)送者必須準(zhǔn)備接收至少 N個(gè)確認(rèn)。假定底層的通信系統(tǒng)只需要不可靠的多播，那么這意味著多播消息會(huì)以某種方式丟失，它只能傳遞給其中一些接收者而不是全部。在前一種情況下，如果能保證所有正常的組成員接收到消息，那么就認(rèn)為多播是可靠的。 ?區(qū)分 RPC系統(tǒng)中發(fā)生 5種失敗形式： ?客戶不能定位服務(wù)器； ?客戶到服務(wù)器的請(qǐng)求消息丟失； ?服務(wù)器在收到請(qǐng)求之后崩潰； ?從服務(wù)器到客戶的響應(yīng)消息丟失； ?客戶在發(fā)送請(qǐng)求之后崩潰。 TCP可以通過(guò)確認(rèn)