術(shù)語介紹

• myid
  每個(gè) Zookeeper 服務(wù)器格侯，都需要在數(shù)據(jù)文件夾下創(chuàng)建一個(gè)名為 myid 的文件肄满，該文件包含整個(gè) Zookeeper 集群唯一的 ID（整數(shù)）。
  例如某 Zookeeper 集群包含三臺(tái)服務(wù)器苍碟，hostname 分別為 zoo1稠集、zoo2 和 zoo3，其 myid 分別為 1库糠、2 和 3伙狐，則在配置文件中其
  ID 與 hostname 必須一一對(duì)應(yīng)，如下所示曼玩。在該配置文件中鳞骤， server. 后面的數(shù)據(jù)即為 myid
  1
  2
  3
  server.1=zoo1:2888:3888
  server.2=zoo2:2888:3888
  server.3=zoo3:2888:3888

• zxid
  類似于 RDBMS 中的事務(wù) ID，用于標(biāo)識(shí)一次更新操作的 Proposal ID黍判。為了保證順序性豫尽，該 zkid 必須單調(diào)遞增。因此 Zookeeper 使
  用一個(gè) 64 位的數(shù)來表示顷帖，高 32 位是 Leader 的 epoch美旧，從 1 開始渤滞，每次選出新的 Leader，epoch 加一榴嗅。低 32 位為該 epoch 內(nèi)的
  序號(hào)妄呕，每次 epoch 變化，都將低 32 位的序號(hào)重置嗽测。這樣保證了 zkid 的全局遞增性绪励。

• 支持的領(lǐng)導(dǎo)選舉算法
  可通過 electionAlg 配置項(xiàng)設(shè)置 Zookeeper 用于領(lǐng)導(dǎo)選舉的算法。
  到 3.4.10 版本為止唠粥，可選項(xiàng)有
  o 0 基于 UDP 的 LeaderElection
  o 1 基于 UDP 的 FastLeaderElection
  o 2 基于 UDP 和認(rèn)證的 FastLeaderElection
  o 3 基于 TCP 的 FastLeaderElection
  在 3.4.10 版本中疏魏，默認(rèn)值為 3，也即基于 TCP 的 FastLeaderElection晤愧。另外三種算法已經(jīng)被棄用大莫，并且有計(jì)劃在之后的版本中將它
  們徹底刪除而不再支持。

• FastLeaderElection
  FastLeaderElection 選舉算法是標(biāo)準(zhǔn)的 Fast Paxos 算法實(shí)現(xiàn)官份，可解決 LeaderElection 選舉算法收斂速度慢的問題只厘。

• 服務(wù)器狀態(tài)
  o LOOKING 不確定 Leader 狀態(tài)。該狀態(tài)下的服務(wù)器認(rèn)為當(dāng)前集群中沒有 Leader舅巷，會(huì)發(fā)起 Leader 選舉
  o FOLLOWING 跟隨者狀態(tài)羔味。表明當(dāng)前服務(wù)器角色是 Follower，并且它知道 Leader 是誰
  o LEADING 領(lǐng)導(dǎo)者狀態(tài)悄谐。表明當(dāng)前服務(wù)器角色是 Leader介评，它會(huì)維護(hù)與 Follower 間的心跳
  o OBSERVING 觀察者狀態(tài)。表明當(dāng)前服務(wù)器角色是 Observer爬舰，與 Folower 唯一的不同在于不參與選舉，也不參與集群寫
  操作時(shí)的投票

• 選票數(shù)據(jù)結(jié)構(gòu)
  每個(gè)服務(wù)器在進(jìn)行領(lǐng)導(dǎo)選舉時(shí)寒瓦，會(huì)發(fā)送如下關(guān)鍵信息
  o logicClock 每個(gè)服務(wù)器會(huì)維護(hù)一個(gè)自增的整數(shù)情屹，名為 logicClock，它表示這是該服務(wù)器發(fā)起的第多少輪投票
  o state 當(dāng)前服務(wù)器的狀態(tài)
  o self_id 當(dāng)前服務(wù)器的 myid
  o self_zxid 當(dāng)前服務(wù)器上所保存的數(shù)據(jù)的最大 zxid
  o vote_id 被推舉的服務(wù)器的 myid
  o vote_zxid 被推舉的服務(wù)器上所保存的數(shù)據(jù)的最大 zxid

投票流程

