【正文】 工作者最適合，然后把請(qǐng)求轉(zhuǎn)發(fā)給它。當(dāng)然，也可能有更復(fù)雜的等級(jí)關(guān)系。 23 平等組與等級(jí)組 ?每種組織都具有它的優(yōu)點(diǎn)和缺點(diǎn)。平等組是對(duì)稱的，沒有單獨(dú)的失敗點(diǎn)。如果一個(gè)進(jìn)程崩潰，組只是簡(jiǎn)單地變得更小，但是還可以繼續(xù)。它的缺點(diǎn)在于做出決定比較復(fù)雜。例如，要決定某事常常需要進(jìn)行表決，這導(dǎo)致了一些延遲和開銷。 ?平等組則相反。協(xié)調(diào)者的故障會(huì)使整個(gè)組崩潰，但是只要它保持運(yùn)行，就可以獨(dú)自做出決定，不需要其他進(jìn)程參加。 24 平等組與等級(jí)組 a) Communication in a flat group. b) Communication in a simple hierarchical group 25 組成員 ?當(dāng)組通信發(fā)生時(shí)，需要一些方法來創(chuàng)建和刪除組，以及允許進(jìn)程加入和離開組。一種可能的方法是使用組服務(wù)器，所有這些請(qǐng)求都發(fā)送給它。這個(gè)組服務(wù)器保持著所有組及其成員的完整的數(shù)據(jù)庫。這種方法直接、有效、容易實(shí)現(xiàn)。不幸的是它具有所有集中式技術(shù)的缺點(diǎn)：?jiǎn)我坏氖↑c(diǎn)。所有組服務(wù)器崩潰、組管理就不再存在?？赡艽蠖鄶?shù)或所有組都不得不從頭開始重建，所有組都不得不從頭開始重建，所有正在進(jìn)行的工作都可能終止。 ?與之相反的方法是以分布式的方法來管理組成員。例如，如果可靠的多播可用，一個(gè)外部進(jìn)程就可以發(fā)送消息給所有的組成員表示希望加入該組。 26 組成員 ?離開一個(gè)組，理想的情況是，成員只需要給所有成員發(fā)送一個(gè)再見消息。在容錯(cuò)環(huán)境中，故障停機(jī)的語義一般并不確切。問題在于當(dāng)一個(gè)進(jìn)程崩潰時(shí)不能像一個(gè)進(jìn)程自動(dòng)離開那樣進(jìn)行通知。其他成員不得不通過注意到崩潰的成員不再進(jìn)行響應(yīng)來發(fā)現(xiàn)這一點(diǎn)。一旦確定崩潰的成員是真正的崩潰 (而不是速度慢 )，就從組中刪除它。 27 組成員 ?另外一個(gè)棘手的問題是進(jìn)程的離開與加入必須跟數(shù)據(jù)消息的發(fā)送同步。即，從進(jìn)程加入一個(gè)組開始，它就必須接收發(fā)送給該組的所有消息。與之類似，一旦進(jìn)程離開一個(gè)組，它就不能接收來自該組的任何消息，其他的成員也不能接收來自它的任何消息。一種確保把進(jìn)程的加入或離開集成到消息流中的正確位臵的方法，是把這個(gè)操作轉(zhuǎn)換為一個(gè)發(fā)送到整個(gè)組的消息序列。 28 組成員 ?與組成員相關(guān)的最后一個(gè)問題是如果很多機(jī)器停機(jī)使得組完全不能工作時(shí)該怎么辦。這時(shí)需要通過一些協(xié)議來重建組。一些進(jìn)程不得不進(jìn)行初始化來重新啟動(dòng)，但是如果有兩個(gè)或三個(gè)進(jìn)程同時(shí)進(jìn)行嘗試會(huì)發(fā)生什么？協(xié)議必須能夠處理這些問題。 29 故障掩蓋和復(fù)制 ?進(jìn)程組是建立容錯(cuò)系統(tǒng)方法的一部分，特別是在有一組相同的進(jìn)程允許我們掩蓋組中的一個(gè)或多個(gè)發(fā)生故障的進(jìn)程的情況下。即，我們可以復(fù)制進(jìn)程并把它們組織在一個(gè)組中來用一個(gè)容錯(cuò)的組取代一個(gè)脆弱的進(jìn)程。像前面討論過的那樣，有兩種方法來進(jìn)行復(fù)制：通過基于主進(jìn)程的協(xié)議或通過復(fù)制寫協(xié)議。 ?在容錯(cuò)的情況下，基于主進(jìn)程的復(fù)制通常以主進(jìn)程后備協(xié)議的形式出現(xiàn)。在這種情況下，以等級(jí)方式來組織一個(gè)進(jìn)程組，其中一個(gè)主進(jìn)程組協(xié)調(diào)所有的寫操作。在實(shí)踐中，這個(gè)主進(jìn)程是固定的，盡管如果需要可以用一個(gè)后備進(jìn)程來接管它。實(shí)際上，如果主進(jìn)程崩潰，后備進(jìn)程執(zhí)行一些選舉算法來選擇一個(gè)新的主進(jìn)程。 30 故障掩蓋和復(fù)制 ?與基于團(tuán)體的協(xié)議相同，復(fù)制寫協(xié)議以主動(dòng)復(fù)制的形式使用。這些解決方法把相同進(jìn)程的集合組織到一個(gè)平等組中。這樣做的主要優(yōu)點(diǎn)在于這樣的組沒有單一的失敗點(diǎn)，代價(jià)是分布式的協(xié)調(diào)。 ?使用進(jìn)程組進(jìn)行容錯(cuò)中一個(gè)重要的問題是需要多少?gòu)?fù)制。為了簡(jiǎn)化我們的討論，我們只考慮復(fù)制 —— 寫系統(tǒng)的情況。如果系統(tǒng)能夠經(jīng)受 k個(gè)組件的故障并且還能滿足規(guī)范的要求，那么就稱為 k容錯(cuò)。如果這些組件 (進(jìn)程 )是失敗沉默的，那么具有 k+1個(gè)組件就足夠提供 k個(gè)容錯(cuò)。如果 k個(gè)組件停止工作，還可以用剩下的一個(gè)組件來得到響應(yīng)。 31 故障掩蓋和復(fù)制 ?另一方面，如果進(jìn)程發(fā)生拜占庭失敗，繼續(xù)錯(cuò)誤運(yùn)行并發(fā)送出錯(cuò)誤或隨機(jī)的應(yīng)答，那么最少需要 2k+1個(gè)進(jìn)程才能獲得 k容錯(cuò)。在最壞的情況下， k個(gè)失敗的進(jìn)程可以意外地產(chǎn)生同樣的回答，這樣，客戶或表決電路還可以相信多數(shù)進(jìn)程的回答。 ?當(dāng)然，說一個(gè)系統(tǒng)是 k容錯(cuò)的，讓 k+1相同的進(jìn)程以票數(shù)勝過 k個(gè)相同的應(yīng)答在理論上是好的，但是在實(shí)踐中很難想象這樣的情況，即 k個(gè)進(jìn)程失敗了，但是k+1個(gè)進(jìn)程沒有失敗。這樣，即使在容錯(cuò)系統(tǒng)中也需要某種統(tǒng)計(jì)分析。 ?與這種模式有關(guān)的一個(gè)明顯的前提是所有請(qǐng)求按相同的順序到達(dá)所有的服務(wù)器，這個(gè)問題被稱為原子多播問題 (atomic multicast problem)。實(shí)際上，這個(gè)條件可以稍微放松，因?yàn)樽x操作不會(huì)有問題而一些寫操作也可以替換，但是還留有一般的問題。 32 故障系統(tǒng)的協(xié)議 ?把復(fù)制的進(jìn)程組織在一個(gè)組中有助于提供容錯(cuò)性。正如我們提到的那樣，如果客戶可以根據(jù)它的表決機(jī)制做出決定，我們甚至可以容忍 2k+1個(gè)進(jìn)程中的 k個(gè)進(jìn)程得出錯(cuò)誤的結(jié)果。但是，我們做出的假定是這些進(jìn)程沒有組合成團(tuán)隊(duì)來共同產(chǎn)生錯(cuò)誤的結(jié)果。 ?通常，如果要求進(jìn)程組達(dá)成一致，事情會(huì)變得更復(fù)雜。在很多情況下要求達(dá)到一致。例如，選擇一個(gè)協(xié)調(diào)者，決定是否提交一個(gè)事務(wù)，在工作者之間劃分任務(wù)以及同步。當(dāng)通信和進(jìn)程都很完美時(shí)，達(dá)成這樣的一致通常是簡(jiǎn)單又直接的，但是如果不是這樣，就會(huì)出現(xiàn)問題。 ?分布式協(xié)議算法的一般目標(biāo)是使所有的非故障進(jìn)程就一些問題達(dá)成一致，而且在有限的步驟內(nèi)就達(dá)成一致。根據(jù)系統(tǒng)參數(shù)的不同可能有不同的情況，包括通信是否可靠或進(jìn)程崩潰性失敗的語義。 33 故障系統(tǒng)的協(xié)議 ?在考慮故障進(jìn)程的情況之前，我們先看簡(jiǎn)單的情況：進(jìn)程運(yùn)行很好但是通信線路丟失消息。有一個(gè)稱為兩軍問題 (twoarmy problem)的著名問題，它說明了在兩個(gè)運(yùn)行良好的進(jìn)程之間即使只就 1位信息達(dá)成協(xié)議也是非常困難的。紅軍具有 5000個(gè)士兵，在一個(gè)山谷中扎營(yíng)。兩支藍(lán)軍各有 3000人，分別在山谷兩邊的山坡上扎營(yíng)。如果兩支藍(lán)軍可以協(xié)調(diào)他們對(duì)紅軍的攻擊，那么他們就能獲得勝利。但是如果只有一支藍(lán)軍獨(dú)自發(fā)動(dòng)攻擊，則會(huì)被消滅。藍(lán)軍的目的是就攻擊達(dá)成協(xié)議。他們只能使用不可靠的方法進(jìn)行通信：派一個(gè)可能會(huì)被紅軍抓獲的使者。 34 故障系統(tǒng)的協(xié)議 ?假定藍(lán)軍 1的司令 A發(fā)送一個(gè)消息給藍(lán)軍 2的司令官 B：“ 我有一個(gè)計(jì)劃 —— 我們?cè)诿魈炝璩堪l(fā)起攻擊 ” 。試著到達(dá)藍(lán)軍 2， B讓它帶回一個(gè)消息： “ 好主意，明天凌晨見 ” 。使者安全回到它的基地傳達(dá)了這個(gè)消息，A通知它的士兵準(zhǔn)備在凌晨進(jìn)行戰(zhàn)斗。 ?但是后來 A意識(shí)到 B并不知道使者是否安全返回，而不知道這一點(diǎn)可能不敢發(fā)動(dòng)攻擊。然后 A讓使者去告訴 B他 (B)的消息已經(jīng)到達(dá)，可以進(jìn)行戰(zhàn)斗。 35 故障系統(tǒng)的協(xié)議 ?使者再次穿過山谷傳達(dá)這個(gè)確認(rèn)。但是現(xiàn)在 B在擔(dān)心A不知道確認(rèn)是否能夠到達(dá)，他擔(dān)心的原因是如果 A認(rèn)為使者會(huì)被抓住，他就不能確認(rèn)他 (A)的計(jì)劃，可能不會(huì)冒險(xiǎn)發(fā)起攻擊，所以他派遣使者再次回去。 ?很容易看出，即使使者每次都能成功通過山谷，不論它們發(fā)送了多少確認(rèn)， A和 B也永遠(yuǎn)不會(huì)達(dá)成協(xié)議。假定有某個(gè)可以在有限步驟內(nèi)結(jié)束的協(xié)議，這是一種結(jié)尾去掉任何額外的步驟而得到的可以工作的最小協(xié)議。現(xiàn)在某個(gè)消息是最后的消息，它對(duì)達(dá)成協(xié)議是關(guān)鍵性的 (因?yàn)檫@是最小的協(xié)議 )。如果這個(gè)消息沒有到達(dá)，行動(dòng)就被取消。 36 故障系統(tǒng)的協(xié)議 ?但是，最后一個(gè)消息的發(fā)送者并不知道消息是否到達(dá)。如果沒有到達(dá)，就沒有完成協(xié)議，其他的司令官也不會(huì)發(fā)起攻擊。由于最后一個(gè)消息的發(fā)送者不能知道是否一定發(fā)動(dòng)攻擊，所以也就不能調(diào)動(dòng)他的軍隊(duì)。既然最后一個(gè)消息的接收者知道發(fā)送者不能確認(rèn)，它也就不會(huì)冒險(xiǎn)，因?yàn)闆]有達(dá)成協(xié)議。在不可靠傳輸?shù)臈l件下，即使是無錯(cuò)誤的進(jìn)程，在兩個(gè)進(jìn)程之間達(dá)成協(xié)議也是不可能的。 37 故障系統(tǒng)的協(xié)議 ?現(xiàn)在我們假定通信良好，但是進(jìn)程卻并不好。這里也有一個(gè)經(jīng)典的軍事問題稱為拜占庭將軍問題(Byzantine generals problem)。在這個(gè)問題中，紅軍還是在山谷中扎營(yíng)，但是在附近的山上有 n個(gè)帶領(lǐng)部隊(duì)的藍(lán)軍將領(lǐng)。通信是通過電話雙向進(jìn)行的，及時(shí)而且質(zhì)量很好。但是有 n個(gè)將軍是叛徒 (故障 )，他們通過給忠誠(chéng)的將軍發(fā)送錯(cuò)誤的和矛盾的信息 (模擬故障進(jìn)程 )來阻止他們達(dá)成協(xié)議?，F(xiàn)在問題在于忠誠(chéng)的將軍是否還能達(dá)成協(xié)議。 ?為了一般化，我們?cè)谶@里按照一種稍微不同的方式來定義協(xié)議。假定每個(gè)將軍都知道他有多少士兵，將軍的目的是交換兵力，這樣在算法結(jié)束時(shí)每個(gè)將軍都得到一個(gè)對(duì)應(yīng)于所有軍隊(duì)的兵力情況的長(zhǎng)度為 n的向量。如果將軍 i是忠誠(chéng)的，那么他的兵力中的元素就為 i，否則就是未定義的。 38 故障系統(tǒng)的協(xié)議 ? Lamport等 (1992)建議使用一種遞歸算法，這種算法可以在一定條件下解決這個(gè)問題。在圖 n=4而 m=1的情況下這種算法的工作情況。對(duì)這樣的參數(shù)來說，這個(gè)算法需要進(jìn)行 4步操作。在第 1步中，每個(gè)將軍發(fā)送一個(gè) (可靠的 )消息給其他所有將軍以宣布他的兵力，忠誠(chéng)的將軍說的是實(shí)話；而叛徒則向別的將軍說謊。在圖 ，我們看到將軍 1報(bào)告有1000兵力，將軍 2報(bào)告兵力有 2022兵力，將軍 3向每個(gè)人都說謊，分別給出 x, y和 z，將軍 4報(bào)告有 4000兵力。在第 2步中，第 1步里宣布的結(jié)果按圖 量格式收集在一起。 39 故障系統(tǒng)的協(xié)議 ?第 3步，每個(gè)將軍把他從圖 其他所有將軍。每個(gè)將軍都得到來自其他三個(gè)將軍的三個(gè)向量。將軍 3在這里還是說了謊，編造了 12個(gè)新的值。第 3步的結(jié)果在圖 。最后在第 4步中，每個(gè)將軍都檢查新收到的向量中的第 i個(gè)元素。如果哪個(gè)值為多數(shù)，就把它放到結(jié)果向量中。如果沒有值為多數(shù)，那么結(jié)果向量中的對(duì)應(yīng)的元素就被標(biāo)記為unknown。從圖 ，我們看到將軍 2和 4都對(duì)正確結(jié)果 (1, 2, Unknown, 4) 達(dá)成了一致。叛徒不能破壞忠誠(chéng)的將軍的信息，因此他也不能破壞這個(gè)工作。 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 rec