天天看點
傳回

算法進階（5）-分布式系統選舉算法及腦裂一、選舉算法定義二、選舉算法分類三、Zookeeper的ZAB協定四、Zookeeper的Quorum機制-談談怎樣解決腦裂(split-brain)五、總結

一、選舉算法定義

分布式中有這麼一個疑難問題，用戶端向一個分布式叢集的服務端發出一系列更新資料的消息，由于分布式叢集中的各個服務端節點是互為同步資料的，是以運作完用戶端這系列消息指令後各服務端節點的資料應該是一緻的，但由于網絡或其他原因，各個服務端節點接收到消息的序列可能不一緻，最後導緻各節點的資料不一緻。要確定資料一緻，需要選舉算法的支撐，這就引申出了今天我們要讨論的題目，關于選舉算法的原了解釋及實作，選舉包括對機器的選舉，也包括對消息的選舉。

在分布式系統中，通常稱主節點為Master（主人），其他從節點為Slave（奴隸），因為涉及到種族歧視，目前很多程式已經改為了Leader（首領）和Follower（追随者）。

一句話總結：選舉算法是為了解決叢集中誰說了算這個問題的。

二、選舉算法分類

很多分布式算法需要有一個程序作為協作者。下面介紹一些常用的選舉算法。

欺負算法

當任何一個程序發現協作者不再響應請求時，它就發起一次選舉。算法實作如下：

  1. P向所有編号比它大的程序發送一個ELECTION消息
  2. 如果無人響應，P獲勝并成為協作者
  3. 如果有編号比它大的程序響應，則有響應者接管選舉工作。P的工作完成。
  4. 将選舉獲勝的消息發送給所有程序，通知這些程序自己是新的協作者。
  5. 當一個以前崩潰了的程序現在恢複過來時，它将主持一次選舉。如果該程序恰好是目前正在運作的程序中程序号最大的程序，它将赢得此次選舉，接管協作者的工作。這樣，最大的程序總是取勝，故稱為“欺負算法”。

環算法

  1. 當任何一個程序注意到協作者不工作時，它就構造一個帶有它自己的程序号的ELECTION消息，并将該消息發送給它的後繼者。
  2. 如果後繼者崩潰了，發送者沿着此環跳過它的後繼者發送給下一個程序，或者再下一個，直到找到一個正在運作的程序。
  3. 在每一步中，發送者都将自己的程序号加到該消息清單中，以使自己成為協作者的候選人之一。
  4. 最終，消息傳回到發起此次選舉的程序。當發起者程序接收到一個包含它自己程序号的消息時，它就識别出這個事件。
  5. 此時，消息類型變成COORDINATIOR消息，并再一次繞環運作，向所有程序通知誰是協作者（成員清單中程序号最大的那個）以及新環中的成員都有誰。
  6. 這個消息在循環一周後被删除，随後每個程序都恢複原來的工作。
  7. 如果有多個ELECTION消息，那麼循環多周後被删除。

下面具體的算法其實都是基于上面兩種原理來實作的。

1.最簡單的選舉算法

如果你需要開發一個分布式叢集系統，一般來說你都需要去實作一個選舉算法，來選舉出Master節點。為了解決Master節點的單點問題，一般我們也會選舉出一個Master-HA節點（高可用）。

如果不采用後文的算法，我們也可以實作一個簡單的選舉政策。

這類型簡單的選舉算法可以依賴很多計算機硬體因素作為選舉因子，比如IP位址、CPU核數、記憶體大小、自定義序列号等等，比如采用自定義序列号，我們假設每台伺服器利用多點傳播方式擷取區域網路内所有叢集分析相關的伺服器的自定義序列号，以自定義序列号作為優先級，如果接收到的自定義序列号比本地自定義序列号大，則退出競争，最終選擇一台自定義序列号最大的伺服器作為Leader伺服器，其他伺服器則作為普通伺服器。這種簡單的選舉算法沒有考慮到選舉過程中的異常情況，選舉産生後不會再對選舉結果有異議，這樣可能會出現序列号較小的機器被標明為Master節點（有機器臨時脫離叢集），實作僞代碼如清單1所示。

