前言

之前在學(xué)習(xí)MongoDB復(fù)制集時(shí)發(fā)現(xiàn)網(wǎng)上的很多相關(guān)的分享都是針對(duì)r3.2.0以前的版本扮授，新版本對(duì)選舉機(jī)制做了較大的更改，但是在網(wǎng)上大多都是一筆帶過板丽。于是寫過一篇《MongoDB選舉機(jī)制》呈枉。當(dāng)時(shí)主要結(jié)合了官網(wǎng)最新的文檔和部分源碼。由于官網(wǎng)介紹比較泛泛埃碱，源碼閱讀的時(shí)候又受限于個(gè)人能力與時(shí)間猖辫，最終只整理了選舉相關(guān)的核心邏輯，對(duì)應(yīng)復(fù)雜的條件檢查和數(shù)據(jù)結(jié)構(gòu)沒有深入的了解砚殿。最近了解了一些分布式一致性算法之后啃憎，打算換一個(gè)角度從協(xié)議層面重新整理一下MongoDB的選舉。本文簡(jiǎn)要介紹分布式系統(tǒng)一致性相關(guān)的概念似炎，重點(diǎn)介紹Bully算法和Raft算法在MongoDB選舉中的應(yīng)用辛萍。

分布式系統(tǒng)簡(jiǎn)介

分布式系統(tǒng)是一個(gè)硬件或軟件組件分布在不同的網(wǎng)絡(luò)計(jì)算機(jī)上，彼此之間僅僅通過消息傳遞進(jìn)行通信和協(xié)調(diào)的系統(tǒng)羡藐。分布式系統(tǒng)具有分布性贩毕、對(duì)等性、并發(fā)性仆嗦、缺乏全局時(shí)鐘辉阶、故障總會(huì)發(fā)生的特點(diǎn)，由于這些特點(diǎn)導(dǎo)致了分布式系統(tǒng)中的一致性難題。

CAP理論

分布式系統(tǒng)的CAP理論：

CAP理論告訴我們谆甜，一個(gè)分布式系統(tǒng)不可能同時(shí)滿足一致性(C)垃僚，可用性(A)，分區(qū)容錯(cuò)性(P)這三個(gè)基本需求规辱，最多只能同時(shí)滿足其中兩項(xiàng)谆棺。

• 分布式環(huán)境中的一致性是指數(shù)據(jù)在多個(gè)副本之間是否能夠保持一致的特性。
• 可用性是指系統(tǒng)必須一致處于可用的狀態(tài)按摘，對(duì)用用戶的請(qǐng)求能夠在有限時(shí)間內(nèi)返回結(jié)果包券。其中，“有限時(shí)間”是相對(duì)的炫贤，是用戶可接受的合理響應(yīng)時(shí)間溅固；“返回結(jié)果”是期望的結(jié)果，可以是成功或失敗兰珍，不能是用戶不能接受的結(jié)果侍郭。
• 分布式系統(tǒng)在遇到網(wǎng)絡(luò)分區(qū)故障時(shí)，仍能夠?qū)ν馓峁M足一致性和可用性的服務(wù)掠河，除非整個(gè)網(wǎng)絡(luò)發(fā)生故障亮元。

由于分區(qū)容錯(cuò)性是分布式系統(tǒng)首先要保證的，所以只能在一致性和可用性之間找平衡唠摹。

BASE理論

BASE是Basically Available（基本可用）爆捞、Soft state（軟狀態(tài)）和Eventually consistent（最終一致）三個(gè)短語的簡(jiǎn)寫，基于CAP發(fā)展而來勾拉，主要解決一致性和可用性之間的平衡煮甥。

• 基本可用是指允許故障發(fā)生時(shí)損失部分可用性，但不是說系統(tǒng)不可用藕赞。比如MongoDB選舉過程中系統(tǒng)是只讀的成肘。
• 軟狀態(tài)是指允許數(shù)據(jù)存在中間狀態(tài)，既允許數(shù)據(jù)不同副本之間的同步過程存在延時(shí)斧蜕。
• 最終一致是指數(shù)據(jù)副本在經(jīng)過一段時(shí)間的軟狀態(tài)后最終達(dá)到一致双霍。最終一致是一種特殊的弱一致性。

