深入淺出共識演算法–Consensus algorithms

摘要： 我們將從分散式儲存系統面臨的一致性問題開始進行討論，進而比較詳細地分析Raft和ZAB兩種近年來最受關注的演算法。 因為希望儘量涵蓋演算法的內容，所以文章很長，建議備好啤酒飲料 雖然已經很長，還是不夠涵蓋Paxos的內容 2333 軟體系統面臨很多問題 硬體異常：硬...

我們將從分散式儲存系統面臨的一致性問題開始進行討論，進而比較詳細地分析Raft和ZAB兩種近年來最受關注的演算法。

因為希望儘量涵蓋演算法的內容，所以文章很長，建議備好啤酒飲料

雖然已經很長，還是不夠涵蓋Paxos的內容 2333

軟體系統面臨很多問題

• 硬體異常：硬碟錯誤，RAM錯誤，電源錯誤，網路錯誤。隨著資料中心擴大，接入的硬體越來越多，硬體出現問題的可能性也越來越大 （1W件99.9999%可用的裝置，組合在一起可用性會變為99%，如果是10W件，可用性只剩下90%）
• 軟體異常：即使經過長期實踐檢驗，程式碼review非常嚴謹的軟體，也難以擺脫bug。更糟糕的是，很多bug是難以通過測試發現的，就像硬體錯誤一樣
• 人為因素：運維人員的失誤。人比起軟硬體系統，更加不可靠。即使一個非常專業，也非常專注的運維工程師，也可能誤操作，防止一個因失戀而心不在焉的工程師犯錯就更加困難了

分散式系統的情況就 更加糟糕

網路的本質是節點之間互相傳送訊息（光/電訊號），其物理本質是非同步，單向且無反饋的。即使有TCP/IP協議，仍然要面對許多問題

• 訊息可能丟失
• 訊息可能被緩衝起來，增加了很多延遲
• 目標節點不可用（可能down機，也可能由於某些原因暫時不能響應，如正在GC）
• 訊息可能被正常接收並處理，但是響應訊息不能傳達
• 響應訊息可能被延遲

傳送方甚至無法確定目標節點是不是完全不可用：

上圖列舉了(a), (b), (c)三種情況，client完全不能區分接收不到響應的原因

Replication and high availability

分散式系統通常通過replication，partition來提高availability和scalability。兩者經常會結合使用

Replication通過將同樣的資料複製在不同節點，來達成：

1. 使系統可以在部分節點異常的情況下繼續工作（high availability）
2. 將資料複製到距離使用者更近的資料中心以提高訪問速度（low latency）
3. 擁有更多節點來直接對使用者提供服務（scalability）

Partition通過將資料分組儲存，來滿足scalability

這篇文章我們只討論high availability和replication，也就是consensus演算法發揮作用的地方

quorum

quorum經常被用在replicated系統中，協助保證high availability

原理很簡單，如果有n個replica，每個寫操作必須被w個replica確認才算完成，則讀操作必須讀取r個replica：則只要 w + r > n， 就能保證讀操作可以讀到最新的值，這個限制就構成了一個讀寫操作的quorum

更簡單做法是要求w和r都 > n/2，這也是quorum經常被mojarity替代的原因

Consistency guarantees (Consistency models)

Eventual consistency

if no new updates are made to a given data item, eventually all accesses to that item will return the last updated value

解釋一下這句話：如果某個資料項沒有被更新，最終對該資料項的所有訪問將返回它最後一次被更新的值

這是一個非常弱的guarantee。甚至你在同一程序裡，對一個值進行寫操作後立即讀取它都可能讀到寫操作之前值（read your own write）。雖然Eventual consistency被很多系統用作廣告（因為大家意識裡它和高可用，快聯絡在一起），但實際上大部分宣稱eventual consistent的系統都會提供更強一些的guarantee（至少是以可選的方式提供）

Linearizability

與之相反的，我們來看一看軟體系統能提供的最強的guarantee，linearizability，也叫做atomic consistency, strong consistency, immediate consistency, external consistency

Linearizability並不是理論上最強的，更強的是Strict Consistency，但是Strict Consistency，至少在現代工程和物理的範疇內無法實現

用易理解的方式描述一下，linearizability要求系統表現的像只有一份資料replica，並且所有對資料的操作都是原子的。這樣，在一次寫操作執行完畢前，任何讀操作都讀不到新的值，而在寫操作執行完成後，任何讀操作都會讀到新的值，直到另一次寫操作完成

做比說難，下面的圖說明了一個常用的主從結構，非同步複製的replicas cluster下，client可能讀取到延遲的資料（常見的mysql，redis叢集都採用類似的機制），這樣的叢集都不滿足linearizability