state:=candidate; 
send(my_id):receive(nid);
while nid!=my_id
do if nid>my_id
then state:=no_leader;
send(nid):receive(nid);
od; 
if state=candidate then state:=leader;

2.拜占庭将軍問題

拜占庭帝國國土遼闊，為了防禦目的，每支軍隊都分隔很遠，将軍之間隻能依靠信差傳信。在戰争的時候，拜占庭軍隊内所有司令和将軍必需達成一緻的共識，決定是否有赢的機會才去攻打敵人的陣營。但是，在軍隊内有可能存有叛徒和敵軍的間諜，左右将軍們的決定又擾亂整體軍隊的秩序。是以表決的結果并不一定能代表大多數人的意見。這時候，在已知有成員謀反的情況下，其餘忠誠的将軍在不受叛徒的影響下如何達成一緻的協定，拜占庭問題就此形成。

拜占庭将軍問題實則是一個協定問題。一個可靠的分布式系統必須容忍一個或多個部分的失效，失效的部分可能會送出互相沖突的資訊給系統的其他部分。紐約的一家銀行可以在東京、巴黎、蘇黎世設定異地備份，當某些點受到攻擊甚至破壞以後，可以保證賬目仍然不錯，得以複原和恢複。從技術的角度講，這是一個很困難的問題，因為被攻擊的系統不但可能不作為，而且可能進行破壞。對于這類故障的問題被抽象地表達為拜占庭将軍問題。

解決拜占庭将軍問題的算法必須保證

  • A．所有忠誠的将軍必須基于相同的行動計劃做出決策；
  • B．少數叛徒不能使忠誠的将軍做出錯誤的計劃。

拜占庭問題的解決可能性

（1）叛徒數大于或等于1/3，拜占庭問題不可解

  • 如果有三位将軍，一人是叛徒。當司令發進攻指令時，将軍3可能告訴将軍2，他收到的是“撤退”的指令。這時将軍2收到一個“進攻”的指令，一個“撤退”的指令，而無所适從。
  • 如果司令是叛徒，他告訴将軍2“進攻”，将軍3“撤退”。當将軍3告訴将軍2，他收到“撤退”指令時，将軍2由于收到了司令“進攻”的指令，而無法與将軍3保持一緻。
  • 正由于上述原因，在三模備援系統中，如果允許一機有拜占庭故障，即叛徒數等于1/3，因而，拜占庭問題不可解。也就是說，三模備援對付不了拜占庭故障。三模備援隻能容故障-當機(fail-frost)那類的故障。就是說元件故障後，它就當機在某一個狀态不動了。對付這類故障，用三模備援比較有效。

（2）用口頭資訊，如果叛徒數少于1/3，拜占庭問題可解

  • 這裡是在四模備援基礎上解決。在四模中有一個叛徒，叛徒數是少于1/3的。
  • 拜占庭問題可解是指所有忠誠的将軍遵循同一指令。若司令是忠誠的，則所有忠誠将軍遵循其指令。我們可以給出一個多項式複雜性的算法來解這一問題。算法的中心思想很簡單，就是司令把指令發給每一位将軍，各将軍又将收到的司令的指令轉告給其他将軍，遞歸下去，最後用多數表決。例如，司令送一個指令v給所有将軍。若将軍3是叛徒，當他轉告給将軍2時指令可能變成x。但将軍2收到{v, v, x}，多數表決以後仍為v，忠誠的将軍可達成一緻。如果司令是叛徒，他發給将軍們的指令可能互不相同，為x, y, z。當副官們互相轉告司令發來的資訊時，他們會發現，他們收到的都是{x,y,z}，因而也取得了一緻。

（3）用書寫資訊，如果至少有2/3的将軍是忠誠的，拜占庭問題可解

  • 所謂書寫資訊，是指帶簽名的資訊，即可認證的資訊。它是在口頭資訊的基礎上，增加兩個條件：
    • ①忠誠司令的簽名不能僞造，内容修改可被檢測。
    • ②任何人都可以識别司令的簽名，叛徒可以僞造叛徒司令的簽名。
  • 一種已經給出的算法是接收者收到資訊後，簽上自己的名字後再發給别人。由于書寫資訊的保密性，可以證明，用書寫資訊，如果至少有2/3的将軍是忠誠的，拜占庭問題可解。

