本文內(nèi)容為《從PAXOS到ZOOKEEPER分布式一致性原理與實(shí)踐》一書(shū)學(xué)習(xí)筆記。本文主要概述第七章選舉部分的內(nèi)容。
Leader選舉隱式條件：ZooKeeper的集群規(guī)模至少是2臺(tái)機(jī)器。以3臺(tái)機(jī)器組成的集群為例。在服務(wù)器集群初始化階段：有1臺(tái)服務(wù)器（假設(shè)此機(jī)器myid為1，稱其為Server1）啟動(dòng)時(shí)，是無(wú)法進(jìn)行Leader選舉的。當(dāng)?shù)?臺(tái)服務(wù)器（myid為2，Server2）啟動(dòng)后，兩臺(tái)機(jī)器可以互相通信，都試圖找到一個(gè)Leader，進(jìn)入Leader選舉流程。
服務(wù)器啟動(dòng)時(shí)的Leader選舉：
每個(gè)Server發(fā)出一個(gè)投票。由于是初始化階段，Server1和Server2都會(huì)選自己作Leader并投票。投票元素包括所推選的服務(wù)器的myid和ZXID，以（myid , ZXID）形式表示。所以Server1的投票是（1，0）；Server2的投票是（2，0），然后將這個(gè)投票發(fā)給集群中所有其他機(jī)器。
接收來(lái)自各個(gè)服務(wù)器的投票。每個(gè)服務(wù)器都會(huì)接受來(lái)自其他服務(wù)器的投票，并判斷該投票的有效性，例如是否是本輪投票，是否來(lái)自LOOKING狀態(tài)的服務(wù)器。
處理投票（即再次投票）。接受到來(lái)自其他服務(wù)器的投票后，每臺(tái)服務(wù)器都會(huì)變更投票。變更規(guī)則：先比較ZXID，ZXID大的優(yōu)先作為L(zhǎng)eader；ZXID相同則比較myid，myid較大的作為L(zhǎng)eader。對(duì)于Server1來(lái)說(shuō)，自己的投票是（1，0），接受的投票是（2，0）；兩者ZXID相同，而接受到的投票的myid是2，更大，所以Server1會(huì)更新自己的投票為（2，0）并重新發(fā)出去，Server2則不需要更新投票信息，將上次投票信息再發(fā)送一次即可。
統(tǒng)計(jì)投票。每次投票后，服務(wù)器都會(huì)統(tǒng)計(jì)所有投票，看是否已經(jīng)有過(guò)半的機(jī)器接收到相同的投票信息（過(guò)半指大于集群數(shù)量的一半，即大于或等于（n/2+1））。將該機(jī)器作為L(zhǎng)eader。
改變服務(wù)器狀態(tài)。確定Leader后，每個(gè)服務(wù)器都會(huì)更新自己的狀態(tài)：如果是Follower，變更為FOLLOWING，如果是Leader，變更為L(zhǎng)EADING。
服務(wù)器運(yùn)行期間的Leader選舉：
ZooKeeper集群正常運(yùn)行過(guò)程中，Leader選出一般不再變化，即使集群中有非Leader機(jī)器掛了或有新集群加入Leader也不會(huì)影響Leader。但Leader如果掛了就需要新一輪選舉。
變更狀態(tài)。Leader掛了后，余下的非Observer服務(wù)器都會(huì)將自己的服務(wù)器狀態(tài)變更為L(zhǎng)OOKING，然后開(kāi)始Leader選舉。
每個(gè)Server發(fā)出一個(gè)投票。運(yùn)行期間每個(gè)機(jī)器上的ZXID可能不同。但第一輪投票都是投給自己。
接收來(lái)自各個(gè)服務(wù)器的投票。
處理投票。
統(tǒng)計(jì)投票。
改變服務(wù)器狀態(tài)。
選舉過(guò)程底層實(shí)現(xiàn)：
涉及術(shù)語(yǔ)解釋：
SID：服務(wù)器ID，唯一標(biāo)識(shí)一臺(tái)ZooKeeper集群中的機(jī)器，值和myid一致。
ZXID：事務(wù)ID，唯一標(biāo)識(shí)一次服務(wù)器狀態(tài)的變更。
Quorum：過(guò)半機(jī)器數(shù)。
ZooKeeper底層采用的是基于TCP的FastLeaderElection算法實(shí)現(xiàn)。底層網(wǎng)絡(luò)IO部分是QuorumCnxManager管理選舉之間的通信（每臺(tái)服務(wù)器啟動(dòng)的時(shí)候，都會(huì)啟動(dòng)一個(gè)QuorumCnxManager）。在QuorumCnxManager這個(gè)類內(nèi)部維護(hù)了一系列隊(duì)列：
a. recvQueue：消息接收隊(duì)列。存放從其他服務(wù)器接收到的消息
b. queueSendMap：消息發(fā)送隊(duì)列，保存待發(fā)送的消息。它是一個(gè)Map，按照SID分組形成隊(duì)列集合；為集群中的每臺(tái)機(jī)器分配了一個(gè)單獨(dú)隊(duì)列，保證各臺(tái)機(jī)器之間的消息發(fā)送互不影響。（按照SID分組定義：假設(shè)集群中除自身外還有4臺(tái)服務(wù)器，那么當(dāng)前服務(wù)器會(huì)為這4臺(tái)服務(wù)器分別創(chuàng)建一個(gè)發(fā)送隊(duì)列，互不干擾。）
c. senderWorkerMap：發(fā)送器集合。同樣按照SID分組。每個(gè)消息發(fā)送器與遠(yuǎn)程ZooKeeper服務(wù)器是一對(duì)一關(guān)系。
d. lastMessageSent：最近發(fā)送過(guò)的消息。同樣按照SID分組。為每個(gè)SID保留最近發(fā)送過(guò)的一個(gè)消息。
建立連接：所有機(jī)器都需要兩兩建立起連接。為了避免兩臺(tái)服務(wù)器之間重復(fù)創(chuàng)建TCP連接。只允許SID大的服務(wù)器主動(dòng)和其他服務(wù)器建立連接。當(dāng)前服務(wù)器接收到連接請(qǐng)求后如果發(fā)現(xiàn)自己的SID值比遠(yuǎn)程服務(wù)器更大，會(huì)斷開(kāi)當(dāng)前連接，自己去和遠(yuǎn)程服務(wù)器建立連接。
消息接收與發(fā)送：消息的接收：ZooKeeper會(huì)為每個(gè)遠(yuǎn)程服務(wù)器（集群中處了自己其他的服務(wù)器）分配一個(gè)單獨(dú)的消息接收器RecvWorker。每個(gè)RecvWorker不斷從TCP連接中讀取消息，并保存到recvQueue里去。消息發(fā)送：同上，每個(gè)服務(wù)器單獨(dú)有消息發(fā)送器SendWorker，SendWorker不斷從消息發(fā)送隊(duì)列（自：queueSendMap）獲取一個(gè)消息發(fā)送即可，同時(shí)將這個(gè)消息放入lastMessageSent。有個(gè)細(xì)節(jié)：一旦ZooKeeper發(fā)現(xiàn)針對(duì)當(dāng)前遠(yuǎn)程服務(wù)器的的消息發(fā)送隊(duì)列為空，那么此時(shí)從lastMessageSent取出一個(gè)最近未發(fā)送過(guò)的消息來(lái)再次發(fā)送。這個(gè)細(xì)節(jié)主要是為了解決這么一類分布式問(wèn)題：接收方在消息接收前或接收到消息后服務(wù)器掛掉了，導(dǎo)致消息尚未被正確處理。同時(shí)ZooKeeper能保證接收方在處理消息的時(shí)候，會(huì)對(duì)重復(fù)消息進(jìn)行正確的處理。
選票管理：
外部投票：其他服務(wù)器發(fā)來(lái)的投票。
內(nèi)部投票：服務(wù)器自身當(dāng)前的投票。
底層接收（QuorumCnxManager）數(shù)據(jù)，上層則進(jìn)行選票管理。接收器WorkerReceiver（我的理解是上面的RecvWorker）會(huì)不斷地從QuorumCnxManager獲取從其他服務(wù)器發(fā)來(lái)的選舉消息，并將其轉(zhuǎn)換成一個(gè)選票，然后保存到recvQueue隊(duì)列中去，再由具體選舉算法得出選票放入sendqueue選票發(fā)送隊(duì)列，由WorkSender發(fā)送至底層網(wǎng)絡(luò)IO發(fā)送給其他服務(wù)器（我的理解是上面的SendWorker）。
統(tǒng)計(jì)投票說(shuō)明：最后進(jìn)行選票統(tǒng)計(jì)時(shí)，是對(duì)自己內(nèi)部選票的統(tǒng)計(jì)（自己投的票）是否過(guò)半認(rèn)可，若認(rèn)可，則根據(jù)投票內(nèi)容決定自己是Leader還是Follower。
