【正文】 elivery 61 虛擬同步 ?現(xiàn)在假定 m在發(fā)送者具有組視圖 G時(shí)進(jìn)行多播?，F(xiàn)在有兩個(gè)多播消息在同時(shí)進(jìn)行傳輸：m和 vc。作為選擇， m可以被每個(gè)成員忽略，這對(duì)應(yīng)于在發(fā)送 m之前發(fā)送者崩潰的情況。 63 虛擬同步 ?考慮圖 4個(gè)進(jìn)程。但是，虛擬同步保證這個(gè)消息根本不會(huì)被傳送，這就有效地建立起一種情況，使得在 P3崩潰之前消息從來(lái)沒(méi)有被發(fā)送。即 ， 視圖改變作為一個(gè)屏障 ， 不能跨越它進(jìn)行多播 。在簡(jiǎn)單的方案中，協(xié)調(diào)者通知所有涉及到的稱為參與者的其他進(jìn)程是否 (本地 )按要求執(zhí)行操作。 ?在實(shí)踐中需要更復(fù)雜的方法，最常用的是兩階段提交協(xié)議，但它的缺點(diǎn)是不能有效地處理協(xié)調(diào)者失敗的情況。在可靠多播的情況下，操作就是消息的傳遞。假定沒(méi)有故障發(fā)生，協(xié)議就由以下兩個(gè)階段組成，每個(gè)階段又由兩步組成。如果所有的參與者都表決要提交事務(wù)，那么協(xié)調(diào)者就進(jìn)行提交。如果參與者接收到一個(gè) Global_Commit消息，那么它就在本地提交事務(wù)，否則接收到一個(gè) Global_Abort消息時(shí)，就在本地取消事務(wù)。盡管 3PC在文章中廣泛出現(xiàn)，但是它在實(shí)際中用得并不多，因?yàn)樵?2PC中阻塞的情況很少發(fā)生。 ? 沒(méi)有一個(gè)這樣的狀態(tài)：它不能做出最后決定，而且可以從它直接轉(zhuǎn)換到 Commit狀態(tài)。因此存活進(jìn)程總是可以做出的最后決定。從本質(zhì)上說(shuō)，有兩種形式的錯(cuò)誤恢復(fù)。 ? 另一種是前向恢復(fù) (forward recovery)。 77 恢復(fù) ? 考慮一下可靠通信的實(shí)現(xiàn)，很容易解釋前向錯(cuò)誤恢復(fù)與回退錯(cuò)誤恢復(fù)之間的區(qū)別。 ? 還有一種可供選擇的方式是使用一種稱為擦除修正 (erasure correction)的方法。如果沒(méi)有足夠的分組被傳送，發(fā)送者就不得不繼續(xù)發(fā)送分組直到先前丟失的分組可以被重建為止。換句話說(shuō)，它可以作為一項(xiàng)通用的服務(wù)集成到分布式系統(tǒng)的中間層中。 79 恢復(fù) ? 第二，因?yàn)榛赝隋e(cuò)誤恢復(fù)機(jī)制不依賴于實(shí)際使用的分布式應(yīng)用程序，不能保證一旦進(jìn)行了恢復(fù)就不再發(fā)生相同或類似的失敗。例如，如果一個(gè)人從柜員機(jī)取走了 1000美元時(shí)，那么即使自動(dòng)柜員機(jī)立即回退這些錢也很難追回。在這種情況下，在沒(méi)有設(shè)臵檢查點(diǎn)后，一個(gè)進(jìn)程在發(fā)送消息之前對(duì)它進(jìn)行記錄 (稱為基于發(fā)送者的日志 )。把檢查點(diǎn)與消息日志相結(jié)合使得有可能恢復(fù)到最近檢查點(diǎn)的狀態(tài)而無(wú)需付出設(shè)臵檢查點(diǎn)的代價(jià)。但是，如果使用了消息日志，那么就會(huì)發(fā)生從上次檢查點(diǎn)之后事件的真實(shí)重放。著重強(qiáng)調(diào)了記錄一致全局狀態(tài)的必要性，稱為分布式快照。要在進(jìn)程或系統(tǒng)失敗之后進(jìn)行恢復(fù)，就需要我們從這些局部狀態(tài)中建立一致的全局狀態(tài)。要找到恢復(fù)線需要每個(gè)進(jìn)程都回退到它最近保存的狀態(tài)。圖 。因此，P2需要回退到更早的狀態(tài)。 87 獨(dú)立檢查點(diǎn) ? 由于進(jìn)程獨(dú)立地設(shè)臵本地檢查點(diǎn)，所以這種方法也被稱為獨(dú)立的檢查點(diǎn)方法。 ? 實(shí)現(xiàn)獨(dú)立的檢查點(diǎn)需要記錄依賴關(guān)系，應(yīng)按照進(jìn)程可以共同回退到一個(gè)一致的全局狀態(tài)的方法來(lái)進(jìn)行記錄。然后，當(dāng) Pj采用檢查點(diǎn) CP[j](n)時(shí)，它就把這個(gè)依賴關(guān)系與恢復(fù)信息的其他部分一起寫入它的本地穩(wěn)定存儲(chǔ)中。如果 CP[j](m1)導(dǎo)致了不一致的全局狀態(tài)，那么還需要進(jìn)行更多的回退。相反，需要把狀態(tài)保存到本地穩(wěn)定存儲(chǔ)中，它還造成一些額外開(kāi)銷，因此，協(xié)調(diào)檢查點(diǎn)使用得更為普遍，它也比獨(dú)立檢查點(diǎn)更為簡(jiǎn)單。首先協(xié)調(diào)者向所有進(jìn)程多播一個(gè) Checkpoint_Request消息。其原因在于任何跟隨在設(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è)檢查點(diǎn)狀態(tài)作為開(kāi)始點(diǎn)，然后簡(jiǎn)單地把從該點(diǎn)以后發(fā)送的所有消息都重發(fā)并執(zhí)行處理。假如，一個(gè)事件可能是一條指令的執(zhí)行、一條消息的發(fā)送等。 ? 實(shí)際上，如果以相同的非確定性事件作為開(kāi)始進(jìn)行重放，那么一個(gè)間隔的重放可以具有已知的結(jié)果，也就是說(shuō)，以一種完全確定的方式進(jìn)行重放。 ? 孤兒進(jìn)程就是在其他進(jìn)程崩潰之后還存在的進(jìn)程，但是它的狀態(tài)與恢復(fù)之后的崩潰進(jìn)程不一致。如果進(jìn)程 Q崩潰然后恢復(fù)，那么要恢復(fù) Q只需要重放記錄了的消息，在我們的例子中就是 m1，因?yàn)閙2沒(méi)有進(jìn)行記錄，它的傳輸也就不會(huì)被重放，這意味著 m2的傳輸不會(huì)發(fā)生。另外還有一個(gè)傳送號(hào)碼用來(lái)確定它應(yīng)該在何時(shí)被傳送給接收應(yīng)用程序。特別是， DEP(m)由那些接收 m的進(jìn)程組成。當(dāng)一個(gè)進(jìn)程傳送消息 m時(shí)，它就也成為 COPY(m)的成員。假定一些進(jìn)程在分布式系統(tǒng)中崩潰了， Q是幸存的進(jìn)程之一。即， DEP(m)中的所有進(jìn)程都應(yīng)該已經(jīng)崩潰了。第一種方法稱為悲觀日志協(xié)議。 ? 最壞的情況就是 P在 m還沒(méi)有被記錄的時(shí)候就崩潰了。 101 消息日志 ? 相反，在樂(lè)觀日志協(xié)議中，在發(fā)生崩潰之后才進(jìn)行實(shí)際的工作。 ? 像在 (Einozahy等 1996)中指出的那樣，悲觀日志要比樂(lè)觀的方法簡(jiǎn)單得多，所以在實(shí)際的分布式設(shè)計(jì)中它是消息日志的首選方法。在樂(lè)觀的方法中， DEP(m)中的任何孤兒進(jìn)程都被回退到一個(gè)不再屬于 DEP(m)的狀態(tài)。因此，沒(méi)有其他進(jìn)程會(huì)依賴于 m的傳送，就沒(méi)有了重放 m的傳輸?shù)目赡苄浴Q句話說(shuō)，悲觀日志協(xié)議確保每個(gè)非穩(wěn)定的消息 m都最多被傳送給一個(gè)進(jìn)程。即，不論何時(shí)一個(gè)進(jìn)程要依賴于m的傳送，那么它就總要保持 m的一份拷貝。即，如果一個(gè)依賴于 m，但是沒(méi)有辦法來(lái)重放 m的傳輸時(shí)它就是一個(gè)孤兒進(jìn)程。如果所有這些進(jìn)程都崩潰了，那么重放 m的傳輸顯然就是不可能的。注意 m’是按因果關(guān)系依賴于 m的傳送的，如果它由先前傳送 m的同一個(gè)進(jìn)程發(fā)送，或者它傳送了另一個(gè)按因果關(guān)系依賴于 m的傳送的消息。因此可以使用重放穩(wěn)定消息的傳輸來(lái)進(jìn)行恢復(fù)。認(rèn)為每個(gè)消息 m都具有頭部，頭部中包含了重發(fā) m并正確處理它所需的所有信息。進(jìn)程 Q從進(jìn)程 P與 R那里分別接收到消息 m1和 m2，然后把消息 m2發(fā)送給 R。 95 消息日志 ? 考慮到要從進(jìn)程崩潰中恢復(fù)到一個(gè)全局一致的狀態(tài)時(shí)消息日志是必需的，準(zhǔn)確地知道什么時(shí)候?qū)ο⑦M(jìn)行記錄是很重要的。但是，這個(gè)時(shí)刻之后進(jìn)程的執(zhí)行就是完全確定的。在這種模式中，假定每個(gè)進(jìn)程的執(zhí)行者都有一連串的間隔，事件是在這些間隔中發(fā)生的。在分布式系統(tǒng)中有一種重要的技術(shù)消息日志。當(dāng)進(jìn)程 P接收到這樣的請(qǐng)求時(shí)，它就把請(qǐng)求轉(zhuǎn)發(fā)給那些在上次檢查點(diǎn)之后 P本身向之發(fā)送了消息的所有進(jìn)程，等等。 92 協(xié)調(diào)檢查點(diǎn) ? 對(duì)這種算法的一種改進(jìn)是只對(duì)那些依賴協(xié)調(diào)者的恢復(fù)的進(jìn)程多播檢查點(diǎn)請(qǐng)求而忽略其他進(jìn)程。當(dāng)協(xié)調(diào)者接收到所有進(jìn)程的確認(rèn)時(shí)，它就多播一個(gè) Checkpoint_Done消息讓 (阻塞的 )進(jìn)程繼續(xù)執(zhí)行。協(xié)調(diào)檢查點(diǎn)的主要優(yōu)點(diǎn)是所保存的狀態(tài)自動(dòng)保持全局一致，這樣就可以避免導(dǎo)致多米諾效應(yīng)的折疊回退。我們不討論更多的細(xì)節(jié)，可以證明：這樣的計(jì)算是相當(dāng)復(fù)雜的，與協(xié)調(diào)檢查點(diǎn)相比，獨(dú)立檢查點(diǎn)對(duì)這些計(jì)算的需求也是不盡合理的。要確保全局一致性，我們需要確保所有從 Pi那里接收到了按間隔 Int[i](m)發(fā)送的消息的進(jìn)程都回退到在接收這個(gè)消息之前的檢查點(diǎn)狀態(tài)。 88 獨(dú)立檢查點(diǎn) ? 當(dāng)進(jìn)程 Pi按 Int[i](m)的間隔發(fā)送消息時(shí)，它就在接收進(jìn)程中加入 (i, m)對(duì)。獨(dú)立檢查點(diǎn)的另一個(gè)缺點(diǎn)是每個(gè)本地存儲(chǔ)都需要按時(shí)清理，例如通過(guò)運(yùn)行一個(gè)特定的分布式垃圾收集器來(lái)進(jìn)行清理。在這種情況下， P1將記錄消息 m’ 的接收，但是沒(méi)有這一消息被發(fā)送的記錄事件，因此，有必要把 P1回退到以前的狀態(tài)。與此類似，進(jìn)程 P1也需要進(jìn)行回退。下面要說(shuō)明一種尋找恢復(fù)線的方法。即，恢復(fù)線就對(duì)應(yīng)于最近的一致性切面，圖 。畢竟消息必須是來(lái)自某個(gè)地方的。 82 檢查點(diǎn) ? 在容錯(cuò)的分布式系統(tǒng)中，回退錯(cuò)誤恢復(fù)需要系統(tǒng)把它的狀態(tài)有規(guī)律地保存到穩(wěn)定存儲(chǔ)中。在只使用檢查點(diǎn)的系統(tǒng)中，進(jìn)程將被恢復(fù)到設(shè)臵檢查點(diǎn)時(shí)的狀態(tài)，它們的行為將與發(fā)生故障之前不同。這種方法也稱為接收者的日志。但是，設(shè)臵檢查點(diǎn)通常是一個(gè)開(kāi)銷很大的操作，可能引起嚴(yán)重的性能問(wèn)題。即，回退錯(cuò)誤恢復(fù)機(jī)制通常不能提供完全的故障透明性。首先，把一個(gè)系統(tǒng)或進(jìn)程恢復(fù)到原先的狀態(tài)通常是一個(gè)相對(duì)開(kāi)銷較大的操作。 78 恢復(fù) ? 一般來(lái)說(shuō)，回退錯(cuò)誤恢復(fù)技術(shù)作為一種從分布式系統(tǒng)故障中恢復(fù)的機(jī)制被廣泛應(yīng)用。例如，在一個(gè) (n, k)塊的擦除碼中，一組 k個(gè)源分組被編碼為一組 n個(gè)已編碼的分組，這樣任意 k個(gè)已編碼的分組都可以重建出原來(lái)的 k個(gè)源分組。實(shí)際上，分組重發(fā)就是嘗試著回退到以前的正確狀態(tài)，也就是發(fā)送丟失的分組時(shí)的狀態(tài)。前向錯(cuò)誤恢復(fù)機(jī)制的關(guān)鍵在于它必須預(yù)先知道會(huì)發(fā)生什么錯(cuò)誤。要做到這一點(diǎn)，必須定時(shí)記錄系統(tǒng)的狀態(tài)，以便當(dāng)發(fā)生錯(cuò)誤時(shí)恢復(fù)到記錄的狀態(tài)。錯(cuò)誤是系統(tǒng)中可能導(dǎo)致失敗的部分。在這種情況下，其余的可能操作進(jìn)程不能做出最后的決定，不得不在崩潰的進(jìn)程恢復(fù)之前阻塞。它們各自的狀態(tài)機(jī)如圖 。因此參與者可能在協(xié)調(diào)者恢復(fù)之前保持阻塞。但是，如果有一個(gè)參與者表決要取消事務(wù)，那么協(xié)調(diào)者就決定取消事務(wù)并多播一個(gè) Global_Abort消息。 2. 當(dāng)參與者接收到 Vote_Request消息時(shí)，就向協(xié)調(diào)者返回一個(gè)Vote_Commit消息通知協(xié)調(diào)者它已經(jīng)準(zhǔn)備好本地提交事務(wù)中屬于它的部分，否則就返回一個(gè) Vote_Abort消息。 69 兩階段提交 ? 兩階段提交協(xié)議 (2PC)是由 Gray(1978)提出的。 68 分布式提交 ?前面討論的原子多播問(wèn)題是一個(gè)稱為分布式提交的更一般化問(wèn)題中一個(gè)例子。如果有一個(gè)參與者不能真正執(zhí)行該操作，那么就說(shuō)明它存在著明顯的缺陷，因?yàn)樗鼪](méi)有辦法來(lái)通知協(xié)調(diào)者。 在視圖改變時(shí)進(jìn)行的所有多播都在視圖改變生效之前完成 。后來(lái) P3恢復(fù)了，它可以在它的狀態(tài)進(jìn)行更新之后再次加入該組。在多播了一些消息之后，進(jìn)程 P3崩潰了。如果消息的發(fā)送者在多播期間崩潰，那么消息或者被投遞給所有剩余的進(jìn)程或者被每個(gè)進(jìn)程忽略。 62 虛擬同步 ?這里出現(xiàn)了一個(gè)問(wèn)題，如果 m沒(méi)有被傳送到任何一個(gè)進(jìn)程，怎么能說(shuō)這種協(xié)議是可靠的多播協(xié)議呢 ?原則上，只有一種情況下 m的傳送允許失?。寒?dāng)組成員關(guān)系的改變是由于 m的發(fā)送者崩潰造成的結(jié)果時(shí)。組成員關(guān)系的這個(gè)改變被宣告給 G中的所有進(jìn)程。很重要的一點(diǎn)是列表中的每個(gè)進(jìn)程都具有相同的視圖。消息在這個(gè)通信層中進(jìn)行發(fā)送和接收。當(dāng)一個(gè)副本從故障中恢復(fù)并重復(fù)加入組時(shí)，原子多播強(qiáng)制它與組的其他成員一致。 ?當(dāng)崩潰的副本恢復(fù)時(shí)，它就被強(qiáng)迫再次加入該組。 58 原子多播 ?現(xiàn)在假定底層的分布式系統(tǒng)支持原子多播。但是另一方面，在其他的副本上的更新被正確執(zhí)行了。因此，復(fù)制的