• 自增選舉輪次
  Zookeeper 規(guī)定所有有效的投票都必須在同一輪次中杂腰。每個(gè)服務(wù)器在開始新一輪投票時(shí)垃你，會(huì)先對(duì)自己維護(hù)的 logicClock 進(jìn)行自增操作。

• 初始化選票
  每個(gè)服務(wù)器在廣播自己的選票前喂很，會(huì)將自己的投票箱清空惜颇。該投票箱記錄了所收到的選票。例：服務(wù)器 2 投票給服務(wù)器 3少辣，服務(wù)器 3 投
  票給服務(wù)器 1凌摄，則服務(wù)器 1 的投票箱為(2, 3), (3, 1), (1, 1)。票箱中只會(huì)記錄每一投票者的最后一票漓帅，如投票者更新自己的選票锨亏，則
  其它服務(wù)器收到該新選票后會(huì)在自己票箱中更新該服務(wù)器的選票痴怨。

• 發(fā)送初始化選票
  每個(gè)服務(wù)器最開始都是通過廣播把票投給自己。

• 接收外部投票
  服務(wù)器會(huì)嘗試從其它服務(wù)器獲取投票器予，并記入自己的投票箱內(nèi)浪藻。如果無法獲取任何外部投票，則會(huì)確認(rèn)自己是否與集群中其它服務(wù)器保
  持著有效連接乾翔。如果是爱葵，則再次發(fā)送自己的投票；如果否反浓，則馬上與之建立連接萌丈。

• 判斷選舉輪次
  收到外部投票后，首先會(huì)根據(jù)投票信息中所包含的 logicClock 來進(jìn)行不同處理

  • 外部投票的 logicClock 大于自己的 logicClock勾习。說明該服務(wù)器的選舉輪次落后于其它服務(wù)器的選舉輪次浓瞪，立即清空自己的投
    票箱并將自己的 logicClock 更新為收到的 logicClock，然后再對(duì)比自己之前的投票與收到的投票以確定是否需要變更自己的
    投票巧婶，最終再次將自己的投票廣播出去乾颁。
  • 外部投票的 logicClock 小于自己的 logicClock。當(dāng)前服務(wù)器直接忽略該投票艺栈，繼續(xù)處理下一個(gè)投票英岭。
  • 外部投票的 logickClock 與自己的相等。當(dāng)時(shí)進(jìn)行選票 PK湿右。

• 選票 PK
  選票 PK 是基于(self_id, self_zxid)與(vote_id, vote_zxid)的對(duì)比

  • 外部投票的logicClock大于自己的logicClock诅妹，則將自己的logicClock及自己的選票的logicClock 變更為收到的logicClock
  • 若 logicClock 一致，則對(duì)比二者的 vote_zxid毅人，若外部投票的 vote_zxid 比較大吭狡，則將自己的票中的 vote_zxid 與 vote_myid
    更新為收到的票中的 vote_zxid 與 vote_myid 并廣播出去，另外將收到的票及自己更新后的票放入自己的票箱丈莺。如果票箱
    內(nèi)已存在(self_myid, self_zxid)相同的選票划煮，則直接覆蓋
  • 若二者 vote_zxid 一致，則比較二者的 vote_myid缔俄，若外部投票的 vote_myid 比較大弛秋，則將自己的票中的 vote_myid 更
    新為收到的票中的 vote_myid 并廣播出去，另外將收到的票及自己更新后的票放入自己的票箱

• 統(tǒng)計(jì)選票
  如果已經(jīng)確定有過半服務(wù)器認(rèn)可了自己的投票（可能是更新后的投票）俐载，則終止投票蟹略。否則繼續(xù)接收其它服務(wù)器的投票。

• 更新服務(wù)器狀態(tài)
  投票終止后遏佣，服務(wù)器開始更新自身狀態(tài)挖炬。若過半的票投給了自己，則將自己的服務(wù)器狀態(tài)更新為 LEADING贼急，否則將自己的狀態(tài)更新為
  FOLLOWING

幾種領(lǐng)導(dǎo)選舉場景

