標籤：

論文筆記：[USENIX ATC14] In Search of an Understandable Consensus Algorithm (Raft)

04-29

Raft 是一種分散式共識演算法，用於解決在非同步通信網路中存在節點失效且本地存儲可靠的情況下多個分散式節點達成一致的問題。在已經提出 Paxos 演算法用於解決這一問題的情況下繼續提出 Raft 演算法，主要是為了解決 Paxos 理解困難的問題。Paxos 演算法更偏向於理論研究，對於實現的很多細節雖然略有提及，但是並沒有進行深入的講解和討論，因此對於演算法的實現和優化而言還有很多困難。

個人認為 ，Raft 演算法本身，在理解上並不比 Paxos 具有更多優勢。就好像數學中的 非標準分析 之於 ??δ 極限表示法 下的 標準實分析 。雖然使用非標準分析表述微積分內部的概念比較易於理解，但是其保證其正確的基礎證明非常難以理解，而標準實分析中表述微積分內部的概念雖然有點繞，但是其基礎證明的難度卻沒有那麼高。對比而言，Paxos 的 safety 和 liveness 性質就很好理解，而 Raft 協議雖然給出了一些性質約束，但是由此能夠得出 linearizability consistency 的證明卻要難以理解的多 [3]。此外，這篇論文中還給出了在 Paxos Made Simple [2] 中沒有討論清楚的一些實現細節，因此對演算法的實現人員比較友好，但是相對而言，對其進行進一步優化的難度也要大得多。

基本思路

Single-decree Paxos 協議中，如果想要高效的推進演算法進度，也是需要選主的。但是 Paxos 論文中引入選主這一問題相當晚，直到最後一步沒有 lead 時候有可能不能推進演算法進行的時候，才提出可以引入主節點，通過總是讓主節點獲勝的方法來使得演算法進行下去。而在 Multi-decrees Paxos 的場景中，如果已經有了（唯一的）主節點，又可以對演算法進行相當程度的優化。Raft 協議就是針對這一點進行展開的，即先選出唯一的主節點，再由該主節點主導 log replication 過程。在此，Raft 協議還做了一個假設，即 client 的請求只由主節點進行處理。考慮到上述要求，Raft 協議的第一部分要求就是選主，對此有如下限制：

  1. 任意時刻最多只能有 1 個主節點
  2. client 的請求只由主節點進行處理
  3. 主節點從不修改自己的（狀態機指令）日誌，至對其進行 append 操作
  4. 主節點已經提交過的日誌，在換主後，必將出現在新主節點的日誌中

用論文中的說法就是這樣的：

  • Election Safety at most one leader can be elected in a given term. §5.2
  • Client interaction Clients of Raft send all of their requests to the leader. §8
  • Leader Append-Only a leader never overwrites or deletes entries in its log; it only appends new entries. §5.3
  • Leader Completeness if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms. §5.4 （此處 term 表示 leader 的任期）

其中 Leader Append-Only 和 Leader Completeness 這兩個性質約束了選主的時候，新的主節點必須擁有最新的 committed 的日誌。

在有了主節點之後，問題就簡單了。主節點只需將 client 的請求定序，並複製給其他節點即可。由此引申出如下性質：

  • Log Matching if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index. §5.3
  • State Machine Safety if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index. §5.4.3

直覺上應該沒什麼問題，主節點永遠擁有最新的狀態，所有的請求都發給主節點，主節點在 replica 到多數後回應請求結果。liveness 主要集中在選主上面，即是否能在這樣的約束條件下保證能夠選出主節點，本論文沒有證明這一結論。

實現細節

Raft 協議的核心在於選主。Raft 使用心跳機制用於檢測主節點的存活，從而觸發選主流程。每個節點有三種狀態：跟隨者（Follower），候選者（Candidate），領導者（Leader）。每個節點初始處於跟隨者的狀態。如果它認為領導者節點已經失效，則進行選主流程：

  1. 首先增加 term 順序號，然後將自己的狀態轉為一個候選者。
  2. 然後提議選舉自己成為領導者，並將這一請求廣播給其他節點
  3. 重複上述步驟，直到以下幾種情況發生：
    1. 贏得選舉
    2. 其他節點已經成為了領導者

當一個節點得到多數節點的認可時，可認為其贏得選舉。每個節點按照先到先得的原則同意其他節點的選舉請求（此處原因可參考 Paxos，即只有一個節點選舉時也會贏得選舉）。考慮到 Leader Append-Only 和 Leader Completeness 這兩個性質，在此過程中應該對選主過程做出合理限制，以免新任領導者節點沒有最新的 committed 的狀態，從而違背 State Machine Safety 性質。這一限制即，在選主請求中，攜帶當前自己已知的最新的 committed index。每個節點在應答其他節點的選主請求時，如果對方具有比自己當前最新 committed index 更低的值，就拒絕其選主請求。

