柚子快報邀請碼778899分享：分布式核心技術之分布式選舉

http://yzkb.51969.com/

文章目錄

為什么要有分布式選舉？分布式選舉的算法長者為大：Bully 算法民主投票：Raft 算法具有優(yōu)先級的民主投票：ZAB 算法

三種選舉算法的對比分析

為什么要有分布式選舉？

主節(jié)點，在一個分布式集群中負責對其他節(jié)點的協(xié)調和管理，也就是說，其他節(jié)點都必須聽從主節(jié)點的安排。主節(jié)點的存在，就可以保證其他節(jié)點的有序運行，以及數(shù)據庫集群中的寫入數(shù)據在每個節(jié)點上的一致性。這里的一致性是指，數(shù)據在每個集群節(jié)點中都是一樣的，不存在不同的情況。當然，如果主故障了，集群就會天下大亂。比如，數(shù)據庫集群中主節(jié)點故障后，可能導致每個節(jié)點上的數(shù)據會不一致。分布式系統(tǒng)中就是“集群不可一刻無主”?？偨Y來說，選舉的作用就是選出一個主節(jié)點，由它來協(xié)調和管理其他節(jié)點，以保證集群有序運行和節(jié)點間數(shù)據的一致性。

分布式選舉的算法

如何在集群中選出一個合適的主呢？這是一個技術活兒，目前常見的選主方法有基于序號選舉的算法（ 比如，Bully 算法）、多數(shù)派算法（比如，Raft 算法、ZAB 算法）等。

長者為大：Bully 算法

Bully 算法是一種霸道的集群選主算法，為什么說是霸道呢？因為它的選舉原則是“長者”為大，即在所有活著的節(jié)點中，選取 ID 最大的節(jié)點作為主節(jié)點。在 Bully 算法中，節(jié)點的角色有兩種：普通節(jié)點和主節(jié)點。初始化時，所有節(jié)點都是平等的，都是普通節(jié)點，并且都有成為主的權利。但是，當選主成功后，有且僅有一個節(jié)點成為主節(jié)點，其他所有節(jié)點都是普通節(jié)點。當且僅當主節(jié)點故障或與其他節(jié)點失去聯(lián)系后，才會重新選主。Bully 算法在選舉過程中，需要用到以下 3 種消息：

Election 消息，用于發(fā)起選舉；Alive 消息，對 Election 消息的應答；Victory 消息，競選成功的主節(jié)點向其他節(jié)點發(fā)送的宣誓主權的消息。 Bully 算法選舉的原則是“長者為大”，意味著它的假設條件是，集群中每個節(jié)點均知道其他節(jié)點的 ID。在此前提下，其具體的選舉過程是：

集群中每個節(jié)點判斷自己的 ID 是否為當前活著的節(jié)點中 ID 最大的，如果是，則直接向其他節(jié)點發(fā)送 Victory 消息，宣誓自己的主權；如果自己不是當前活著的節(jié)點中 ID 最大的，則向比自己 ID 大的所有節(jié)點發(fā)送 Election 消息，并等待其他節(jié)點的回復；若在給定的時間范圍內，本節(jié)點沒有收到其他節(jié)點回復的 Alive 消息，則認為自己成為主節(jié)點，并向其他節(jié)點發(fā)送 Victory 消息，宣誓自己成為主節(jié)點；若接收到來自比自己 ID 大的節(jié)點的 Alive 消息，則等待其他節(jié)點發(fā)送 Victory 消息；若本節(jié)點收到比自己 ID 小的節(jié)點發(fā)送的 Election 消息，則回復一個 Alive 消息，告知其他節(jié)點，我比你大，重新選舉。

目前已經有很多開源軟件采用了 Bully 算法進行選主，比如 MongoDB 的副本集故障轉移功能。MongoDB 的分布式選舉中，采用節(jié)點的最后操作時間戳來表示 ID，時間戳最新的節(jié)點其 ID 最大，也就是說時間戳最新的、活著的節(jié)點是主節(jié)點。Bully 算法的選擇特別霸道和簡單，誰活著且誰的 ID 最大誰就是主節(jié)點，其他節(jié)點必須無條件服從。這種算法的優(yōu)點是，選舉速度快、算法復雜度低、簡單易實現(xiàn)。但這種算法的缺點在于，需要每個節(jié)點有全局的節(jié)點信息，因此額外信息存儲較多；其次，任意一個比當前主節(jié)點 ID 大的新節(jié)點或節(jié)點故障后恢復加入集群的時候，都可能會觸發(fā)重新選舉，成為新的主節(jié)點，如果該節(jié)點頻繁退出、加入集群，就會導致頻繁切主。

