zookeeper配置為集群模式時(shí)，在啟動(dòng)或異常情況時(shí)會(huì)選舉出一個(gè)實(shí)例作為L(zhǎng)eader逼侦。其默認(rèn)選舉算法為FastLeaderElection。
不知道zookeeper的可以考慮這樣一個(gè)問(wèn)題：某個(gè)服務(wù)可以配置為多個(gè)實(shí)例共同構(gòu)成一個(gè)集群對(duì)外提供服務(wù)腰耙。其每一個(gè)實(shí)例本地都存有冗余數(shù)據(jù)偿洁，每一個(gè)實(shí)例都可以直接對(duì)外提供讀寫(xiě)服務(wù)。在這個(gè)集群中為了保證數(shù)據(jù)的一致性沟优，需要有一個(gè)Leader來(lái)協(xié)調(diào)一些事務(wù)。那么問(wèn)題來(lái)了：如何確定哪一個(gè)實(shí)例是Leader呢睬辐？
問(wèn)題的難點(diǎn)在于：
- 沒(méi)有一個(gè)仲裁者來(lái)選定Leader
- 每一個(gè)實(shí)例本地可能已經(jīng)存在數(shù)據(jù)挠阁，不確定哪個(gè)實(shí)例上的數(shù)據(jù)是最新的
分布式選舉算法正是用來(lái)解決這個(gè)問(wèn)題的宾肺。
本文基于zookeeper 3.4.6 的源碼進(jìn)行分析。FastLeaderElection算法的源碼全部位于FastLeaderElection.java文件中侵俗，其對(duì)外接口為FastLeaderElection.lookForLeader锨用，該接口是一個(gè)同步接口，直到選舉結(jié)束才會(huì)返回隘谣。同樣由于網(wǎng)上已有類似文章增拥，所以我就從圖示的角度來(lái)闡述。閱讀一些其他文章有利于獲得初步印象
主要流程
包括了一個(gè)消息處理主循環(huán)寻歧，也是選舉的主要邏輯掌栅，以及一個(gè)消息發(fā)送隊(duì)列處理線程和消息解碼線程。主要流程可概括為下圖
我們從感性上來(lái)理解這個(gè)算法码泛。
每一個(gè)節(jié)點(diǎn)猾封，相當(dāng)于一個(gè)選民，他們都有自己的推薦人噪珊，最開(kāi)始他們都推薦自己晌缘。誰(shuí)更適合成為L(zhǎng)eader有一個(gè)簡(jiǎn)單的規(guī)則，例如sid夠大（配置）痢站、持有的數(shù)據(jù)夠新(zxid夠大)磷箕。每個(gè)選民都告訴其他選民自己目前的推薦人是誰(shuí)，類似于出去搞宣傳拉攏其他選民阵难。每一個(gè)選民發(fā)現(xiàn)有比自己更適合的人時(shí)就轉(zhuǎn)而推薦這個(gè)更適合的人岳枷。最后，大部分人意見(jiàn)一致時(shí)多望，就可以結(jié)束選舉嫩舟。
就這么簡(jiǎn)單』惩担總體上有一種不斷演化逼近結(jié)果的感覺(jué)家厌。
當(dāng)然，會(huì)有些特殊情況的處理椎工。例如總共3個(gè)選民饭于，1和2已經(jīng)確定3是Leader，但3還不知情维蒙，此時(shí)就走入LEADING/FOLLOWING的分支掰吕，選民3只是接收結(jié)果。
代碼中不是所有邏輯都在這個(gè)大流程中完成的颅痊。在接收消息線程中殖熟，還可能單獨(dú)地回應(yīng)某個(gè)節(jié)點(diǎn)(WorkerReceiver.run)：
從這里可以看出，當(dāng)某個(gè)節(jié)點(diǎn)已經(jīng)確定選舉結(jié)果不再處于
LOOKING狀態(tài)時(shí)斑响，其收到LOOKING消息時(shí)都會(huì)直接回應(yīng)選舉的最終結(jié)果菱属。結(jié)合上面那個(gè)比方钳榨，相當(dāng)于某次選舉結(jié)束了，這個(gè)時(shí)候來(lái)了選民4又發(fā)起一次新的選舉纽门，那么其他選民就直接告訴它當(dāng)前的Leader情況薛耻。相當(dāng)于，在這個(gè)集群主從已經(jīng)就緒的情況下赏陵，又開(kāi)啟了一個(gè)實(shí)例饼齿，這個(gè)實(shí)例就會(huì)直接使用當(dāng)前的選舉結(jié)果
狀態(tài)轉(zhuǎn)換
每個(gè)節(jié)點(diǎn)上有一些關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)：
- 當(dāng)前推薦人，初始推薦自己蝙搔，每次收到其他更好的推薦人時(shí)就更新
- 其他人的投票集合缕溉，用于確定何時(shí)選舉結(jié)束
每次推薦人更新時(shí)就會(huì)進(jìn)行廣播，正是這個(gè)不斷地廣播驅(qū)動(dòng)整個(gè)算法趨向于結(jié)果杂瘸。假設(shè)有3個(gè)節(jié)點(diǎn)A/B/C倒淫，其都還沒(méi)有數(shù)據(jù)，按照sid關(guān)系為C>B>A败玉，那么按照規(guī)則敌土，C更可能成為L(zhǎng)eader，其各個(gè)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換為：
圖中运翼，v(A)表示當(dāng)前推薦人為A返干；r[]表示收到的投票集合。需要注意一個(gè)細(xì)節(jié)血淌，初始投票集合里包含了自己的投票矩欠，代碼中自己會(huì)將推薦人推薦給自己，網(wǎng)絡(luò)模塊(
QuorumCnxManager)直接將該消息放入接收隊(duì)列悠夯。
可以看看當(dāng)其他節(jié)點(diǎn)已經(jīng)確定投票結(jié)果時(shí)癌淮，即不再是LOOKING時(shí)的狀態(tài)：
代碼中有一個(gè)特殊的投票集合
outofelection，我理解為選舉已結(jié)束的那些投票沦补，這些投票僅用于表征選舉結(jié)果乳蓄。當(dāng)一個(gè)新啟動(dòng)的節(jié)點(diǎn)加入集群時(shí)，它對(duì)集群內(nèi)其他節(jié)點(diǎn)發(fā)出投票請(qǐng)求夕膀，而其他節(jié)點(diǎn)已不處于LOOKING狀態(tài)虚倒，此時(shí)其他節(jié)點(diǎn)回應(yīng)選舉結(jié)果，該節(jié)點(diǎn)收集這些結(jié)果到
outofelection中产舞，最終在收到合法LEADER消息且這些選票也構(gòu)成選舉結(jié)束條件時(shí)魂奥，該節(jié)點(diǎn)就結(jié)束自己的選舉行為。注意到代碼中會(huì)logicalclock = n.electionEpoch;更新選舉輪數(shù)
一個(gè)簡(jiǎn)單例子描述zookeeper 選舉算法
假設(shè)有五臺(tái)服務(wù)器組成的zookeeper集群,它們的id從1-5,同時(shí)它們都是最新啟動(dòng)的,也就是沒(méi)有歷史數(shù)據(jù),在存放數(shù)據(jù)量這一點(diǎn)上,都是一樣的.假設(shè)這些服務(wù)器依序啟動(dòng),來(lái)看看會(huì)發(fā)生什么.
1 服務(wù)器1啟動(dòng),此時(shí)只有它一臺(tái)服務(wù)器啟動(dòng)了,它發(fā)出去的報(bào)沒(méi)有任何響應(yīng),所以它的選舉狀態(tài)一直是LOOKING狀態(tài)
2 服務(wù)器2啟動(dòng),它與最開(kāi)始啟動(dòng)的服務(wù)器1進(jìn)行通信,互相交換自己的選舉結(jié)果,由于兩者都沒(méi)有歷史數(shù)據(jù),所以id值較大的服務(wù)器2勝出,但是由于沒(méi)有達(dá)到超過(guò)半數(shù)以上的服務(wù)器都同意選舉它(這個(gè)例子中的半數(shù)以上是3),所以服務(wù)器1,2還是繼續(xù)保持LOOKING狀態(tài).
3 服務(wù)器3啟動(dòng),根據(jù)前面的理論分析,服務(wù)器3成為服務(wù)器1,2,3中的老大,而與上面不同的是,此時(shí)有三臺(tái)服務(wù)器選舉了它,所以它成為了這次選舉的leader.
4 服務(wù)器4啟動(dòng),根據(jù)前面的分析,理論上服務(wù)器4應(yīng)該是服務(wù)器1,2,3,4中最大的,但是由于前面已經(jīng)有半數(shù)以上的服務(wù)器選舉了服務(wù)器3,所以它只能接收當(dāng)小弟的命了.
5 服務(wù)器5啟動(dòng),同4一樣,當(dāng)小弟.
