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