標籤：

關於一致性協議的一些對比和總結

01-24

choices in consensus protocol

在我看來包含 log, state machine, consensus algorithm 這3個部分, 並且是有 electing, normal case, recovery 這3個階段都可以稱為paxos 協議一族.

為什麼說raft 也是3個階段, 因為其實raft 在重新選舉成leader 以後, 也是需要一段recovery 的時間, 如果超過半數的follower 沒有跟上leader 的日誌, 其實這個時候raft 寫入都是超時的, 只不過raft 把這個recovery 基本和normal case 合併在一起了, zab 不用說有一個synchronization 階段, multi-paxos 因為選舉的是任意一個節點作為leader, 那麼需要有一個對日誌重確認的階段

1. 選擇是primary-backup system 或者是 state machine system

對於具體primary-backup system 和 state machine system 的區別可以看這個文章 baotiao.github.io/2017/ , 在這裡primary-backup system 也叫做 passive replication, state machine system 也叫做 active replication

2. 是否支持亂序提交日誌和亂序apply 狀態機

其實這兩個亂系提交是兩個完全不一樣的概念.

是否支持亂序提交日誌是區分是raft 協議和不是raft 協議很重要的一個區別

在我看來multi-paxos 與raft 對比主要是能夠亂序提交日誌, 但是不能夠亂序apply 狀態機. 當然也有paxos 實現允許亂序apply 狀態機, 這個我們接下來說, 但是亂序提交日誌帶來的只是寫入性能的提升, 是無法帶來讀性能的提升的, 因為只要提交的日誌還沒有apply, 那麼接下來的讀取是需要等待前面的寫入apply 到狀態機才行. 並且由於允許亂序提交日誌, 帶來的問題是選舉leader 的時候, 無法選舉出擁有最多日誌的leader, 並且也無法確認當前這個term/epoch/ballot 的操作都提交了, 所以就需要做重確認的問題. 因此raft/zab/vsp 都是要求日誌連續, 因為新版本的zab 的FLE 演算法也是默認選舉的是擁有最長日誌的節點作為leader

支持亂序apply 日誌是能夠帶來讀取性能的提升, 這個也是Generalized Paxos 和 Egalitarian Paxos 所提出的做法. 但是這個就需要在應用層上層去做這個保證, 應用層需要確定兩次操作A, B 完全沒有重疊. 如果大量的操作都互相依賴的話, 這個優化也很難執行下來. 換個角度來考慮的話, 其實支持亂序 apply 日誌, 其實是和multi group 類似的一個做法, 都是在應用層已經確定某些操作是互相不影響的. 比如PhxPaxos 團隊就是用的是multi group 的做法, 所以有些宣傳raft 不適合在資料庫領域使用, 其實我覺得有點扯, 亂序提交日誌帶來的收益其實不高, 想要亂序apply 狀態機的話, multi group 基本是一樣的

3. 是否支持primary order

primary order, 也叫做FIFO client order, 這是一個非常好的功能, 也是zab 特別大的宣稱的一個功能. 但是這裡要主要這裡所謂的FIFO client order 指的是針對單個tcp 連接, 所以說如果一個client 因為重試建立了多個channel, 是無法保證FIFO order. 其實想做到client 級別的FIFO order 也是挺簡單, 就是需要給每一個client request 一個id, 然後在server 去等待這個id 遞增. 目前基於raft 實現的 Atomix 做了這個事情 atomix.io/copycat/docs/

具體討論: http://mail-archives.apache.org/mod_mbox/zookeeper-user/201711.mbox/%3cCAGbZs7g1Dt6QXZo1S0DLFrJ6X5SxvXXFR+j2OJeyksGBVyGe-Q@mail.gmail.com%3e

所以我認為 tcp + 順序apply 狀態機都能夠做到單個tcp連接級別的FIFO order, 但是如果需要支持 client 級別的FIFO order, 那麼就需要在client 上記錄一些東西.

4. 在選舉leader 的時候, 是否支持 designated 大多數. 選舉leader 的時候如何選舉出leader

designated 有什麼用呢? 比如在 VSR 的場景裡面, 我們可以指定某幾個節點必須apply 成功才可以返回. 現實中的場景比如3個城市5個機房, 那麼我們可以配置每個城市至少有一個機房在這個designated 裡面, 那麼就不會出現有一個城市完全沒有拷貝到數據的情況.

如何選舉出leader 這個跟是否支持亂序提交日誌有關, 像raft/zab/vsr 這樣的場景裡面, 只能讓擁有最長日誌的節點作為leader, 而paxos 可以在這裡增加一些策略, 比如讓成為leader 的節點有優先順序順序等等

5. 也是和選舉相關, 在選舉完成以後, 如何執行recovery 的過程. 以及這個rocovery 的過程是如何進行的, 是只同步日誌, 還是根據快照進行同步, 是單向同步, 還是雙向同步.

早期的zab 實現就是雙向同步, 任意選取一個節點作為新的leader, 那麼這個時候帶來的問題就是需要找到其他的follower 裡面擁有最長日誌的節點, 把他的日誌內容拉取過來, 然後再發送給其他的節點, 不過後來zab 也改成FLE(fast leader election), 也只需要單向同步日誌內容. raft/vsr 也都只需要單向的同步日誌了. paxos 因為允許亂序提交日誌, 因此需要和所有的節點進行重確認, 因此需要雙向的同步日誌.

