柚子快報邀請碼778899分享：分布式核心技術(shù)之分布式選舉
柚子快報邀請碼778899分享：分布式核心技術(shù)之分布式選舉
文章目錄
為什么要有分布式選舉？分布式選舉的算法長者為大：Bully 算法民主投票：Raft 算法具有優(yōu)先級的民主投票：ZAB 算法
三種選舉算法的對比分析
為什么要有分布式選舉？
主節(jié)點，在一個分布式集群中負責(zé)對其他節(jié)點的協(xié)調(diào)和管理，也就是說，其他節(jié)點都必須聽從主節(jié)點的安排。主節(jié)點的存在，就可以保證其他節(jié)點的有序運行，以及數(shù)據(jù)庫集群中的寫入數(shù)據(jù)在每個節(jié)點上的一致性。這里的一致性是指，數(shù)據(jù)在每個集群節(jié)點中都是一樣的，不存在不同的情況。當(dāng)然，如果主故障了，集群就會天下大亂。比如，數(shù)據(jù)庫集群中主節(jié)點故障后，可能導(dǎo)致每個節(jié)點上的數(shù)據(jù)會不一致。分布式系統(tǒng)中就是“集群不可一刻無主”。總結(jié)來說，選舉的作用就是選出一個主節(jié)點，由它來協(xié)調(diào)和管理其他節(jié)點，以保證集群有序運行和節(jié)點間數(shù)據(jù)的一致性。
分布式選舉的算法
如何在集群中選出一個合適的主呢？這是一個技術(shù)活兒，目前常見的選主方法有基于序號選舉的算法（ 比如，Bully 算法）、多數(shù)派算法（比如，Raft 算法、ZAB 算法）等。
長者為大：Bully 算法
Bully 算法是一種霸道的集群選主算法，為什么說是霸道呢？因為它的選舉原則是“長者”為大，即在所有活著的節(jié)點中，選取 ID 最大的節(jié)點作為主節(jié)點。在 Bully 算法中，節(jié)點的角色有兩種：普通節(jié)點和主節(jié)點。初始化時，所有節(jié)點都是平等的，都是普通節(jié)點，并且都有成為主的權(quán)利。但是，當(dāng)選主成功后，有且僅有一個節(jié)點成為主節(jié)點，其他所有節(jié)點都是普通節(jié)點。當(dāng)且僅當(dāng)主節(jié)點故障或與其他節(jié)點失去聯(lián)系后，才會重新選主。Bully 算法在選舉過程中，需要用到以下 3 種消息：
Election 消息，用于發(fā)起選舉；Alive 消息，對 Election 消息的應(yīng)答；Victory 消息，競選成功的主節(jié)點向其他節(jié)點發(fā)送的宣誓主權(quán)的消息。 Bully 算法選舉的原則是“長者為大”，意味著它的假設(shè)條件是，集群中每個節(jié)點均知道其他節(jié)點的 ID。在此前提下，其具體的選舉過程是：
集群中每個節(jié)點判斷自己的 ID 是否為當(dāng)前活著的節(jié)點中 ID 最大的，如果是，則直接向其他節(jié)點發(fā)送 Victory 消息，宣誓自己的主權(quán)；如果自己不是當(dāng)前活著的節(jié)點中 ID 最大的，則向比自己 ID 大的所有節(jié)點發(fā)送 Election 消息，并等待其他節(jié)點的回復(fù)；若在給定的時間范圍內(nèi)，本節(jié)點沒有收到其他節(jié)點回復(fù)的 Alive 消息，則認為自己成為主節(jié)點，并向其他節(jié)點發(fā)送 Victory 消息，宣誓自己成為主節(jié)點；若接收到來自比自己 ID 大的節(jié)點的 Alive 消息，則等待其他節(jié)點發(fā)送 Victory 消息；若本節(jié)點收到比自己 ID 小的節(jié)點發(fā)送的 Election 消息，則回復(fù)一個 Alive 消息，告知其他節(jié)點，我比你大，重新選舉。
目前已經(jīng)有很多開源軟件采用了 Bully 算法進行選主，比如 MongoDB 的副本集故障轉(zhuǎn)移功能。MongoDB 的分布式選舉中，采用節(jié)點的最后操作時間戳來表示 ID，時間戳最新的節(jié)點其 ID 最大，也就是說時間戳最新的、活著的節(jié)點是主節(jié)點。Bully 算法的選擇特別霸道和簡單，誰活著且誰的 ID 最大誰就是主節(jié)點，其他節(jié)點必須無條件服從。這種算法的優(yōu)點是，選舉速度快、算法復(fù)雜度低、簡單易實現(xiàn)。但這種算法的缺點在于，需要每個節(jié)點有全局的節(jié)點信息，因此額外信息存儲較多；其次，任意一個比當(dāng)前主節(jié)點 ID 大的新節(jié)點或節(jié)點故障后恢復(fù)加入集群的時候，都可能會觸發(fā)重新選舉，成為新的主節(jié)點，如果該節(jié)點頻繁退出、加入集群，就會導(dǎo)致頻繁切主。
民主投票：Raft 算法
Raft 算法是典型的多數(shù)派投票選舉算法，其選舉機制與我們?nèi)粘Ｉ钪械拿裰魍镀睓C制類似，核心思想是“少數(shù)服從多數(shù)”。也就是說，Raft 算法中，獲得投票最多的節(jié)點成為主。采用 Raft 算法選舉，集群節(jié)點的角色有 3 種：
Leader，即主節(jié)點，同一時刻只有一個 Leader，負責(zé)協(xié)調(diào)和管理其他節(jié)點；Candidate，即候選者，每一個節(jié)點都可以成為 Candidate，節(jié)點在該角色下才可以被選為新的 Leader；Follower，Leader 的跟隨者，不可以發(fā)起選舉。 Raft 選舉的流程，可以分為以下幾步：
初始化時，所有節(jié)點均為 Follower 狀態(tài)。開始選主時，所有節(jié)點的狀態(tài)由 Follower 轉(zhuǎn)化為 Candidate，并向其他節(jié)點發(fā)送選舉請求。其他節(jié)點根據(jù)接收到的選舉請求的先后順序，回復(fù)是否同意成為主。這里需要注意的是，在每一輪選舉中，一個節(jié)點只能投出一張票。若發(fā)起選舉請求的節(jié)點獲得超過一半的投票，則成為主節(jié)點，其狀態(tài)轉(zhuǎn)化為 Leader，其他節(jié)點的狀態(tài)則由 Candidate 降為 Follower。Leader 節(jié)點與 Follower 節(jié)點之間會定期發(fā)送心跳包，以檢測主節(jié)點是否活著。當(dāng) Leader 節(jié)點的任期到了，即發(fā)現(xiàn)其他服務(wù)器開始下一輪選主周期時，Leader 節(jié)點的狀態(tài)由 Leader 降級為 Follower，進入新一輪選主。 節(jié)點的狀態(tài)遷移如下所示（圖中的 term 指的是選舉周期）： Raft 算法中，選主是周期進行的，包括選主和任值兩個時間段，選主階段對應(yīng)投票階段，任值階段對應(yīng)節(jié)點成為主之后的任期。但也有例外的時候，如果主節(jié)點故障，會立馬發(fā)起選舉，重新選出一個主節(jié)點。Google 開源的 Kubernetes，擅長容器管理與調(diào)度，為了保證可靠性，通常會部署 3 個節(jié)點用于數(shù)據(jù)備份。這 3 個節(jié)點中，有一個會被選為主，其他節(jié)點作為備。Kubernetes 的選主采用的是開源的 etcd 組件。etcd 的集群管理器 etcds，是一個高可用、強一致性的服務(wù)發(fā)現(xiàn)存儲倉庫，就是采用了 Raft 算法來實現(xiàn)選主和一致性的。Raft 算法具有選舉速度快、算法復(fù)雜度低、易于實現(xiàn)的優(yōu)點；缺點是，它要求系統(tǒng)內(nèi)每個節(jié)點都可以相互通信，且需要獲得過半的投票數(shù)才能選主成功，因此通信量大。該算法選舉穩(wěn)定性比 Bully 算法好，這是因為當(dāng)有新節(jié)點加入或節(jié)點故障恢復(fù)后，會觸發(fā)選主，但不一定會真正切主，除非新節(jié)點或故障后恢復(fù)的節(jié)點獲得投票數(shù)過半，才會導(dǎo)致切主。
具有優(yōu)先級的民主投票：ZAB 算法
ZAB（ZooKeeper Atomic Broadcast）選舉算法是為 ZooKeeper 實現(xiàn)分布式協(xié)調(diào)功能而設(shè)計的。相較于 Raft 算法的投票機制，ZAB 算法增加了通過節(jié)點 ID 和數(shù)據(jù) ID 作為參考進行選主，節(jié)點 ID 和數(shù)據(jù) ID 越大，表示數(shù)據(jù)越新，優(yōu)先成為主。相比較于 Raft 算法，ZAB 算法盡可能保證數(shù)據(jù)的最新性。所以，ZAB 算法可以說是對 Raft 算法的改進。使用 ZAB 算法選舉時，集群中每個節(jié)點擁有 3 種角色：
Leader，主節(jié)點；Follower，跟隨者節(jié)點；Observer，觀察者，無投票權(quán)。 選舉過程中，集群中的節(jié)點擁有 4 個狀態(tài)：
Looking 狀態(tài)，即選舉狀態(tài)。當(dāng)節(jié)點處于該狀態(tài)時，它會認為當(dāng)前集群中沒有 Leader，因此自己進入選舉狀態(tài)。Leading 狀態(tài)，即領(lǐng)導(dǎo)者狀態(tài)，表示已經(jīng)選出主，且當(dāng)前節(jié)點為 Leader。Following 狀態(tài)，即跟隨者狀態(tài)，集群中已經(jīng)選出主后，其他非主節(jié)點狀態(tài)更新為 Following，表示對 Leader 的追隨。Observing 狀態(tài)，即觀察者狀態(tài)，表示當(dāng)前節(jié)點為 Observer，持觀望態(tài)度，沒有投票權(quán)和選舉權(quán)。 投票過程中，每個節(jié)點都有一個唯一的三元組 (server_id, server_zxID, epoch)，其中 server_id 表示本節(jié)點的唯一 ID；server_zxID 表示本節(jié)點存放的數(shù)據(jù) ID，數(shù)據(jù) ID 越大表示數(shù)據(jù)越新，選舉權(quán)重越大；epoch 表示當(dāng)前選取輪數(shù)，一般用邏輯時鐘表示。ZAB 選舉算法的核心是“少數(shù)服從多數(shù)，ID 大的節(jié)點優(yōu)先成為主”，因此選舉過程中通過 (vote_id, vote_zxID) 來表明投票給哪個節(jié)點，其中 vote_id 表示被投票節(jié)點的 ID，vote_zxID 表示被投票節(jié)點的服務(wù)器 zxID。ZAB 算法選主的原則是：server_zxID 最大者成為 Leader；若 server_zxID 相同，則 server_id 最大者成為 Leader。
以 3 個 Server 的集群為例，此處每個 Server 代表一個節(jié)點，介紹 ZAB 選主的過程。
第一步：當(dāng)系統(tǒng)剛啟動時，3 個服務(wù)器當(dāng)前投票均為第一輪投票，即 epoch=1，且 zxID 均為 0。此時每個服務(wù)器都推選自己，并將選票信息
ZAB 算法性能高，對系統(tǒng)無特殊要求，采用廣播方式發(fā)送信息，若節(jié)點中有 n 個節(jié)點，每個節(jié)點同時廣播，則集群中信息量為 n*(n-1) 個消息，容易出現(xiàn)廣播風(fēng)暴；且除了投票，還增加了對比節(jié)點 ID 和數(shù)據(jù) ID，這就意味著還需要知道所有節(jié)點的 ID 和數(shù)據(jù) ID，所以選舉時間相對較長。但該算法選舉穩(wěn)定性比較好，當(dāng)有新節(jié)點加入或節(jié)點故障恢復(fù)后，會觸發(fā)選主，但不一定會真正切主，除非新節(jié)點或故障后恢復(fù)的節(jié)點數(shù)據(jù) ID 和節(jié)點 ID 最大，且獲得投票數(shù)過半，才會導(dǎo)致切主。
三種選舉算法的對比分析
分布式選舉的 3 種經(jīng)典算法，即 Bully 算法、Raft 算法和 ZAB 算法。從消息傳遞內(nèi)容、選舉機制和選舉過程的維度，對這 3 種算法進行一個對比分析
知識擴展：為什么“多數(shù)派”選主算法通常采用奇數(shù)節(jié)點，而不是偶數(shù)節(jié)點呢？ 多數(shù)派選主算法的核心是少數(shù)服從多數(shù)，獲得投票多的節(jié)點勝出。想象一下，如果現(xiàn)在采用偶數(shù)節(jié)點集群，當(dāng)兩個節(jié)點均獲得一半投票時，到底應(yīng)該選誰為主呢？ 答案是，在這種情況下，無法選出主，必須重新投票選舉。但即使重新投票選舉，兩個節(jié)點擁有相同投票數(shù)的概率也會很大。因此，多數(shù)派選主算法通常采用奇數(shù)節(jié)點。 這，也是大家通常看到 ZooKeeper、 etcd、Kubernetes 等開源軟件選主均采用奇數(shù)節(jié)點的一個關(guān)鍵原因。
你知道的越多，你不知道的越多。
柚子快報邀請碼778899分享：分布式核心技術(shù)之分布式選舉
文章鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Farfetch優(yōu)選時尚