上面的系統中，replica中的資料被用作讀快取，偶爾讀到延遲的資料完全可以接收。但是，應用系統需要Linearizable的系統來協助解決問題，例如：

鎖：把CAS操作看作獲取鎖（compare-and-swap。獲取鎖需要執行兩個步驟，檢查鎖是否可以獲取，然後更新鎖的持有者，這種操作經常通過CAS只使用一個原子操作完成)，鎖需要一個嚴格的linearizable的實現

leader election：利用分散式鎖實現leader election是一個常見的用法（例如kafka通過zk實現partition的leader election）

constraints：其中最廣為使用的應當是uniqueness constraint，當併發的請求到來時，系統需要linearizable的儲存才能判斷哪一個請求能成功

解決race condition：我們在圖3裡展示了一類race condition，顯然lineariable的系統可以避免這種情況

在分散式系統中實現Linearizable

單一系統實現linearizable並不複雜，因為作業系統提供了對記憶體/檔案系統的原子操作

consistency models（strict consistency, sequential consistency, week consistency）本來是描述多程序作業系統的（多程序，共享CPU，記憶體，硬碟等資源），分散式系統面臨同樣的問題，所以使用了同樣的術語

分散式系統可能有如下模型：

• 單一leader：可能是linearizable的
• multiple leaders：非linearizable，多主節點不可避免的會引入衝突，因而會表露出不止有一份資料的行為
• leaderless：多半不是，因為採取leaderless的考量通常是為了能更靈活的平衡效能和一致性
• consensus algorithms：後面我們將討論如何基於consensus來實現linearizable

COST of Linearizability

• 如果你的系統要求linearizability，一旦某些replica與其它replica斷開，這些斷開的replica就不能再處理請求，它們只能等待網路得以恢復，或者返回錯誤。不論採取哪種方案，它們都不再可用
• 如果你的系統不需要linearizability，單個replica就可以獨立的處理請求，這樣哪怕它斷開與其它replica的連線，也可以保持可用，但是整個系統的行為就不可能保持linearizable

這就是著名的CAP理論。不要求linearizability的系統可以提供更高的可用性和低於linearizable，但是高於eventual consistent的一致性。

注意，另一方面，CAP中availability的定義也非常嚴格，從系統中脫出的replica也要能獨立處理請求。通常的資料系統不需要這樣的可用性，從而可以考慮在降低一些可用性（例如在多數節點正常的情況下，這些節點可以工作）的情況提供linearizability

比可用性更重要的影響是 效能

Linearizable的系統會犧牲很多效能，甚至多核處理器訪問RAM都不是linearizable的（由於cache）

現代的資料系統通常會細緻分析不同等級的Consistency model，使用低於linearizability的模型來優化效能

Consensus algorithms

分散式系統通過replication保證高可用性，但是我們看到要保證linearizable，多個replica需要保持同步。Consensus algorithm的作用就是讓系統的多個節點達成一致。也就是說，通過consensus algorithm，我們可以提供一致，高可用的分散式儲存（注意，高可用的定義與CAP不同，一致也不限於linearizability）

最經典的consensus algorithm就是2PC（2-phase-commit）和3PC

我們不細緻討論2PC和3PC，只列舉一下它們的問題

2PC是blocking protocol，需要等所有參與者完成。這意味著必須等待最慢的參與者，效率非常低下。同時，依賴broker來協調，broker成為single point of failure

3PC對2PC做了一些改進，但仍然有問題。比如，在一些特例情況下，consensus不能保證

Paxos是正確性得以證明的最著名的consensus algorithm。Paxos不僅經過嚴謹證明和超過20年的研究，還以其複雜性和難以理解著稱。考慮到篇幅的關係，本文不準備對Paxos做很多介紹

本文後續將以Raft和ZAB為例項，對consensus進行分析介紹

RAFT

Raft是當今最受關注的consensus algorithm，它最重要的特點是易於理解和實現（對飆Paxos） Raft採用leader-follower機制，通過replicated log在節點之間同步資料

Leader負責維護replicated log，接收client的請求，並將log複製到其它節點。Leader可能異常（出錯或斷開），在此情況下將選舉出新leader

這樣的機制大大簡化系統設計，因為leader且只有leader能修改log，寫操作就可以變成簡單的在log末尾加入新行（Write Ahead Log）。資料同步的方向也變為簡單的leader --> follower

這樣，RAFT就把consensus的問題就分為三個相對獨立，更小更細緻的問題：

Leader election：系統啟動時，或leader異常時，要選舉出一個且只有一個新leader