• 集群啟動(dòng)領(lǐng)導(dǎo)選舉
  初始投票給自己
  集群剛啟動(dòng)時(shí)茅茂，所有服務(wù)器的 logicClock 都為 1捏萍，zxid 都為 0。
  各服務(wù)器初始化后空闲，都投票給自己令杈，并將自己的一票存入自己的票箱，如下圖所示碴倾。

  
  
  image.png
  
  

  在上圖中逗噩，(1, 1, 0)第一位數(shù)代表投出該選票的服務(wù)器的 logicClock，第二位數(shù)代表被推薦的服務(wù)器的 myid跌榔，第三位代表被推薦的服
  務(wù)器的最大的 zxid异雁。由于該步驟中所有選票都投給自己，所以第二位的 myid 即是自己的 myid僧须，第三位的 zxid 即是自己的 zxid纲刀。
  此時(shí)各自的票箱中只有自己投給自己的一票。

• 更新選票
  服務(wù)器收到外部投票后担平，進(jìn)行選票 PK示绊，相應(yīng)更新自己的選票并廣播出去，并將合適的選票存入自己的票箱暂论，如下圖所示面褐。

  
  
  image.png
  
  

  服務(wù)器 1 收到服務(wù)器 2 的選票（1, 2, 0）和服務(wù)器 3 的選票（1, 3, 0）后，由于所有的 logicClock 都相等取胎，所有的 zxid 都相等展哭，
  因此根據(jù) myid 判斷應(yīng)該將自己的選票按照服務(wù)器 3 的選票更新為（1, 3, 0），并將自己的票箱全部清空闻蛀，再將服務(wù)器 3 的選票與自
  己的選票存入自己的票箱匪傍，接著將自己更新后的選票廣播出去。此時(shí)服務(wù)器 1 票箱內(nèi)的選票為(1, 3)觉痛，(3, 3)析恢。
  同理，服務(wù)器 2 收到服務(wù)器 3 的選票后也將自己的選票更新為（1, 3, 0）并存入票箱然后廣播秧饮。此時(shí)服務(wù)器 2 票箱內(nèi)的選票為(2, 3)，
  (3, ,3)泽篮。
  服務(wù)器 3 根據(jù)上述規(guī)則盗尸，無須更新選票，自身的票箱內(nèi)選票仍為（3, 3）帽撑。
  服務(wù)器 1 與服務(wù)器 2 更新后的選票廣播出去后泼各，由于三個(gè)服務(wù)器最新選票都相同，最后三者的票箱內(nèi)都包含三張投給服務(wù)器 3 的選票亏拉。

• 根據(jù)選票確定角色
  根據(jù)上述選票扣蜻，三個(gè)服務(wù)器一致認(rèn)為此時(shí)服務(wù)器 3 應(yīng)該是 Leader逆巍。因此服務(wù)器 1 和 2 都進(jìn)入 FOLLOWING 狀態(tài)，而服務(wù)器 3 進(jìn)入
  LEADING 狀態(tài)莽使。之后 Leader 發(fā)起并維護(hù)與 Follower 間的心跳锐极。

  
  
  image.png

Follower 重啟

• Follower 重啟投票給自己
  Follower 重啟，或者發(fā)生網(wǎng)絡(luò)分區(qū)后找不到 Leader芳肌，會(huì)進(jìn)入 LOOKING 狀態(tài)并發(fā)起新的一輪投票灵再。

  
  
  image.png

• 發(fā)現(xiàn)已有 Leader 后成為 Follower
  服務(wù)器 3 收到服務(wù)器 1 的投票后，將自己的狀態(tài) LEADING 以及選票返回給服務(wù)器 1亿笤。服務(wù)器 2 收到服務(wù)器 1 的投票后翎迁，將自己的狀
  態(tài) FOLLOWING 及選票返回給服務(wù)器 1。此時(shí)服務(wù)器 1 知道服務(wù)器 3 是 Leader净薛，并且通過服務(wù)器 2 與服務(wù)器 3 的選票可以確定服務(wù)
  器 3 確實(shí)得到了超過半數(shù)的選票汪榔。因此服務(wù)器 1 進(jìn)入 FOLLOWING 狀態(tài)。

  
  
  image.png

Leader 重啟

• Follower 發(fā)起新投票
  Leader（服務(wù)器 3）宕機(jī)后肃拜，F(xiàn)ollower（服務(wù)器 1 和 2）發(fā)現(xiàn) Leader 不工作了痴腌，因此進(jìn)入 LOOKING 狀態(tài)并發(fā)起新的一輪投票，并
  且都將票投給自己爆班。

image.png

