為什么要有分布式選舉？

在分布式集群中，主節(jié)點承擔(dān)著對其他節(jié)點的協(xié)調(diào)與管理職責(zé)，其他節(jié)點需遵循主節(jié)點的安排。主節(jié)點的存在能夠保障集群內(nèi)各節(jié)點有序運行，確保數(shù)據(jù)庫集群寫入數(shù)據(jù)在每個節(jié)點保持一致，即各節(jié)點數(shù)據(jù)完全相同。

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

分布式選舉的算法

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

選舉過程依賴 3 種消息：Election 消息用于發(fā)起選舉；Alive 消息是對 Election 消息的應(yīng)答；Victory 消息由競選成功的主節(jié)點向其他節(jié)點發(fā)送，宣告主權(quán)。

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

圖片

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

民主投票：Raft 算法

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

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

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

圖片

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

Google 開源的 Kubernetes 擅長容器管理與調(diào)度，一般部署 3 個節(jié)點用于數(shù)據(jù)備份，其中 1 個為主節(jié)點，其余為備節(jié)點。Kubernetes 選主采用開源的 etcd 組件，etcd 的集群管理器 etcds 是高可用、強(qiáng)一致性的服務(wù)發(fā)現(xiàn)存儲倉庫，運用 Raft 算法實現(xiàn)選主和數(shù)據(jù)一致性。

小結(jié)一下。Raft 算法具有選舉速度快、算法復(fù)雜度低、易于實現(xiàn)的優(yōu)點；缺點是，它要求系統(tǒng)內(nèi)每個節(jié)點都可以相互通信，且需要獲得過半的投票數(shù)才能選主成功，因此通信量大。該算法選舉穩(wěn)定性比 Bully 算法好，這是因為當(dāng)有新節(jié)點加入或節(jié)點故障恢復(fù)后，會觸發(fā)選主，但不一定會真正切主，除非新節(jié)點或故障后恢復(fù)的節(jié)點獲得投票數(shù)過半，才會導(dǎo)致切主。

具有優(yōu)先級的民主投票：ZAB 算法

ZAB 選舉算法是為 ZooKeeper 實現(xiàn)分布式協(xié)調(diào)功能而設(shè)計，是對 Raft 算法的改進(jìn)，在選主時增加了節(jié)點 ID 和數(shù)據(jù) ID 作為參考，更注重保證數(shù)據(jù)的最新性。

使用 ZAB 算法選舉時，集群節(jié)點有 Leader（主節(jié)點）、Follower（跟隨者節(jié)點）、Observer（觀察者，無投票權(quán)）三種角色 ，且節(jié)點有 Looking（選舉狀態(tài)）、Leading（領(lǐng)導(dǎo)者狀態(tài)）、Following（跟隨者狀態(tài)）、Observing（觀察者狀態(tài)）四種狀態(tài)。

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

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

三種選舉算法的對比分析

知識擴(kuò)展：為什么“多數(shù)派”選主算法通常采用奇數(shù)節(jié)點，而不是偶數(shù)節(jié)點呢？

圖片

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