前面談的多是「容忍」故障的演算法；然而失效一旦發生，發生失效的行程還必須能復原（recover）到正確狀態。本節先釐清「復原到正確狀態」是什麼意思，再討論何時、如何記錄分散式系統的狀態——也就是檢查點（checkpointing）與訊息日誌（message logging）。

導論#

容錯的根基是從錯誤中復原。回想：錯誤（error）是系統狀態中可能導致失效的部分；錯誤復原的整個想法，就是用無錯誤的狀態取代出錯的狀態。有兩種基本形式：

• 回溯復原（backward recovery）：把系統從當前的錯誤狀態帶回先前的正確狀態。這要求不時記錄系統狀態——每次記錄（部分）當前狀態，就稱做了一個檢查點（checkpoint）。
• 前向復原（forward recovery）：不回頭，而是設法把系統帶進一個正確的新狀態繼續執行。主要難題是必須事先知道可能發生哪些錯誤，才有辦法修正並前進。

兩者的差別用可靠通訊來說最清楚：遺失封包時讓傳送者重傳，等於回到「封包正要送出」的先前正確狀態——是回溯復原；抹除更正（erasure correction）則從其他成功送達的封包中重建遺失的封包——例如 (n, k) 區塊抹除碼把 k 個來源封包編碼成 n 個封包，任意 k 個編碼封包即可重建原始資料（典型值 k = 16 或 32，k < n ≤ 2k）——是前向復原。

回溯復原是分散式系統中應用最廣的通用復原機制，最大優點是與具體系統或行程無關，可以做成中介軟體層的通用服務。但它也有代價：

• 昂貴：把系統或行程還原到先前狀態，效能成本通常不低。一個可能的出路是設計極廉價的機制，直接把元件重開（見後文的復原導向計算）。
• 無法保證不再犯：復原機制獨立於應用，無法保證復原後同樣的失效不會再發生；若需要這種保證，往往得讓應用參與復原——換言之，回溯復原一般給不出完整的失效透明性。
• 有些狀態根本回不去：搶走故障 ATM 吐出來的一千元的人，不太可能把錢塞回去；在錯誤的工作目錄下熱情地敲了 rm -fr *，也沒有回頭路。有些事就是不可逆。

檢查點本身很昂貴，因此許多容錯分散式系統把檢查點與訊息日誌結合：做完檢查點後，行程在送出訊息前先記錄之（傳送端日誌，sender-based logging），或讓接收行程在遞送給應用前先記錄進來的訊息（接收端日誌，receiver-based logging）。接收行程當機時，還原最近的檢查點，再重放（replay）其後送過的訊息——不必頻繁做檢查點，也能還原到比最近檢查點更晚的狀態。

兩者還有一個重要差別：只用檢查點時，行程還原後的行為可能與失效前不同——通訊時間不確定，訊息可能以不同順序送達，引發接收者不同的反應。有訊息日誌則是把上次檢查點以來發生的事件實際重放一遍，這讓與外界互動容易得多。例如失效起因於使用者輸入錯誤：只靠檢查點，就得在接受輸入前先拍檢查點才能回到一模一樣的狀態；有訊息日誌，可以用較舊的檢查點重放到「該由使用者輸入」的那一刻。實務上「少量檢查點＋訊息日誌」比頻繁拍檢查點更有效率。

穩定儲存#

復原所需的資訊必須安全地保存——能挺過行程當機、站點失效，甚至各種儲存媒體故障。儲存分三級：一般 RAM（斷電或當機即消失）、磁碟（挺得過 CPU 失效，但磁頭損毀就沒了），以及穩定儲存（stable storage）——設計上除了水災、地震等重大災難外什麼都挺得住。

穩定儲存可用一對普通磁碟實作：磁碟 2 的每個區塊都是磁碟 1 對應區塊的精確複本。更新時先寫並驗證磁碟 1 的區塊，再寫磁碟 2 的同一區塊。

• 若系統在「磁碟 1 已更新、磁碟 2 未更新」時當機：復原時逐區塊比對，凡兩邊不同，以磁碟 1 為準（因為它永遠先被更新），把新區塊複製到磁碟 2，完成後兩碟又完全一致。
• 若區塊自然衰變（灰塵、磨損使原本有效的區塊突然出現總和檢查碼錯誤）：從另一顆磁碟的對應區塊重建即可。

由於這種實作方式，穩定儲存非常適合原子交易等要求高度容錯的應用：資料寫入穩定儲存並回讀驗證無誤後，之後遺失的機率極低。

檢查點#

回溯復原要求系統定期把狀態存入穩定儲存，特別是要能記錄一致的全域狀態，即分散式快照（distributed snapshot）：若行程 P 記錄了某訊息的接收，就必須也存在一個行程 Q 記錄了該訊息的發送——訊息總得有出處。