例如，如果司令是叛徒，他發送“進攻”指令給将軍1，并帶有他的簽名0，發送“撤退”指令給将軍2，也帶簽名0。将軍們轉送時也帶了簽名。于是将軍1收到{“進攻”：0，“撤退”：0,2}，說明司令發給自己的指令是“進攻”，而發給将軍2的指令是“撤退”，司令對我們發出了不同的指令。對将軍2同解。

3.Paxos算法

算法起源

  • Paxos算法是LesileLamport于1990年提出的一種基于消息傳遞且具有高度容錯特性的一緻性算法，是目前公認的解決分布式一緻性問題最有效的算法之一。
  • 在常見的分布式系統中，總會發生諸如機器當機或網絡異常等情況。Paxos算法需要解決的問題就是如何在一個可能發生上述異常的分布式系統中，快速且正确地在叢集内部對某個資料的值達成一緻，并且保證不論發生以上任何異常，都不會破壞整個系統的一緻性。
  • 為了更加清晰概念，當client1、client2、client3分别發出消息指令A、B、C時，Server1~4由于網絡問題，接收到的消息序列就可能各不相同，這樣就可能由于消息序列的不同導緻Server1~4上的資料不一緻。對于這麼一個問題，在分布式環境中很難通過像單機裡處理同步問題那麼簡單，而Paxos算法就是一種處理類似于以上資料不一緻問題的方案。
  • Paxos算法是要在一堆消息中通過選舉，使得消息的接收者或者執行者能達成一緻，按照一緻的消息順序來執行。其實，以最簡單的想法來看，為了達到所有人執行相同序列的指令，完全可以通過串行來做，比如在分布式環境前加上一個FIFO隊列來接收所有指令，然後所有服務節點按照隊列裡的順序來執行。這個方法當然可以解決一緻性問題，但它不符合分布式特性，如果這個隊列出現異常這麼辦？而Paxos的高明之處就在于允許各個client互不影響地向服務端發指令，大夥按照選舉的方式達成一緻，這種方式具有分布式特性，容錯性更好。
  • Paxos規定了四種角色（Proposer，Acceptor，Learner，以及Client）和兩個階段（Promise和Accept）。

實作原理

Paxos算法的主要互動過程在Proposer和Acceptor之間。Proposer與Acceptor之間的互動主要有4類消息通信。這4類消息對應于paxos算法的兩個階段4個過程：

階段1：

  • a) proposer向網絡内超過半數的acceptor發送prepare消息；
  • b) acceptor正常情況下回複promise消息。

階段2：

  • a) 在有足夠多acceptor回複promise消息時，proposer發送accept消息；
  • b) 正常情況下acceptor回複accepted消息。

Paxos算法的最大優點在于它的限制比較少，它允許各個角色在各個階段的失敗和重複執行，這也是分布式環境下常有的事情，隻要大夥按照規矩辦事即可，算法的本身保障了在錯誤發生時仍然得到一緻的結果。

4.Raft分布式選舉算法

參考我的另外一篇博文算法進階（6）-Raft算法

三、Zookeeper的ZAB協定

1.基本概念

ZooKeeper并沒有完全采用Paxos算法，而是使用了一種稱為ZooKeeper Atomic Broadcast（ZAB，ZooKeeper原子消息廣播協定）的協定作為其資料一緻性的核心算法。

ZAB協定是為分布式協調服務ZooKeeper專門設計的一種支援崩潰恢複的原子廣播協定。ZAB協定最初并沒有要求其具有很好的擴充性，最初隻是為雅虎公司内部那些高吞吐量、低延遲、健壯、簡單的分布式系統場景設計的。在ZooKeeper的官方文檔中也指出，ZAB協定并不像Paxos算法那樣，是一種通用的分布式一緻性算法，它是一種特别為ZooKeeper設計的崩潰可恢複的原子消息廣播算法。

