前言：最近在關(guān)注分布式系統(tǒng)的選舉算法，想了解下 ElasticSearch 是如何選主的，以及使用何種選主算法。發(fā)現(xiàn)了 elastic 官網(wǎng)上的一篇文章，寫得還不錯。故翻譯過來，供大家學(xué)習(xí)，如翻譯有誤，敬請大家指正。原文

介紹

所有的分布式系統(tǒng)必須用這樣或那樣的方式處理一致性問題。為了簡化，我們可以把策略分成兩類。一類是試圖避免非一致性情況的出現(xiàn)以及定義如何保持一致性。另一類對于適用的問題非常強(qiáng)大，但是對其他問題的數(shù)據(jù)模型附加了不可接受的約束。

在本文中，我們將研究第一類的一個示例，以及它如何處理網(wǎng)絡(luò)故障。

為什么要用 Leader ?

在分布式系統(tǒng)中指定一個節(jié)點(diǎn)為 Leader 實(shí)際上與 Java 中的 synchronized 關(guān)鍵字非常相似。Java synchronized 的經(jīng)典例子是兩個線程嘗試遞增同一個整數(shù)。例如，兩個線程試圖分別存入 $100 到同一個賬戶中。每個線程都必須讀取余額，增加其值并將其寫回。假設(shè)初始余額為 $100，并且沒有線程同步，則可能發(fā)生以下情況：

• 線程 A 讀取余額 $100
• 線程 B 讀取余額 $100
• 線程 A 計算新的余額 $200
• 線程 B 計算新的余額 $200
• 線程 A 寫入新的余額 $200
• 線程 B 寫入新的余額 $200

很明顯，賬戶一開始是 $100，總共存了 $200，最后的余額應(yīng)該是 $300。然而，線程 A 的存款被覆蓋，因?yàn)榫€程 B 寫入更新的余額是基于已過時的數(shù)據(jù)計算而來。

Java 中的解決方案是在執(zhí)行增加計算的代碼上使用 synchronized 關(guān)鍵字，它使一個線程在另一個線程讀取余額之前，完成其余額計算并寫入的工作?！缸g者注：多線程串行化」

如果將線程視為節(jié)點(diǎn)，那么可以想象，在分布式系統(tǒng)中很容易出同樣的問題，但沒有synchronized 關(guān)鍵字可以解決。因?yàn)?synchronized 是使用信號量實(shí)現(xiàn)的，而信號量又由底層操作系統(tǒng)和它所運(yùn)行的硬件支持「譯者注：Java 中的 synchronized 的實(shí)現(xiàn)原理并不是信號量」。但是如果我們看看 synchronized 的功能，我們可能會將這個概念應(yīng)用到分布式環(huán)境中。在 Java 中把一個代碼塊聲明為 synchronized 時，它總是同步到特定對象的監(jiān)視器。監(jiān)視器的大小只是一個。這就意味著在任何給定的時間內(nèi)，監(jiān)視器內(nèi)都可能只有一個線程。當(dāng)一個線程請求監(jiān)視器并且監(jiān)視器可用時，它被允許立即進(jìn)入。如果監(jiān)視器被占用，則把線程放入等待隊(duì)列并掛起，直到監(jiān)視器被其它線程釋放。

我們?nèi)绾伟堰@種概念應(yīng)用到分布式環(huán)境中？我們可以在每個節(jié)點(diǎn)上創(chuàng)建任意多個的監(jiān)視器，但是對于給定需要保護(hù)的資源，只存在一個監(jiān)視器。換句話說，每個帳戶余額只有一個監(jiān)視器。這將維護(hù)數(shù)據(jù)一致性的問題轉(zhuǎn)化為確保所有節(jié)點(diǎn)都同意哪個節(jié)點(diǎn)負(fù)責(zé)實(shí)現(xiàn)每個余額的監(jiān)控的問題。在我們這個簡單的例子中，這可以由領(lǐng)導(dǎo)者來處理，剩下要做的就是選出一個領(lǐng)導(dǎo)者。