• 廣播更新選票
  服務(wù)器 1 和 2 根據(jù)外部投票確定是否要更新自身的選票衷掷。這里有兩種情況
  • 服務(wù)器 1 和 2 的 zxid 相同。例如在服務(wù)器 3 宕機(jī)前服務(wù)器 1 與 2 完全與之同步柿菩。此時(shí)選票的更新主要取決于 myid 的大
    小
  • 服務(wù)器 1 和 2 的 zxid 不同戚嗅。在舊 Leader 宕機(jī)之前，其所主導(dǎo)的寫操作枢舶，只需過半服務(wù)器確認(rèn)即可懦胞，而不需所有服務(wù)器確
    認(rèn)。換句話說凉泄，服務(wù)器 1 和 2 可能一個(gè)與舊 Leader 同步（即 zxid 與之相同）另一個(gè)不同步（即 zxid 比之絮镂尽）。此時(shí)選
    票的更新主要取決于誰的 zxid 較大

在上圖中后众，服務(wù)器 1 的 zxid 為 11胀糜，而服務(wù)器 2 的 zxid 為 10，因此服務(wù)器 2 將自身選票更新為（3, 1, 11）蒂誉，如下圖所示教藻。

image.png

• 選出新 Leader
  經(jīng)過上一步選票更新后，服務(wù)器 1 與服務(wù)器 2 均將選票投給服務(wù)器 1右锨，因此服務(wù)器 2 成為 Follower括堤，而服務(wù)器 1 成為新的 Leader 并
  維護(hù)與服務(wù)器 2 的心跳。

image.png

• 舊 Leader 恢復(fù)后發(fā)起選舉
  舊的 Leader 恢復(fù)后，進(jìn)入 LOOKING 狀態(tài)并發(fā)起新一輪領(lǐng)導(dǎo)選舉悄窃，并將選票投給自己讥电。此時(shí)服務(wù)器 1 會(huì)將自己的 LEADING 狀態(tài)及
  選票（3, 1, 11）返回給服務(wù)器 3，而服務(wù)器 2 將自己的 FOLLOWING 狀態(tài)及選票（3, 1, 11）返回給服務(wù)器 3轧抗。如下圖所示恩敌。

image.png

• 舊 Leader 成為 Follower
  服務(wù)器 3 了解到 Leader 為服務(wù)器 1，且根據(jù)選票了解到服務(wù)器 1 確實(shí)得到過半服務(wù)器的選票鸦致，因此自己進(jìn)入 FOLLOWING 狀態(tài)潮剪。

image.png

一致性保證

ZAB 協(xié)議保證了在 Leader 選舉的過程中，已經(jīng)被 Commit 的數(shù)據(jù)不會(huì)丟失分唾，未被 Commit 的數(shù)據(jù)對(duì)客戶端不可見抗碰。

Commit 過的數(shù)據(jù)不丟失

• Failover 前狀態(tài)
  為更好演示 Leader Failover 過程，本例中共使用 5 個(gè) Zookeeper 服務(wù)器绽乔。A 作為 Leader弧蝇，共收到 P1、P2折砸、P3 三條消息看疗，并且
  Commit 了 1 和 2，且總體順序?yàn)?P1睦授、P2两芳、C1、P3去枷、C2怖辆。根據(jù)順序性原則，其它 Follower 收到的消息的順序肯定與之相同删顶。其
  中 B 與 A 完全同步竖螃，C 收到 P1、P2逗余、C1特咆，D 收到 P1、P2录粱，E 收到 P1腻格，如下圖所示。

  
  
  image.png

這里要注意

• 由于 A 沒有 C3啥繁，意味著收到 P3 的服務(wù)器的總個(gè)數(shù)不會(huì)超過一半荒叶，也即包含 A 在內(nèi)最多只有兩臺(tái)服務(wù)器收到 P3。在這里
  A 和 B 收到 P3输虱，其它服務(wù)器均未收到 P3

• 由于 A 已寫入 C1、C2脂凶，說明它已經(jīng) Commit 了 P1宪睹、P2愁茁，因此整個(gè)集群有超過一半的服務(wù)器，即最少三個(gè)服務(wù)器收到
  P1亭病、P2鹅很。在這里所有服務(wù)器都收到了 P1，除 E 外其它服務(wù)器也都收到了 P2