每個行程不時把自己的狀態存到本地的穩定儲存。行程或系統失效後，得從這些本地狀態拼出一致的全域狀態；最好是能還原到最近的分散式快照，稱為復原線（recovery line）——最近一組彼此一致的檢查點。

獨立檢查點#

若各行程只是各自不定時、不協調地記錄本地狀態（獨立檢查點，independent checkpointing），找出復原線可能很困難：把每個行程回捲（roll back）到最近的檢查點後，若這些本地狀態合起來不是分散式快照，就得繼續往回捲。這種串接回捲（cascaded rollback）可能引發骨牌效應（domino effect）。

延伸案例：骨牌效應如何一路捲回初始狀態

P2 當機後，先還原到它最近的檢查點，於是 P1 也得跟著回捲。不巧，兩者最近的本地狀態並不構成一致的全域狀態：P2 存下的狀態記錄了收到訊息 m，卻找不到任何行程記錄了 m 的發送，因此 P2 得再往前捲一格。但 P2 的上一個狀態同樣不能用——這回換成 P1 記錄了收到訊息 m′，卻沒有對應的發送紀錄，於是 P1 也得再往前捲。在這個例子裡，最後的復原線竟是系統的初始狀態。

實作獨立檢查點必須記錄相依關係，讓行程能共同回捲到一致的全域狀態。記 CPi(m) 為行程 Pi 的第 m 個檢查點，INTi(m) 為 CPi(m−1) 與 CPi(m) 之間的區間：

• Pi 在區間 INTi(m) 內送訊息時，附帶（piggyback）數對 (i, m) 給接收方。
• Pj 在區間 INTj(n) 內收到帶著 (i, m) 的訊息時，記下相依關係 INTi(m) → INTj(n)，並在拍檢查點 CPj(n) 時把它與其他復原資訊一併寫入本地穩定儲存。
• 若之後 Pi 必須回捲到 CPi(m−1)，則所有收過「Pi 在 INTi(m) 內所送訊息」的行程，都得回捲到收到那些訊息之前的檢查點狀態——本例中 Pj 至少得回捲到 CPj(n−1)；若仍不一致，就得繼續回捲。

計算復原線需要分析每個行程記錄的區間相依關係，相當複雜，並不足以正當化獨立檢查點相對於協調式檢查點的採用。而且事實證明，主導效能的往往不是行程間的協調，而是把狀態寫入本地穩定儲存的開銷。因此簡單得多的協調式檢查點更受歡迎，而且即使系統規模繼續成長，預期也會如此（Elnozahy 與 Planck）。獨立檢查點還有一個缺點：各地儲存得定期清理，例如跑一個特殊的分散式垃圾回收器。

協調式檢查點#

協調式檢查點（coordinated checkpointing）讓所有行程同步地一起把狀態寫入本地穩定儲存。最大優點：存下的狀態自動全域一致，從根本上避免骨牌效應。第六章的分散式快照演算法就可拿來協調檢查點，屬於非阻塞式協調。

更簡單的解法是兩階段阻塞協定：

• 協調者先向所有行程多播 CHECKPOINT_REQUEST。
• 行程收到後拍下本地檢查點，把應用其後交付的訊息全部排入佇列（暫不送出），並向協調者確認已完成檢查點。
• 協調者收齊所有確認後，多播 CHECKPOINT_DONE，讓（阻塞中的）行程繼續。

這樣做必然全域一致：任何跟在檢查點請求之後的進來訊息都不會被算進本地檢查點，而外送訊息會在本地排隊直到收到 CHECKPOINT_DONE。

改良版只把檢查點請求發給依賴協調者復原的行程——即自上次檢查點以來，收過與協調者所送訊息有直接或間接因果關聯訊息的行程——其餘行程不必參與，這就是增量快照（incremental snapshot）。做法：協調者只向上次檢查點後它送過訊息的行程多播請求；行程 P 收到請求後，再轉發給 P 自己在上次檢查點後送過訊息的所有行程，依此類推（每個行程只轉發一次）。等所有行程都被識別出來，再用第二次多播真正觸發檢查點並讓大家繼續。

訊息日誌#

檢查點昂貴（尤其是寫穩定儲存的部分），訊息日誌則是減少檢查點數量、又不犧牲可復原性的重要技術。基本想法：若訊息傳輸可以重放，就能不靠穩定儲存還原全域一致狀態——以某個檢查點為起點，把其後送過的訊息重傳、照常處理即可。

這套做法成立的前提是分段確定性模型（piecewise deterministic model）：每個行程的執行是一連串「區間」，每個區間以一個非確定性事件（如收到訊息）開始，自那之後行程的執行完全確定，區間結束於下一個非確定性事件之前的最後一個事件。只要從相同的非確定性事件出發，區間就能以已知結果、完全確定地重放；因此記下所有非確定性事件，就能確定性地重放行程的完整執行。