Paxos批销，Raft洒闸，ZAB等常見的分布式一致性算法都是符合BASE理論。

MongoDB的選舉機(jī)制

MongoDB復(fù)制集的目的是提供高可用性风钻，如果一個(gè)寫操作被復(fù)制到大多數(shù)節(jié)點(diǎn)顷蟀，只要任意大多數(shù)節(jié)點(diǎn)可用，那么數(shù)據(jù)就是可靠的骡技。復(fù)制集一般包含一個(gè)Primary和若干個(gè)Secondary節(jié)點(diǎn)鸣个。選舉機(jī)制主要負(fù)責(zé)在集群初始化及節(jié)點(diǎn)發(fā)生變化時(shí)重新選舉主節(jié)點(diǎn)羞反，保證系統(tǒng)可用性。

MongoDB節(jié)點(diǎn)之間維護(hù)心跳檢查囤萤，主節(jié)點(diǎn)選舉由心跳觸發(fā)昼窗。MongoDB復(fù)制集成員會(huì)向自己之外的所有成員發(fā)送心跳并處理響應(yīng)信息，因此每個(gè)節(jié)點(diǎn)都維護(hù)著從該節(jié)點(diǎn)POV看到的其他所有節(jié)點(diǎn)的狀態(tài)信息涛舍。節(jié)點(diǎn)根據(jù)自己的集群狀態(tài)信息判斷是否需要發(fā)起選舉澄惊。

MongoDB r3.2.0以前選舉協(xié)議是基于Bully算法，從r3.2.0開始默認(rèn)使用基于Raft算法的選舉策略富雅。MongoDB選舉過程比較復(fù)雜掸驱，下面的在介紹算法應(yīng)用時(shí)重點(diǎn)關(guān)注與算法應(yīng)用相關(guān)的邏輯。

Bully算法

算法描述

Bully算法是一種相對(duì)簡(jiǎn)單的協(xié)調(diào)者競(jìng)選算法没佑。算法的主要思想是集群的每個(gè)成員都可以聲明它是協(xié)調(diào)者并通知其他節(jié)點(diǎn)毕贼。別的節(jié)點(diǎn)可以選擇接受這個(gè)聲稱或是拒絕并進(jìn)入?yún)f(xié)調(diào)者競(jìng)爭(zhēng)。被其他所有節(jié)點(diǎn)接受的節(jié)點(diǎn)才能成為協(xié)調(diào)者蛤奢。節(jié)點(diǎn)按照一些屬性來判斷誰應(yīng)該勝出鬼癣。

Bully算法中有三類消息：

• Election Message：宣布發(fā)起選舉
• Answer Message：響應(yīng)選舉消息
• Victory Message：由選舉勝利者發(fā)送，宣布勝利

當(dāng)一個(gè)節(jié)點(diǎn)從故障中恢復(fù)或者監(jiān)測(cè)到主節(jié)點(diǎn)故障時(shí)，執(zhí)行過程如下：

• 如果該節(jié)點(diǎn)具有最高ID，則向其他節(jié)點(diǎn)發(fā)送Victory Message遗遵，成為主節(jié)點(diǎn)并結(jié)束選舉，否則向所有編號(hào)比它大的節(jié)點(diǎn)發(fā)送Election Message章郁；
• 如果該節(jié)點(diǎn)規(guī)定時(shí)間內(nèi)沒有收到答復(fù)，則向其他節(jié)點(diǎn)發(fā)送Victory Message志衍，成為主節(jié)點(diǎn)并結(jié)束選舉驱犹；
• 如果有ID比該節(jié)點(diǎn)大的節(jié)點(diǎn)響應(yīng)，則等待Victory Message（如果一定時(shí)間后仍未收到Victory Message足画，則重新發(fā)起選舉）
• 如果一個(gè)節(jié)點(diǎn)收到較低ID發(fā)來的Election Message，它將發(fā)送一個(gè)Answer Message佃牛，并發(fā)送Election Message到更高ID的節(jié)點(diǎn)開始選舉淹辞。
• 如果一個(gè)節(jié)點(diǎn)收到Victory Message，則將發(fā)送者視為主節(jié)點(diǎn)俘侠。

舉例

下面是Bully算法選舉過程的一個(gè)經(jīng)典例子：

image

