一、zookeeper集群

配置多個(gè)實(shí)例共同構(gòu)成一個(gè)集群對(duì)外提供服務(wù)以達(dá)到水平擴(kuò)展的目的，每個(gè)服務(wù)器上的數(shù)據(jù)是相同的，每一個(gè)服務(wù)器均可以對(duì)外提供讀和寫(xiě)的服務(wù)，這點(diǎn)和redis是相同的，即對(duì)客戶(hù)端來(lái)講每個(gè)服務(wù)器都是平等的。

這篇主要分析leader的選擇機(jī)制，zookeeper提供了三種方式：

• LeaderElection
• AuthFastLeaderElection
• FastLeaderElection （最新默認(rèn)）

默認(rèn)的算法是FastLeaderElection，所以這篇主要分析它的選舉機(jī)制。

二、選舉流程簡(jiǎn)述

目前有5臺(tái)服務(wù)器，每臺(tái)服務(wù)器均沒(méi)有數(shù)據(jù)，它們的編號(hào)分別是1,2,3,4,5,按編號(hào)依次啟動(dòng)，它們的選擇舉過(guò)程如下：

• 服務(wù)器1啟動(dòng)，給自己投票，然后發(fā)投票信息，由于其它機(jī)器還沒(méi)有啟動(dòng)所以它收不到反饋信息，服務(wù)器1的狀態(tài)一直屬于Looking(選舉狀態(tài))。
• 服務(wù)器2啟動(dòng)，給自己投票，同時(shí)與之前啟動(dòng)的服務(wù)器1交換結(jié)果，由于服務(wù)器2的編號(hào)大所以服務(wù)器2勝出，但此時(shí)投票數(shù)沒(méi)有大于半數(shù)，所以?xún)蓚€(gè)服務(wù)器的狀態(tài)依然是LOOKING。
• 服務(wù)器3啟動(dòng)，給自己投票，同時(shí)與之前啟動(dòng)的服務(wù)器1,2交換信息，由于服務(wù)器3的編號(hào)最大所以服務(wù)器3勝出，此時(shí)投票數(shù)正好大于半數(shù)，所以服務(wù)器3成為領(lǐng)導(dǎo)者，服務(wù)器1,2成為小弟。
• 服務(wù)器4啟動(dòng)，給自己投票，同時(shí)與之前啟動(dòng)的服務(wù)器1,2,3交換信息，盡管服務(wù)器4的編號(hào)大，但之前服務(wù)器3已經(jīng)勝出，所以服務(wù)器4只能成為小弟。
• 服務(wù)器5啟動(dòng)，后面的邏輯同服務(wù)器4成為小弟。

三、選擇機(jī)制中的概念

1、Serverid：服務(wù)器ID

比如有三臺(tái)服務(wù)器，編號(hào)分別是1,2,3。

編號(hào)越大在選擇算法中的權(quán)重越大。

2、Zxid：數(shù)據(jù)ID

服務(wù)器中存放的最大數(shù)據(jù)ID.

值越大說(shuō)明數(shù)據(jù)越新，在選舉算法中數(shù)據(jù)越新權(quán)重越大。

3、Epoch：邏輯時(shí)鐘

或者叫投票的次數(shù)，同一輪投票過(guò)程中的邏輯時(shí)鐘值是相同的。每投完一次票這個(gè)數(shù)據(jù)就會(huì)增加，然后與接收到的其它服務(wù)器返回的投票信息中的數(shù)值相比，根據(jù)不同的值做出不同的判斷。

4、Server狀態(tài)：選舉狀態(tài)

• LOOKING，競(jìng)選狀態(tài)。
• FOLLOWING，隨從狀態(tài)，同步leader狀態(tài)，參與投票。
• OBSERVING，觀(guān)察狀態(tài),同步leader狀態(tài)，不參與投票。
• LEADING，領(lǐng)導(dǎo)者狀態(tài)。

四、選舉消息內(nèi)容

在投票完成后，需要將投票信息發(fā)送給集群中的所有服務(wù)器，它包含如下內(nèi)容。

• 服務(wù)器ID
• 數(shù)據(jù)ID
• 邏輯時(shí)鐘
• 選舉狀態(tài)

五、選舉流程圖

因?yàn)槊總€(gè)服務(wù)器都是獨(dú)立的，在啟動(dòng)時(shí)均從初始狀態(tài)開(kāi)始參與選舉，下面是簡(jiǎn)易流程圖。

六、選舉狀態(tài)圖

