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