ZooKeeper使用一個單一的主程序來接收并處理用戶端的所有事務請求，并采用ZAB的原子廣播協定，将伺服器資料的狀态變更以事務Proposal的形式廣播到所有的副本程序上去。ZAB協定的這個主備模型架構保證了同一時刻叢集中隻能夠有一個主程序來廣播伺服器的狀态變更，是以能夠很好地處理用戶端大量的并發請求。另一方面，考慮到在分布式環境中，順序執行的一些狀态變更其前後會存在一定的依賴關系，有些狀态變更必須依賴于比它早生成的那些狀态變更，例如變更C需要依賴變更A和變更B。這樣的依賴關系也對ZAB協定提出了一個要求，即ZAB協定需要保證如果一個狀态變更已經被處理了，那麼所有其依賴的狀态變更都應該已經被提前處理掉了。最後，考慮到主程序在任何時候都有可能出現奔潰退出或重新開機現象，是以，ZAB協定還需要做到在目前主程序出現上述異常情況的時候，依舊能夠工作。

下面這段日志所示是ZooKeeper叢集啟動時選舉過程所列印的日志，從裡面可以看出初始階段是LOOKING狀态，該節點在極短時間内就被選舉為Leader節點。

zookeeper.out:
2016-06-14 16:28:57,336 [myid:3] - INFO [main:[email protected]] - Starting quorum peer
2016-06-14 16:28:57,592 [myid:3] - INFO [QuorumPeer[myid=3]/0:0:0:0:0:0:0:0:2181:[email protected]] - LOOKING
2016-06-14 16:28:57,593 [myid:3] - INFO [QuorumPeer[myid=3]/0:0:0:0:0:0:0:0:2181:[email protected]] - New election. My id =  3, proposed zxid=0xc00000002
2016-06-14 16:28:57,599 [myid:3] - INFO [WorkerSender[myid=3]:[email protected]] - Resolved hostname: 10.17.138.225 to address: /10.17.138.225
2016-06-14 16:28:57,599 [myid:3] - INFO [WorkerReceiver[myid=3]:[email protected]] - Notification: 1 (message format version), 3 (n.leader), 0xc00000002 (n.zxid)
, 0x1 (n.round), LOOKING (n.state), 3 (n.sid), 0xc (n.peerEpoch) LOOKING (my state)
2016-06-14 16:28:57,602 [myid:3] - INFO [WorkerReceiver[myid=3]:[email protected]] - Notification: 1 (message format version), 1 (n.leader), 0xc00000002 (n.zxid)
, 0x1 (n.round), LOOKING (n.state), 1 (n.sid), 0xc (n.peerEpoch) LOOKING (my state)
2016-06-14 16:28:57,605 [myid:3] - INFO [WorkerReceiver[myid=3]:[email protected]] - Notification: 1 (message format version), 3 (n.leader), 0xc00000002 (n.zxid)
, 0x1 (n.round), LOOKING (n.state), 1 (n.sid), 0xc (n.peerEpoch) LOOKING (my state)
2016-06-14 16:28:57,806 [myid:3] - INFO [QuorumPeer[myid=3]/0:0:0:0:0:0:0:0:2181:[email protected]] - LEADING
2016-06-14 16:28:57,808 [myid:3] - INFO [QuorumPeer[myid=3]/0:0:0:0:0:0:0:0:2181:[email protected]] - TCP NoDelay set to: true

2.ZAB協定實作原理

ZAB協定的核心是定義了對于那些會改變ZooKeeper伺服器資料狀态的事務請求的處理方式，即所有事務請求必須由一個全局唯一的伺服器來協調處理，這樣的伺服器被稱為Leader伺服器，而餘下的伺服器則稱為Follower伺服器，ZooKeeper後來又引入了Observer伺服器，主要是為了解決叢集過大時衆多Follower伺服器的投票耗時時間較長問題，這裡不做過多讨論。Leader伺服器負責将一個用戶端事務請求轉換成一個事務Proposal（提議），并将該Proposal分發給叢集中所有的Follower伺服器。之後Leader伺服器需要等待所有Follower伺服器的回報資訊，一旦超過半數的Follower伺服器進行了正确的回報後，那麼Leader就會再次向所有的Follower伺服器分發Commit消息，要求其将前一個Proposal進行送出。

3.支援模式

ZAB協定包括兩種基本的模式，分别是崩潰恢複和消息廣播。

當整個服務架構在啟動的過程中，或是當Leader伺服器出現網絡中斷、崩潰退出與重新開機等異同步之後，ZAB協定就會退出恢複模式。其中，所謂的狀态同步是指資料同步，用來保證叢集中存在過半的惡機器能夠和Leader伺服器的資料狀态保持一緻。通常情況下，ZAB協定會進入恢複模式并選舉産生新的Leader伺服器。當選舉産生了新的Leader伺服器，同時叢集中已經有過半的機器與該Leader伺服器完成了狀态。在上文所示選舉的基礎上，我們把Leader節點的程序手動關閉（kill -9 pid），随即進入崩潰恢複模式，重新選舉Leader的過程日志輸出如下所示。

2016-06-14 17:33:27,723 [myid:2] - WARN  [RecvWorker:3:[email protected]] - Connection broken for id 3, my id = 2, error =
java.io.EOFException 
atjava.io.DataInputStream.readInt(DataInputStream.java:392) 
at org.apache.zookeeper.server.quorum.QuorumCnxManager$RecvWorker.run(QuorumCnxManager.java:795) 
2016-06-14 17:33:27,723 [myid:2] - WARN  [RecvWorker:3:[email protected]] - Connection broken for id 3, my id = 2, error = 
java.io.EOFException 
atjava.io.DataInputStream.readInt(DataInputStream.java:392) 
at org.apache.zookeeper.server.quorum.QuorumCnxManager$RecvWorker.run(QuorumCnxManager.java:795) 
2016-06-14 17:33:27,728 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - shutdown called 
java.lang.Exception: shutdown Follower 
at org.apache.zookeeper.server.quorum.Follower.shutdown(Follower.java:166) 
at org.apache.zookeeper.server.quorum.QuorumPeer.run(QuorumPeer.java:850) 
2016-06-14 17:33:27,728 [myid:2] - WARN  [RecvWorker:3:[email protected]] - Interrupting SendWorker 
2016-06-14 17:33:27,729 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - Shutting down
2016-06-14 17:33:27,730 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - shutting down 
2016-06-14 17:33:27,730 [myid:2] - WARN  [SendWorker:3:[email protected]] - Interrupted while waiting for message on queue
java.lang.InterruptedException
at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.reportInterruptAfterWait(AbstractQueuedSynchronizer.java:2017)
at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.awaitNanos(AbstractQueuedSynchronizer.java:2095)
at java.util.concurrent.ArrayBlockingQueue.poll(ArrayBlockingQueue.java:389)
at org.apache.zookeeper.server.quorum.QuorumCnxManager.pollSendQueue(QuorumCnxManager.java:879)
at org.apache.zookeeper.server.quorum.QuorumCnxManager.access$500(QuorumCnxManager.java:65)
at org.apache.zookeeper.server.quorum.QuorumCnxManager$SendWorker.run(QuorumCnxManager.java:715)
2016-06-14 17:33:27,730 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - Shutting down
2016-06-14 17:33:27,731 [myid:2] - WARN  [SendWorker:3:[email protected]] - Send worker leaving thread
2016-06-14 17:33:27,732 [myid:2] - INFO  [FollowerRequestProcessor:2:[email protected]] - FollowerRequestProcessor exited loop!
2016-06-14 17:33:27,732 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - Shutting down
2016-06-14 17:33:27,733 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - shutdown of request processor complete 
2016-06-14 17:33:27,733 [myid:2] - INFO  [CommitProcessor:2:[email protected]] - CommitProcessor exited loop! 
2016-06-14 17:33:27,733 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - Shutting down 
2016-06-14 17:33:27,734 [myid:2] - INFO  [SyncThread:2:[email protected]] - SyncRequestProcessor exited!
2016-06-14 17:33:27,734 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - LOOKING 
2016-06-14 17:33:27,739 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - Reading snapshot /home/hemeng/zookeeper-3.4.7/data/zookeepe 
r/version-2/snapshot.c00000002[QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] – LEADING 
2016-06-14 17:33:27,957 [myid:2] - INFO  [QuorumPeer[myid=2]/0:0:0:0:0:0:0:0:2181:[email protected]] - LEADING - LEADER ELECTION TOOK - 222

