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