分佈式選舉算法#
內容來自
選舉(election)是分佈式系統實踐中常見的問題，通過打破節點間的對等關係，選得的 leader (或叫 master、coordinator) 有助於實現事務原子性、提升決議效率。
多數派(quorum)的思路幫助我們在網絡分化的情況下達成決議一致性，在 leader 選舉的場景下幫助我們選出唯一 leader。
租約(lease)中心思想是每次租約時長內只有一個節點獲得租約成為 leader、到期後必須重新頒發租約，確保了一個時刻最多只有一個 leader，避免只使用心跳機制時因為網絡擁塞或瞬斷而產生雙主的問題。
Bully 算法 (選舉)#
Bully 算法是最常見的選舉算法, 要求每個節點對應一個序號，序號最高的節點為 leader。leader 宕機後次高序號的節點被重選為 leader。
Bully 算法在選舉過程中，需要用到以下 3 種消息：
- Election 消息，用於發起選舉；
- Alive 消息，對 Election 消息的應答；
- Victory 消息，競選成功的主節點向其他節點發送的宣誓主權的消息。
選舉流程#
- 集群中每個節點判斷自己的 ID 是否為當前活著的節點中 ID 最大的，如果是，則直接向其他節點發送 Victory 消息，宣誓自己的主權；
- 如果自己不是當前活著的節點中 ID 最大的，則向比自己 ID 大的所有節點發送 Election 消息，並等待其他節點的回覆；
- 若在給定的時間範圍內，本節點沒有收到其他節點回覆的 Alive 消息，則認為自己成為主節點，並向其他節點發送 Victory 消息，宣誓自己成為主節點；
- 若接收到來自比自己 ID 大的節點的 Alive 消息，則等待其他節點發送 Victory 消息；若本節點收到比自己 ID 小的節點發送的 Election 消息，則回覆一個 Alive 消息，告知其他節點，我比你大，重新選舉。
優缺點以及應用場景#
優點：
Bully 算法的選擇特別霸道和簡單，誰活著且誰的 ID 最大誰就是主節點，其他節點必須無條件服從。這種算法的優點是，選舉速度快、算法複雜度低、簡單易實現。
缺點：
- 需要每個節點有全局的節點信息，因此額外信息存儲較多；
- 其次，任意一個比當前主節點 ID 大的新節點或節點故障後恢復加入集群的時候，都可能會觸發重新選舉，成為新的主節點，如果該節點頻繁退出、加入集群，就會導致頻繁切主。
應用場景：
MongoDB 的副本集故障轉移功能。
MongoDB 的分佈式選舉中，採用節點的最後操作時間戳來表示 ID，時間戳最新的節點其 ID 最大，也就是說時間戳最新的、活著的節點是主節點。
Raft 算法 (多數派)#
Raft 算法是典型的多數派投票選舉算法，核心思想是 “少數服從多數”，獲得投票最多的節點成為主。
採用 Raft 算法選舉，集群節點的角色有 3 種：
Leader，即主節點，同一時刻只有一個 Leader，負責協調和管理其他節點；Candidate，即候選者，每一個節點都可以成為 Candidate，節點在該角色下才可以被選為新的 Leader；Follower，Leader 的跟隨者，不可以發起選舉。
選舉流程#
- 初始化時，所有節點均為 Follower 狀態。
- 開始選主時，所有節點的狀態由 Follower 轉化為 Candidate，並向其他節點發送選舉請求。
- 其他節點根據接收到的選舉請求的先後順序，回覆是否同意成為主。這裡需要注意的是，在每一輪選舉中，一個節點只能投出一張票。
- 若發起選舉請求的節點獲得超過一半的投票，則成為主節點，其狀態轉化為 Leader，其他節點的狀態則由 Candidate 降為 Follower。Leader 節點與 Follower 節點之間會定期發送心跳包，以檢測主節點是否活著。
- 當 Leader 節點的任期到了，即發現其他伺服器開始下一輪選主週期時，Leader 節點的狀態由 Leader 降級為 Follower，進入新一輪選主。
優缺點以及應用場景#
優點：
- 選舉速度快、算法複雜度低、易於實現；
- 穩定性比 Bully 算法好，這是因為當有新節點加入或節點故障恢復後，會觸發選主，但不一定會真正切主，除非新節點或故障後恢復的節點獲得投票數過半，才會導致切主。
缺點：
要求系統內每個節點都可以相互通信，且需要獲得過半的投票數才能選主成功，因此通信量大。
應用場景：
Google 開源的 Kubernetes, 採用了 etcd 組件就是採用了 Raft 算法來實現選主和一致性的。
ZAB 算法 (多數派)#
ZAB 選舉算法的核心是 “少數服從多數，ID 大的節點優先成為主”，因此選舉過程中通過 (vote_id, vote_zxID) 來表明投票給哪個節點，其中 vote_id 表示被投票節點的 ID，vote_zxID 表示被投票節點的伺服器 zxID。ZAB 算法選主的原則是：server_zxID 最大者成為 Leader；若 server_zxID 相同，則 server_id 最大者成為 Leader。
使用 ZAB 算法選舉時，集群中每個節點擁有 3 種角色：
Leader，主節點；Follower，跟隨者節點；Observer，觀察者，無投票權。
對應到選舉過程中，集群中的節點擁有 4 個狀態：
Looking 狀態，即選舉狀態。當節點處於該狀態時，它會認為當前集群中沒有 Leader，因此自己進入選舉狀態；Leading 狀態，即領導者狀態，表示已經選出主，且當前節點為 Leader；Following 狀態，即跟隨者狀態，集群中已經選出主後，其他非主節點狀態更新為 Following，表示對 Leader 的追隨；Observing 狀態，即觀察者狀態，表示當前節點為 Observer，持觀望態度，沒有投票權和選舉權。
選舉流程#
- 當系統剛啟動時，3 個伺服器當前投票均為第一輪投票，即 epoch=1，且 zxID 均為 0。此時每個伺服器都推選自己，並將選票信息廣播出去；
- 根據判斷規則，由於 3 個 Server 的 epoch、zxID 都相同，因此比較 server_id，較大者即為推選對象，因此 Server 1 和 Server 2 將 vote_id 改為 3，更新自己的投票箱並重新廣播自己的投票；
- 此時系統內所有伺服器都推選了 Server 3，因此 Server 3 當選 Leader，處於 Leading 狀態，向其他伺服器發送心跳包並維護連接；Server1 和 Server2 皆處於 Following 狀態。
優缺點以及應用場景#
優點
- 算法性能高，對系統無特殊要求；
- 算法選舉穩定性比較好，當有新節點加入或節點故障恢復後，會觸發選主，但不一定會真正切主。
缺點
- 採用廣播方式發送信息，若節點中有 n 個節點，每個節點同時廣播，則集群中信息量為 n*(n-1) 個消息，容易出現
廣播風暴(類似分佈式互斥中的分佈式算法的 “信令風暴”)； - 除了投票，還增加了對比節點 ID 和數據 ID，這就意味著還需要知道所有節點的 ID 和數據 ID，所以選舉時間相對較長。
應用場景
為 ZooKeeper 實現分佈式協調功能而設計的。
總結分析#
三種算法對比分析#
思維導圖總結#
思考拓展#
1. 為什麼 “多數派” 選主算法通常採用奇數節點，而不是偶數節點呢#
可能會出現兩個節點均獲得一半投票的情況，採用偶數節點時無法選出主，必須重新投票選舉。但即使重新投票選舉，兩個節點擁有相同投票數的概率也會很大。
2. 分佈式選舉和一致性的關係是什麼#
一致性是指多個副本之間，在同一時刻能否有同樣的值。分佈式選舉通常是實現一致性的基礎，通過選舉出主節點協調和管理其他節點，從而保證其他節點的有序運行以及各個節點之間的一致性。
3. 是否存在一個集群中有雙主的場景？#
雙主的情況，一般是因為網絡故障，比如網絡分區 (某一時刻集群因為網絡不通形成兩個網絡集群) 等導致的。出現雙主的期間，如果雙主均提供服務，可能會導致集群中數據不一致。所以，需要根據業務對數據不一致的容忍度來決定是否允許雙主情況下提供服務。
聯想記憶：集群的腦裂現象，參考: