Zab，Raft，Viewstamp的區別（1）選舉；

它們究竟有啥區別，本文主要說說 選舉方面的區別。首先看raft

1、Raft選舉涉及的幾個概念

（1）raft的每一個伺服器（server）都處於三個狀態之一：leader，follower，candidate。

（2）term：raft將時間分成各個時隙，每個term內有唯一的leader，遞增

（3）log index：raft中每個log都有唯一的index

2、Raft的選舉期望

Raft要求選舉出來的leader包含了所有已經提交的log entry。

（1）、正常狀態下leader 發送心跳到follower，若follower超時未收到來自leader的心跳，則follower發起election。

（2）、發起election的follower切換狀態到candidate並給自己投票，該伺服器保持此狀態直到如下三個事件發生。

a.贏得選舉

b.其他伺服器贏得選舉

c.超時沒有人贏選舉

（3）、某一candidate在同一個term獲得大多數server投票，贏得選舉，變成leader，發送心跳到其他伺服器

（4）、在選舉過程中，伺服器A可能收到其他伺服器B當選請求，若B的vote相較於A的vote「更新」，則認為該選舉合法，A切換回follower，否則拒絕該請求。

附 「更新」 定義：

若參與比較的兩個server中current term不同，則term更大的更新，否則log index更大的更新

4、Raft投票原則

當一個candidate發起選舉時，其他server使用on afirst-come-first-served basis原則，若在一定時間內，沒選出來主（即沒有達成quorum），則重啟選舉。

我們再來看看Zab協議

Zab本身沒有規定選舉演算法，只要求達到quorum就好，但是Zab有個預設FLE（FastleaderElection）演算法，下文Zab的選舉流程即指代FLE演算法

1、Zab中的幾個基本概念

（1）和Raft類似，Zab的伺服器（Zab論文中使用peer，其實和Raft的server是一回事）也有三個狀態：election、following、leading。其中election對應Raft的candidate、following對應Raft的follower，leading和Raft的leader略有差別，下文會詳述。

（2）Zxid： 在zab中，一個事務被Zxid唯一標識，Zxid是一個二元組(e,c)，其中e是事務的epoch編號，c是counter

（3）round：選舉投票的輪次

（4）對p（i）的一個vote的：一個vote可表示為（z（i），i），其中z（i）是p（i）的最後一個事務。兩個vote（z(i),i）大於(z(j),j)時滿足，z(i)>z(j)或【z(i)=z(j)，且i>=j】

2、Zab的選舉期望

Zab本身不對選舉有任何期望要求，任意一個peer都可以做primary，只需收到quorum的投票就好。但zab預設的FLE演算法同樣要求選出來的，要求選舉出來的primary包含了最新propose的log（可以沒有commit），下文講的流程也是FLE的流程。

3、Zab的選舉流程

（1）peer在啟動階段，處於election狀態，正常情況下，primary收到心跳到其它peer，若超時未收到quorum的心跳，則primary切狀態至election，發起選舉。同樣 follower若超時也發起選舉。選舉時peer首先投票給自己，投票輪次+1，發送notification（vote，id，state，round），其中vote是其意向leader（初始是自己），id是自己的id，state為election，round是輪次

（2）一旦peer P收到來自peer Q的notification，若P自身狀態是election，將Q的投票壓入P的FIFO隊列，若Q的狀態是election且P自身的round大於Q的round，說明P是一個更新的投票，則P發送P自身選舉信息給Q。（P投票的peer id P自身id P狀態 P輪次），若P的狀態不是election（following或者leading，此時意味著已有quorum達成共識），則P發送自己選舉信息給Q。

（3）P（只是符號，不一定是上面的P）檢查自己的隊列，若隊列為空，則發送自己選舉信息到其餘peer。否則，若第一個收到的選舉信息的來自peer Q，且Q為election（說明系統剛啟動或者leader故障，大家都是election）。此時分三種情況，

a. Q輪次比P更新。更新P投票輪次為Q的輪次，清空P收到的投票。若此時Q.vote相對於（P.lastZxid,P.id）較大，P使用Q投票的peer作為自己投票的peer)，否則P繼續投票給自己（P.vote=（P.lastZxid,P.id））。

b. Q和P輪次相等 , 若此時Q.vote相對於（P.lastZxid,P.id）較大，P使用Q投票的peer作為自己投票的peer)，發送投票信息

c.Q.輪次小 ，則取P隊列中收到的下個投票信息

（4）記錄投票，若記錄中有一個quorum並且在時間閾值能沒有收到其他投票信息或P收到的投票數量為全體伺服器投票。此時根據P的投票，若P投自己，則置狀態為leading，否則置狀態為follower。

以上部分是系統啟動或leader故障時狀態，以下為P是新加入系統 系統有leader

（5）此時Q為leading或following

