分散式選舉的原因

分散式系統中需要一個主節點，該節點用於負責對其他節點進行協調和管理。同時主節點的存在能夠保證分散式集群數據的一致性。

分散式選舉演算法

1. Bully演算法

選舉原則：偏向於讓ID更大的節點作為集群的leader

前提條件：假設集群中所有節點都知道其他節點的id

消息類型/節點狀態：

　　election消息,用於發起選舉

       alive消息，用於對election消息的應答

       victory消息，競選成功的主節點向其他節點發送宣誓主權的消息

選舉過程：

　　觸發條件: ID比當前主節點大的節點加入集群，主節點故障

       具體過程: 

       (1) 每個節點判斷自己的ID是否最大，最大則直接發送victory消息

       (2) 如果ID不是最大的，則向比自己id大的節點發送election消息

       (3) 在給定時間範圍內，本節點沒有收到其他節點回覆的alive消息，則認為自己是主節點，並向其他節點發送victory消息；若收到alive消息，則等待其他節點的victory消息

       (4) 收到比本節點id小的節點發送的election消息則回覆一個alive消息

優缺點：

　　優點： 選舉速度快，演算法複雜度低，簡單易實現

       缺點：每個節點額外存儲信息較多，任意一個ID比前主節點大的節點加入時都會觸發重新選舉過程

軟體舉例： MongoDB

2. Raft演算法

選舉原則：獲得多數投票的集群節點成為leader

前提條件：假設集群中所有節點之間都能相互通信

消息類型/節點狀態：

　　leader: 主節點

       candidate：候選者，每個節點都可以成功候選者

       follower：leader的跟隨者

選舉過程：

　　觸發條件: leader任期到了，新節點加入集群或者主節點故障

       具體過程: 

       (1) 初始化所有節點為follower，開始選舉時有follower轉化為candidate，並向其他節點發送選舉消息

       (2) 收到消息的節點進行投票，票數超過一半的節點成為主節點，其他節點由candidate降為follower

優缺點：

　　優點： 選舉速度快，演算法複雜度低，簡單易實現，當有新節點加入或者節點故障恢復時不會觸發真正的切主

       缺點：每個節點之間都需要相互通信，所以通信量較大

軟體舉例： ETCD

 3. ZAB(Zookeeper Atomic Broadcast)選舉演算法

選舉原則：少數服從多數，節點id大的或者數據最新的優先成為主節點

消息類型/節點狀態：

       投票信息 <epoch, vote_id, vote_zxID>

　　leader: 主節點

       follower：leader的跟隨者

       observer: 觀察者，無投票權

      Looking，Following，Leading，Observing

優缺點：

　　優點： 穩定性較好，性能較好

       缺點：容易出現廣播風暴，投票時間較長，複雜度較高

軟體舉例：zookeeper

總結圖

說明:

 本文是極客時間付費課程《分散式技術原理與演算法解析》筆記