• 1象缀，最初集群中有5個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)5是一個(gè)公認(rèn)的協(xié)調(diào)者
• 2爷速，如果節(jié)點(diǎn)5掛了央星，并且節(jié)點(diǎn)2和節(jié)點(diǎn)3同時(shí)發(fā)現(xiàn)了這一情況。兩個(gè)節(jié)點(diǎn)開始競(jìng)選并發(fā)送競(jìng)選消息給ID更大的節(jié)點(diǎn)惫东。
• 3莉给，節(jié)點(diǎn)4淘汰了節(jié)點(diǎn)2和3毙石，節(jié)點(diǎn)3淘汰了節(jié)點(diǎn)2
• 4，這時(shí)候節(jié)點(diǎn)1察覺了節(jié)點(diǎn)5失效并向所有ID更大的節(jié)點(diǎn)發(fā)送了競(jìng)選信息
• 5颓遏，節(jié)點(diǎn)2徐矩、3和4都淘汰了節(jié)點(diǎn)1
• 6，節(jié)點(diǎn)4發(fā)送競(jìng)選信息給節(jié)點(diǎn)5
• 7叁幢，節(jié)點(diǎn)5沒有響應(yīng)滤灯，所以節(jié)點(diǎn)4宣布自己當(dāng)選并向其他節(jié)點(diǎn)通告了這一消息

算法應(yīng)用

MongoDB在實(shí)現(xiàn)時(shí)對(duì)Bully算法做了一些調(diào)整：

• Bully ID對(duì)應(yīng)MongoDB節(jié)點(diǎn)的priority，且兩個(gè)節(jié)點(diǎn)priority可能相等
• Secondary發(fā)現(xiàn)集群中沒有Primary后不止向更高priority節(jié)點(diǎn)曼玩，而是向所有節(jié)點(diǎn)發(fā)送選舉
• 收到選舉請(qǐng)求的節(jié)點(diǎn)發(fā)現(xiàn)候選節(jié)點(diǎn)中有更高priority節(jié)點(diǎn)時(shí)投veto票鳞骤，每個(gè)veto會(huì)將得票數(shù)-10000
• MongoDB沒有vote權(quán)限的節(jié)點(diǎn)才能投票
• 發(fā)起選舉過程中的節(jié)點(diǎn)不會(huì)投票
• 選舉發(fā)起和投票過程中包含復(fù)雜的條件判斷，但不影響協(xié)議理解
• 通過審核的節(jié)點(diǎn)會(huì)投vote票黍判，每個(gè)vote會(huì)將得票數(shù)+1
• 最終得票數(shù)超過集群可投票節(jié)點(diǎn)數(shù)一半時(shí)通過選舉豫尽，發(fā)起節(jié)點(diǎn)成為Primary。
• 當(dāng)?shù)闷辈蛔阋话霑r(shí)样悟，發(fā)起者隨機(jī)退讓拂募，隨機(jī)sleep 0 到1 秒后重新發(fā)起選舉。
• 引入30s的“選舉鎖”窟她，在持有鎖的時(shí)間內(nèi)不得給其他發(fā)起者投票陈症，避免一個(gè)節(jié)點(diǎn)同時(shí)給兩個(gè)發(fā)起者投票。
• 如果新選舉出的主節(jié)點(diǎn)立馬掛掉,至少需要30s時(shí)間重新選主震糖。

Raft算法

新版本的MongoDB用Raft取代了Bully录肯。

算法描述

Raft將問題拆成數(shù)個(gè)子問題分開解決：

• 領(lǐng)袖選舉（Leader Election）
• 記錄復(fù)寫（Log Replication）
• 安全性（Safety）

這里我們主要關(guān)注領(lǐng)袖選舉。
Raft cluster中為服務(wù)器定義了三種角色：

• Leader：領(lǐng)導(dǎo)者
• Flower：追隨者
• Candidate：候選者

在正常情況下吊说，集群中只有一個(gè) leader 并且其他的節(jié)點(diǎn)全部都是 follower 论咏。Follower 都是被動(dòng)的：他們不會(huì)發(fā)送任何請(qǐng)求，只是簡(jiǎn)單的響應(yīng)來自 leader 和 candidate 的請(qǐng)求颁井。三種角色的轉(zhuǎn)換關(guān)系：

image