log replication：leader處理client的請求，並將之轉化為log entry，並將log複製到整個叢集。其它節點的log都要遵從leader

safety：safety的含義是系統不會給出錯誤的結果。例如，程序將key a的值設定為1，在沒有其它寫操作執行前，讀取a應該返回1。對於replicated log來說，就是在任意節點上，index相同的log entry應該一致

Raft基礎

Raft使用replicated state machine作為基礎資料結構，通過replicated log在節點之間同步資料。log的條目（entry）會包含state machine可執行的命令。收到命令的節點在本地state machine執行命令。命令可能如下：set key a to 'a'; update key a to 'b'; delete key a; set key a to 'c' if value(a) = 'b' （寫操作，CAS操作……）

Raft叢集使用quorum來進行寫操作和leader election（注意與我們之前提到的讀和寫的quorum略有不同，w + e > n 保證選舉出的新leader持有最全的log entries）。每個伺服器可能處在3種狀態：leader，follower，candidate（leader候選）。正常執行時，叢集有一個leader，其它節點都是follower。Follower不會主動向系統的其它部分發送訊息，只會接收並響應leader和candidate的訊息

RAFT按term劃分時間。每一個term都從election開始，到下次election開始前結束。election期間可以有1個或多個candidates嘗試成為leader，raft保證每次election只會選出0個或1個leader。如果沒有選出leader，term立即結束，開始下一個term

可以看出，term可以被用作邏輯時鐘，Raft也確實給term賦予單向增長的term number，作為系統邏輯時鐘的一部分

Raft並沒有限制伺服器間的通訊模式，只要求通訊滿足RPC模式（request-response）。Raft主要使用兩種RPC：

RequestVote：由candidate在election期間發起

使用RPC方式通訊也是Raft簡化系統的方式。每個請求都要求接收方給出響應。Raft允許訊息丟失，請求方在這種情況下需要重試，伺服器可以並行傳送請求，Raft不要求網路保持RPC訊息的順序

可以看到，Raft對網路的要求非常寬鬆，不要求必須送達，也不要求保持順序。這與ZAB形成了一個鮮明的對比。如果讀者有了解CvRDT和CmRDT，可以看到這裡有相當程度的相似性。這種相似度不是偶然，我會嘗試找或寫一篇文章分析這種相似的原因

Leader election

Raft使用心跳機制觸發leader election。伺服器啟動後都處在follower狀態。如果follower能收到leader或candidate的訊息，它就會維持在follower狀態。

Leader會定時傳送心跳訊息給所有follower。如果follower經過一定時間沒有收到訊息，它就會將自身轉化為candidate，啟動election（增加當前term number，啟動新term。注意，其它follower可能用同樣的方式加入這個term，成為term的candidate）

Candidate會投票給自己，然後通過RPC向叢集的其它所有伺服器傳送RequestVote RPC。投票可能有3種結果：

• Candidate自身獲選（超過半數票）
• 另一個Candidate獲選
• 超時，沒有獲選者

每個伺服器在一個term只能投票給一個candidate，採用先到先得的方式（candidate會投自己），這樣，超半數票的要求就限制了一次election只可能選出一個leader。一旦選出新leader，新leader就開始向其它伺服器傳送心跳，防止新election發生

在等待選舉的時候，candidate可能收到AppendEntries RPC，傳送方可能是之前斷開的leader，也可能是收到多數票的新leader。如果傳送方的term number和該candidate一樣或更大（更大的原因是選舉timeout，又啟動了新term），如果小於自身的term number，則candidate拒絕請求，繼續等待選舉結果

如果同時有多個follower成為candidate，選票可能分散，沒有candidate能得到超半數票。Raft會指定一個election timeout，超過這個時間candidate會繼續增加term number，啟動新選舉。新發出的RequestVote會帶有更大的term number。

為避免選舉得不到結果的情況反覆出現，Raft使用一個固定區間內的隨機election timeout（好比在一個平均通訊時間10ms的網路裡，election timeout在150ms-300ms之間）。這樣，大部分情況下只有一個candidate會timeout，並迅速啟動/完成新一輪election。

Raft最初考慮採用排榜的方式處理多個candidate分選票的情況。亦即給每個伺服器分配一個不同的排名，如果一個candidate收到更高排名的RequestVote，它會放棄candidate身份，回到follower。但是這種方式在某些情況下變得很複雜。Raft最終選擇隨機超時重試的方式，因為這種方式更易於理解

Log replication

Leader被選出後，就開始處理客戶端請求。客戶端請求會包含需要伺服器執行的命令。Leader將這個命令加入自己日誌末尾（新條目會記錄當前的term number，以及它在當前term的序號），然後傳送AppendEntries RPC給其它伺服器。

