Leader選舉

Leader選舉是保證分布式數(shù)據(jù)一致性的關(guān)鍵所在。當(dāng)Zookeeper集群中的一臺服務(wù)器出現(xiàn)以下兩種情況之一時，需要進入Leader選舉铃肯。

• (1) 服務(wù)器初始化啟動沐鼠。（集群的每個節(jié)點都沒有數(shù)據(jù) → 以SID的大小為準(zhǔn)）
• (2) 服務(wù)器運行期間無法和Leader保持連接绳军。（集群的每個節(jié)點都有數(shù)據(jù) ,或者Leader 宕機→ 以ZXID 和 SID 的最大值為準(zhǔn)）

1. 服務(wù)器啟動時期的Leader選舉

若進行Leader選舉五督，則至少需要2臺機器彰导，兩臺的高可用性會差一些蛔翅，如果Leader 宕機，就剩下一臺螺戳，自己沒辦法選舉搁宾。這里選取3臺機器組成的服務(wù)器集群為例。

在集群初始化階段倔幼，當(dāng)有一臺服務(wù)器Server1啟動時盖腿，其單獨無法進行和完成Leader選舉，當(dāng)?shù)诙_服務(wù)器Server2啟動時损同，此時兩臺機器可以相互通信翩腐，每臺機器都試圖找到Leader，于是進入Leader選舉過程膏燃。選舉過程如下

• (1) 每個Server發(fā)出一個投票茂卦。由于是初始情況，Server1和Server2都會將自己作為Leader服務(wù)器來進行投票组哩，每次投票會包含所推舉的服務(wù)器的myid和ZXID等龙，使用(myid, ZXID)來表示，此時Server1的投票為(1, 0)伶贰，Server2的投票為(2, 0)蛛砰，然后各自將這個投票發(fā)給集群中其他機器。
• (2) 接受來自各個服務(wù)器的投票黍衙。集群的每個服務(wù)器收到投票后泥畅，首先判斷該投票的有效性，如檢查是否是本輪投票琅翻、是否來自LOOKING狀態(tài)的服務(wù)器位仁。
• (3) 處理投票柑贞。針對每一個投票，服務(wù)器都需要將別人的投票和自己的投票進行PK聂抢，PK規(guī)則如下：
• 優(yōu)先檢查ZXID钧嘶。ZXID比較大的服務(wù)器優(yōu)先作為Leader。（這個很重要：是數(shù)據(jù)最新原則涛浙，保證數(shù)據(jù)的完整性）
• 如果ZXID相同康辑，那么就比較myid。myid較大的服務(wù)器作為Leader服務(wù)器轿亮。（集群的節(jié)點標(biāo)識）對于Server1而言，它的投票是(1, 0)胸墙，接收Server2的投票為(2, 0)我注，首先會比較兩者的ZXID，均為0迟隅。再比較myid但骨，此時Server2的myid最大，于是更新自己的投票為(2, 0)智袭，然后重新投票奔缠，對于Server2而言，其無須更新自己的投票吼野，只是再次向集群中所有機器發(fā)出上一次投票信息即可校哎。
• (4) 統(tǒng)計投票。每次投票后瞳步，服務(wù)器都會統(tǒng)計投票信息闷哆，判斷是否已經(jīng)有過半機器接受到相同的投票信息，對于Server1单起、Server2而言抱怔，都統(tǒng)計出集群中已經(jīng)有兩臺機器接受了(2, 0)的投票信息，此時便認(rèn)為已經(jīng)選出了Leader嘀倒。
• (5) 改變服務(wù)器狀態(tài)屈留。一旦確定了Leader，每個服務(wù)器就會更新自己的狀態(tài)测蘑，如果是Follower灌危，那么就變更為FOLLOWING，如果是Leader帮寻，就變更為LEADING乍狐。

2. 服務(wù)器運行時期的Leader選舉