如果你像我一樣有 P2P 背景，你可能會建議使用分布式哈希表（distributed hash table，DHT）而不是領(lǐng)導(dǎo)者來決定哪個節(jié)點(diǎn)實(shí)現(xiàn)每個資源的監(jiān)視器。事實(shí)上，有一些非常棒的 DHT 實(shí)現(xiàn)可以處理每小時數(shù)千個節(jié)點(diǎn)的離開和加入?？紤]到它們也可以在不了解底層網(wǎng)絡(luò)拓?fù)涞漠悩?gòu)網(wǎng)絡(luò)中工作，4 到 10 個消息跳轉(zhuǎn)的查詢響應(yīng)時間是相當(dāng)不錯的，但是在節(jié)點(diǎn)同構(gòu)且網(wǎng)絡(luò)相當(dāng)穩(wěn)定的網(wǎng)格設(shè)置中，我們可以做得更好。

在 Elasticsearch 的典型場景中，一個可以簡化的地方是集群沒有那么多節(jié)點(diǎn)。通常，節(jié)點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)少于單個節(jié)點(diǎn)能夠維護(hù)的連接數(shù)量，而網(wǎng)格環(huán)境不必頻繁地處理節(jié)點(diǎn)的連接和離開。這就是為什么 Leader 方法更適合于 Elasticsearch?！缸g者注：官方建議 ES 節(jié)點(diǎn)數(shù)為百級別，此處解釋了為什么 ES 采用 主從架構(gòu)模式，而不是 P2P 式的無主模式」

ZenDiscovery 機(jī)制

因此我們有一個 Leader 定期將當(dāng)前版本的全局集群狀態(tài)推送到每個節(jié)點(diǎn)。如果 Leader 宕掉了怎么辦？即便我們的節(jié)點(diǎn)相當(dāng)可靠也并不意味著我們可以接受單點(diǎn)故障。假設(shè)只有 Leader節(jié)點(diǎn)崩潰，而所有其他節(jié)點(diǎn)仍然能夠通信，則 Elasticsearch 可以優(yōu)雅地處理這一問題。因?yàn)槠溆喙?jié)點(diǎn)將檢測到 Leader 的失?。ǜ_切地說是沒有收到來自 Leader 的消息），并啟動Leader 選舉。如果使用的是 ZenDiscovery（默認(rèn)），過程如下「譯者注：從ZenDiscovery過程看，它使用類 Bullly 算法來進(jìn)行選舉，使用法定人數(shù)來解決腦裂問題」：

• 每個節(jié)點(diǎn)計算已知的最小節(jié)點(diǎn) ID，并向該節(jié)點(diǎn)發(fā)送投票
• 如果一個節(jié)點(diǎn)獲得足夠多的投票「譯者注：多數(shù)派」，并且該節(jié)點(diǎn)也為自己投票，那么它將扮演 Leader 的角色，并開始向其它節(jié)點(diǎn)發(fā)布集群狀態(tài)。

贏得選舉所需足夠票數(shù)的定義就是法定人數(shù)。ElasticSearch 中的法定人數(shù)是一個可配的參數(shù)。在分布式系統(tǒng)中，一個節(jié)點(diǎn)不能確定另一個節(jié)點(diǎn)是死亡還是網(wǎng)絡(luò)消息不可達(dá)，因此通常有一個先前商定的閾值——法定人數(shù)大小（quorum size，也可翻譯成仲裁大?。獊泶砹硪环降耐镀薄Ｒ砸韵聢鼍盀槔阂粋€集群有 A、B、C、D、E 五個節(jié)點(diǎn)，法定人數(shù)為 3。A 是 Leader。碰巧，A 和 B 在一個網(wǎng)絡(luò)上，C、D、E 在另一個網(wǎng)絡(luò)上，這些網(wǎng)絡(luò)通過一條鏈路連接起來。