Leader決定何時log entry可以算作已提交（committed）。Raft保證已提交的日誌不會丟失，且最終會複製到所有節點。提交一條日誌也意味著這條日誌之前的日誌都已提交。下面繼續說明

• 如果不同日誌（不同伺服器上）上的兩條記錄屬於相同的term，且在該term中序號一致，則它們包含相同的內容
• 如果不同日誌裡的兩條記錄term和序號都一致，則它們之前的日誌也一致

第一條：因為日誌都是由leader產生的，而一個term內只會有一個leader，這就保證了term number+日誌序號可以唯一的決定一條日誌。leader的日誌是WAL，所以順序不會變化。

第二條：AppendEntries會進行一致性檢查。AppendEntries RPC會帶有當前term number和上一條日誌的序號，如果follower找不到上一條日誌，就會拒絕這個請求。這樣，一旦follower接收AppendEntries RPC，leader就可以確認該follower的日誌與leader完全一致

在Leader異常的情況下，可能出現日誌不一致的情況，圖7列舉了這類情況

圖中顏色代表term，數字為term number。follower可能：

• 缺少entry（a，b）
• 包含多餘的未commit的entry（c，d）
• 同時缺少entry和包含多餘的未commit的entry（e，f）

注，出現不一致的地方都是未commit的entry

為了解決這些不一致的情況，leader需要找到每一個follower和自己log開始不一致的點，刪除follower上不一致的log entries，再將自己的log傳送給follower

Leader會保有每一個follower上日誌相對於自己的位置。這一動作在leader確立後就通過AppendEntries RPC完成。

leader首先根據自己log最後的位置發出AppendEntries RPC，如果follower拒絕（找不到上一個log），leader會將follower的日誌位置向後移動一位，再繼續請求，直到follower接受請求為止。Follower一旦發現AppendEntries RPC裡包含的位置本地也存在，就會刪除掉本地多餘的entries，接受AppendEntries RPC

Leader可以傳送空的AppendEntries來節省頻寬，直到確認follower上日誌位置後再發送資料

Follower也可以在響應中加入本地日誌的資訊，避免Leader一位一位的嘗試

實踐中，Raft迴避了這些優化。因為這些不一致的情況都不易出現，這些優化帶來的複雜度很大，但效能上的收益非常小

可以看到，這個機制非常簡單，Raft認為大部分情況下按照此機制實現就足夠現實需求。當然，也可以按需進一步優化

AppendEntries RPC的機制簡化了保持日誌同步的麻煩。Leader只需正常的嘗試AppendEntries RPC，所有伺服器的日誌就會很快保持一致。

與follower不同，leader不會覆蓋或刪除自己的日誌（WAL）。這樣可以確保已經一致的follower只會落後，不會再變得不一致

Safety

Raft還需要一定的機制來保證每次leader election選出的新leader一定要包含最近的committed log。這樣，committed log才不會被改寫

任何consensus algorithm都要求leader最終保有全部committed log entries。但有些演算法允許選舉出缺少committed entries的leader，然後再將缺少的部分同步給leader。

Raft要求只有包含上一個term全部committed entries的follower才能被選為新leader，這就避免了很多複雜度

這一機制包含在election的過程中。一個candidate必須聯絡過半數節點，這些節點中必然有至少一個包含全部committed log entry。RequestVote RPC會包含candidate上最後一條log的資訊，接收的節點如果發現自身的日誌更up-to-date，就會拒絕RequestVote。因為必然有過半數節點包含最近的committed log，所以如果一個candidate沒有最近的committed log，就不會比這些節點更up-to-date，也就不能獲選。

up-to-date通過比較最近term裡最後一個log entry的term number和序號來判斷。如果最後term number不同，則term number比較大的更up-to-date；如果term number相當，則log entry序號更大的更up-to-date

注意：雖然在一個term內，可以通過對AppendEntries RPC計數來判斷該term內產生的log entry是否已commit，這樣的方法不能用在commit上一個term的entry裡，這種情況可以參見圖8

a）S1是leader，正在複製entry 2 （term 1）

b）S1異常，S5被選舉為新leader，添加了entry 3 （term 2）

c）S5異常，S1恢復並被選舉為新leader，開始繼續複製entry 2。（term 3）注意S3雖然複製到了entry 2，它最後的entry仍然在term 1

d1）S1又異常。即使entry 2被複制到多數節點，S5仍然可能被選為新leader，因為S2/S3會認為自己的日誌比較落後，這樣就會走向d1的情況，被多數節點複製的entry 2最終被抹掉