這裡要注意的是 paxos 這種做法需要重新確認所有的他不確認是否有提交的日誌, 不只是包含他沒有, 還包含他有的也有可能沒有提交. 因此一般paxos 會保存一下當前已經提交到哪裡了, 然後成為新的leader 以後, 需要重新確認從當前的commitIndex 以後的所有的日誌. 這個成本還是很高的, 因此就是我們所說的重確認問題. 那麼這個重確認什麼時候到頭呢? 需要確認到所有的server 都沒有某一條日誌了才行

6. 讀取的時候的策略, 包括lease 讀取或者在任意一個replica 讀取, 那麼可能讀到舊數據. 然後通過版本號進行判斷是否讀取到的是最新數據.

lease 做法其實和協議無關, 任意一種的paxos 都可以通過lease 的優化讀取的性能, 當然lease 做法其實是違背分散式系統的基礎理論, 就是分散式系統是處於一個asynchronization network 裡面, 無法保證某一條消息是到達還是在網路中延遲

zookeeper 的實現裡面為了提高讀取的性能, 就允許client 直接去讀取follower 的內容, 但是這樣的讀取是可能讀取到舊數據, 所以有提供了一個sync 語義, 在sync 完之後的讀取一定能夠讀取到最新的內容, 其實sync 就是寫入操作, 寫入操作成功以後, 會返回一個最新的zxid, 那麼client 拿這個zxid 去一個follower 去讀取的時候, 如果發現follower 的zxid 比當前的client 要來的小, 那麼這個follower 就會主動去拉取數據

目前在raft phd thesis 裡面讀取的優化就包含了 lease 讀取和只需要通過Heartbeat 確認leader 信息進行讀取

如何儘可能減少leader 的壓力, 是一致性協議都在做的一個事情, 想zookeeper 這種通過上層應用去保證, 允許讀取舊數據也是一個方向, 當然還有的比如像Rotating leader, Fast Paxos 給client 發送當前的proposal number 的做法.

7. 在檢測leader 是否存活的時候是單向檢測還是雙向檢測

比如在raft 裡面的心跳只有leader 向follower 發送心跳, 存在這樣的場景. 如果有5個節點, 只有leader 節點被割裂了, 其實4個節點網路正常, 新的這4個節點選舉出一個leader, 舊的leader 由於完全與其他節點割裂, 所有的AppendEntry 都是失敗的, 不會收到一個新的Term號, 因此一直保持著自己是leader 的狀態. 那麼這樣系統就會同時存在兩個leader, 但是這個不影響協議正確性, 因為舊的leader 是無法寫入成功的.

在zab 裡面心跳是雙向的, 也就是說leader 向follower 發送心跳, 如果超過半數的follower 沒有應答, 那麼leader 會進入到electing 狀態. 同時follower 也會向leader 發送心跳, 如果leader 沒有回應, 那麼這個follower 節點同樣會進入到electing 狀態. 那麼對應於上述的場景, zab 就不會出現像raft 一樣, 長期同時存在兩個leader 的情況.

通過上述對比, 我還是覺得raft 實現更簡潔, 而雙向心跳檢測這種做法增加了大量的複雜度

最後的結論是這樣

對於計算密集型任務, 也就是寫入量比較大的場景, 建議選擇passive replication strategy, 那麼也就是選擇VSR 或者 ZAB 這樣.其實主要就是考慮到passive replication 只需要更新的是state 的修改, 而不是用於操作, 那麼就可以少做很多操作.

對於對性能比較敏感的場景, 那麼應該選擇active replication stategy, 那麼也就是選擇mulit-paxos, raft 這樣, 並且不需要designated majorities. 因為passive replication strategy 在rocovery 需要更多的時間, 因為client 的操作是需要寫入到狀態機, 如果這個client 的操作最後沒有被提交, 因為log 可以提供一個回滾操作, 而狀態機很少能夠提供這種回滾操作, 因此就需要將這個節點的狀態機的內容重寫, 所以會導致recovery 需要較長的時間.

其實可以看到這些一致性一些都是在一些細節的地方不一樣,我們完全也可以在這些細節的地方去選擇, 從而實現自己的一致性協議, 當然協議的正確性還是最好通過TLA+來驗證. 最後我們的raft 的協議實現: Qihoo360/floyd

Reference:

  1. tcs.hut.fi/Studies/T-79
  2. arxiv.org/pdf/1309.5671
  3. ramcloud.stanford.edu/r
  4. read.seas.harvard.edu/~
  5. research.microsoft.com/
  6. research.microsoft.com/
  7. baotiao.github.io/2017/

推薦閱讀：

※CockroachDB和TiDB中的Multi Raft Group是如何實現的?
※raft協議疑問？
※分散式一致性演算法是如何解決少數派節點的寫順序一致性問題的?
※網路遊戲如何保證數據一致性？

TAG:分布式一致性 | Paxos | 分布式系统 |