image

當(dāng)這條鏈路失效時，A 和 B 仍然可以通信，但不能與 C、D、E 通信。同樣，在另一個網(wǎng)絡(luò)上，C、D、E 可以通信，但不能與 A、B 通信。

image

接下來會發(fā)生的是：節(jié)點(diǎn) C、D、E 探測到它們無法與 Leader A 通信，隨后向 C 發(fā)起投票選舉。一旦 C 獲得了三票，它就開始扮演領(lǐng)導(dǎo)者的角色，并開始向 D、E 發(fā)布通知。在另一個網(wǎng)絡(luò)中，Leader A 探測到它無法與節(jié)點(diǎn) C、D、E 通信。Leader A 計算新的集群大小小于法定人數(shù)大小并放棄 Leader 角色，有效地阻止節(jié)點(diǎn) A、B 響應(yīng)查詢，直到鏈路恢復(fù)。在現(xiàn)實(shí)生活中，不太可能有人被重要的網(wǎng)絡(luò)電纜絆倒，但是網(wǎng)絡(luò)比我上面的例子更復(fù)雜，而且網(wǎng)絡(luò)分區(qū)實(shí)際上并不少見。不難想象，當(dāng)一個系統(tǒng)依賴于多個數(shù)據(jù)中心時，很容易出現(xiàn)網(wǎng)絡(luò)分裂；另一種就是錯誤的網(wǎng)絡(luò)路由和交換機(jī)配置。正如在《網(wǎng)絡(luò)是可靠的》中提到的，網(wǎng)卡確實(shí)會在發(fā)送出站包的同時丟棄所有入站包，導(dǎo)致服務(wù)器仍然發(fā)送心跳，但無法處理任何請求。

避免腦裂（Brain Split）

法定人數(shù)大小有兩個明顯的優(yōu)勢：首先，它簡化了選舉過程，因?yàn)檫x票只需要送給它們重新投票的節(jié)點(diǎn)。其次，更重要的是，這是避免大腦分裂的唯一方法。想象一下，相同的集群和相同的網(wǎng)絡(luò)分裂，但法定人數(shù)大小為 2。C 仍然會被選為領(lǐng)導(dǎo)者，但是 A 不會放棄領(lǐng)導(dǎo)者的角色。這樣就會產(chǎn)生兩個領(lǐng)導(dǎo)者以及彼此無法感知的集群。這就是所謂的腦裂。兩個集群都將接受讀寫操作，并且如預(yù)期的那樣，它們將不同步。如果沒有人為干預(yù)，他們可能永遠(yuǎn)都無法恢復(fù)。根據(jù)數(shù)據(jù)模型的不同，也許不可能統(tǒng)一兩個數(shù)據(jù)版本，而迫使其中一個集群丟棄所有的數(shù)據(jù)。

不要重復(fù)造輪子

正如你所料，多年來，領(lǐng)導(dǎo)者選舉一直是學(xué)術(shù)界一個有趣的話題，不少聰明的人也進(jìn)行了大量的思考。如果你更熱衷于讓分布式系統(tǒng)工作，而不是投入大量精力進(jìn)行研究和開發(fā)，那么你最好嘗試實(shí)現(xiàn)一個眾所周知的算法。在將來的某一天，當(dāng)你最終發(fā)現(xiàn)了系統(tǒng)中那個瘋狂的 bug時，它很可能只是實(shí)現(xiàn)中的一個 bug，而不是算法中的一個主要設(shè)計缺陷。當(dāng)然，這同樣適用于調(diào)整或集成現(xiàn)有的實(shí)現(xiàn)，而不是從頭開始實(shí)現(xiàn)，特別是如果你希望使用更高級的算法。這份 bug 報告 說明了創(chuàng)造一個好的領(lǐng)導(dǎo)者選舉實(shí)現(xiàn)是多么的復(fù)雜，即使你有一個合理的算法。

Bully 算法