Raft 選擇隨機等待重試的方法來盡量避免選舉平局的出現。根據 [4] 中的結論，在不依賴於真實物理時間的情況下（包括隨機量），只需有 1 個節點失效即有可能導致選主失敗，因此我們只能盡量避免這一情況，而不存在確定性的策略，沒有 corner case 的解決這一問題。儘管還有其他可能的策略來盡量避免這一局面的出現，但是 Raft 論文的作者認為隨機 back-off 的策略比較簡單而且不容易出現 corner case，個人認同這一觀點。

有了主節點（領導者）後，其他問題就好辦了。所有的客戶端請求都統一發給主節點，這些請求在主節點上被定序，然後順序的進行處理。主節點將接到的請求廣播給所有其他節點，一旦多數節點確認接收到這一請求，即可認為該請求已經 committed，至此主節點將這一操作應用到自身的狀態機上，並將結果返回給客戶端。

儘管主節點可能在沒有來得及將一個請求發送給多數節點時就掛掉了，此時會有兩種可能性

  1. 這一請求被下一任領導者繼續完成
  2. 這一請求被下一任領導者放棄，並使用其他內容覆蓋

儘管這兩種情況可能以任意順序交替發生，但是仍然可以保證當且僅當一個請求被擴散到多數節點後才被 committed，一旦 committed 就不會被重寫覆蓋。原論文 [1] 中沒有進行形式化證明，但是直覺上感覺是正確的，因為在選主的時候做出了合理的限制。論文 [3] 中含有正確性證明（不確定，沒看完）。

一般來說，一個狀態機系統的操作日誌不會是無限長的。因此在必要的時候，我們要對狀態機操作日誌進行壓縮（compact）。Raft 論文中使用狀態機快照（snapshot）來進行日誌壓縮，但是其他多種方案也可以達到這一目的，例如 LSM（Log-Structured Merge tree）。一個快照可以被看作是在此時之前的所有操作日誌順序執行的結果。在保留了一定數目的操作日誌後，更老的日誌子集就被狀態機快照所取代。快照的一個問題是，有可能某個節點落後主節點太多，以至於所需的操作日誌已經變成了快照而不可獲取單獨的操作日誌項。這既有可能是因為慢節點，也有可能是因為網路分區，還有可能是新添加的節點。對於此種情況，該節點只能獲取最新的快照，進行狀態機恢復，然後繼續獲取並應用在此之後的操作日誌。

成員變換

成員變換之所以成為一個問題，是因為由於成員組成不同，在切換的時刻，可能由這兩組不同的成員分別各自選出主節點，從而出現兩個主節點，違背了 Election Safety 性質。

Paxos 由於不要求一定有主節點，也不要求只有一個主節點，因此可以不用進行特殊處理，只是將成員列表作為狀態機的一個狀態即可。Paxos 論文 [2] 中設計每個提議者（proposer）最多只能緩衝 α 條來自客戶端的指令，因此只需將成員變更的命令放在將要提交的第 α+1 條指令處即可。在此成員變更指令生效前，新加入的節點只作為學習者（learner）的角色即可。此外也可以參考論文 [5] 中的方法。

Raft 處理這一問題採用重疊（overlapped）集群的方式，在成員變更的過程中，要求兩個重疊集群一致認可同一個主節點。需要注意的是，被移出集群的節點可能形成一個小的封閉系統自發選主，從而干擾正常集群。在此需要進行特殊處理，即當一個跟隨者（Follower）認為領導者存活時（通過心跳包），不再接受其他節點的選主請求。

與 Paxos 的簡單對比

Raft 應該算是 Paxos 的一個簡化特例版本，由於提供了更多的工程細節，省略了一些證明的過程，所以變得更容易理解和實現。但是如果需要進一步優化，則 Paxos 應該是一個更好的選擇。目前已知的兩個優化的點是：

  1. 無主節點的並行提交（Raft 的前提就是有且只有一個主節點，這上面完全優化不了）
  2. 狀態機指令的可交換性（例如 key-value store 場景下對兩個不同 key 的操作是可交換的，Raft 不存在並行提交，所以對此也無從優化）

References

[1] Diego Ongaro, and John Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. Atc 』14 22, 2 (2014), 305–320. DOI:doi.org/10.1145/1529974

[2] Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News 32, 4 (2001), 51–58. DOI:doi.org/10.1145/568425.

[3] Doug Woos, James R Wilcox, and Steve Anton, et al. 2016. Planning for change in a formal verification of the raft consensus protocol. In Proceedings of the 5th ACM SIGPLAN Conference on Certified Programs and Proofs - CPP 2016, 154–165. DOI:doi.org/10.1145/2854065

[4] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382. DOI:doi.org/10.1145/3149.21

[5] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. 2009. Vertical paxos and primary-backup replication. Proc. 28th ACM Symp. Princ. Distrib. Comput. - Pod. 』09 February (2009), 312. DOI:doi.org/10.1145/1582716


推薦閱讀：

※PacificA 一致性協議解讀
※從零開始開發一個單機存儲引擎
※分散式數據劃分的技術挑戰
※分散式系統設計:服務(多節點)模式
※用zookeeper來構建的一種一致性副本協議

TAG:分散式系統 | 分散式一致性 |