d2）如果S1沒有異常，entry 4在term 3中被複制到多數節點（committed），entry 2也被commit。因為AppendEntries的機制，commit一個entry時，leader之前的所有entry都會被commit

這裡有一些額外的複雜度，根源在於Raft會保持每個log entry的term number。一些其它的演算法可能會給從前一個leader帶來的log entry提供新的term number（類比Raft的術語）。Raft希望保持log的結構更容易理解

Follower & Candidate異常

很容易處理，Raft會無限重試RPC

Raft RPC是冪等的，所以沒有錯誤會因此產生

Log compaction

隨著執行時間增加，會有越來越多操作被記錄到日誌中。需要某種方案來壓縮日誌

壓縮日誌的思路是將不需要的日誌刪除。例如如果日誌中出現 set x to 2，那麼之前的set x to 1就可以刪除。

Raft壓縮日誌需要各個節點的state machine配合完成，而Raft並沒有規定state machine的具體實現。所以Raft只給出了日誌壓縮的建議

我們不細緻討論這些方案，只大致列舉：

• 使用Snapshot。將當前的整個系統狀態寫入穩定的儲存，然後刪除之前的所有log
• 如果state machine是持久化的，系統狀態本身就寫在硬碟上。Raft log可以在被執行完後立即丟棄。
• 使用log cleanning，log-structured merge tree等資料結構

Raft建議日誌壓縮時採用一些核心思路：

壓縮日誌由各個節點獨立完成，不通過leader統一做決定。這樣可以避免日誌壓縮受到Raft的演算法影響，增加更多複雜度。（在很小的state machine的情況下，由leader完成壓縮再發送給follower可能更好）

壓縮日誌後，節點還需要儲存一些資訊，不能影響到AppendEntries RPC

因為節點自主壓縮了日誌，節點可能需要將狀態儲存起來以備重啟時使用。同時，還要考慮節點長時間斷開，日誌落後很多時的情況（可能需要通過leader傳送snapshot來跟上）

Membership changes

動態新增/刪除節點

本文不細緻討論Raft具體如何支援membership changes。只概括一下思路

新增/刪除節點時，系統需要顧及到safety（不要出現錯誤的響應）和availability

下文中，我們把節點的狀況也稱為配置（configuration），新增/刪除節點的操作就包括提供伺服器，和使用新配置Cnew替換舊配置Cold

先介紹常見的做法：

系統首先切換到一個臨時狀態，leader將臨時狀態提交到叢集，然後切換到新狀態。臨時狀態是Cold和Cnew的組合（同時要求兩種多數票）

此時，新的log entry只有同時複製到滿足Cold和Cnew的多數節點才算committed

現在，系統的所有操作需要同時滿足Cold和Cnew。leader繼續提交Cnew狀態給叢集，提交完成後，Cold配置對系統已無關緊要

Raft在實現此方案的過程中，發現了更簡單，不依賴臨時狀態的方案，每次更改配置時，只能增加或刪除一個節點。更復雜的配置變更可以通過一系列增/刪單個節點的操作完成

Raft比較推薦使用後一方案，實現會簡化，操作複雜度和效率都不會有明顯降低

只增/刪一個節點不需要中間狀態的根源在於：只有一個節點變化的情況下，新舊配置的多數節點必然會有重合。新配置生效後，舊配置自然無法無法再形成多數票

新增/刪除節點還意味著需要rebalance clients。我們也不細緻分析，只提示存在此問題

Raft Client

發現raft服務

由於raft叢集可能動態變換leader，member，通過簡單的靜態配置就不太可行。可以通過使用外部目錄服務（如DNS），當然，需要隨著系統狀態的變化更新目錄服務資料

routing to leader

Raft是leader based，所以client的請求需要轉發給leader。Client啟動時會隨機連線到一臺伺服器上。之後，可以由該伺服器返回leader地址給client，client重連到leader，也可以由伺服器向leader轉發client的請求

無論那種情況，raft都需要避免伺服器上leader資訊過期導致client請求被無限延遲。而不論leader，follower還是client，都可能儲存過期的leader資訊

leader：伺服器可能處在leader狀態下，但不是叢集當前的leader。這樣，該伺服器即無法處理client請求，也不能返回正確的leader地址給client。這種情況下，raft通過election timeout進行控制，如果leader在一個election timeout內無法完成叢集多數節點的heartbeat，它就會退出leader狀態。client可以連線到其它伺服器進行重試

follower：follower無法連線到leader時會啟動新的election，在新leader選出後follower會更新leader資訊。