Raft用Term區(qū)分每一次任期（包含一次選舉）厅贪，Term在Raft中起到邏輯時(shí)鐘（時(shí)序）的作用，Term是單調(diào)遞增的雅宾。每個(gè)節(jié)點(diǎn)都保存當(dāng)前的Term养涮，并在服務(wù)器間通信中包含Term字段。
Raft為實(shí)現(xiàn)一致性定義了兩種基本RPC：

• 請(qǐng)求投票（RequestVote） RPC 由 candidate 在選舉期間發(fā)起
• 追加條目（AppendEntries）RPC 由 leader 發(fā)起眉抬，用來復(fù)制日志和提供一種心跳機(jī)制

Raft 用心跳來觸發(fā) leader 選舉贯吓。當(dāng)服務(wù)器程序啟動(dòng)時(shí)，他們都是 follower 蜀变。一個(gè)服務(wù)器節(jié)點(diǎn)只要能從 leader 或 candidate 處接收到有效的 RPC 就一直保持 follower 狀態(tài)悄谐。Leader 周期性地向所有 follower 發(fā)送心跳（不包含日志條目的 AppendEntries RPC）來維持自己的地位。如果一個(gè) follower 在一段選舉超時(shí)時(shí)間內(nèi)沒有接收到任何消息库北，它就假設(shè)系統(tǒng)中沒有可用的 leader 爬舰，然后開始進(jìn)行選舉以選出新的 leader 们陆。

選舉規(guī)則中有一些限制條件：

• 對(duì)于同一個(gè)任期，每個(gè)服務(wù)器節(jié)點(diǎn)只會(huì)投給一個(gè) Candidate 洼专，按照先來先服務(wù)的原則棒掠。
• 只有當(dāng)候選人的操作日志至少跟投票人一樣新時(shí)，才投贊同票屁商。
• 如果一個(gè) Follower 在一段選舉超時(shí)時(shí)間內(nèi)沒有接收到任何消息烟很，則發(fā)起選舉。
• 每個(gè)節(jié)點(diǎn)的選舉超時(shí)有一定隨機(jī)性蜡镶，新任期重置選舉超時(shí)雾袱。

下面詳細(xì)的介紹一下選舉的過程：

• follower 先增加自己的當(dāng)前任期號(hào)并且轉(zhuǎn)換到 Candidate 狀態(tài)。
• 投票給自己并且并行地向集群中的其他服務(wù)器節(jié)點(diǎn)發(fā)送 RequestVote RPC官还。
• Candidate 會(huì)一直保持當(dāng)前狀態(tài)直到以下三件事情之一發(fā)生：
  • (a) 收到過半的投票芹橡，贏得了這次的選舉
  • (b) 其他的服務(wù)器節(jié)點(diǎn)成為 leader
  • (c) 一段時(shí)間之后沒有任何獲勝者。

Candidate 贏得選舉
當(dāng)一個(gè) Candidate 獲得集群中過半服務(wù)器節(jié)點(diǎn)針對(duì)同一個(gè)任期的投票望伦，它就贏得了這次選舉并成為 Leader 林说。對(duì)于同一個(gè)任期，每個(gè)服務(wù)器節(jié)點(diǎn)只會(huì)投給一個(gè) Candidate 屯伞，按照先來先服務(wù)的原則腿箩。一旦 Candidate 贏得選舉，就立即成為 Leader 劣摇。然后它會(huì)向其他的服務(wù)器節(jié)點(diǎn)發(fā)送心跳消息來確定自己的地位并阻止新的選舉珠移。

其他節(jié)點(diǎn)成為L(zhǎng)eader
在等待投票期間，Candidate 可能會(huì)收到另一個(gè)聲稱自己是 leader 的服務(wù)器節(jié)點(diǎn)發(fā)來的 AppendEntries RPC 末融。如果這個(gè) Leader 的任期號(hào)（包含在RPC中）不小于 candidate 當(dāng)前的任期號(hào)钧惧，那么 Candidate 會(huì)承認(rèn)該 Leader 的合法地位并回到 Follower 狀態(tài)。 如果 RPC 中的任期號(hào)比自己的小勾习，那么 Candidate 就會(huì)拒絕這次的 RPC 并且繼續(xù)保持 Candidate 狀態(tài)浓瞪。