關鍵問題是訊息該在何時記錄。依 Alvisi 與 Marzullo 的方法，從「如何處理孤兒行程」切入，就能簡潔刻畫各種訊息日誌方案。

孤兒行程（orphan process）：挺過另一行程當機、但狀態與該行程復原後不一致的行程。

延伸案例：漏記一則訊息如何製造孤兒

行程 Q 先後收到來自 P 的 m1 與來自 R 的 m2，接著送出 m3 給 R；其中只有 m2 沒有被記錄。若 Q 當機後復原，只會重放已記錄且復原所需的訊息（即 m1）；m2 沒有日誌，其傳輸不會被重放，連帶 m3 的傳輸也可能不會發生。但在當機之前，R 實實在在收到了 m3——復原後的重放中，這則訊息的接收與遞送卻不存在。R 於是持有一則「與 Q 復原後的歷史對不上」的訊息，成為孤兒。這種不一致必須避免。

刻畫訊息日誌方案#

設每則訊息 m 帶有標頭，含重傳與正確處理 m 所需的所有資訊（傳送者、接收者、辨識重複用的序號，可能還有決定遞送時機的遞送編號）。若 m 不會再遺失（例如已寫入穩定儲存），稱 m 為穩定訊息——穩定訊息可用來重放。定義兩個集合：

• DEP(m)：依賴 m 遞送的行程集合——包含 m 已遞送到的行程；此外若另一訊息 m′ 因果依賴 m 的遞送、且 m′ 已遞送給行程 Q，則 Q 也屬於 DEP(m)。（m′ 因果依賴 m 的遞送，意指它由先前遞送過 m 的行程所送出，或由遞送過「因果依賴 m 之訊息」的行程所送出。）
• COPY(m)：持有 m 的複本、但尚未存入本地穩定儲存的行程集合。行程 Q 遞送 m 時即加入 COPY(m)。這些行程能交出可用於重放 m 傳輸的複本；若它們全數當機，重放 m 就無從談起。

精確定義：某些行程剛當機後，倖存的行程 Q 是孤兒行程，若且唯若存在訊息 m，使 Q ∈ DEP(m) 且 COPY(m) 中的行程全數當機——Q 依賴 m，卻再也無法重放 m 的傳輸。避免孤兒的充分條件是：行程一旦成為 DEP(m) 的成員，就必須同時成為 COPY(m) 的成員——依賴 m 的遞送，就得自己留一份 m。

由此得出兩大類協定：

• 悲觀日誌協定（pessimistic logging protocol）：確保每則非穩定訊息 m 至多遞送給一個行程。m 遞送給 P 後，P 即屬 COPY(m)；最壞情況是 P 在 m 尚未記錄時當機——但悲觀協定規定 P 在確保 m 已寫入穩定儲存之前，不得送出任何訊息。於是不會有其他行程在「無法重放 m」的情況下依賴 m 的遞送，孤兒永遠不會出現。
• 樂觀日誌協定（optimistic logging protocol）：把工作留到當機之後。若某訊息 m 的 COPY(m) 全數當機，就把 DEP(m) 中的孤兒行程回捲到不再屬於 DEP(m) 的狀態。顯然這需要追蹤相依關係，使實作複雜化。

如 Elnozahy 等人指出，悲觀日誌比樂觀方法簡單太多，是實務分散式系統設計中訊息日誌的首選。

復原導向計算#

另一條處理復原的路子是乾脆重來：與其追求長時間無失效，不如把成本花在「讓復原變便宜」——這稱為復原導向計算（recovery-oriented computing）（Candea 等人）。它有幾種風味：

• 重開機（rebooting）（部分系統），已在網際網路伺服器的重啟上被探索。要能只重開系統的一部分，故障必須被正確定位；屆時重開就是刪除已識別元件的所有實例與其上運作的執行緒，並且（通常）直接重啟相關的請求。注意故障定位本身可能就是件不簡單的事。要讓重開成為實用的復原技術，元件之間必須高度解耦——若相依很強，故障定位與分析可能仍得重啟整台伺服器，此時套用前述傳統復原技術也許更有效率。
• 在改變過的環境中繼續執行：套用檢查點與復原技術，但換個執行環境。基本想法是許多失效其實可以避免——給程式多一點緩衝空間、記憶體配置前先歸零、（在不影響語意的前提下）改變訊息遞送順序等等。這招針對的是軟體失效（前面多數技術針對或基於硬體失效）：軟體執行高度確定，換個執行環境或許就能救回一命——當然，什麼也沒真正修好。