Client：Client失去連線後（可能是leader退出leader狀態，follower拒絕響應，等等情況），會隨機嘗試另一伺服器，而不是嘗試重連

linearizable

client和伺服器間的通訊是at-least-once模式。client會在請求沒有得到響應的情況下重試，但是我們之前看到，網路環境下沒有響應的原因是無法判斷的。重試的請求可能已經被正常處理過。這一問題通過session來解決。Client會為session內的請求進行序列編號，session會跟蹤最近處理過的序列號，如果請求已經被處理過，伺服器會跳過執行，直接返回結果

client會在每一個請求裡告知伺服器它尚未接到響應的請求中最小的編號。伺服器由此得知哪些請求已經響應成功不會再被重試，可以在session中清理掉

伺服器總是需要session過期的問題，這裡又出現了需要伺服器達成一致的情況，如果過期的時間不一致，有些伺服器可能會再次處理重複的訊息，導致系統狀態不一致。可以有各種做法：

LRU policy：每個伺服器只維護一定數量的session，數量達到就開始移除

在client session過期時，可能出edge case：client在session過期後繼續傳送的請求。如果給client分配新session，會無法處理重複請求的問題。Raft的參考實現LogCabin對這種情況會直接返回錯誤，client進而直接crush。

可以看到，這種機制本身不支援無限scale client。

read-only requests

如果只讀請求可以不通過raft log（無需consensus），就可以非常快速的處理。

但是，如果繞過raft log，可能會導致讀取過期資料。

有一些手段可以在保持linearizable的情況下繞過raft log：

1. leader會保有自身log中committed部分的序號。如果只讀請求到來時，leader尚未確定提交任何一個entry（剛剛成為leader），就等到有entry提交。一旦有entry提交完成，raft就保證了leader上提交的entry和任意一個follower一樣up to date。
2. leader把這個提交過的entry的序號作為readIndex。傳送到leader的只讀請求可以從這個index的位置構建出的狀態讀取
3. leader還不能直接使用readindex來響應只讀請求，因為還需要明確它沒有被新的leader替代。這個檢查通過一輪心跳檢查完成（一輪心跳可以為多個readonly request服務）
4. leader等待自身的狀態機執行完readIndex，然後根據狀態機響應只讀請求

follower可以通過像leader請求當前的readIndex，然後執行第4步來響應只讀請求

還有一些更近一步的手段可以優化只讀的請求，我們這裡不再細緻討論。思路是一致的，只要處理請求的伺服器能夠確定最新的committed index，就可以根據執行到這一步的狀態機返回結果而不破話linearizability

Total Order broadcast (Atomic broadcast)

total order broadcast也被歸為consensus algorithms，雖然zookeeper官方有強調ZAB不是consensus algorithm。下面將對其簡要介紹，並最終介紹ZAB演算法（Zookeeper atomic broadcast）

Ordering，Causality

再次以圖3展示的簡單情況來討論

儘管網路訊息本質上是無序/混亂的，各個參與者的操作和系統事件之間是有一定因果關係的

圖中，Follower 1必須在收到leader的訊息後才能把新結果的訊息發給Alice，Referee也只有傳送訊息到leader後才可能收到更新成功的ok訊息

Alice和Bob看到不同結果，是因果關係被破壞的一個反映（其原因是cross channel，亦即Alice和Bob之間有兩個不同的訊息渠道--一個通過系統，一個通過電話。本文不做細緻討論）

Causality隱含了訊息/事件的順序關係：因在果前；訊息傳送在接收前；響應發生在請求後。系統中有因果關係的事件會形成鏈條：某個節點讀取資料，進行一些計算，然後把結果儲存下來；另一個節點讀取並根據這些結果寫入一些其它的結果。這些有因果關係的操作就定義了系統中發生的事件的因果關係

保證訊息的處理遵循這些因果關係的系統，就是causally consistent的系統。這是一個比Linearizable弱的consistency model，但是又比eventual consistency強。

我們之前從資料儲存的角度討論了linearizable的系統，現在來看一看Ordering（對系統事件的排序）和consistency model的關係

捕獲Causality

我們需要一些手段來記錄系統中事件的因果關係，來識別有因果關係的操作和併發操作。很容易想象，可以用時間戳來記錄事件的先後順序。

很遺憾，大部分情況下這是不可行的。作業系統的時間並不可靠，總是會在一段時間後偏離正確的時間。所以我們有許多時間伺服器供世界各地的作業系統隨時進行同步。但是系統總會在某些時段返回給應用程式錯亂的時間。VM/Container的廣泛應用帶來更多時間上的問題，VM可能會在某些時候整個被停住，來排程硬體資源

