一個(gè)國(guó)家需要領(lǐng)導(dǎo)人制定各種國(guó)家決策，一個(gè)軍隊(duì)也需要最高統(tǒng)領(lǐng)來(lái)制定各種軍事決策，同理，一個(gè)分布式集群也需要一個(gè)領(lǐng)導(dǎo)，來(lái)協(xié)調(diào)整個(gè)集群的事務(wù)，比如保證數(shù)據(jù)一致性(這也是最重要的！)，分布式集群的領(lǐng)導(dǎo)，我們一般稱之為主節(jié)點(diǎn)，這個(gè)主節(jié)點(diǎn)選擇的過(guò)程我們就叫做分布式選舉，而分布式選舉可以有各種不同的方案，這些不同的方案叫做分布式選舉算法，本文就是來(lái)一起來(lái)學(xué)習(xí)常見(jiàn)的分布式選角算法都有哪些，接下來(lái)我們就一起看下吧！
常見(jiàn)的算法有bully，raft，zab，分別來(lái)看下。
2：分布式選舉算法 2.1：bully英文[?b?li] 恐嚇，傷害，盛氣凌人 school bully校園暴力，該算法比較簡(jiǎn)單粗暴，直接選擇id大的一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)。
重慶分公司
重慶分公司
Election消息：發(fā)起選舉
Alive消息：告知自己擁有更大id的消息
Victory消息：自己成為主。告知其它節(jié)點(diǎn)的消息（為什么不是在消息中攜帶自己的id？），則過(guò)程如下：1：如果是節(jié)點(diǎn)判斷自己當(dāng)前擁有大的id，則直接向其它節(jié)點(diǎn)發(fā)送Victory消息，宣布自己成為主節(jié)點(diǎn)
2：如果是當(dāng)前節(jié)點(diǎn)判斷自己并非擁有大id，則向其它節(jié)點(diǎn)發(fā)送Election消息，發(fā)起選舉過(guò)程，如果是指定的時(shí)間內(nèi)都沒(méi)有收到Alive消息回復(fù)，則宣布自己成為主節(jié)點(diǎn)，并再次向其它節(jié)點(diǎn)發(fā)送Victory消息，如果是在指定的時(shí)間內(nèi)收到了大于等于1個(gè)的Alive消息，則等待接收其它節(jié)點(diǎn)發(fā)送的Victory消息如下是一個(gè)可能的選舉過(guò)程節(jié)點(diǎn)2發(fā)起選舉最終節(jié)點(diǎn)3成為主節(jié)點(diǎn)：
選主完成后，正常就不會(huì)重新選主了，除非主節(jié)點(diǎn)故障，或者是主節(jié)點(diǎn)與其它節(jié)點(diǎn)失去聯(lián)系。
優(yōu)點(diǎn)：
算法本身簡(jiǎn)單，容易實(shí)現(xiàn)，選舉速度快缺點(diǎn)：
1：每個(gè)節(jié)點(diǎn)都要存儲(chǔ)其它節(jié)點(diǎn)的id等信息，占用額外存儲(chǔ)空間
2：如果是有id更大的節(jié)點(diǎn)加入集群，或者是id更大的節(jié)點(diǎn)故障后重新加入集群，都會(huì)導(dǎo)致重新選主，如果是頻繁發(fā)生，則會(huì)頻繁出現(xiàn)重新選主，影響集群的穩(wěn)定性因此該算法適合節(jié)點(diǎn)較少的集群，較大集群首先每個(gè)節(jié)點(diǎn)都要存儲(chǔ)大量的信息，其次，當(dāng)節(jié)點(diǎn)增多時(shí)，部分節(jié)點(diǎn)出現(xiàn)故障的概率也會(huì)增大，導(dǎo)致頻繁重新選主。
2.2：raft英文[r?ft] 木排；橡皮艇,這是一種少數(shù)服從多數(shù)的算法。
leader：主節(jié)點(diǎn)，負(fù)責(zé)管理和協(xié)調(diào)其它節(jié)點(diǎn)
candidate：候選節(jié)點(diǎn)，只有處于該角色的節(jié)點(diǎn)才有資格成為leader
follower：leader的跟隨者，當(dāng)選出leader后，其它節(jié)點(diǎn)都是該角色注意：
1：每個(gè)節(jié)點(diǎn)只能投一票。
2：投票原則是時(shí)間優(yōu)先，即如果是某節(jié)點(diǎn)收到投票申請(qǐng)，如果是還沒(méi)有進(jìn)行過(guò)投票，則直接投票，后續(xù)在收到投票申請(qǐng)，因?yàn)橐呀?jīng)投過(guò)票，就不能再次投票了。
集群初始化完成后，每個(gè)節(jié)點(diǎn)的狀態(tài)都是follower,如下：
在經(jīng)過(guò)時(shí)間范圍在150ms到300ms的Election timeout后，會(huì)轉(zhuǎn)換狀態(tài)follower->candidate，如下圖其中一個(gè)節(jié)點(diǎn)首先到達(dá)Election timeout，變?yōu)閏andidate狀態(tài)，如下圖：
如圖節(jié)點(diǎn)A，率先變?yōu)閏andidate狀態(tài)，其term即任期從0變?yōu)?，然后先給自己投一票，所以Vote Count變?yōu)?。然后其會(huì)向NodeB，Node C，發(fā)送投票申請(qǐng)，如下圖：
Node B，Node C，收到Node A的投票請(qǐng)求后，發(fā)現(xiàn)自己的term小于當(dāng)前收到請(qǐng)求term，會(huì)從0更新為1，另外因?yàn)槎歼€未投過(guò)票，所以會(huì)返回同意票，如下圖：
此時(shí)，Node A的得票數(shù)是3，超過(guò)了集群總節(jié)點(diǎn)數(shù)3的多半，成為新的主節(jié)點(diǎn)，其它節(jié)點(diǎn)都成為follower節(jié)點(diǎn)，主節(jié)點(diǎn)會(huì)以heartbeat timeout時(shí)間間隔發(fā)送心跳包到所有follower節(jié)點(diǎn)，以供follower檢測(cè)主節(jié)點(diǎn)狀態(tài)，此時(shí)如下圖：
接下來(lái)當(dāng)其中一個(gè)follower變?yōu)閏andidate狀態(tài)時(shí)，就代表主節(jié)點(diǎn)任期結(jié)束，此時(shí)轉(zhuǎn)換為candidate狀態(tài)節(jié)點(diǎn)，會(huì)發(fā)起重新選舉，如下是發(fā)起投票，和接受投票，如下圖:
Node C成為term 2的新主節(jié)點(diǎn)。
接下來(lái)我們看下raft是如何保證數(shù)據(jù)一致性的，如下當(dāng)前主節(jié)點(diǎn)是Node A：
假設(shè)此時(shí)客戶端向主節(jié)點(diǎn)發(fā)送了set 5，如下圖：
然后主節(jié)點(diǎn)會(huì)將set 5同步給所有的follower，只有當(dāng)主節(jié)點(diǎn)收到大多數(shù)follower數(shù)據(jù)寫(xiě)入確認(rèn)后，才會(huì)提交數(shù)據(jù)，返回給客戶端數(shù)據(jù)寫(xiě)入成功，這樣就保證了數(shù)據(jù)的安全性，如下圖：
后續(xù)有數(shù)據(jù)更新也是這個(gè)流程。
以上我們可以看到，節(jié)點(diǎn)狀態(tài)在不斷的轉(zhuǎn)換，如下?tīng)顟B(tài)轉(zhuǎn)換圖：
1：選舉速度快，復(fù)雜度低。
2：節(jié)點(diǎn)退出后重新加入，雖然會(huì)觸發(fā)重新選主，但是因?yàn)槌^(guò)半數(shù)投票才能成為主節(jié)點(diǎn)，一般一會(huì)導(dǎo)致更換主，所以穩(wěn)定性好缺點(diǎn)：
1：要求所有節(jié)點(diǎn)可通信，因?yàn)槌^(guò)半數(shù)才能選主成功，所以通信量大
2：重新選主產(chǎn)生的主節(jié)點(diǎn)數(shù)據(jù)比較舊，從而導(dǎo)致大量數(shù)據(jù)丟失，即數(shù)據(jù)安全性低英文全程zookeeper atomic broadcast,是zookeeper提出的一種帶有優(yōu)先級(jí)的少數(shù)服從多數(shù)選主算法，該算法和raft相比增加了優(yōu)先級(jí)，而非簡(jiǎn)單的先到先得選票，這里的優(yōu)先級(jí)主要是數(shù)據(jù)的最新程度。
leader：主節(jié)點(diǎn)
follower：跟隨節(jié)點(diǎn)
observer：觀察者，無(wú)權(quán)投票節(jié)點(diǎn)可能的狀態(tài)如下：
looking狀態(tài)：選舉狀態(tài)，無(wú)主節(jié)點(diǎn)時(shí)處于該狀態(tài)
leader狀態(tài)：主節(jié)點(diǎn)狀態(tài)，代表是主節(jié)點(diǎn)，即處于leader角色
follower狀態(tài)：跟隨者狀態(tài)，選主成功后從looking狀態(tài)，變更為該狀態(tài)，即處于follower角色
observer狀態(tài)：觀察者狀態(tài)，即處于observer角色(server_id, server_zxID, epoch)，含義如下：server_id：服務(wù)器id
server_zxID：服務(wù)節(jié)點(diǎn)數(shù)據(jù)id，越大說(shuō)明數(shù)據(jù)越新
epoch：選舉輪數(shù)（為了便于理解，該值可先忽略）對(duì)比過(guò)程是取server_zxID大的投票，相同的則取server_id投票。
初始狀態(tài)時(shí)，epoch=1，即第一輪投票，server_zxID=0,因?yàn)榇藭r(shí)還沒(méi)有任何數(shù)據(jù)，因此先投自己一票，將投自己的三元組投票發(fā)給其它節(jié)點(diǎn)，如下圖：
接著server1，server2，都發(fā)現(xiàn)server3按照優(yōu)先級(jí)，應(yīng)該投一票，因此將vote_id都改為server3的serverID，即3，然后將其放到投票箱中，并廣播出去，如下：
server3成為主節(jié)點(diǎn)后開(kāi)始和follower節(jié)點(diǎn)發(fā)送heartbeat，follower回復(fù)ACK，即開(kāi)始心跳，如下圖：
1：算法穩(wěn)定性好，新節(jié)點(diǎn)加入，故障節(jié)點(diǎn)恢復(fù)，不會(huì)造成頻繁選主缺點(diǎn)：
1：需要額外比較server_zxID，server_id，選舉時(shí)間長(zhǎng)
2：廣播方式發(fā)送消息，容易產(chǎn)生廣播風(fēng)暴參考下圖：
寫(xiě)在后面少數(shù)服從多數(shù)算法為什么要奇數(shù)個(gè)節(jié)點(diǎn)？
偶數(shù)時(shí)，容易出現(xiàn)，相同個(gè)數(shù)的選票，從而無(wú)法選擇主節(jié)點(diǎn)，即便重新選主，出現(xiàn)相同選票的概率也比較大，但奇數(shù)個(gè)節(jié)點(diǎn)，更容易出現(xiàn)某個(gè)節(jié)點(diǎn)獲取大多數(shù)選票，從而成為主節(jié)點(diǎn)。
參考文章列表：
raft動(dòng)畫(huà)演示 。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
