這篇文章主要描述分散式技術中的選舉演算法，分散式選舉是為選出一個主節點，由它來協調和管理其他節點，保證集群有序運行和節點間數據的一致性。涉及到的選舉演算法包括Bully演算法、Raft演算法和ZAB演算法。 ...
分散式選舉演算法
為什麼需要分散式選舉？
分散式意味著我們的應用部署在一個集群中，集群包含多個節點或者伺服器，對於一個集群來說，多個節點是怎麼協同工作的呢？我們需要有一個主節點來負責對其他節點的協調和管理。
分散式選舉是為了選出一個主節點，由它來協調和管理其他節點，以保證集群有序運行和節點間數據的一致性。
常見的分散式選舉演算法有哪些？
分散式選舉演算法一般會分為兩類：
- 基於序號選舉的演算法（例如Bully演算法）
- 多數派演算法（Raft，ZAB等）
Bully演算法
Bully演算法中，節點的角色有兩種：普通節點和主節點。初始化時，所有節點都是平等的，都是普通節點，並且都有成為主節點的權利，但是當選主結束後，有且僅有一個節點成為主節點，其他所有節點變為普通節點。
Bully演算法在選舉的過程中，需要使用3種消息：
- Election消息，用於發起選舉。
- Alive消息，對Election消息的應答。
- Victory消息，競選成功的主節點向其他節點發送的宣誓主權的消息。
Bully演算法選舉的原則是“長者為大”，它假設集群中的每個節點都知道其他節點的ID。整個選舉過程如下：
- 集群中每個節點判斷自己的ID是否為當前活著的節點中ID最大的，如果是，則直接向其他節點發送Victory消息，宣示自己的主權。
- 如果自己不是當前活著的節點中ID最大的，則向比自己ID大的所有節點發送Election消息，並等待其他節點的回覆。
- 若在給定的時間範圍內，本節點沒有收到其他節點回覆的Alive消息，則認為自己成為主節點，並向其他節點發送Victory消息，宣誓自己成為主節點，若接收到來自比自己ID大的節點的Alive消息，則等待其他節點發送Victory消息。
- 若本節點收到比自己ID小的節點發送的Election消息，則回覆一個Alive消息，告知其他節點，我比你大，重新選舉。
Bully演算法的優點是選舉速度快、演算法複雜度低、簡單易實現。它的缺點在於需要每個節點都保存全局的節點信息，因此額外信息存儲比較多，其次，任意一個比當前主節點ID大的新節點或者節點故障後回覆加入集群的時候，都會觸發重新選舉，成為新的主節點，如果該節點頻繁退出、加入集群，就會導致頻繁切主。
Raft演算法
Raft演算法是典型的多數派投票選舉演算法，它的核心思想是“少數服從多數”。
在Raft算中，集群節點的角色有3種：
- Leader，主節點，同一時刻只有一個Leader
- Candidate，候選者，每一個節點都可以成為Candidate，節點在該角色下才可能被選為新的Leader
- Follower，跟隨者，不可以發起選舉。
Raft選舉的流程如下：
- 初始化時，所有節點都是Follower狀態。
- 開始選主時，所有節點的狀態由Follower轉化為Candidate，並向其他節點發送選舉請求。
- 其他節點根據收到的選舉請求的先後順序，回覆是否同意成為主，在每一輪選舉中，一個節點只能投出一張票。
- 如果發起選舉請求的節點獲得超過一半的投票，則成為主節點，其狀態轉化為Leader，其他節點的狀態則由Candidate變為Follower。
- Leader節點和Follower節點之間會定期發送心跳包，來檢測主節點是否正常。
- 當Leader節點的任期到了，即發現其他伺服器開始下一輪選主周期時，Leader節點的狀態也會由Leader降級為Follower，進入新一輪選主。
Raft演算法的優點是選舉速度快、演算法複雜度低、易於實現。它的缺點是要求系統內每個節點都可以相互通信，其需要獲得過半的投票數才能選主成功，因此通信量大。
Kubernetes的選主採用開源組件etcd，etcd的集群管理器etcds，是一個高可用、強一致性的服務發現存儲倉庫，就是採用了Raft演算法實現選主和一致性的。
http://thesecretlivesofdata.com/raft/#election對Raft演算法做了很好的動畫演示，可以很好的幫助我們理解Raft演算法的選舉過程。
ZAB演算法
ZAB選舉演算法是為ZooKeeper實現分散式協調功能而設計的，和Raft演算法相比，ZAB演算法增加了通過節點ID和數據ID作為參考進行選主，節點ID和數據ID越大，標識數據越新，優先成為主節點。
ZAB選舉演算法的核心是“少數服從多數，ID大的節點優先成為主節點”。
ZAB演算法中，集群里的每個節點擁有三種角色：
- Leader，主節點
- Follower，跟隨者節點
- Observer，觀察者，無投票權
選舉過程中，集群中的節點擁有4個狀態：
- Looking狀態，選舉狀態，當節點處於該狀態時，它會認為當前集群中沒有Leader，會進入選舉狀態。
- Leading狀態，領導者狀態，表示已經選擇出主節點，且當前節點為Leader。
- Following狀態，跟隨者狀態，集群中已經選出主節點後，其他非主節點的狀態變更為Following。
- Observing狀態，觀察者狀態，表示當前節點為Observer，持觀望態度，沒有投票權和選舉權。
投票過程中，每個節點都有一個唯一的三元組(service_id, service_zxID, epoch)：
- servier_id：該節點唯一ID
- service_zxID：該節點存放的數據ID，數據ID越大，表示數據越新，選舉權重越大
- epoch：當前選舉論數，一般用邏輯時鐘錶示。
選舉的原則：server_zxID最大者成為Leader，如果server_zxID相同，則service_id最大者成為Leader。
ZAB演算法性能高，對系統無特殊要求，採用廣播方式發送信息，若集群中有n個節點，每個節點同事廣播，則集群中的信息量為n*(n-1)個消息，容易出現廣播風暴，而且消息中增加了節點ID和數據ID，意味著需要知道所有節點的ID和數據ID，所以選舉時間相對較長。但是該演算法穩定性比較好，當有新節點加入或者節點故障恢復後，會觸發選主，但不一定會真正切主，除非新節點或者故障恢復後的節點數據ID和節點ID最大，且獲得投票數過半，才會切主。
ZAB演算法適合大規模分散式場景，例如ZooKeeper。
關於Bully演算法、Raft演算法和ZAB演算法，有一個比較形象的比喻：
- Bully演算法：類似於選武林盟主，誰武功最高，誰來當
- Raft演算法：類似於選總統，誰票數最高，誰來當
- ZAB演算法：類似於選優秀班幹部，是班幹部且票多才可以
更加詳細的比較信息如下表所示。