沒有獲勝者
第三種可能的結(jié)果是 Candidate 既沒有贏得選舉也沒有輸：如果有多個(gè) follower 同時(shí)成為 candidate ，那么選票可能會(huì)被瓜分以至于沒有 candidate 贏得過半的投票巧婶。當(dāng)這種情況發(fā)生時(shí)追逮，每一個(gè)候選人都會(huì)超時(shí)，然后通過增加當(dāng)前任期號(hào)來開始一輪新的選舉粹舵。然而，如果沒有其他機(jī)制的話骂倘，該情況可能會(huì)無限重復(fù)眼滤。

舉例

這里還是用Bully算法中的案例來說明：

• 1，最初集群中有5個(gè)節(jié)點(diǎn)历涝，節(jié)點(diǎn)5是 Leader诅需，此時(shí)集群Term為1
• 2漾唉，如果節(jié)點(diǎn)5掛了，并且節(jié)點(diǎn)2和節(jié)點(diǎn)3同時(shí)發(fā)現(xiàn)這一情況堰塌，兩個(gè)節(jié)點(diǎn)同時(shí)發(fā)起選舉
• 3赵刑，節(jié)點(diǎn)2，3 Term變?yōu)?场刑，轉(zhuǎn)換為Candidate般此，給自己投一票并分別向其中中其他節(jié)點(diǎn)發(fā)送RequestVote RPC。
  • 假如節(jié)點(diǎn)1牵现，4都先收到節(jié)點(diǎn)2铐懊，Term2 RequestVote：
    • 將Term 記為2
    • 都會(huì)為節(jié)點(diǎn)2投票，拒絕后收到的投票瞎疼，此時(shí)節(jié)點(diǎn)2勝出科乎，切換為L(zhǎng)eader 并發(fā)送心跳
    • 節(jié)點(diǎn)3 受到心跳，且Term不小于自己Term贼急，則轉(zhuǎn)換為Flower茅茂，集群達(dá)到最終一致
  • 假如節(jié)點(diǎn)1，4分別先收到節(jié)點(diǎn)2太抓，3Term2 的RequestVote：
    • 將Term 記為2
    • 節(jié)點(diǎn)2空闲，3分別收到1票，拒絕后收到的投票腻异，Candidate節(jié)點(diǎn)各自總共兩票进副，都不到多半(5/2 + 1)，沒有獲勝者
    • 此時(shí)會(huì)由第一個(gè)選舉超時(shí)的節(jié)點(diǎn)悔常，重新發(fā)起新一輪Term為3的選舉

算法應(yīng)用

MongoDB在實(shí)現(xiàn)時(shí)對(duì)Raft算法做了一些調(diào)整：

• Secondary節(jié)點(diǎn)不只是被動(dòng)接受影斑，也會(huì)發(fā)起心跳監(jiān)測(cè)
• 當(dāng)Secondary節(jié)點(diǎn)發(fā)現(xiàn)集群中沒有Primary或者自己priority比Primary高時(shí)發(fā)起選舉
• 保留了優(yōu)先級(jí)但只考慮自己和當(dāng)前主結(jié)點(diǎn)的優(yōu)先級(jí)，其他結(jié)點(diǎn)的優(yōu)先級(jí)不決定選舉與否机打，也不影響投票

對(duì)比

對(duì)比新舊版本的選舉：

• Raft為MongoDB選舉引入Term矫户，取消Bully的選舉鎖，效率更高残邀，更優(yōu)雅的避免重復(fù)投票皆辽，減少投票等待時(shí)間。
• Raft弱化了priority功能芥挣，可能出現(xiàn)非最高priority候選節(jié)點(diǎn)當(dāng)選的情況驱闷，后續(xù)的心跳中會(huì)發(fā)現(xiàn)，并重新選舉空免。
• 取消了veto空另，選舉不一定需要等待心跳超時(shí)。
• 主節(jié)點(diǎn)的降級(jí)有自己發(fā)起蹋砚，效率更高扼菠。

參考

深入理解NoSQL數(shù)據(jù)庫分布式算法及策略
維基百科-Bully algorithm
《從Paxos到ZooKeeper 分布式一致性原理與實(shí)踐》
《Time, Clocks, and the Ordering of Events in a Distributed System》
《MongoDB 中的Raft一致性協(xié)議》