分散式系統通常會適用邏輯時鐘來代替物理時鐘。我們常用的樂觀鎖機制就是在資料里加入只增長的版本號，寫操作會先讀取當前版本號，確保與之前讀取的版本號一致才完成寫入，如果當前版本號高於寫操作之前的版本，就發現了併發操作（為了避免引入事務，nosql資料庫通常會提供CAS-compare and swap-操作，可以將對比版本和寫入算作一個原子操作）

更泛化的邏輯時鐘包括lamport timestamp，vector clock，它們都可以用來識別併發操作，以及為因果順序的操作排序。我們這裡不詳細討論

Total order broadcast (Atomic broadcast)

顧名思義，total order broadcast包括兩部分，一是要對系統內的操作進行全域性順序編排，二是要將操作按編排好的順序傳送到系統的各個節點

由於這樣的特性，total order broadcast可以被用來實現linearizable儲存

寫操作可以被視為新增一個訊息，系統的每個節點都會按同樣的順序收到所有的寫操作。讀操作也將被視為新增一個訊息，執行讀操作的節點將在自身收到這個讀操作訊息後再返回響應，這樣，系統中任何節點都不會返回過期的資料

我們前面討論過的unique constraint，leader election等也可以通過類似的方式實現，例如：Unique constraint可以通過先新增一個寫操作訊息，然後等待這個訊息返回到執行節點，因為所有在它之前的訊息都會被髮送過來，執行的節點就可以判斷新寫入的值是否已經被佔用。如果被佔用，就對客戶端返回失敗，如果沒有，就成功寫入（注意，這些操作體現了linearizability影響效能）

反過來，linearizable儲存也可以用來實現total order broadcast：

將linearizable儲存的每一次資料變化都順序生成一個版本號，然後將變化內容和版本號一起傳送給系統的所有節點。注意這裡版本號必須是連續的，這樣接收的節點才知道有時需要等待空缺的版本送達

ZAB (Zookeeper atomic broadcast)

ZAB也是leader-based consensus algorithm，所以與Raft有很多相似點。ZAB允許沒有最近提交日誌的節點被選為leader，在election完成後再對日誌的不一致進行修訂（具體演算法是可替換的）。

ZAB提供比Raft強一些的guarantee：client可以pipeline一些列請求，ZAB保證這些請求會被順序執行（或者全部不執行）。這可以用來：申請鎖-執行一些列操作-釋放鎖。其它客戶端可以按此順序觀察到執行結果。（Raft同樣可以用來提供這樣的機制，但需要額外的工作處理客戶端的重試）

我們看到了total order broadcast可以用來實現linearizable儲存，而linearizable儲存可以用作分散式鎖，leader election（distribute coordinator）等等功能，這正是Zookeeper的目標

那麼ZK是如何實現total order broadcast（atomic broadcast）的呢？

通過它的linearizable儲存。

當然這是玩笑，ZK需要的是用atomic broadcast來實現它的linearizable儲存。

ZAB是leader-based，client可以連線到一個或多個節點。節點會將client的請求轉發到leader（如果只讀會直接處理，通過sync()操作保證linearizable），leader執行請求，然後將狀態變化傳送到followers

注意這裡，leader會直接執行未commit的操作，然後傳送狀態變化給follower，follower直接應用狀態變化，不會執行操作（根本就沒不知道操作是什麼）

而Raft會先將操作傳送給follower，待commit之後再執行到本地狀態，follower各自執行操作

這兩種機制分別稱為replicated state machine和primary backup。（就像event sourcing中的command，event）各有利弊，但是顯然，ZAB無法用Raft類似的機制，根據readIndex直接提供linearizable的只讀響應

Raft將自身實現為replicated log，ZAB的機制相似，但是使用了不同術語描述。Raft的term在ZAB中被稱為epoch，leader上每一次執行操作導致的狀態變化被稱為transaction（記得ZK可以pipeline請求），類似Raft的log entry， transaction也有一個id被稱為zxid，其值與Raft相同，epoch序列號和epoch內的transaction序列號

概覽

ZK通過TCP協議傳輸訊息，這樣就不需要自己處理一些網路底層的問題，ZK同樣通過heartbeat來檢測錯誤的節點

準確的說，TCP協議幫助ZK實現兩個目標：

一個FIFO channel，傳遞的訊息可以保證順序

FIFO channel關閉後不會再收到訊息

Raft沒有要求使用TCP通道，完全可以有UDP方式的實現。但是，保證訊息傳遞順序的通道對Raft效能的優化至關重要（AppendEntries會順序到達，不需要無止境的重試，等待……）

ZK叢集存在兩個生命週期的階段：

