zookeeper配置為集群模式時(shí)，在啟動(dòng)或異常情況時(shí)會(huì)選舉出一個(gè)實(shí)例作為Leader。其默認(rèn)選舉算法為FastLeaderElection。
不知道zookeeper的可以考慮這樣一個(gè)問題：某個(gè)服務(wù)可以配置為多個(gè)實(shí)例共同構(gòu)成一個(gè)集群對(duì)外提供服務(wù)。其每一個(gè)實(shí)例本地都存有冗余數(shù)據(jù)，每一個(gè)實(shí)例都可以直接對(duì)外提供讀寫服務(wù)。在這個(gè)集群中為了保證數(shù)據(jù)的一致性，需要有一個(gè)Leader來協(xié)調(diào)一些事務(wù)。那么問題來了：如何確定哪一個(gè)實(shí)例是Leader呢？
問題的難點(diǎn)在于：
- 沒有一個(gè)仲裁者來選定Leader
- 每一個(gè)實(shí)例本地可能已經(jīng)存在數(shù)據(jù)，不確定哪個(gè)實(shí)例上的數(shù)據(jù)是最新的
分布式選舉算法正是用來解決這個(gè)問題的。
本文基于zookeeper 3.4.6 的源碼進(jìn)行分析。FastLeaderElection算法的源碼全部位于FastLeaderElection.java文件中，其對(duì)外接口為FastLeaderElection.lookForLeader，該接口是一個(gè)同步接口，直到選舉結(jié)束才會(huì)返回。同樣由于網(wǎng)上已有類似文章，所以我就從圖示的角度來闡述。閱讀一些其他文章有利于獲得初步印象：
主要流程
閱讀代碼和以上推薦文章可以把整個(gè)流程梳理清楚。實(shí)現(xiàn)上，包括了一個(gè)消息處理主循環(huán)，也是選舉的主要邏輯，以及一個(gè)消息發(fā)送隊(duì)列處理線程和消息解碼線程。主要流程可概括為下圖：
推薦對(duì)照著推薦的文章及代碼理解，不贅述。
我們從感性上來理解這個(gè)算法。
每一個(gè)節(jié)點(diǎn)，相當(dāng)于一個(gè)選民，他們都有自己的推薦人，最開始他們都推薦自己。誰更適合成為Leader有一個(gè)簡單的規(guī)則，例如sid夠大（配置）、持有的數(shù)據(jù)夠新(zxid夠大)。每個(gè)選民都告訴其他選民自己目前的推薦人是誰，類似于出去搞宣傳拉攏其他選民。每一個(gè)選民發(fā)現(xiàn)有比自己更適合的人時(shí)就轉(zhuǎn)而推薦這個(gè)更適合的人。最后，大部分人意見一致時(shí)，就可以結(jié)束選舉。
就這么簡單。總體上有一種不斷演化逼近結(jié)果的感覺。
當(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í)候來了選民4又發(fā)起一次新的選舉，那么其他選民就直接告訴它當(dāng)前的Leader情況。相當(dāng)于，在這個(gè)集群主從已經(jīng)就緒的情況下，又開啟了一個(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，其都還沒有數(shù)據(jù)，按照sid關(guān)系為C>B>A，那么按照規(guī)則，C更可能成為Leader，其各個(gè)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)換為：
圖中，v(A)表示當(dāng)前推薦人為A；r[]表示收到的投票集合。
可以看看當(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ù)
完