在Zookeeper運行期間，Leader與非Leader服務(wù)器各司其職固逗，即便當(dāng)有非Leader服務(wù)器宕機或新加入浅蚪，此時也不會影響Leader藕帜，但是一旦Leader服務(wù)器掛了，那么整個集群將暫停對外服務(wù)惜傲，進入新一輪Leader選舉洽故，其過程和啟動時期的Leader選舉過程基本一致。

假設(shè)正在運行的有Server1盗誊、Server2时甚、Server3三臺服務(wù)器，當(dāng)前Leader是Server2哈踱，若某一時刻Leader掛了荒适，此時便開始Leader選舉。

選舉過程如下：

• (1) 變更狀態(tài)开镣。Leader掛后刀诬，余下的非Observer服務(wù)器都會講自己的服務(wù)器狀態(tài)變更為LOOKING，然后開始進入Leader選舉過程邪财。
• (2) 每個Server會發(fā)出一個投票陕壹。在運行期間，每個服務(wù)器上的ZXID可能不同树埠，此時假定Server1的ZXID為123糠馆，Server3的ZXID為122；在第一輪投票中怎憋，Server1和Server3都會投自己又碌，產(chǎn)生投票(1, 123)，(3, 122)盛霎，然后各自將投票發(fā)送給集群中所有機器赠橙。
• (3) 接收來自各個服務(wù)器的投票。與啟動時過程相同愤炸。
• (4) 處理投票期揪。與啟動時過程相同，此時规个，Server1將會成為Leader凤薛。
• (5) 統(tǒng)計投票。與啟動時過程相同诞仓。
• (6) 改變服務(wù)器的狀態(tài)缤苫。與啟動時過程相同。

2.2 Leader選舉算法分析

在3.4.0后的Zookeeper的版本只保留了TCP版本的FastLeaderElection選舉算法墅拭。當(dāng)一臺機器進入Leader選舉時活玲，當(dāng)前集群可能會處于以下兩種狀態(tài)

• 集群中已經(jīng)存在Leader。
• 集群中不存在Leader。

對于集群中已經(jīng)存在Leader而言舒憾，此種情況一般都是某臺機器啟動得較晚镀钓，在其啟動之前，集群已經(jīng)在正常工作镀迂，對這種情況丁溅，該機器試圖去選舉Leader時，會被告知當(dāng)前服務(wù)器的Leader信息探遵，對于該機器而言窟赏，僅僅需要和Leader機器建立起連接，并進行狀態(tài)同步即可箱季。而在集群中不存在Leader情況下則會相對復(fù)雜涯穷，其步驟如下

(1) 第一次投票。無論哪種導(dǎo)致進行Leader選舉藏雏，集群的所有機器都處于試圖選舉出一個Leader的狀態(tài)求豫，即LOOKING狀態(tài)，LOOKING機器會向所有其他機器發(fā)送消息诉稍，該消息稱為投票。投票中包含了SID（服務(wù)器的唯一標(biāo)識）和ZXID（事務(wù)ID）最疆，(SID, ZXID)形式來標(biāo)識一次投票信息杯巨。假定Zookeeper由5臺機器組成，SID分別為1努酸、2服爷、3、4获诈、5仍源，ZXID分別為9、9舔涎、9笼踩、8、8亡嫌，并且此時SID為2的機器是Leader機器嚎于，某一時刻，1挟冠、2所在機器出現(xiàn)故障于购，因此集群開始進行Leader選舉。在第一次投票時知染，每臺機器都會將自己作為投票對象肋僧，于是SID為3、4、5的機器投票情況分別為(3, 9)嫌吠，(4, 8)止潘， (5, 8)。

(2) 變更投票居兆。每臺機器發(fā)出投票后覆山，也會收到其他機器的投票，每臺機器會根據(jù)一定規(guī)則來處理收到的其他機器的投票泥栖，并以此來決定是否需要變更自己的投票簇宽，這個規(guī)則也是整個Leader選舉算法的核心所在，其中術(shù)語描述如下

