在對 Raft 算法的領導者選舉、日志復制和安全性機制有了基本了解后，本文將深入探討 Raft 論文的后半部分。我們將重點分析 Section 7 至文末的內容，涵蓋日志壓縮、客戶端交互、算法的實現與評估，以及與其他相關工作的比較。這些內容對于理解 Raft 在實際系統中的應用和優勢至關重要。

Section 7: 日志壓縮 (Log Compaction)

Raft 的日志在正常運行期間會持續增長，以包含更多的客戶端請求。然而，在實際系統中，日志不能無限增長，否則會占用過多存儲空間，并且在節點重啟時需要更長的回放時間，這最終可能導致可用性問題。因此，必須有一種機制來丟棄日志中累積的過時信息。

為何需要日志壓縮

隨著系統的長時間運行，日志會變得非常龐大，遠超狀態機當前的狀態所占空間。如果服務器重啟，回放整個日志會非常耗時。此外，向新加入的服務器或落后較多的服務器發送整個日志也是不切實際的。

快照機制 (Snapshotting)

最簡單的壓縮方法是 快照 (snapshotting)。其基本思想是，系統的整個當前狀態被寫入一個持久化的快照文件，然后該時間點之前的所有日志條目都可以被丟棄。

每個服務器獨立地創建快照，僅覆蓋其日志中已提交的條目。主要工作包括狀態機將其當前狀態寫入快照。例如，對于一個鍵值存儲服務，快照將包含當前的鍵值表。Raft 在快照中也包含少量元數據：

• lastIncludedIndex: 快照所取代的日志中的最后一個條目的索引（即狀態機已應用的最后一個條目）。
• lastIncludedTerm: lastIncludedIndex 條目所屬的任期號。 這兩個元數據用于支持快照之后第一個日志條目的 AppendEntries 一致性檢查。
• 最新配置: 為了支持集群成員變更（Section 6），快照還會包含截至 lastIncludedIndex 時日志中的最新配置信息。

一旦服務器完成了快照的寫入，它可以刪除 lastIncludedIndex 及其之前的所有日志條目，以及任何更早的快照。

InstallSnapshot RPC

雖然服務器通常獨立創建快照，但領導者偶爾需要向落后太多的追隨者發送快照。當領導者已經丟棄了需要發送給某個追隨者的下一個日志條目時，就會發生這種情況。此時，領導者會使用一個名為 InstallSnapshot 的新 RPC 將快照發送給該追隨者。

InstallSnapshot RPC 的參數包括領導者的任期、leaderId、快照的 lastIncludedIndex 和 lastIncludedTerm、快照數據塊的偏移量 (offset) 以及數據本身，還有一個 done 標記指示是否為最后一個數據塊?？煺湛赡軙环指畛啥鄠€塊（chunks）進行傳輸，offset 字段指明了當前數據塊在完整快照中的位置。

當追隨者接收到 InstallSnapshot RPC 時：

1. 如果 RPC 中的任期 term < currentTerm，則立即回復。
2. 如果是第一個數據塊 (offset 為 0)，則創建新的快照文件。
3. 在指定偏移量處寫入數據。
4. 如果 done 為 false，則回復并等待更多數據塊。
5. 如果 done 為 true，則保存快照文件，丟棄任何具有較小索引的現有或部分快照。
6. 檢查其現有日志。如果其日志中存在與快照的 lastIncludedIndex 和 lastIncludedTerm 相同的條目，則保留該條目之后的所有日志條目并回復。這意味著快照描述了其日志的一個前綴，該前綴所包含的操作效果已在快照中，可以安全丟棄。這種情況可能因為網絡消息亂序送達導致，例如領導者先發送了索引為 100 的快照，再發送索引為 110 的快照，但網絡先投遞了后者。
7. 否則（通常情況，快照包含新信息），丟棄整個日志。
8. 使用快照內容重置狀態機（并加載快照的集群配置）。

追隨者必須拒絕過時的快照，例如，如果它已經擁有一個比接收到的快照更新的快照。InstallSnapshot 的實現必須是原子的，領導者重發快照是無害的。

這種快照方法偏離了 Raft 的強領導者原則，因為追隨者可以在領導者不知情的情況下創建快照。但這被認為是合理的，因為在快照創建時，相關的日志條目已經達成共識，不會產生決策沖突。數據流仍然是從領導者到追隨者。

快照的性能考量