民主投票：Raft 算法

Raft 算法是典型的多數(shù)派投票選舉算法，其選舉機制與我們日常生活中的民主投票機制類似，核心思想是“少數(shù)服從多數(shù)”。也就是說，Raft 算法中，獲得投票最多的節(jié)點成為主。采用 Raft 算法選舉，集群節(jié)點的角色有 3 種：

Leader，即主節(jié)點，同一時刻只有一個 Leader，負責協(xié)調和管理其他節(jié)點；Candidate，即候選者，每一個節(jié)點都可以成為 Candidate，節(jié)點在該角色下才可以被選為新的 Leader；Follower，Leader 的跟隨者，不可以發(fā)起選舉。 Raft 選舉的流程，可以分為以下幾步：

初始化時，所有節(jié)點均為 Follower 狀態(tài)。開始選主時，所有節(jié)點的狀態(tài)由 Follower 轉化為 Candidate，并向其他節(jié)點發(fā)送選舉請求。其他節(jié)點根據接收到的選舉請求的先后順序，回復是否同意成為主。這里需要注意的是，在每一輪選舉中，一個節(jié)點只能投出一張票。若發(fā)起選舉請求的節(jié)點獲得超過一半的投票，則成為主節(jié)點，其狀態(tài)轉化為 Leader，其他節(jié)點的狀態(tài)則由 Candidate 降為 Follower。Leader 節(jié)點與 Follower 節(jié)點之間會定期發(fā)送心跳包，以檢測主節(jié)點是否活著。當 Leader 節(jié)點的任期到了，即發(fā)現(xiàn)其他服務器開始下一輪選主周期時，Leader 節(jié)點的狀態(tài)由 Leader 降級為 Follower，進入新一輪選主。 節(jié)點的狀態(tài)遷移如下所示（圖中的 term 指的是選舉周期）： Raft 算法中，選主是周期進行的，包括選主和任值兩個時間段，選主階段對應投票階段，任值階段對應節(jié)點成為主之后的任期。但也有例外的時候，如果主節(jié)點故障，會立馬發(fā)起選舉，重新選出一個主節(jié)點。Google 開源的 Kubernetes，擅長容器管理與調度，為了保證可靠性，通常會部署 3 個節(jié)點用于數(shù)據備份。這 3 個節(jié)點中，有一個會被選為主，其他節(jié)點作為備。Kubernetes 的選主采用的是開源的 etcd 組件。etcd 的集群管理器 etcds，是一個高可用、強一致性的服務發(fā)現(xiàn)存儲倉庫，就是采用了 Raft 算法來實現(xiàn)選主和一致性的。Raft 算法具有選舉速度快、算法復雜度低、易于實現(xiàn)的優(yōu)點；缺點是，它要求系統(tǒng)內每個節(jié)點都可以相互通信，且需要獲得過半的投票數(shù)才能選主成功，因此通信量大。該算法選舉穩(wěn)定性比 Bully 算法好，這是因為當有新節(jié)點加入或節(jié)點故障恢復后，會觸發(fā)選主，但不一定會真正切主，除非新節(jié)點或故障后恢復的節(jié)點獲得投票數(shù)過半，才會導致切主。

具有優(yōu)先級的民主投票：ZAB 算法

ZAB（ZooKeeper Atomic Broadcast）選舉算法是為 ZooKeeper 實現(xiàn)分布式協(xié)調功能而設計的。相較于 Raft 算法的投票機制，ZAB 算法增加了通過節(jié)點 ID 和數(shù)據 ID 作為參考進行選主，節(jié)點 ID 和數(shù)據 ID 越大，表示數(shù)據越新，優(yōu)先成為主。相比較于 Raft 算法，ZAB 算法盡可能保證數(shù)據的最新性。所以，ZAB 算法可以說是對 Raft 算法的改進。使用 ZAB 算法選舉時，集群中每個節(jié)點擁有 3 種角色：

Leader，主節(jié)點；Follower，跟隨者節(jié)點；Observer，觀察者，無投票權。 選舉過程中，集群中的節(jié)點擁有 4 個狀態(tài)：

