【正文】 圖 恢復(fù)線 84 獨(dú)立檢查點(diǎn) ? 不幸的是，每個(gè)進(jìn)程的檢查點(diǎn)是以一種不協(xié)調(diào)的方式來按時(shí)記錄它的本地狀態(tài)的，這種分布式本性使得找到一個(gè)恢復(fù)線很困難。要找到恢復(fù)線需要每個(gè)進(jìn)程都回退到它最近保存的狀態(tài)。如果這些本地狀態(tài)不能組成一個(gè)分布式快照，那么就需要進(jìn)一步的回退。下面要說明一種尋找恢復(fù)線的方法。這種折疊回退的過程可能會(huì)導(dǎo)致多米諾效應(yīng)。圖 。 85 獨(dú)立檢查點(diǎn) 圖 多米諾效應(yīng) 86 獨(dú)立檢查點(diǎn) ? 當(dāng)進(jìn)程 P2崩潰時(shí)，我們需要把它的狀態(tài)恢復(fù)到最近保存的檢查點(diǎn)。與此類似，進(jìn)程 P1也需要進(jìn)行回退。不幸的是，這兩個(gè)最近保存的本地狀態(tài)不能組成一個(gè)一致的全局狀態(tài)， P2保存的狀態(tài)表明了消息 m的接收，但是沒有其他進(jìn)程說明其為發(fā)送者。因此，P2需要回退到更早的狀態(tài)。 ? 但是， P2要回退到的下一個(gè)狀態(tài)不能用作分布式快照的一部分。在這種情況下， P1將記錄消息 m’ 的接收，但是沒有這一消息被發(fā)送的記錄事件，因此，有必要把 P1回退到以前的狀態(tài)。在這個(gè)例子中，恢復(fù)線就是系統(tǒng)的最初狀態(tài)。 87 獨(dú)立檢查點(diǎn) ? 由于進(jìn)程獨(dú)立地設(shè)臵本地檢查點(diǎn)，所以這種方法也被稱為獨(dú)立的檢查點(diǎn)方法。另一種可以選擇的方法是像我們下面要討論的那樣設(shè)臵全局協(xié)調(diào)的檢查點(diǎn)，但是協(xié)調(diào)需要全局同步，這可能會(huì)引起一些性能問題。獨(dú)立檢查點(diǎn)的另一個(gè)缺點(diǎn)是每個(gè)本地存儲(chǔ)都需要按時(shí)清理，例如通過運(yùn)行一個(gè)特定的分布式垃圾收集器來進(jìn)行清理。但是它主要的缺點(diǎn)還是恢復(fù)線的計(jì)算。 ? 實(shí)現(xiàn)獨(dú)立的檢查點(diǎn)需要記錄依賴關(guān)系，應(yīng)按照進(jìn)程可以共同回退到一個(gè)一致的全局狀態(tài)的方法來進(jìn)行記錄。用 CP[i](m)來表示進(jìn)程 Pi采用的第 m個(gè)檢查點(diǎn)，用 Int[i](m)來表示檢查點(diǎn) CP[i](m1)與 CP[i](m)之間的間隔。 88 獨(dú)立檢查點(diǎn) ? 當(dāng)進(jìn)程 Pi按 Int[i](m)的間隔發(fā)送消息時(shí)，它就在接收進(jìn)程中加入 (i, m)對(duì)。當(dāng)進(jìn)程 Pi按 Int[j](n)的間隔接收消息時(shí)，就使用 (i, m)是索引對(duì)，它記錄了Int[i](m)?Int[j](n)的依賴關(guān)系。然后，當(dāng) Pj采用檢查點(diǎn) CP[j](n)時(shí)，它就把這個(gè)依賴關(guān)系與恢復(fù)信息的其他部分一起寫入它的本地穩(wěn)定存儲(chǔ)中。 ? 現(xiàn)在假定進(jìn)程 Pi在某個(gè)時(shí)刻需要回退到檢查點(diǎn)CP[i](m1)。要確保全局一致性，我們需要確保所有從 Pi那里接收到了按間隔 Int[i](m)發(fā)送的消息的進(jìn)程都回退到在接收這個(gè)消息之前的檢查點(diǎn)狀態(tài)。特別是，在我們的例子中，進(jìn)程至少需要回退到檢查點(diǎn)CP[j](m1)。如果 CP[j](m1)導(dǎo)致了不一致的全局狀態(tài)，那么還需要進(jìn)行更多的回退。 89 獨(dú)立檢查點(diǎn) ? 計(jì)算恢復(fù)線需要對(duì)每個(gè)進(jìn)程設(shè)臵檢查點(diǎn)時(shí)記錄的時(shí)間間隔依賴關(guān)系進(jìn)行分析。我們不討論更多的細(xì)節(jié)，可以證明：這樣的計(jì)算是相當(dāng)復(fù)雜的，與協(xié)調(diào)檢查點(diǎn)相比，獨(dú)立檢查點(diǎn)對(duì)這些計(jì)算的需求也是不盡合理的。另外，它不是支配性能因素的進(jìn)程之間的協(xié)調(diào)。相反，需要把狀態(tài)保存到本地穩(wěn)定存儲(chǔ)中，它還造成一些額外開銷，因此，協(xié)調(diào)檢查點(diǎn)使用得更為普遍，它也比獨(dú)立檢查點(diǎn)更為簡(jiǎn)單。 90 協(xié)調(diào)檢查點(diǎn) ? 顧名思義，在協(xié)調(diào)檢查點(diǎn)中，所有的進(jìn)程都同步地把它們的狀態(tài)寫到本地穩(wěn)定存儲(chǔ)中。協(xié)調(diào)檢查點(diǎn)的主要優(yōu)點(diǎn)是所保存的狀態(tài)自動(dòng)保持全局一致，這樣就可以避免導(dǎo)致多米諾效應(yīng)的折疊回退。 ? 一種比較簡(jiǎn)單的方法是使用兩階段的阻塞協(xié)議。首先協(xié)調(diào)者向所有進(jìn)程多播一個(gè) Checkpoint_Request消息。當(dāng)進(jìn)程接收到這樣的消息時(shí)就設(shè)臵一個(gè)本地檢查點(diǎn)，通過它正在執(zhí)行的應(yīng)用程序?qū)㈦S后傳遞給它的消息進(jìn)行排隊(duì)，然后向協(xié)調(diào)者確認(rèn)它已經(jīng)設(shè)臵了檢查點(diǎn)。當(dāng)協(xié)調(diào)者接收到所有進(jìn)程的確認(rèn)時(shí)，它就多播一個(gè) Checkpoint_Done消息讓 (阻塞的 )進(jìn)程繼續(xù)執(zhí)行。 91 協(xié)調(diào)檢查點(diǎn) ? 很容易看出這個(gè)方法可以使全局狀態(tài)一致，因?yàn)闆]有即將近來的消息注冊(cè)為檢查點(diǎn)的一部分。其原因在于任何跟隨在設(shè)臵檢查點(diǎn)的請(qǐng)求之后的消息都不被認(rèn)為是本地檢查點(diǎn)的一部分。同時(shí)，在接收到Checkpoint_Done消息之前對(duì)即將發(fā)出的消息 (當(dāng)通過運(yùn)行的應(yīng)用程序傳遞給檢查點(diǎn)進(jìn)程的時(shí)候 )在本地進(jìn)行排隊(duì)。 92 協(xié)調(diào)檢查點(diǎn) ? 對(duì)這種算法的一種改進(jìn)是只對(duì)那些依賴協(xié)調(diào)者的恢復(fù)的進(jìn)程多播檢查點(diǎn)請(qǐng)求而忽略其他進(jìn)程。如果一個(gè)進(jìn)程在設(shè)臵了上個(gè)檢查點(diǎn)之后接收到了與協(xié)調(diào)者發(fā)送的消息直接或間接相關(guān)的消息，那么這個(gè)進(jìn)程就是依賴于協(xié)調(diào)者的。這稱為增量快照。 ? 要設(shè)臵一個(gè)增量快照，協(xié)調(diào)者只對(duì)那些在上次設(shè)臵檢查點(diǎn)之后對(duì)之發(fā)送了消息的進(jìn)程多播檢查點(diǎn)請(qǐng)求。當(dāng)進(jìn)程 P接收到這樣的請(qǐng)求時(shí)，它就把請(qǐng)求轉(zhuǎn)發(fā)給那些在上次檢查點(diǎn)之后 P本身向之發(fā)送了消息的所有進(jìn)程，等等。一個(gè)進(jìn)程只轉(zhuǎn)發(fā)一次請(qǐng)求。當(dāng)確認(rèn)所有的進(jìn)程之后，使用第二次多播來引發(fā)實(shí)際的檢查點(diǎn)，然后所有的進(jìn)程繼續(xù)執(zhí)行。 93 消息日志 ? 考慮到設(shè)臵檢查點(diǎn)是一個(gè)開銷很大的操作，特別是該操作涉及到向穩(wěn)定存儲(chǔ)中寫入狀態(tài)，需要尋找一種可以減少檢查點(diǎn)的數(shù)目但是還允許恢復(fù)的技術(shù)。在分布式系統(tǒng)中有一種重要的技術(shù)消息日志。 ? 消息日志的基本思想是：如果消息的傳播可以重放，那么我們就能夠到達(dá)一個(gè)全局一致的狀態(tài)而不需要從穩(wěn)定存儲(chǔ)中恢復(fù)該狀態(tài)。它使用一個(gè)檢查點(diǎn)狀態(tài)作為開始點(diǎn)，然后簡(jiǎn)單地把從該點(diǎn)以后發(fā)送的所有消息都重發(fā)并執(zhí)行處理。 94 消息日志 ? 假定采用分段確定模式 (piecewise deterministic model)，這種方法可以很好地工作。在這種模式中，假定每個(gè)進(jìn)程的執(zhí)行者都有一連串的間隔，事件是在這些間隔中發(fā)生的。這些事件與第 5章中討論過的 Lamport的先發(fā)生關(guān)系的事件相同。假如，一個(gè)事件可能是一條指令的執(zhí)行、一條消息的發(fā)送等。假定分段確定模式中的每個(gè)間隔都以一個(gè)非確定性的事件，加入一條消息的接收開始。但是，這個(gè)時(shí)刻之后進(jìn)程的執(zhí)行就是完全確定的。一個(gè)時(shí)間間隔以發(fā)生非確定性的事件之前的最后一個(gè)事件結(jié)束。 ? 實(shí)際上，如果以相同的非確定性事件作為開始進(jìn)行重放，那么一個(gè)間隔的重放可以具有已知的結(jié)果，也就是說，以一種完全確定的方式進(jìn)行重放。因此，如果我們?cè)谶@樣的模式中記錄下所有的非確定性事件，就有可能以一種確定的方式完全重放整個(gè)進(jìn)程的執(zhí)行。 95 消息日志 ? 考慮到要從進(jìn)程崩潰中恢復(fù)到一個(gè)全局一致的狀態(tài)時(shí)消息日志是必需的，準(zhǔn)確地知道什么時(shí)候?qū)ο⑦M(jìn)行記錄是很重要的。 Alvisi和 Marzullo(1998)介紹的方法說明，如果我們關(guān)注現(xiàn)存的消息日志方案如何處理孤兒進(jìn)程，那么可以容易地描述消息日志方案的特征。 ? 孤兒進(jìn)程就是在其他進(jìn)程崩潰之后還存在的進(jìn)程，但是它的狀態(tài)與恢復(fù)之后的崩潰進(jìn)程不一致。圖 個(gè)例子。進(jìn)程 Q從進(jìn)程 P與 R那里分別接收到消息 m1和 m2，然后把消息 m2發(fā)送給 R。但是，與其他消息不同，消息 m2沒有進(jìn)行日志記錄。如果進(jìn)程 Q崩潰然后恢復(fù)，那么要恢復(fù) Q只需要重放記錄了的消息，在我們的例子中就是 m1，因?yàn)閙2沒有進(jìn)行記錄，它的傳輸也就不會(huì)被重放，這意味著 m2的傳輸不會(huì)發(fā)生。 96 消息日志 圖 在恢復(fù)之后不正確的重放導(dǎo)致孤兒進(jìn)程 97 消息日志 ? 為了描述不同的消息日志方案的特征，我們使用文獻(xiàn) (Alvisi, Marzullo 1998)中說明的方法。認(rèn)為每個(gè)消息 m都具有頭部，頭部中包含了重發(fā) m并正確處理它所需的所有信息。例如，每個(gè)頭部都包含了發(fā)送者和接收者的標(biāo)識(shí)符以及一個(gè)用來識(shí)別它的序列號(hào)。另外還有一個(gè)傳送號(hào)碼用來確定它應(yīng)該在何時(shí)被傳送給接收應(yīng)用程序。 ? 如果消息不再被丟失就被稱為穩(wěn)定的，例如，因?yàn)樗粚懭肓朔€(wěn)定存儲(chǔ)。因此可以使用重放穩(wěn)定消息的傳輸來進(jìn)行恢復(fù)。 98 消息日志 ? 每個(gè)消息 m都導(dǎo)致產(chǎn)生一個(gè)進(jìn)程組 DEP (m)，它依賴于 m的傳送。特別是， DEP(m)由那些接收 m的進(jìn)程組成。另外，如果另一個(gè)消息 m’由于因果關(guān)系也要依賴 m的傳送，而且 m’被傳送給進(jìn)程 Q，那么 Q也包含在 DEP(m)中。注意 m’是按因果關(guān)系依賴于 m的傳送的，如果它由先前傳送 m的同一個(gè)進(jìn)程發(fā)送，或者它傳送了另一個(gè)按因果關(guān)系依賴于 m的傳送的消息。 ? COPY(m)進(jìn)程集由那些具有 m的拷貝，但是該拷貝不在它的本地穩(wěn)定存儲(chǔ)中的進(jìn)程組成。當(dāng)一個(gè)進(jìn)程傳送消息 m時(shí)，它就也成為 COPY(m)的成員。注意COPY(m)由那些可以移交 m的拷貝的進(jìn)程組成，這些拷貝可以用來重放 m的傳輸。如果所有這些進(jìn)程都崩潰了，那么重放 m的傳輸顯然就是不可能的。 99 消息日志 ? 使用這些表示，現(xiàn)在很容易就可以準(zhǔn)確定義孤兒進(jìn)程是什么了。假定一些進(jìn)程在分布式系統(tǒng)中崩潰了， Q是幸存的進(jìn)程之一。如果 Q包含在 DEP(m)中，在 COPY(m)中的每個(gè)進(jìn)程都崩潰了的同時(shí)存在消息 m，那么 Q就是一個(gè)孤兒進(jìn)程。即，如果一個(gè)依賴于 m，但是沒有辦法來重放 m的傳輸時(shí)它就是一個(gè)孤兒進(jìn)程。 ? 要避免產(chǎn)生孤兒進(jìn)程，需要確認(rèn)：如果 COPY(m)中的每個(gè)進(jìn)程都崩潰了，在 DEP(m)中沒有幸存的進(jìn)程。即， DEP(m)中的所有進(jìn)程都應(yīng)該已經(jīng)崩潰了。如果我們能夠保證不論何時(shí)一個(gè)進(jìn)程為了 DEP(m)的成員，它也要稱為 COPY(m)的成員，那么就可以滿足這個(gè)條件。即，不論何時(shí)一個(gè)進(jìn)程要依賴于m的傳送，那么它就總要保持 m的一份拷貝。 100 消息日志 ? 可以使用兩種方法來做到這一點(diǎn)。第一種方法稱為悲觀日志協(xié)議。這個(gè)協(xié)議認(rèn)為對(duì)于每個(gè)非穩(wěn)定的消息 m，都最多有一個(gè)進(jìn)程依賴它。換句話說，悲觀日志協(xié)議確保每個(gè)非穩(wěn)定的消息 m都最多被傳送給一個(gè)進(jìn)程。注意只要 m被傳送給進(jìn)程 P， P就稱為COPY(m)的成員。 ? 最壞的情況就是 P在 m還沒有被記錄的時(shí)候就崩潰了。使用悲觀日志，在傳送 m之后，如果還沒有確保 m被寫到穩(wěn)定存儲(chǔ)就不允許 P發(fā)送任何消息。因此，沒有其他進(jìn)程會(huì)依賴于 m的傳送，就沒有了重放 m的傳輸?shù)目赡苄浴＿@種方法可以避免孤兒進(jìn)程。 101 消息日志 ? 相反，在樂觀日志協(xié)議中，在發(fā)生崩潰之后才進(jìn)行實(shí)際的工作。特別是，假定對(duì)某個(gè)消息 m， COPY(m)中的每個(gè)進(jìn)程都崩潰了。在樂觀的方法中， DEP(m)中的任何孤兒進(jìn)程都被回退到一個(gè)不再屬于 DEP(m)的狀態(tài)。很明顯，樂觀日志協(xié)議需要跟蹤依賴關(guān)系，這使它們的實(shí)現(xiàn)變得更復(fù)雜。 ? 像在 (Einozahy等 1996)中指出的那樣，悲觀日志要比樂觀的方法簡(jiǎn)單得多，所以在實(shí)際的分布式設(shè)計(jì)中它是消息日志的首選方法。