描述Leader選擇過(guò)程中的狀態(tài)變化，這是假設(shè)全部實(shí)例中均沒(méi)有數(shù)據(jù)，假設(shè)服務(wù)器啟動(dòng)順序分別為：A,B,C。

七、判斷是否已經(jīng)勝出

默認(rèn)是采用投票數(shù)大于半數(shù)則勝出的邏輯。

八、選舉流程詳述

一、首先開(kāi)始選舉階段，每個(gè)Server讀取自身的zxid。

二、發(fā)送投票信息

a、首先，每個(gè)Server第一輪都會(huì)投票給自己。

b、投票信息包含 ：所選舉leader的Serverid，Zxid，Epoch。Epoch會(huì)隨著選舉輪數(shù)的增加而遞增。

三、接收投票信息

1、如果服務(wù)器B接收到服務(wù)器A的數(shù)據(jù)（服務(wù)器A處于選舉狀態(tài)(LOOKING 狀態(tài))

1）首先，判斷邏輯時(shí)鐘值：

a）如果發(fā)送過(guò)來(lái)的邏輯時(shí)鐘Epoch大于目前的邏輯時(shí)鐘。首先，更新本邏輯時(shí)鐘Epoch，同時(shí)清空本輪邏輯時(shí)鐘收集到的來(lái)自其他server的選舉數(shù)據(jù)。然后，判斷是否需要更新當(dāng)前自己的選舉leader Serverid。判斷規(guī)則rules judging：保存的zxid最大值和leader Serverid來(lái)進(jìn)行判斷的。先看數(shù)據(jù)zxid,數(shù)據(jù)zxid大者勝出;其次再判斷l(xiāng)eader Serverid,leader Serverid大者勝出；然后再將自身最新的選舉結(jié)果(也就是上面提到的三種數(shù)據(jù)（leader Serverid，Zxid，Epoch）廣播給其他server)

b）如果發(fā)送過(guò)來(lái)的邏輯時(shí)鐘Epoch小于目前的邏輯時(shí)鐘。說(shuō)明對(duì)方server在一個(gè)相對(duì)較早的Epoch中，這里只需要將本機(jī)的三種數(shù)據(jù)（leader Serverid，Zxid，Epoch）發(fā)送過(guò)去就行。

c）如果發(fā)送過(guò)來(lái)的邏輯時(shí)鐘Epoch等于目前的邏輯時(shí)鐘。再根據(jù)上述判斷規(guī)則rules judging來(lái)選舉leader ，然后再將自身最新的選舉結(jié)果(也就是上面提到的三種數(shù)據(jù)（leader Serverid，Zxid，Epoch）廣播給其他server)。

2）其次，判斷服務(wù)器是不是已經(jīng)收集到了所有服務(wù)器的選舉狀態(tài)：若是，根據(jù)選舉結(jié)果設(shè)置自己的角色(FOLLOWING還是LEADER)，退出選舉過(guò)程就是了。

最后，若沒(méi)有收到?jīng)]有收集到所有服務(wù)器的選舉狀態(tài)：也可以判斷一下根據(jù)以上過(guò)程之后最新的選舉leader是不是得到了超過(guò)半數(shù)以上服務(wù)器的支持,如果是,那么嘗試在200ms內(nèi)接收一下數(shù)據(jù),如果沒(méi)有新的數(shù)據(jù)到來(lái),說(shuō)明大家都已經(jīng)默認(rèn)了這個(gè)結(jié)果,同樣也設(shè)置角色退出選舉過(guò)程。

2、 如果所接收服務(wù)器A處在其它狀態(tài)（FOLLOWING或者LEADING）。

a)邏輯時(shí)鐘Epoch等于目前的邏輯時(shí)鐘，將該數(shù)據(jù)保存到recvset。此時(shí)Server已經(jīng)處于LEADING狀態(tài)，說(shuō)明此時(shí)這個(gè)server已經(jīng)投票選出結(jié)果。若此時(shí)這個(gè)接收服務(wù)器宣稱(chēng)自己是leader, 那么將判斷是不是有半數(shù)以上的服務(wù)器選舉它，如果是則設(shè)置選舉狀態(tài)退出選舉過(guò)程。

b) 否則這是一條與當(dāng)前邏輯時(shí)鐘不符合的消息，那么說(shuō)明在另一個(gè)選舉過(guò)程中已經(jīng)有了選舉結(jié)果，于是將該選舉結(jié)果加入到outofelection集合中，再根據(jù)outofelection來(lái)判斷是否可以結(jié)束選舉,如果可以也是保存邏輯時(shí)鐘，設(shè)置選舉狀態(tài)，退出選舉過(guò)程。