Bully 算法是領(lǐng)導(dǎo)者選舉的基本算法之一。它假設(shè)所有節(jié)點(diǎn)都有一個惟一的 ID，它強(qiáng)制按所有節(jié)點(diǎn)排序。任何時候的當(dāng)前 Leader 都是集群中 ID 最大的節(jié)點(diǎn)。此算法的優(yōu)點(diǎn)是易于實(shí)現(xiàn)，但不能很好地處理 ID 最大的節(jié)點(diǎn)不穩(wěn)定的情況。特別是在繁瑣的 Leader角色下， ID 最大的節(jié)點(diǎn)容易過載。因此，作為領(lǐng)導(dǎo)者它將崩潰；選擇 ID 第二大的節(jié)點(diǎn)；而最大的 ID 節(jié)點(diǎn)將恢復(fù)——因?yàn)樗辉俪d——并隨后再次啟動領(lǐng)導(dǎo)者選舉，只有當(dāng)選和再次崩潰。然而，在底層的硬件接口中，bully 算法非常常見。將選舉推遲到現(xiàn)任領(lǐng)導(dǎo)者失敗之后，可能會避免選舉失敗，但很容易導(dǎo)致腦裂。

Paxos 算法

Paxos 實(shí)際上不僅僅是一個領(lǐng)導(dǎo)者選舉算法。Paxos 是一組協(xié)議族，用于保持分布式系統(tǒng)的一致性。我不會詳細(xì)介紹 Paxos 的各種類型，而是討論 Paxos 的一般概念和特點(diǎn)。Paxos中使用的數(shù)據(jù)模型是一個不斷增長的語句列表，其中每個語句都有一個惟一的編號。經(jīng)過數(shù)學(xué)證明，Paxos 可以保證是，對于相同編號的語句，兩個節(jié)點(diǎn)永遠(yuǎn)不會出現(xiàn)不同，并且只要有一個仲裁者參與，算法就會繼續(xù)。這意味著節(jié)點(diǎn)永遠(yuǎn)不會不一致，算法永遠(yuǎn)不會陷入死鎖，但是如果沒有足夠的節(jié)點(diǎn)在線，它可能會停止。這些保證實(shí)際上與我們想要的領(lǐng)導(dǎo)者選舉算法非常相似。我們希望參與集群的所有節(jié)點(diǎn)都能就哪個節(jié)點(diǎn)是領(lǐng)導(dǎo)者達(dá)成一致，我們不希望任何其他節(jié)點(diǎn)能夠運(yùn)行并創(chuàng)建自己的集群，從而導(dǎo)致腦裂。用 Paxos 進(jìn)行領(lǐng)導(dǎo)者選舉就變得像提出“我是領(lǐng)導(dǎo)者”這樣簡單。如果它被接受，那么它就是領(lǐng)導(dǎo)者，直到另一個節(jié)點(diǎn)提議成為領(lǐng)導(dǎo)者。然而，這還不足以避免腦裂。在上面的網(wǎng)絡(luò)分區(qū)示例中，現(xiàn)有的 Leader A 不會收到來自另一個交換機(jī)上節(jié)點(diǎn) C 的通知。這就需要有另一個標(biāo)準(zhǔn)來結(jié)束這種領(lǐng)導(dǎo)關(guān)系。一種方法是，當(dāng)發(fā)起領(lǐng)導(dǎo)者選舉時，所使用的語句將出現(xiàn)在表單上：“I am leader until”。但另一種更好的方法是，領(lǐng)導(dǎo)者能夠探測到與之通信的節(jié)點(diǎn)數(shù)低于法定人數(shù)，然后將自己降級。

根據(jù)上面的網(wǎng)絡(luò)分區(qū)示例，讓我們假設(shè)一個看門人將網(wǎng)絡(luò)線纜連接到節(jié)點(diǎn) C，然后將線纜重新連接到另一個交換機(jī)，從而產(chǎn)生一個新的網(wǎng)絡(luò)分區(qū)。