當叢集中已經有過半的Follower伺服器完成了和Leader伺服器的狀态同步，那麼整個服務架構就可以進入消息廣播模式了。當一台同樣遵守ZAB協定的伺服器啟動後加入到叢集中時，如果此時叢集中已經存在一個Leader伺服器在負責進行消息廣播，那麼新加入的伺服器就會自覺地進入資料恢複模式：找到Leader所在的伺服器，并與其進行資料同步，然後一起參與到消息廣播流程中去。ZooKeeper設計成隻允許唯一的一個Leader伺服器來進行事務請求的處理。Leader伺服器在接收到用戶端的事務請求後，會生成對應的事務提案并發起一輪廣播協定；而如果叢集中的其他機器接收到用戶端的事務請求，那麼這些非Leader伺服器會首先将這個事務請求轉發給Leader伺服器。

4.選舉三階段

整個ZAB協定主要包括消息廣播和崩潰恢複這兩個過程，進一步可以細分為三個階段，分别是發現、同步和廣播階段。組成ZAB協定的每一個分布式程序，會循環地執行這三個階段，我們将這樣一個循環稱為一個主程序周期。

  • 發現：要求zookeeper叢集必須選舉出一個 Leader 程序，同時 Leader 會維護一個 Follower 可用用戶端清單。将來用戶端可以和這些 Follower節點進行通信。
  • 同步：Leader 要負責将本身的資料與 Follower 完成同步，做到多副本存儲。這樣也是提現了CAP中的高可用和分區容錯。Follower将隊列中未處理完的請求消費完成後，寫入本地事務日志中。
  • 廣播：Leader 可以接受用戶端新的事務Proposal請求，将新的Proposal請求廣播給所有的 Follower。

5. 伺服器啟動時期的Leader選舉核心算法

若進行Leader選舉，則至少需要兩台機器，這裡選取3台機器組成的伺服器叢集為例。在叢集初始化階段，當有一台伺服器Server1啟動時，其單獨無法進行和完成Leader選舉，當第二台伺服器Server2啟動時，此時兩台機器可以互相通信，每台機器都試圖找到Leader，于是進入Leader選舉過程。選舉過程如下

(1) 每個Server發出一個投票。由于是初始情況，Server1和Server2都會将自己作為Leader伺服器來進行投票，每次投票會包含所推舉的伺服器的myid和ZXID，使用(myid, ZXID)來表示，此時Server1的投票為(1, 0)，Server2的投票為(2, 0)，然後各自将這個投票發給叢集中其他機器。

(2) 接受來自各個伺服器的投票。叢集的每個伺服器收到投票後，首先判斷該投票的有效性，如檢查是否是本輪投票、是否來自LOOKING狀态的伺服器。

(3) 處理投票。針對每一個投票，伺服器都需要将别人的投票和自己的投票進行PK，PK規則如下

  • 優先檢查ZXID。ZXID比較大的伺服器優先作為Leader。
  • 如果ZXID相同，那麼就比較myid。myid較大的伺服器作為Leader伺服器。

對于Server1而言，它的投票是(1, 0)，接收Server2的投票為(2, 0)，首先會比較兩者的ZXID，均為0，再比較myid，此時Server2的myid最大，于是更新自己的投票為(2, 0)，然後重新投票，對于Server2而言，其無須更新自己的投票，隻是再次向叢集中所有機器發出上一次投票資訊即可。

