為什么要有分布式選舉？

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

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

分布式選舉的算法

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

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

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

圖片

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

民主投票：Raft 算法

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

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

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

圖片

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

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

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

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

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

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

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

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

三種選舉算法的對(duì)比分析

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

圖片

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