1. 何時創建快照 ：過于頻繁會浪費磁盤帶寬和能源；過于不頻繁則有耗盡存儲的風險，并增加重啟時的日志回放時間。一個簡單的策略是當日志達到固定大小時進行快照。如果快照的大小遠小于日志大小，那么快照帶來的磁盤帶寬開銷會比較小。但如果快照和日志大小相當（例如，每次更新都插入唯一的鍵），快照的價值可能不大，除非快照以更易于訪問的方式組織數據（如排序表），從而加速重啟。
2. 寫入快照的耗時 ：寫入快照可能耗時較長，不應阻塞正常操作。解決方案是使用 寫時復制 (copy-on-write, COW) 技術。例如，基于函數式數據結構的狀態機天然支持此功能?；蛘?，操作系統的 COW 支持（如 Linux 上的 fork()）可用于創建整個狀態機的內存快照。fork() 通常不會立即復制所有內存，而是將頁面標記為“寫時復制”，并在父進程或子進程嘗試寫入頁面時才實際復制該頁面。
3. 網絡帶寬 ：如果狀態非常大（如數據庫），InstallSnapshot RPC 會產生高昂的帶寬成本。領導者應保留足夠的日志以覆蓋追隨者滯后或臨時離線的常見情況，從而減少發送快照的頻率。也可以考慮只傳輸狀態差異。
4. 數據壓縮 ：快照的壓縮方案取決于服務存儲的數據類型。例如，圖像可以使用 JPEG 壓縮。如果快照間共享大量內容，可以使用樹狀結構共享節點。

Section 8: 客戶端交互 (Client Interaction)

本節描述客戶端如何與 Raft 交互，包括客戶端如何找到集群領導者以及 Raft 如何支持 線性化語義 (linearizable semantics)。

尋找 Leader 與請求路由

Raft 的客戶端將所有請求發送給領導者。當客戶端首次啟動時，它會連接到一個隨機選擇的服務器。如果該服務器不是領導者，它將拒絕客戶端的請求，并提供它所知道的最近領導者的信息（AppendEntries 請求包含領導者的網絡地址）。如果領導者崩潰，客戶端請求將超時；客戶端隨后會重試其他隨機選擇的服務器。

實現線性化語義

Raft 的目標是實現線性化語義，即每個操作都表現為在調用和響應之間的某個點瞬時發生，且僅發生一次。然而，如果領導者在提交日志條目后但在響應客戶端之前崩潰，客戶端會向新的領導者重試該命令，導致命令被執行兩次。

解決方案是讓客戶端為每個命令分配唯一的序列號。然后，狀態機跟蹤每個客戶端已處理的最新序列號以及相關的響應。如果收到一個序列號已被執行的命令，狀態機將立即使用先前保存的響應進行回復，而不會重新執行該請求。

為了維護這個客戶端序列號和響應的表（通常稱為 會話表 或 重復請求檢測表 ）：

• 當新的領導者產生時，由于所有副本都會在執行命令時更新它們的這個表，因此新領導者自然擁有了該信息。
• 如果服務器崩潰并重啟，通過日志回放可以重建這個表。如果使用了快照，快照必須包含這個表的副本。

即使這個表返回的是一個“舊”的值（例如，在兩次 Get 請求之間有一個 Put），只要它符合線性化順序（例如，舊的 Get 操作在時間上可以被視為在 Put 之前完成），這也是正確的。

只讀操作的優化

只讀操作（如 Get(key)）理論上可以不寫入任何日志就進行處理。然而，若無額外措施，這會有返回陳舊數據的風險。因為響應請求的領導者可能已經被它不知道的新領導者取代，而新領導者可能已經處理了對該鍵的 Put 操作，導致舊領導者的數據過時。返回陳舊數據違反了線性化語義。

Raft 需要兩個額外的預防措施來保證只讀操作的線性化，而不必將它們寫入日志：

1. 領導者必須擁有關于哪些條目已提交的最新信息 ： 領導者完整性 (Leader Completeness) 屬性保證領導者擁有所有已提交的條目，但在其任期開始時，它可能不知道哪些條目是（在其看來）已提交的。為了解決這個問題，每個領導者在其任期開始時，會向日志提交一個空的 無操作 (no-op) 條目。一旦這個 no-op 條目被提交，領導者就能知道其之前的所有條目也都提交了。這個 no-op 操作僅在領導者任期開始時發生一次，而不是針對每個只讀請求。這是為了解決圖 8 中描述的情況：一個舊的日志條目可能已復制到多數服務器，但仍可能被未來的領導者覆蓋，除非當前領導者提交了其當前任期的一個條目（例如 no-op）。
2. 領導者在處理只讀請求前必須檢查自己是否已被罷黜 ：它的信息可能因為一個更新的領導者已被選舉出來而變得陳舊。Raft 通過讓領導者在響應只讀請求前，與集群中的多數派交換一次心跳消息（例如，發送空的 AppendEntries RPCs 并等待回復）來處理此問題。這可以確認它仍然是領導者。

另一種方法是，領導者可以依賴心跳機制來提供一種形式的 租約 (lease)。在獲得 AppendEntries 的多數確認后，領導者被授權在一個租約期內響應只讀請求，而無需將這些只讀請求提交到日志。新的領導者在執行寫入操作前，必須等待前一個領導者的租約到期。然而，這種方法依賴于時鐘同步來保證安全性（例如，它假設有界的時鐘偏斜）。在教學實驗中，通常要求將 Get() 操作提交到日志中，而不實現租約機制。

Section 9: 實現與評估 (Implementation and Evaluation)