(4) 統計投票。每次投票後，伺服器都會統計投票資訊，判斷是否已經有過半機器接受到相同的投票資訊，對于Server1、Server2而言，都統計出叢集中已經有兩台機器接受了(2, 0)的投票資訊，此時便認為已經選出了Leader。

(5) 改變伺服器狀态。一旦确定了Leader，每個伺服器就會更新自己的狀态，如果是Follower，那麼就變更為FOLLOWING，如果是Leader，就變更為LEADING。

6. 伺服器運作時期的Leader選舉核心算法

在Zookeeper運作期間，Leader與非Leader伺服器各司其職，即便當有非Leader伺服器當機或新加入，此時也不會影響Leader，但是一旦Leader伺服器挂了，那麼整個叢集将暫停對外服務，進入新一輪Leader選舉，其過程和啟動時期的Leader選舉過程基本一緻。假設正在運作的有Server1、Server2、Server3三台伺服器，目前Leader是Server2，若某一時刻Leader挂了，此時便開始Leader選舉。選舉過程如下：

(1) 變更狀态。Leader挂後，餘下的非Observer伺服器都會講自己的伺服器狀态變更為LOOKING，然後開始進入Leader選舉過程。

(2) 每個Server會發出一個投票。在運作期間，每個伺服器上的ZXID可能不同，此時假定Server1的ZXID為123，Server3的ZXID為122；在第一輪投票中，Server1和Server3都會投自己，産生投票(1, 123)，(3, 122)，然後各自将投票發送給叢集中所有機器。

(3) 接收來自各個伺服器的投票。與啟動時過程相同。

(4) 處理投票。與啟動時過程相同，此時，Server1将會成為Leader。

(5) 統計投票。與啟動時過程相同。

(6) 改變伺服器的狀态。與啟動時過程相同。

7.ZAB與Paxos的差別

ZAB協定并不是Paxos算法的一個典型實作，在講解ZAB和Paxos之間的差別之間，我們首先來看下兩者的聯系。

兩者都存在一個類似于Leader程序的角色，由其負責協調多個Follower程序運作。

Leader程序都會等待超過半數的Follower做出正确的回報後，才會将一個提案進行送出。

在ZAB協定中，每個Proposal中都包含了一個epoch值，用來代表目前的Leader周期，在Paxos算法中，同樣存在這樣的一個辨別，隻是名字變成了Ballot。

在Paxos算法中，一個新選舉産生的主程序會進行兩個階段的工作。第一階段被稱為讀階段，在這個階段中，這個新的主程序會通過和所有其他程序進行通信的方式來收集上一個主程序提出的提案，并将它們送出。第二階段被稱為寫階段，在這個階段，目前主程序開始提出它自己的提案。在Paxos算法設計的基礎上，ZAB協定額外添加了一個同步階段。在同步階斷之前，ZAB協定也存在一個和Paxos算法中的讀階段非常類似的過程，稱為發現階段。在同步階段中，新的Leader會确儲存在過半的Follower已經送出了之前Leader周期中的所有事務Proposal。這一同步階段的引入，能夠有效地保證Leader在新的周期中提出事務Proposal之前，所有的程序都已經完成了對之前所有事務Proposal的送出。一旦完成同步階段後，那麼ZAB就會執行和Paxos算法類似的寫階段。

總的來講，Paxos算法和ZAB協定的本質差別在于，兩者的設計目标不一樣。ZAB協定主要用于建構一個高可用的分布式資料主備系統，例如ZooKeeper，而Paxos算法則是用于建構一個分布式的一緻性狀态機系統。

四、Zookeeper的Quorum機制-談談怎樣解決腦裂(split-brain)

Split-Brain問題說的是1個叢集如果發生了網絡故障，很可能出現1個叢集分成了兩部分，而這兩個部分都不知道對方是否存活，不知道到底是網絡問題還是直接機器down了，是以這兩部分都要選舉1個Leader，而一旦兩部分都選出了Leader, 并且網絡又恢複了，那麼就會出現兩個Brain的情況，整個叢集的行為不一緻了。