1. leader activation 選舉出一個leader，並且保證leader上正確記錄系統當前的狀態
2. active messaging leader開始接收並處理請求

Leader Activation

當新leader被選出後，其它伺服器將連線到新leader，並開始接收自己丟失的請求。如果一個伺服器缺少太多請求（斷線時間太久，或者剛剛加入叢集），leader會把當前的整個資料狀態作為一個snapshot傳送給這個伺服器（可以看到ZK總共能儲存的資料是受限的，並沒有引入類似kafka broker的partition機制）

新leader根據自己最大的zxid來確定下一個zxid，並用這個zxid傳送NEW_LEADER請求給其它伺服器，這個NEW_LEADER請求被叢集接受後leader activation才算作完成

Active messaging

一旦leader被選出，處理請求的過程就比較簡單

ZK預設使用majority quorums，亦即3個節點中的2個，4個節點中的3個（所以通常使用奇數節點），但也支援一些奇怪的用法，例如，如果你有5臺伺服器，其中3臺效能遠強於另外兩臺，可以給這3臺分為一組，賦予更高的優先順序（一票算兩票）

ZAB的4個階段

ZK的兩個階段是一個比較粗糙的劃分，叢集的節點實際上可能處在4個階段

• election (phase 0)
• discovery (phase 1)
• synchronization (phase 2)
• broadcast (phase 3)

當多數節點處在前三個階段時，ZK叢集也就處在leader activation階段。和Raft一樣，此階段叢集不會處理請求，主要處理新leader的選擇和保證已提交的資料都轉移到新leader上

節點可能有三種狀態：following，leading，election

Phase 0: Leader election 節點在此階段處在election狀態。具體選擇演算法可以變化（後續介紹預設演算法FLE），每個投票的節點只要選出一個 可能 得到多數票的leader。被選的節點稱為投票節點的prospective leader。phase 3將在prospective leader中確認leader。若節點投票給自己，則進入leading狀態，否則進入following

Phase 1: Discovery Follower建立到prospective leader的follower-leader連線，併發送自身最近的epoch和transaction資訊，prospective leader確認follower接收過的最近的transaction，找到具備最近transaction的節點（與raft判斷up-to-date的方式一致，先比較epoch，epoch相同再比較zxid），將此節點的歷史記錄同步到本地，並據此建立新的epoch。如果follower嘗試連線following狀態的節點（沒有給自己投票的節點），連線將被拒絕，follower退回Phase 0

注意Raft採用了特定的的投票機制，每個節點投票給自己，且在Phase 0就確認被選的leader必須具備most up-to-date的log entry，從而避免了這一步

Phase 2: Synchronization leader將本地歷史記錄的transaction傳送給follower，一旦過半數follower確認接收，prospective leader傳送提交訊息給這些follower，此時，prospective leader被確認為leader

Phase 3: Broadcast 此階段開始正常處理請求。

很像經典的2-phase commit，但是無需處理abort的情況

注意所有的通訊都通過FIFO channel（TCP connection），如果連線斷開，重連時會根據zxid在斷開的點上繼續

• leader向所有follower傳送propose的順序一致，也與leader自身接收請求的順序一致
• follower處理propose的順序與接收的順序一致，因而返回ACK給leader的順序也與propose順序一致（act like no concurrency）
• 一旦多數ACK被leader收到，leader會發送COMMIT給全部follower。COMMIT的順序與ACK，propose的順序都一致
• COMMIT是通訊的重要部分，也會按順序執行

在Phase 3，follower可以繼續加入該epoch（因為phase 2只需要quorum即可進入phase 3，有些節點可能會被留下）

與Raft相同，如果leader不能收到quorum的heartbeat，或者follower不能收到leader的heartbeat，就會回到phase 0

Fast Leader Election

FLE嘗試選出具備全部committed transaction的節點，這樣就可以省去後續Phase 1的工作

思路大致是在所有節點之間建立聯絡，互相通知每個節點的投票資訊。每個節點初始都投給自己，再收到其它節點的投票資訊後，檢視該投票的物件是否可能比自己有更近的committed transaction，然後根據這個情況更新自己的投票。具體演算法比較複雜，這裡不再細述

FLE達成的結果和Raft election一致

參考資料：

Design data intensive applications ofollow,noindex"> https:// dataintensive.net/

Consensus: Bridging theory and practice

ZooKeeper's atomic broadcast protocol: theory and practice http://www. tcs.hut.fi/Studies/T-79 .5001/reports/2012-deSouzaMedeiros.pdf

Consul:https://consule.io

Zookeeper: https://zookeeper.apache.org

etcd: https:// coreos.com/etcd/