比較Paxos和Raft

- 前言
- - leader選舉
  - 日志同步
  - Commit Index推進
  - 崩潰恢複
  - 成員變更

前言

我一直在講學習paxos和raft最好的方式就是看作者的論文和視訊，隻有看原滋原味的文章，才能真正體會到作者的設計思路，才能在現代繁雜的工程實踐中抓住精髓。

這篇文章作為系列文章的最後一篇，我想談談paxos與raft的異同。算法在變，但是其中的核心思想是不變的。

一緻性協定raft詳解（一）：raft整體介紹
一緻性協定raft詳解（二）：安全性
一緻性協定raft詳解（三）：raft中的消息類型
一緻性協定raft詳解（四）：raft在工程實踐中的優化
一緻性協定Paxos詳解（一）：Basic Paxos協定詳解
一緻性協定Paxos詳解（二）：Multi-Paxos協定流程詳解
一緻性協定Paxos詳解（三）：Multi-Paxos的優化

paxos共識協定是後面所有一緻性協定的基礎，據說Google Chubby的作者Mike Burrows說過：這個世界上隻有一種一緻性算法，那就是Paxos，其它的算法都是殘次品。raft協定在paxos協定的基礎上，抽象出了一個共識協定需要做的以下幾個事情：

Leader選舉（Leader Election）
日志同步（Log Replication）
Commit Index推進（Advance Commit Index）
崩潰恢複（Crash Recovery）
成員變更（Membership Change）

當然每個共識協定不需要都實作這裡面每個方面，但其設計思路上一定是考慮過這些問題，然後根據實際需求做出取舍的。下面我們一個個來說，順便比較paxos/raft的異同。我們這裡講的paxos主要是multi-paxos with leader這種工程上比較常見的版本。basic paxos這種隻對單個決議作出共識的算法和raft可比性不大。

leader選舉

既然Multi-Paxos支援多個proposer，為什麼很多分布式協定仍需要leader？我覺得這是出于對簡化一緻性協定。降低log replication的複雜度的角度考慮的。有了leader之後，日志的送出隻可以由leader發起。簡化了acceptor的處理流程。另外一個好處是，單leader對事務比較友好。各種隔離級别實作起來也比較友善。

當然，引入leader必然要在一緻性協定中引入leader選舉過程，一個叢集怎樣保證隻有一個leader？切主的時候叢集的可用性如何？一緻性如何保證？都是設計者需要考慮的問題。

multi-paxos理論上任何成員都可以成為leader，但是leader當選時要補齊自己本地缺失的日志，還要将自己已經chosen的日志在叢集内進行廣播，這個過程可以叫做日志的“重确認”
raft由于增加了對日志的順序性保證，并且leader隻允許commit目前term的日志，是以raft叢集的leader選舉遵循最大送出原則: During elections, choose candidate with log most likely to contain all committed entries。隻有包含最全日志的節點才可能被選為leader。

日志同步

log replication是一緻性協定的核心。paxos和raft最大的差別也在這裡

multi-paxos允許日志亂序送出，也就是說允許日志中存在空洞。
raft協定增加了日志順序性的保證，每個節點隻能順序的commit日志。順序性日志簡化了一緻性協定複雜程度，當然在性能上也有了更多的限制，為此，工程上又有了很多對應的優化，如：batch、pipline、leader stickness等等。有關pipline的優化可以看這篇文章
另外再多說一句，亂序不亂序的問題其實還是上層業務決定、展現到RSM中的。如果兩條日志有關聯性，就算用paxos協定，業務還是要想辦法保證這種順序。如果使用raft希望亂序送出，大可使用多個raft組。

還有一個隐含的差別：raft/paxos如何對待讀請求？處理讀請求的關鍵是，leader怎樣才能知道某條log已經在整個叢集内達成共識了（paxos叫chosen，raft叫commit）

multi-paxos的leader維護了每一條LogEntry是否被chosen的資訊。但是對未chosen的LogEntry，leader必須重新走paxos流程，才能知道它是否已經被chosen了（“薛定谔的提案”），當然，leader可以在當選時對這些LogEntry執行propose，迅速掌握這些日志的狀态。
raft協定有順序性保證，leader通過在後續送出的過程中對其他節點間接送出，可以将叢集的狀态迅速補齊。但是leader剛當選的時候，它是不清楚自己的日志是否真的commit了。這時我們可以通過引入no-op，讓新當選的leader迅速擷取系統的CommitIndex，友善提供讀服務。

當日志過多之後，需要對已經确認送出的日志做快照（snapshot），将日志壓縮、持久化。後續新上線的節點也可以通過讀取快照的方式迅速追齊日志。

Commit Index推進

一條寫請求到達paxos/raft叢集之後，到底存放在哪裡，這是CommitIndex想要解決的問題

raft得益于其順序日志的設計，CommitIndex的推進比較簡潔。leader不會持久化CommitIndex，而是在當選後與follower互動的過程中擷取。leader隻能推進commit index來送出目前term的已經複制到大多數伺服器上的日志，舊term日志的送出要等到送出目前term的日志來間接送出
Multi-Paxos由于可以亂序送出，index的推進稍顯麻煩。leader在收到client的寫日志請求後，首先要找到空閑的可以送出日志的entry。最簡單的方法是可以LogIndex從低到高嘗試應用paxos去propose，找到一個沒有任何value的LogEntry，去放置新的LogEntry。

崩潰恢複

raft比較巧妙的一點是，通過對日志的順序性保證，将crash recovery做到了log replication裡面。也就是之前提到的：leader隻能推進commit index來送出目前term的已經複制到大多數伺服器上的日志，舊term日志的送出要等到送出目前term的日志來間接送出。leader在這個過程中會覆寫于follower不一緻的LogEntry。
Multi-Paxos的崩潰恢複要複雜的多：
1. 新當選的leader要完整的對所有日志走一遍prepare流程。進而：
  1. Block old proposals：這裡我們需要将ProposalId的影響範圍擴充到整個log上，而不隻是某個LogEntry。通過這樣做，隻要目前leader發送了proposal，自然就可排除掉之前的proposal
  2. Find out about (possibly) chosen values：不同的acceptor上可能會有不同的 acceptedProposal ，是以，acceptor需要回複 [highestProposalIdForCurrentEntry, noMoreAccepted] ，通過這種方式，辨識每一個acceptor到底有哪些LogEntry，以及其狀态是什麼。通過這種方式，leader可以将已經chosen的LogEntry在整個叢集中對齊
2. 對于之前term的日志，leader對自己已經chosen但是其他節點未chosen的LogEntry，對該節點發送 Success RPC 。leader通過這種方式告訴acceptor，某個LogEntry已經被Chosen了。
3. 注意，通過success這種方式，隻能将chosen的LogEntry在整個叢集中對齊，推動整個叢集的Log index。但是對于未被chosen的之前的LogEntry，處理的不好會導緻所謂的幽靈複現的問題，最簡單地解決方式：Leader直接把之前未送出LogEntry全部送出，這也是raft使用的方法。

成員變更

成員變更的論證在這裡不再詳述，raft和paxos以及所有的工程實作都明白：成員變更需要特殊對待，以防在變更過程中叢集同時出現兩個多數派。

很多的工程實作将成員變更作為一條日志，apply進叢集節點的RSM。并且為了簡單，很多工程每次隻允許一個節點變更，上一次變更成功之後才允許下一個變更。

比較Paxos和Raft