image

有趣的是，法定人數(shù)現(xiàn)在由節(jié)點(diǎn) A、B、C組成，而不是以前的C、D、E。如果這些節(jié)點(diǎn)使用的是 Paxos，它們的數(shù)據(jù)可能是這樣的：

image

根據(jù) Paxos 進(jìn)行領(lǐng)導(dǎo)者選舉的具體實(shí)施情況，有許多可能的結(jié)果，但它們都有兩個共同點(diǎn)。節(jié)點(diǎn) D、E 不能選舉新的領(lǐng)導(dǎo)者，因?yàn)樗鼈儧]有達(dá)到法定人數(shù)。在得知節(jié)點(diǎn) C 在第二輪選舉中當(dāng)選之前，節(jié)點(diǎn) A、B 不會選舉新的領(lǐng)導(dǎo)者。假定每個 Leader 任期（leader term）的結(jié)束條件都是超時，那么有兩種可能的結(jié)果。如果節(jié)點(diǎn) C 在其任期結(jié)束前與節(jié)點(diǎn) A、B 建立了聯(lián)系，則節(jié)點(diǎn) C 將重新建立一個法定人數(shù)，恢復(fù)其領(lǐng)導(dǎo)角色，且無需進(jìn)行領(lǐng)導(dǎo)者選舉。如果它的任期結(jié)束，則可以選舉節(jié)點(diǎn)A、B、C。假定節(jié)點(diǎn) A 是網(wǎng)絡(luò)上第一個發(fā)現(xiàn) C 的節(jié)點(diǎn)，它將嘗試連任第 2 期的 Leader，但節(jié)點(diǎn) C 會拒絕，因?yàn)樗呀?jīng)有了第 2 期的 Leader。然后，節(jié)點(diǎn) A 可以選擇嘗試競選第 3 任期。如果這樣，它還將通知節(jié)點(diǎn) B 關(guān)于節(jié)點(diǎn) C 的第 2 任期時間?，F(xiàn)在，如果節(jié)點(diǎn) C 和 A 同時當(dāng)選呢？「譯者注：出現(xiàn)平票，票數(shù)相同」對這個問題的完整回答需要深入研究 Paxos 的細(xì)節(jié)，這超出了本文的范圍，但是簡短的回答是選舉將會失敗。事實(shí)上，原始Paxos 論文提出使用領(lǐng)導(dǎo)者選舉算法來決定應(yīng)該哪些節(jié)點(diǎn)開始一個新提案，但自從 Paxos 協(xié)議保證不會出現(xiàn)不一致，即使有多個節(jié)點(diǎn)提出矛盾的語句，這種領(lǐng)導(dǎo)者選舉可能只是一個簡單的啟發(fā)式算法，以避免連續(xù)失敗。例如，一個節(jié)點(diǎn)可能決定在重新嘗試提出一個失敗的語句之前等待一段隨機(jī)時間。Paxos 在何時以及如何進(jìn)行領(lǐng)導(dǎo)者選舉方面的靈活性，比簡單的恃強(qiáng)凌弱算法有很大的優(yōu)勢，因?yàn)樵诂F(xiàn)實(shí)生活中有比死網(wǎng)絡(luò)鏈接多得多的失敗模式。

總結(jié)

在這篇文章中，我試圖給一些已經(jīng)進(jìn)入學(xué)術(shù)界的領(lǐng)導(dǎo)者選舉算一個簡單的洞察。濃縮版是這樣：

• 如果您關(guān)心數(shù)據(jù)，則法定人數(shù)大小非常重要。
• Paxos 算法確實(shí)很穩(wěn)健，但實(shí)現(xiàn)起來并不容易。
• 最好是實(shí)現(xiàn)一個眾所周知的算法，其中的優(yōu)點(diǎn)和缺點(diǎn)都是已知的，而不是在以后得到一個大驚喜。這當(dāng)然有很多選擇。