若Q.round=P.round，記錄Q的投票，此時有三種情況

a.若Q為leading 則結束P切為follower

b.若Q投P且構成quorum 則P為leading

c.若Q投其它 並且構成quorum 且在有已經存在的成功投票 則P為follower Q投票對象為主投票結束

記錄Q為已經成功投票

a. Q投p 則p為leading結束

b. Q是一個成功的投票 使用Q的投票做leading， 結束。

關於zab的選舉可以看看這篇文章

圖解zookeeper FastLeader選舉演算法。

VR沒有具體的選舉演算法，VR的primary是通過配置和當前primary計算得到下一個primary，具體的流程如下可以參考論文。

這裡主要對比Raft和Zab下區別

1、log的連續性和消息流向

Raft的log（Paxos不要求log連續，Raft本質上是Paxos的特殊情況）必需連續，選出來的leader擁有最多的log，消息流向必須是leader到follower。Zab本身不要求log連續，可以由follower同步到leader。FLE演算法log也必須連續，follower根據leader的log內容更新自己log。

2、leader的確定時間

Raft在達成quorum時已經確定leader，leader開始工作接受請求並廣播。由leader向follower同步消息，可能會出現下圖

（a）在term2 S1是leader，將數據2同步至S2，S1 crash

（b）此時由於數據2未達成quorum，S5在term2 當選為leader S5寫數據3 然後crash

（c）S1重啟，將數據2同步至S3，達成quorum，然後進入term3 寫數據4，crash

（d）因為在term3，沒有達成quorum，並且S2，S3，S4，S5的最後一個log id一致，S5可能當選，此時，S5使用數據3 同步到term2，覆蓋已經提交的數據2

（e）若S1在crash之前將數據4同步至quorum，則S5不能再term3贏得選舉

為了避免上述情況（d）發生，Raft要求在當前term的時候不能直接提交之前term信息。只有在提交本term數據的時候，順帶提交之前term的數據。由於選舉時的要求leader包含所有已經commit的日誌，在當前term時，primary進行數據達到quorum提交的時候，之前term的數據必然也達到了quorum。也就是說，在上圖的情況下，當前term3數據提交的時候，S5是不可能當選為leader的。

Zab在達成quorum時選出「leader」，然後這裡的「leader」只是一個候選，「leader」並不將請求廣播，需要首先進行「leader」和follower的數據同步，達成同步後，建立連接，「leader」才真正成為leader開始廣播新請求。Zab從根本上避免了上述問題。

3、選舉的觸發

Raft：目前只是follower在檢測。follower有一個選舉時間，在該時間內如果未收到leader的心跳信息，則follower轉變成candidate，自增term發起新一輪的投票，leader遇到新的term則自動轉變成follower的狀態

ZooKeeper：leader和follower都有各自的檢測超時方式，leader是檢測是否過半follower心跳回復了，follower檢測leader是否發送心跳了。一旦leader檢測失敗，則leader進入election狀態，其他follower過一段時間因收不到leader心跳也會進入election狀態，從而出發新的leader選舉。一旦follower檢測失敗了，則該follower進入election狀態，此時leader和其他follower仍然保持良好，則該follower仍然是去學習上述leader的投票，而不是觸發新一輪的leader選舉。

4、投票的輪次

Raft使用一輪投票，並採用「哪個candidate先請求投票誰就可能先獲得投票」的策略，可能造成投票衝突即各個candidate都沒有收到過半的投票，此時raft重啟投票。

ZooKeeper中的每個server，ZooKeeper中的每個server，在某個electionEpoch輪次內，可以投多次票，只要遇到更大的票就更新，然後分發新的投票給所有人。這種情況下不存在split vote現象，同時有利於選出含有更新更多的日誌的server，但是選舉時間理論上相對Raft要花費的多。並且理論上可能出現活鎖問題。

5、之前leader的干擾

Raft的copycat實現為：每個follower開通一個複製數據的RPC介面，誰都可以連接並調用該介面，所以Raft需要來阻止上一輪次的leader的調用。每一輪次都會有對應的輪次號，用來進行區分，Raft的輪次號就是term，一旦舊leader對follower發送請求，follower會發現當前請求term小於自己的term，則直接忽略掉該請求，自然就解決了舊leader的干擾問題

ZooKeeper：一旦server進入leader選舉狀態則該follower會關閉與leader之間的連接，所以舊leader就無法發送複製數據的請求到新的follower了，也就無法造成干擾了

參考

Raft對比ZAB協議 - zzm - ITeye技術網站

圖解zookeeper FastLeader選舉演算法。

http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf

http://pdos.csail.mit.edu/6.824/papers/raft-atc14.pdf

http://www.scs.stanford.edu/14au-cs244b/sched/readings/vr-revisited.pdf

推薦閱讀：