在使用zookeeper的過程中,我們經常會看到這樣一些說法:

  • zookeeper cluster的節點數目必須是奇數。
  • zookeeper 叢集中必須超過半數節點(Majority)可用，整個叢集才能對外可用。

所謂整個叢集是否可用，隐含的一個意思就是整個叢集還能夠選舉出一個”Leader”。ZooKeeper預設設定的是采用Majority Qunroms的方式來支援Leader選舉。以這種方式來防止Split-Brain問題出現，即隻有叢集中超過半數節點投票才能選舉出Leader。這樣的方式可以確定leader的唯一性,要麼選出唯一的一個leader,要麼選舉失敗。

在ZooKeeper中Quorums有2個作用：

  • 叢集中最少的節點數用來選舉Leader保證叢集可用
  • 通知用戶端資料已經安全儲存前叢集中最少數量的節點數已經儲存了該資料。一旦這些節點儲存了該資料，用戶端将被通知已經安全儲存了，可以繼續其他任務。而叢集中剩餘的節點将會最終也儲存了該資料

了解了Quorums就不難了解為什麼叢集中的節點數一般配置為奇數。節點數配置成奇數的叢集的容忍度更高。

舉例如下：

  • 比如3個節點的叢集，Quorums = 2, 也就是說叢集可以容忍1個節點失效，這時候還能選舉出1個lead，叢集還可用；
  • 比如4個節點的叢集，它的Quorums = 3，Quorums要超過3，相當于叢集的容忍度還是1，如果2個節點失效，那麼整個叢集還是無效的；

是以4個節點的叢集的容忍度 = 3個節點的叢集的容忍度，但是4個節點的叢集多了1個節點，相當于浪費了資源。

更極端的例子是100個節點的叢集，如果網絡問題導緻分為兩個部分，50個節點和50個節點，這樣整個叢集還是不可用的，因為按照Quorums的方式必須51個節點才能保證選出1個Leader。這時候可以采用Weight權重的方式，有些節點的權值高，有些節點的權值低，最後計算權值，隻要權值過半，也能選出1個Leader。

五、總結

  1. 通常在分布式系統中，構成一個叢集的每一台機器都有自己的角色，最典型的叢集模式就是Master/Slave模式（主備模式）。在這種模式中，我們把能夠處理所有寫操作的機器稱為Master機器，把所有通過異步複制方式擷取最新資料，并提供讀服務的機器稱為Slave機器。在Paxos算法内部，引入了Proposer、Acceptor和Learner三種角色。而在ZooKeeper中，這些概念也做了改變，它沒有沿用傳統的Master/Slave概念，而是引入了Leader、Follower和Observer三種角色。本文通過對Paxos和ZooKeeper ZAB協定進行講解，讓讀者有一些基本的分布式選舉算法方面的認識。
  2. 引入半數選舉機制，必須獲得半數以上票數選舉生效，可以有效避免這種情況下的腦裂問題。

我的微信公衆号：架構真經（id：gentoo666），分享Java幹貨，高并發程式設計，熱門技術教程，微服務及分布式技術，架構設計，區塊鍊技術，人工智能，大資料，Java面試題，以及前沿熱門資訊等。每日更新哦！

算法進階（5）-分布式系統選舉算法及腦裂一、選舉算法定義二、選舉算法分類三、Zookeeper的ZAB協定四、Zookeeper的Quorum機制-談談怎樣解決腦裂(split-brain)五、總結

參考資料：

  1. https://www.jianshu.com/p/f0c717501cee
  2. https://www.jianshu.com/p/c2ced54736aa
  3. https://blog.csdn.net/xiaqunfeng123/article/details/51712983
  4. https://blog.csdn.net/michaelzhou224/article/details/52304777
  5. https://www.jianshu.com/p/2bceacd60b8a
  6. https://blog.csdn.net/varyall/article/details/80151205
  7. https://blog.csdn.net/ai_xiangjuan/article/details/78156505
算法進階 分布式 選舉算法 腦裂
上一篇: c語言水仙花數算法分析,水仙花數之C語言經典案例分析
下一篇: 源碼分析Elasticsearch Master選舉過程

繼續閱讀