• vote_sid：接收到的投票中所推舉Leader服務(wù)器的SID吧享。
• vote_zxid：接收到的投票中所推舉Leader服務(wù)器的ZXID魏割。
• self_sid：當(dāng)前服務(wù)器自己的SID。
• self_zxid：當(dāng)前服務(wù)器自己的ZXID钢颂。

每次對收到的投票的處理钞它，都是對(vote_sid, vote_zxid)和(self_sid, self_zxid)對比的過程。

• 規(guī)則一：如果vote_zxid大于self_zxid殊鞭，就認(rèn)可當(dāng)前收到的投票遭垛，并再次將該投票發(fā)送出去。
• 規(guī)則二：如果vote_zxid小于self_zxid操灿，那么堅持自己的投票锯仪，不做任何變更。
• 規(guī)則三：如果vote_zxid等于self_zxid趾盐，那么就對比兩者的SID庶喜，如果vote_sid大于self_sid，那么就認(rèn)可當(dāng)前收到的投票救鲤，并再次將該投票發(fā)送出去久窟。
• 規(guī)則四：如果vote_zxid等于self_zxid，并且vote_sid小于self_sid本缠，那么堅持自己的投票斥扛，不做任何變更。

結(jié)合上面規(guī)則搓茬，給出下面的集群變更過程犹赖。

Zookeeper選舉算法原理

(3) 確定Leader。經(jīng)過第二輪投票后卷仑，集群中的每臺機器都會再次接收到其他機器的投票峻村，然后開始統(tǒng)計投票，如果一臺機器收到了超過半數(shù)的相同投票锡凝，那么這個投票對應(yīng)的SID機器即為Leader粘昨。此時Server3將成為Leader。

由上面規(guī)則可知，通常那臺服務(wù)器上的數(shù)據(jù)越新（ZXID會越大）张肾，其成為Leader的可能性越大芭析，也就越能夠保證數(shù)據(jù)的恢復(fù)。如果ZXID相同吞瞪，則SID越大機會越大馁启。

2.3 Leader選舉實現(xiàn)細(xì)節(jié)

1. 服務(wù)器狀態(tài)

服務(wù)器具有四種狀態(tài)，分別是LOOKING芍秆、FOLLOWING惯疙、LEADING、OBSERVING妖啥。

• LOOKING：尋找Leader狀態(tài)霉颠。當(dāng)服務(wù)器處于該狀態(tài)時，它會認(rèn)為當(dāng)前集群中沒有Leader荆虱，因此需要進入Leader選舉狀態(tài)蒿偎。
• FOLLOWING：跟隨者狀態(tài)。表明當(dāng)前服務(wù)器角色是Follower怀读。
• LEADING：領(lǐng)導(dǎo)者狀態(tài)诉位。表明當(dāng)前服務(wù)器角色是Leader。
• OBSERVING：觀察者狀態(tài)菜枷。表明當(dāng)前服務(wù)器角色是Observer不从。

2. 投票數(shù)據(jù)結(jié)構(gòu)

每個投票中包含了兩個最基本的信息，所推舉服務(wù)器的SID和ZXID犁跪，投票（Vote）在Zookeeper中包含字段如下

• id：被推舉的Leader的SID。
• zxid：被推舉的Leader事務(wù)ID歹袁。
• electionEpoch：邏輯時鐘坷衍，用來判斷多個投票是否在同一輪選舉周期中，該值在服務(wù)端是一個自增序列条舔，每次進入新一輪的投票后枫耳，都會對該值進行加1操作。
• peerEpoch：被推舉的Leader的epoch孟抗。
• state：當(dāng)前服務(wù)器的狀態(tài)迁杨。

為什么zookeeper集群是單數(shù)？

1凄硼、容錯

由于在增刪改操作中需要半數(shù)以上服務(wù)器通過铅协，來分析以下情況。

