分散式系統理論進階 - Raft、Zab

引言

《分散式系統理論進階 - Paxos》介紹了一致性協議Paxos，今天我們來學習另外兩個常見的一致性協議——Raft和Zab。通過與Paxos對比，了解Raft和Zab的核心思想、加深對一致性協議的認識。

Raft

Paxos偏向於理論、對如何應用到工程實踐提及較少。理解的難度加上現實的骨感，在生產環境中基於Paxos實現一個正確的分散式系統非常難[1]：

There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol.

Raft[2][3]在2013年提出，提出的時間雖然不長，但已經有很多系統基於Raft實現。相比Paxos，Raft的買點就是更利於理解、更易於實行。

為達到更容易理解和實行的目的，Raft將問題分解和具體化：Leader統一處理變更操作請求，一致性協議的作用具化為保證節點間操作日誌副本(log replication)一致，以term作為邏輯時鐘(logical clock)保證時序，節點運行相同狀態機(state machine)[4]得到一致結果。Raft協議具體過程如下：

1. Client發起請求，每一條請求包含操作指令
2. 請求交由Leader處理，Leader將操作指令(entry)追加(append)至操作日誌，緊接著對Follower發起AppendEntries請求、嘗試讓操作日誌副本在Follower落地
3. 如果Follower多數派(quorum)同意AppendEntries請求，Leader進行commit操作、把指令交由狀態機處理
4. 狀態機處理完成後將結果返回給Client

指令通過log index(指令id)和term number保證時序，正常情況下Leader、Follower狀態機按相同順序執行指令，得出相同結果、狀態一致。

宕機、網路分化等情況可引起Leader重新選舉(每次選舉產生新Leader的同時，產生新的term)、Leader/Follower間狀態不一致。Raft中Leader為自己和所有Follower各維護一個nextIndex值，其表示Leader緊接下來要處理的指令id以及將要發給Follower的指令id，LnextIndex不等於FnextIndex時代表Leader操作日誌和Follower操作日誌存在不一致，這時將從Follower操作日誌中最初不一致的地方開始，由Leader操作日誌覆蓋Follower，直到LnextIndex、FnextIndex相等。

Paxos中Leader的存在是為了提升決議效率，Leader的有無和數目並不影響決議一致性，Raft要求具備唯一Leader，並把一致性問題具體化為保持日誌副本的一致性，以此實現相較Paxos而言更容易理解、更容易實現的目標。

Zab

Zab[5][6]的全稱是Zookeeper atomic broadcast protocol，是Zookeeper內部用到的一致性協議。相比Paxos，Zab最大的特點是保證強一致性(strong consistency，或叫線性一致性linearizable consistency)。

和Raft一樣，Zab要求唯一Leader參與決議，Zab可以分解成discovery、sync、broadcast三個階段：

• discovery: 選舉產生PL(prospective leader)，PL收集Follower epoch(cepoch)，根據Follower的反饋PL產生newepoch(每次選舉產生新Leader的同時產生新epoch，類似Raft的term)
• sync: PL補齊相比Follower多數派缺失的狀態、之後各Follower再補齊相比PL缺失的狀態，PL和Follower完成狀態同步後PL變為正式Leader(established leader)
• broadcast: Leader處理Client的寫操作，並將狀態變更廣播至Follower，Follower多數派通過之後Leader發起將狀態變更落地(deliver/commit)

Leader和Follower之間通過心跳判別健康狀態，正常情況下Zab處在broadcast階段，出現Leader宕機、網路隔離等異常情況時Zab重新回到discovery階段。

了解完Zab的基本原理，我們再來看Zab怎樣保證強一致性，Zab通過約束事務先後順序達到強一致性，先廣播的事務先commit、FIFO，Zab稱之為primary order(以下簡稱PO)。實現PO的核心是zxid。

Zab中每個事務對應一個zxid，它由兩部分組成：<e, c>，e即Leader選舉時生成的epoch，c表示當次epoch內事務的編號、依次遞增。假設有兩個事務的zxid分別是z、z，當滿足 z.e < z.e 或者 z.e = z.e && z.c < z.c 時，定義z先於z發生(z < z)。

為實現PO，Zab對Follower、Leader有以下約束：

1. 有事務z和z，如果Leader先廣播z，則Follower需保證先commit z對應的事務
2. 有事務z和z，z由Leader p廣播，z由Leader q廣播，Leader p先於Leader q，則Follower需保證先commit z對應的事務
3. 有事務z和z，z由Leader p廣播，z由Leader q廣播，Leader p先於Leader q，如果Follower已經commit z，則q需保證已commit z才能廣播z

第1、2點保證事務FIFO，第3點保證Leader上具備所有已commit的事務。

相比Paxos，Zab約束了事務順序、適用於有強一致性需求的場景。

Paxos、Raft、Zab再比較

除Paxos、Raft和Zab外，Viewstamped Replication(簡稱VR)[7][8]也是討論比較多的一致性協議。這些協議包含很多共同的內容(Leader、quorum、state machine等)，因而我們不禁要問：Paxos、Raft、Zab和VR等分散式一致性協議區別到底在哪，還是根本就是一回事？[9]

Paxos、Raft、Zab和VR都是解決一致性問題的協議，Paxos協議原文傾向於理論，Raft、Zab、VR傾向於實踐，一致性保證程度等的不同也導致這些協議間存在差異。下圖幫助我們理解這些協議的相似點和區別[10]：

相比Raft、Zab、VR，Paxos更純粹、更接近一致性問題本源，儘管Paxos傾向理論，但不代表Paxos不能應用於工程。基於Paxos的工程實踐，須考慮具體需求場景(如一致性要達到什麼程度)，再在Paxos原始語意上進行包裝。

小結

以上介紹分散式一致性協議Raft、Zab的核心思想，分析Raft、Zab與Paxos的異同。實現分散式系統時，先從具體需求和場景考慮，Raft、Zab、VR、Paxos等協議沒有絕對地好與不好，只是適不適合。

[1] Paxos made live - An engineering perspective, Tushar Chandra, Robert Griesemer and Joshua Redstone, 2007

[2] In Search of an Understandable Consensus Algorithm, Diego Ongaro and John Ousterhout, 2013

[3] In Search of an Understandable Consensus Algorithm (Extended Version), Diego Ongaro and John Ousterhout, 2013

[4] Implementing Fault-Tolerant Services Using the State Machine, Fred B. Schneider, 1990

[5] Zab:High-performance broadcast for primary-backup systems, FlavioP.Junqueira,BenjaminC.Reed,andMarcoSera?ni, 2011

[6] ZooKeepers atomic broadcast protocol: Theory and practice, Andr′e Medeiros, 2012

[7] Viewstamped Replication A New Primary Copy Method to Support Highly-Available Distributed Systems, Brian M.Oki and Barbar H.Liskov, 1988

[8] Viewstamped Replication Revisited, Barbara Liskov and James Cowling, Barbara Liskov and James Cowling ,2012

[9] Can』t we all just agree? The morning paper, 2015

[10] Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab, Robbert van Renesse, Nicolas Schiper and Fred B. Schneider, 2014