• 選出新 Leader
  舊 Leader 也即 A 宕機(jī)后罪帖，其它服務(wù)器根據(jù)上述 FastLeaderElection 算法選出 B 作為新的 Leader促煮。C、D 和 E 成為 Follower 且以
  B 為 Leader 后整袁，會(huì)主動(dòng)將自己最大的 zxid 發(fā)送給 B菠齿，B 會(huì)將 Follower 的 zxid 與自身 zxid 間的所有被 Commit 過的消息同步給
  Follower，如下圖所示坐昙。

  
  
  image.png

在上圖中

• P1 和 P2 都被 A Commit绳匀，因此 B 會(huì)通過同步保證 P1、P2炸客、C1 與 C2 都存在于 C疾棵、D 和 E 中
• P3 由于未被 A Commit，同時(shí)幸存的所有服務(wù)器中 P3 未存在于大多數(shù)據(jù)服務(wù)器中痹仙，因此它不會(huì)被同步到其它 Follower

• 通知 Follower 可對(duì)外服務(wù)
  同步完數(shù)據(jù)后是尔，B 會(huì)向 D、C 和 E 發(fā)送 NEWLEADER 命令并等待大多數(shù)服務(wù)器的 ACK（下圖中 D 和 E 已返回 ACK开仰，加上 B 自身拟枚，
  已經(jīng)占集群的大多數(shù)），然后向所有服務(wù)器廣播 UPTODATE 命令抖所。收到該命令后的服務(wù)器即可對(duì)外提供服務(wù)梨州。

  
  
  image.png

未 Commit 過的消息對(duì)客戶端不可見

在上例中，P3 未被 A Commit 過田轧，同時(shí)因?yàn)闆]有過半的服務(wù)器收到 P3暴匠，因此 B 也未 Commit P3（如果有過半服務(wù)器收到 P3，即
使 A 未 Commit P3傻粘，B 會(huì)主動(dòng) Commit P3每窖，即 C3），所以它不會(huì)將 P3 廣播出去弦悉。
具體做法是窒典，B 在成為 Leader 后，先判斷自身未 Commit 的消息（本例中即 P3）是否存在于大多數(shù)服務(wù)器中從而決定是否要將其
Commit稽莉。然后 B 可得出自身所包含的被 Commit 過的消息中的最小 zxid（記為 min_zxid）與最大 zxid（記為 max_zxid）瀑志。C、D
和 E 向 B 發(fā)送自身 Commit 過的最大消息 zxid（記為 max_zxid）以及未被 Commit 過的所有消息（記為 zxid_set）。B 根據(jù)這些
信息作出如下操作

• 如果 Follower 的 max_zxid 與 Leader 的 max_zxid 相等劈猪，說明該 Follower 與 Leader 完全同步昧甘，無須同步任何數(shù)據(jù)
• 如果 Follower 的 max_zxid 在 Leader 的(min_zxid，max_zxid)范圍內(nèi)战得，Leader 會(huì)通過 TRUNC 命令通知 Follower 將
  其 zxid_set 中大于 Follower 的 max_zxid（如果有）的所有消息全部刪除

上述操作保證了未被 Commit 過的消息不會(huì)被 Commit 從而對(duì)外不可見充边。
上述例子中 Follower 上并不存在未被 Commit 的消息。但可考慮這種情況常侦，如果將上述例子中的服務(wù)器數(shù)量從五增加到七浇冰，服務(wù)器 F
包含 P1、P2聋亡、C1肘习、P3，服務(wù)器 G 包含 P1杀捻、P2井厌。此時(shí)服務(wù)器 F、A 和 B 都包含 P3致讥，但是因?yàn)槠睌?shù)未過半仅仆，因此 B 作為 Leader 不
會(huì) Commit P3，而會(huì)通過 TRUNC 命令通知 F 刪除 P3垢袱。如下圖所示墓拜。

image.png

總結(jié)

• 由于使用主從復(fù)制模式，所有的寫操作都要由 Leader 主導(dǎo)完成请契，而讀操作可通過任意節(jié)點(diǎn)完成咳榜，因此 Zookeeper 讀性能
  遠(yuǎn)好于寫性能，更適合讀多寫少的場景
• 雖然使用主從復(fù)制模式爽锥，同一時(shí)間只有一個(gè) Leader涌韩，但是 Failover 機(jī)制保證了集群不存在單點(diǎn)失敗（SPOF）的問題
• ZAB 協(xié)議保證了 Failover 過程中的數(shù)據(jù)一致性
• 服務(wù)器收到數(shù)據(jù)后先寫本地文件再進(jìn)行處理氯夷，保證了數(shù)據(jù)的持久性