為什么要有分布式選舉？

在分布式集群中，主節點承擔著對其他節點的協調與管理職責，其他節點需遵循主節點的安排。主節點的存在能夠保障集群內各節點有序運行，確保數據庫集群寫入數據在每個節點保持一致，即各節點數據完全相同。

然而，若主節點發生故障，整個集群將陷入混亂，如同國家皇帝駕崩導致國家大亂。以數據庫集群為例，主節點故障后，各節點數據可能出現不一致的情況。由此可見，在分布式系統中 “集群不可一刻無主” 。而選舉的核心意義就在于推選出主節點，借助主節點對其他節點進行協調管理，從而保障集群穩定有序運行，并維持節點間數據的一致性。

分布式選舉的算法

Bully 算法是一種用于集群選主的算法，其選舉原則是 “長者為大”，即在存活節點中選擇 ID 最大的節點作為主節點。該算法中節點角色分為普通節點和主節點，初始化時所有節點均為普通節點，主節點故障或失聯后會重新選主。

選舉過程依賴 3 種消息：Election 消息用于發起選舉；Alive 消息是對 Election 消息的應答；Victory 消息由競選成功的主節點向其他節點發送，宣告主權。

算法假設集群中每個節點都知曉其他節點的 ID，具體選舉流程為：節點判斷自身 ID 是否最大，若是則直接發送 Victory 消息；若不是，則向 ID 比自己大的節點發送 Election 消息并等待回復。若在規定時間內未收到 Alive 消息，該節點認為自己成為主節點并發送 Victory 消息；若收到比自己 ID 大的節點的 Alive 消息，就等待 Victory 消息；若收到比自己 ID 小的節點的 Election 消息，則回復 Alive 消息，通知對方重新選舉 。

圖片

Bully 算法在開源軟件中得到應用，如 MongoDB 副本集故障轉移功能采用節點最后操作時間戳表示 ID，以時間戳最新且存活的節點為主節點。該算法選舉規則霸道簡單，以活著且 ID 最大的節點為主，其他節點服從。其優點是選舉速度快、算法復雜度低、易實現；缺點是每個節點需掌握全局節點信息，額外信息存儲量大，并且當比當前主節點 ID 大的新節點加入或故障恢復節點重新加入集群時，易觸發重新選舉，若此類節點頻繁退出、加入，會造成主節點頻繁切換 。

民主投票：Raft 算法

Raft 算法是多數派投票選舉算法，選舉機制類似民主投票，核心是 “少數服從多數”，得票最多的節點成為主節點。

該算法中集群節點有 3 種角色：Leader（主節點，同一時刻唯一，負責協調管理其他節點）、Candidate（候選者，節點在此角色下可被選為新 Leader）、Follower（跟隨者，不能發起選舉）。

選舉流程為：初始化時節點都是 Follower 狀態；開始選主時節點轉為 Candidate 并發送選舉請求；其他節點按請求先后順序回復是否同意，且每輪選舉一個節點只能投一票；發起請求的節點獲超半數投票就成為 Leader，其他節點降為 Follower；Leader 和 Follower 間定期發心跳包檢測主節點狀態；當 Leader 任期到，發現其他服務器進入下輪選主周期時，Leader 降為 Follower，開啟新一輪選主。

圖片

Raft 算法每輪選舉中每個節點僅能投一次票，選舉類似人大代表選舉，有選主和任值兩個時間段，選主階段對應投票，任值階段對應主節點任期，正常任期到會觸發重新選舉，若主節點故障則立刻重新選主。

Google 開源的 Kubernetes 擅長容器管理與調度，一般部署 3 個節點用于數據備份，其中 1 個為主節點，其余為備節點。Kubernetes 選主采用開源的 etcd 組件，etcd 的集群管理器 etcds 是高可用、強一致性的服務發現存儲倉庫，運用 Raft 算法實現選主和數據一致性。

小結一下。Raft 算法具有選舉速度快、算法復雜度低、易于實現的優點；缺點是，它要求系統內每個節點都可以相互通信，且需要獲得過半的投票數才能選主成功，因此通信量大。該算法選舉穩定性比 Bully 算法好，這是因為當有新節點加入或節點故障恢復后，會觸發選主，但不一定會真正切主，除非新節點或故障后恢復的節點獲得投票數過半，才會導致切主。

具有優先級的民主投票：ZAB 算法

ZAB 選舉算法是為 ZooKeeper 實現分布式協調功能而設計，是對 Raft 算法的改進，在選主時增加了節點 ID 和數據 ID 作為參考，更注重保證數據的最新性。

使用 ZAB 算法選舉時，集群節點有 Leader（主節點）、Follower（跟隨者節點）、Observer（觀察者，無投票權）三種角色 ，且節點有 Looking（選舉狀態）、Leading（領導者狀態）、Following（跟隨者狀態）、Observing（觀察者狀態）四種狀態。

選舉過程中，每個節點有唯一三元組 (server_id, server_zxID, epoch)，其中 server_zxID 越大數據越新、選舉權重越大。ZAB 選舉算法核心是 “少數服從多數，ID 大的節點優先成為主”，通過 (vote_id, vote_zxID) 表明投票對象。選主原則是 server_zxID 最大者成為 Leader，若 server_zxID 相同，則 server_id 最大者成為 Leader。

小結:ZAB 算法性能高，對系統無特殊要求，以廣播方式發送信息，但易引發廣播風暴，因需對比節點 ID 和數據 ID，選舉時間較長。不過該算法選舉穩定性好，新節點加入或故障恢復節點重新加入時，僅當節點數據 ID 和節點 ID 最大且獲過半投票才會切主。

三種選舉算法的對比分析

知識擴展：為什么“多數派”選主算法通常采用奇數節點，而不是偶數節點呢？

圖片

在集群中，當出現兩個節點均獲得一半投票的情況時，究竟該讓哪個節點成為主節點呢？實際上，在這種情形下是無法確定主節點的，必須要進行重新投票選舉。然而，即便是重新開展投票選舉流程，這兩個節點再次擁有相同投票數量的可能性依然很大。鑒于這種情況，多數派選主算法一般都會選用奇數個節點來進行選舉。這也就是為什么我們常常會看到諸如 ZooKeeper、etcd、Kubernetes 等開源軟件，在進行選主操作時均采用奇數個節點的一個關鍵因素。