Raft 算法已經在 RAMCloud 項目中作為復制狀態機的一部分被實現，用于存儲配置信息和協助協調器故障轉移。該 C++ 實現大約有 2000 行代碼（不包括測試、注釋或空行）。此外，還有許多第三方的開源實現。

可理解性 (Understandability)

為了衡量 Raft 相對于 Paxos 的可理解性，研究者們進行了一項用戶研究。結果顯示，學生們在 Raft 上的表現明顯優于 Paxos 。大多數參與者認為 Raft 更容易實現和解釋。Raft 的設計側重于分解問題（如領導者選舉、日志復制、安全性）和減少狀態空間，這使得算法更易于理解。

正確性 (Correctness)

Raft 的核心共識機制（Section 5）已經被形式化規約并證明了其安全性。使用 TLA+ 語言編寫的正式規約約 400 行，并基于此規約，使用 TLA 證明系統機械證明了 日志完整性 (Log Completeness) 屬性。此外，還編寫了一份完整的關于 狀態機安全性 (State Machine Safety) 屬性的非正式證明。

性能 (Performance)

Raft 的性能與其他共識算法（如 Paxos）相當。在最重要的場景——已建立的領導者復制新的日志條目時，Raft 使用最少數量的消息（從領導者到集群半數成員的一次往返）。

領導者選舉過程通過隨機化的選舉超時能夠快速收斂。實驗表明，即使是很小范圍的隨機化（例如，150-155ms 的選舉超時對比固定的 150ms）也能顯著減少分裂投票，從而加快選舉。通過降低選舉超時可以減少領導者崩潰后的停機時間，但過低的超時（例如低于廣播時間一個數量級）會導致不必要的領導者變更，降低系統整體可用性。論文推薦使用保守的選舉超時，如 150-300ms 。

Section 10: 相關工作 (Related Work)

Raft 與許多現有的共識算法和系統有相似之處，但也存在關鍵區別。

• 與 Paxos 的比較 ：Raft 與 Paxos 最顯著的區別在于其 強領導者 (strong leader) 模型。Raft 將領導者選舉作為共識協議的核心部分，并將盡可能多的功能集中在領導者身上。這使得算法更簡單、更易于理解。相比之下，Paxos 中的領導者選舉是正交的，僅作為性能優化，導致了額外的機制（兩階段協議 + 獨立選舉機制）。Raft 將領導者選舉整合為共識的第一階段，機制更少。此外，Paxos 的原始描述側重于單決策 Paxos，擴展到多決策 (multi-Paxos) 缺乏統一的、詳盡的描述，給實踐帶來了困難。
• 與 Viewstamped Replication (VR) 和 ZooKeeper (Zab) 的比較 ：VR 和 ZooKeeper 也是基于領導者的方法，因此共享 Raft 相對于 Paxos 的許多優點。然而，Raft 通過最小化非領導者節點的功能，使得其機制比 VR 或 ZooKeeper 更少。例如，Raft 中的日志條目僅單向從領導者流向追隨者；而在 VR 中，日志條目可以在選舉期間流向領導者，增加了復雜性。Raft 的消息類型也相對較少。
• 性能優化與其他方法 ：一些無領導者的方法，如 Egalitarian Paxos (EPaxos)，在特定條件下（如利用狀態機命令的交換律且并發沖突少時）可以獲得比 Raft 更高的性能和更好的負載均衡，尤其是在廣域網環境中。但 EPaxos 顯著增加了 Paxos 的復雜性。
• 成員變更機制 ：Raft 的 聯合共識 (joint consensus) 成員變更機制利用了共識協議的其余部分，所需額外機制很少。與 VR 和 SMART 等機制相比，Raft 的配置變更可以在不限制正常請求處理的情況下進行，而 VR 在配置變更期間會停止所有正常處理。

Raft 通過其獨特的設計，在可理解性和實踐性之間取得了良好的平衡，并對后續的復制狀態機研究和實現產生了積極影響。

Section 11: 總結 (Conclusion)

算法設計通常以正確性、效率和簡潔性為主要目標。然而，論文作者認為 可理解性 (understandability) 同等重要。開發者需要深刻理解算法才能將其可靠地實現并擴展。

Raft 作為 Paxos 的一個更易于理解的替代方案被提出。它不僅被證明比 Paxos 更易學習，同時也為構建實際系統提供了更好的基礎。將可理解性作為首要設計目標，改變了 Raft 的設計方法，使得設計者能夠反復運用如問題分解和狀態空間簡化等技術。這些技術不僅提升了 Raft 的可理解性，也使其正確性更易于得到保證。

通過對 Raft 論文后半部分的深入分析，我們可以看到 Raft 不僅僅是一個理論上的共識算法，更是一個充分考慮了實際系統需求和開發者體驗的完整方案。其在日志壓縮、客戶端交互、成員變更等方面的設計，都體現了對簡潔性和可理解性的追求，同時保證了系統的正確性和高效性。