Looking 狀態(tài)，即選舉狀態(tài)。當節(jié)點處于該狀態(tài)時，它會認為當前集群中沒有 Leader，因此自己進入選舉狀態(tài)。Leading 狀態(tài)，即領導者狀態(tài)，表示已經選出主，且當前節(jié)點為 Leader。Following 狀態(tài)，即跟隨者狀態(tài)，集群中已經選出主后，其他非主節(jié)點狀態(tài)更新為 Following，表示對 Leader 的追隨。Observing 狀態(tài)，即觀察者狀態(tài)，表示當前節(jié)點為 Observer，持觀望態(tài)度，沒有投票權和選舉權。 投票過程中，每個節(jié)點都有一個唯一的三元組 (server_id, server_zxID, epoch)，其中 server_id 表示本節(jié)點的唯一 ID；server_zxID 表示本節(jié)點存放的數(shù)據 ID，數(shù)據 ID 越大表示數(shù)據越新，選舉權重越大；epoch 表示當前選取輪數(shù)，一般用邏輯時鐘表示。ZAB 選舉算法的核心是“少數(shù)服從多數(shù)，ID 大的節(jié)點優(yōu)先成為主”，因此選舉過程中通過 (vote_id, vote_zxID) 來表明投票給哪個節(jié)點，其中 vote_id 表示被投票節(jié)點的 ID，vote_zxID 表示被投票節(jié)點的服務器 zxID。ZAB 算法選主的原則是：server_zxID 最大者成為 Leader；若 server_zxID 相同，則 server_id 最大者成為 Leader。

以 3 個 Server 的集群為例，此處每個 Server 代表一個節(jié)點，介紹 ZAB 選主的過程。

第一步：當系統(tǒng)剛啟動時，3 個服務器當前投票均為第一輪投票，即 epoch=1，且 zxID 均為 0。此時每個服務器都推選自己，并將選票信息 廣播出去。 第二步：根據判斷規(guī)則，由于 3 個 Server 的 epoch、zxID 都相同，因此比較 server_id，較大者即為推選對象，因此 Server 1 和 Server 2 將 vote_id 改為 3，更新自己的投票箱并重新廣播自己的投票。 第三步：此時系統(tǒng)內所有服務器都推選了 Server 3，因此 Server 3 當選 Leader，處于 Leading 狀態(tài)，向其他服務器發(fā)送心跳包并維護連接；Server1 和 Server2 處于 Following 狀態(tài)。

ZAB 算法性能高，對系統(tǒng)無特殊要求，采用廣播方式發(fā)送信息，若節(jié)點中有 n 個節(jié)點，每個節(jié)點同時廣播，則集群中信息量為 n*(n-1) 個消息，容易出現(xiàn)廣播風暴；且除了投票，還增加了對比節(jié)點 ID 和數(shù)據 ID，這就意味著還需要知道所有節(jié)點的 ID 和數(shù)據 ID，所以選舉時間相對較長。但該算法選舉穩(wěn)定性比較好，當有新節(jié)點加入或節(jié)點故障恢復后，會觸發(fā)選主，但不一定會真正切主，除非新節(jié)點或故障后恢復的節(jié)點數(shù)據 ID 和節(jié)點 ID 最大，且獲得投票數(shù)過半，才會導致切主。

三種選舉算法的對比分析

分布式選舉的 3 種經典算法，即 Bully 算法、Raft 算法和 ZAB 算法。從消息傳遞內容、選舉機制和選舉過程的維度，對這 3 種算法進行一個對比分析

知識擴展：為什么“多數(shù)派”選主算法通常采用奇數(shù)節(jié)點，而不是偶數(shù)節(jié)點呢？ 多數(shù)派選主算法的核心是少數(shù)服從多數(shù)，獲得投票多的節(jié)點勝出。想象一下，如果現(xiàn)在采用偶數(shù)節(jié)點集群，當兩個節(jié)點均獲得一半投票時，到底應該選誰為主呢？ 答案是，在這種情況下，無法選出主，必須重新投票選舉。但即使重新投票選舉，兩個節(jié)點擁有相同投票數(shù)的概率也會很大。因此，多數(shù)派選主算法通常采用奇數(shù)節(jié)點。 這，也是大家通?？吹?ZooKeeper、 etcd、Kubernetes 等開源軟件選主均采用奇數(shù)節(jié)點的一個關鍵原因。

你知道的越多，你不知道的越多。

柚子快報邀請碼778899分享：分布式核心技術之分布式選舉

http://yzkb.51969.com/

文章鏈接