2臺服務(wù)器摊沉，至少2臺正常運行才行（2的半數(shù)為1狐史，半數(shù)以上最少為2），正常運行1臺服務(wù)器都不允許掛掉

3臺服務(wù)器，至少2臺正常運行才行（3的半數(shù)為1.5骏全，半數(shù)以上最少為2）苍柏，正常運行可以允許1臺服務(wù)器掛掉

4臺服務(wù)器，至少3臺正常運行才行（4的半數(shù)為2姜贡，半數(shù)以上最少為3）试吁，正常運行可以允許1臺服務(wù)器掛掉

5臺服務(wù)器，至少3臺正常運行才行（5的半數(shù)為2.5楼咳，半數(shù)以上最少為3）熄捍，正常運行可以允許2臺服務(wù)器掛掉

6臺服務(wù)器，至少3臺正常運行才行（6的半數(shù)為3爬橡，半數(shù)以上最少為4）治唤，正常運行可以允許2臺服務(wù)器掛掉

通過以上可以發(fā)現(xiàn)，3臺服務(wù)器和4臺服務(wù)器都最多允許1臺服務(wù)器掛掉糙申，5臺服務(wù)器和6臺服務(wù)器都最多允許2臺服務(wù)器掛掉

但是明顯4臺服務(wù)器成本高于3臺服務(wù)器成本宾添，6臺服務(wù)器成本高于5服務(wù)器成本。這是由于半數(shù)以上投票通過決定的柜裸。

2缕陕、防腦裂

一個zookeeper集群中，可以有多個follower疙挺、observer服務(wù)器扛邑，但是必需只能有一個leader服務(wù)器。

如果leader服務(wù)器掛掉了铐然，剩下的服務(wù)器集群會通過半數(shù)以上投票選出一個新的leader服務(wù)器蔬崩。

集群互不通訊情況：

一個集群3臺服務(wù)器，全部運行正常搀暑，但是其中1臺裂開了沥阳，和另外2臺無法通訊。3臺機器里面2臺正常運行過半票可以選出一個leader自点。

一個集群4臺服務(wù)器桐罕，全部運行正常，但是其中2臺裂開了桂敛，和另外2臺無法通訊功炮。4臺機器里面2臺正常工作沒有過半票以上達到3，無法選出leader正常運行术唬。

一個集群5臺服務(wù)器薪伏，全部運行正常，但是其中2臺裂開了粗仓，和另外3臺無法通訊毅该。5臺機器里面3臺正常運行過半票可以選出一個leader博秫。

一個集群6臺服務(wù)器，全部運行正常眶掌，但是其中3臺裂開了挡育，和另外3臺無法通訊。6臺機器里面3臺正常工作沒有過半票以上達到4朴爬，無法選出leader正常運行即寒。

通可以上分析可以看出，為什么zookeeper集群數(shù)量總是單出現(xiàn)召噩，主要原因還是在于第2點母赵，防腦裂，對于第1點具滴，無非是正嘲汲埃控制，但是不影響集群正常運行构韵。但是出現(xiàn)第2種裂的情況周蹭，zookeeper集群就無法正常運行了。

ZooKeeper的腦裂的出現(xiàn)和解決方案

出現(xiàn)：

在搭建hadoop的HA集群環(huán)境后疲恢，由于兩個namenode的狀態(tài)不一凶朗，當(dāng)active的namenode由于網(wǎng)絡(luò)等原因出現(xiàn)假死狀態(tài)，standby接收不到active的心跳显拳，因此判斷active的namenode宕機棚愤，但實際上active并沒有死亡。此時standby的namenode就會切換成active的狀態(tài)杂数，保證服務(wù)能夠正常使用宛畦。若原來的namenode復(fù)活，此時在整個集群中就出現(xiàn)2個active狀態(tài)的namenode揍移，該狀態(tài)成為腦裂刃永。腦裂現(xiàn)象可能導(dǎo)致這2個namenode爭搶資源，從節(jié)點不知道該連接哪一臺namenode羊精，導(dǎo)致節(jié)點的數(shù)據(jù)不統(tǒng)一，這在企業(yè)生產(chǎn)中是不可以容忍的囚玫。

解決方案：

1喧锦、添加心跳線。

原來兩個namenode之間只有一條心跳線路抓督，此時若斷開燃少，則接收不到心跳報告，判斷對方已經(jīng)死亡铃在。此時若有2條心跳線路阵具，一條斷開碍遍，另一條仍然能夠接收心跳報告，能保證集群服務(wù)正常運行阳液。2條心跳線路同時斷開的可能性比1條心跳線路斷開的小得多怕敬。再有，心跳線路之間也可以HA（高可用）帘皿，這兩條心跳線路之間也可以互相檢測东跪，若一條斷開，則另一條馬上起作用鹰溜。正常情況下虽填，則不起作用，節(jié)約資源曹动。

2斋日、啟用磁盤鎖。

由于兩個active會爭搶資源墓陈，導(dǎo)致從節(jié)點不知道該連接哪一臺namenode恶守，可以使用磁盤鎖的形式，保證集群中只能有一臺namenode獲取磁盤鎖跛蛋，對外提供服務(wù)熬的，避免數(shù)據(jù)錯亂的情況發(fā)生。但是赊级，也會存在一個問題押框，若該namenode節(jié)點宕機，則不能主動釋放鎖理逊，那么其他的namenode就永遠獲取不了共享資源橡伞。因此，在HA上使用"智能鎖"就成為了必要措施晋被。"智能鎖"是指active的namenode檢測到了心跳線全部斷開時才啟動磁盤鎖兑徘，正常情況下不上鎖。保證了假死狀態(tài)下羡洛，仍然只有一臺namenode的節(jié)點提供服務(wù)挂脑。

3、設(shè)置仲裁機制

腦裂導(dǎo)致的后果最主要的原因就是從節(jié)點不知道該連接哪一臺namenode欲侮，此時如果有一方來決定誰留下崭闲，誰放棄就最好了。因此出現(xiàn)了仲裁機制威蕉，比如提供一個參考的IP地址刁俭，當(dāng)出現(xiàn)腦裂現(xiàn)象時，雙方接收不到對方的心跳機制韧涨，但是能同時ping參考IP牍戚，如果有一方ping不通侮繁，那么表示該節(jié)點網(wǎng)絡(luò)已經(jīng)出現(xiàn)問題，則該節(jié)點需要自行退出爭搶資源的行列如孝，或者更好的方法是直接強制重啟宪哩，這樣能更好的釋放曾經(jīng)占有的共享資源，將服務(wù)的提供功能讓給功能更全面的namenode節(jié)點暑竟。

以上的3種方式可以同時使用斋射，這樣更能減少集群中腦裂情況的發(fā)生。但是還是不能保證完全不出現(xiàn)但荤，如果仲裁機制中2臺機器同時宕機罗岖，那么此時集群中沒有namenode可以使用。此時需要運維人員人工的搶修腹躁，或者提供一臺新的機器作為namenode桑包，這個時間是不可避免的。希望未來能有更好的解決辦法纺非，能徹底杜絕這類情況的發(fā)生吧~

歡迎工作一到五年的Java工程師朋友們加入JavaQQ群：219571750哑了，群內(nèi)提供免費的Java架構(gòu)學(xué)習(xí)資料（里面有高可用、高并發(fā)烧颖、高性能及分布式弱左、Jvm性能調(diào)優(yōu)、Spring源碼炕淮，MyBatis拆火，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構(gòu)資料）合理利用自己每一分每一秒的時間來學(xué)習(xí)提升自己，不要再用"沒有時間“來掩飾自己思想上的懶惰涂圆！趁年輕们镜，使勁拼，給未來的自己一個交代润歉！