高可用集群中的選舉機制

2019 年 10 月 6 日
筆記

一個高可用的集群里，一般都會存在主節點的選舉機制。這裡以elasticsearch集群為例，介紹一下集群的節點選舉方法。

如果查看Elasticsearch集群里的節點資訊，你會發現裡面有一個節點稱為master節點，而且一個集群只有一個master節點。那麼，什麼是master節點呢? 為什麼集群一定要有一個master節點？master什麼時候產生，又是怎麼產生的呢？

什麼是master節點？

簡單的說，master節點就是集群中的leader，或者管理者。master節點知道所有其它節點的狀態，集群中的一些重要的決策交由它來做。

為什麼集群里一定要有一個master節點？

我們可以想像一下一個沒有master節點的集群是什麼樣子的。假設我們有這樣一個集群：集群中有5個節點，分別是A、B、C、D和E。所有的節點都是普通節點，大家的職責沒有任何區別，而且每一個節點都知道其它節點的資訊。我們來看看這樣的「無政府」狀態的集群是否可以正常運行。

在某一時刻，外部系統發來了一個條數據，這個集群要把這條數據存儲起來。Elasticsearch在存儲數據之前，首先要創建一個索引，而創建索引就要生成分片。那麼，分片應該放在哪些節點呢？嗯，這是個問題！如果有個leader在，那麼，這個決策直接交給leader決定就好了。可是現在沒有，試試發揚民主精神，靠大家群策群力如何？

假設集群需要為這個索引生成2個分片。噢，等等！分片數誰說了算？萬一有人認為需要3個分片，有人認為需要2個分片，怎麼辦？真是寸步難行啊！算了，樂觀點，我們姑且認為每個節點在啟動的時候都設置的是2個分片，而且一直沒有變化，大家在這方面暫時沒有分歧，就2個分片吧。下一步就是決定把這兩個分片放到哪裡。在這個烏合之眾的群體中，最簡單有效的方法就是投票。假設大家都認為應該存放在負載最輕的節點上。因為每個節點都知道其它節點的資訊(包括負載資訊)，所以大家都知道該把分片放到哪個節點。比如，這一次大家一致認為E節點最輕鬆，分片就放到E節點了。OK，大功告成！

事情算是搞定了，可是似乎並不輕鬆。我們來算一下賬。這一次投票中，為了檢查其它節點到狀態，每個節點都和其它所有到節點進行了一次通訊。5個節點累計做了4X5=20次通訊。這只是一個5節點到集群，如果50個節點，一次投票則需要50X49= 2450次通訊。如果每次決策都需要全民投票，那麼實在是太重了。這跟現實社會是一樣的，如果頒布每條法律都需要做一次全民投票，基本上這個社會就無法運轉了。最好的辦法是選一個管理者，然後由他來做決策。全民投票僅用於選擇誰來當管理者。

另外，如果沒有master，會產生腦裂(brain split)問題。

假設我們的集群結構是下面這個樣子的。A和B在一個網路里，C、D和E在另一個網路里。如果兩個網路之間的連接斷了，這個集群就變成了兩個小集群，即腦裂。這兩個小集群各自處理數據。一段時間後，可能網路又聯通了，但是它們之間已經產生了數據衝突，無法解決。

「無政府」狀態的集群似乎問題重重，然而，我們仍然不能就此得出結論，說必須有一個master才行，也許存在某種巧妙的方法可以解決裁決問題，可以解決腦裂問題。不過，設置一個master是一個簡介有效的方法。

有了master節點，集群會怎樣？

假設我們的集群設定了一個master節點，比如節點A。整個集群由它負責管理，它可以決定創建多少分片、在哪裡創建分片。

集群中的B節點收到一條數據。B節點先問一下A：「需要創建幾個分片？在哪裡創建？」 A節點掃描一下集群的負載（也可以定時掃描，把集群狀態存起來），發現E節點負載最小。然後告訴B：「創建2個分片，在E節點」。就這麼簡單。

光靠master節點解決不了腦裂問題，還需要引入一個稱為法定人數(quorum)的概念。法定人數表示一個集群最少需要幾個節點數。比如，設置前面集群的法定人數是3，那麼，當兩個交換機的網路斷開時，就不會出現問題。左側兩個節點組成的網達不到法定人數，因此A節點這個master必須退休，B也要停止工作。右側有三個節點，滿足法定人數要求，則可以選舉master。比如，選舉C節點為master，那麼右側3個節點可以繼續正常工作。當交換機之間的連接通了以後，A和B會重新加入以C為master的集群。整個集群跟之前一樣，只是master從A變成了C。

在交換機斷開的那段時間，由於A和B兩個節點不滿足法定人數，所以它們不做任何數據處理。當它們重新介入集群時，它們當數據和集群中其它節點的數據也就不會有衝突。

法定人數一般設置為N/2+1。N為集群的節點數。

集群是怎麼選舉master的？

理論上，集群有很多種選舉辦法。這裡介紹兩種。

1. Bully 演算法－－長幼有序

Bully演算法很像古代中國的皇位繼承製。皇位的繼承一直沿用嫡長繼承、順序嗣位的原則。皇位由長子繼承，如長子早死，則立其子，然後是第三子。Bully演算法與此類似。它為集群中每個節點設一個唯一編號，用編號的大小表示優先次序。在任何時刻，總是編號最大的節點當master。當master節點掛掉時，下一個節點馬上當選新的master。

這種方法的好處是實現起來很簡單，不過缺點也很明顯。最典型的問題是：當編號最大的節點不穩定時，集群就不穩定。因為master節點需要承擔額外當管理任務，所以，該節點的負載會比較大。當負載超過節點的承載能力時，節點就卡住了。這時，編號第二大的節點便當選為新的master。於是，負載便轉移到第二個節點。那麼，第一個節點的負載就會隨之變小。過了一會，它可能又恢復正常運行了。按照規則，第一個節點又會重新當選為master。然後，它又因為負載過大再次被卡住，如此反覆循環，導致集群無法正常運行。

2. Paxos －－少數服從多數

Paxos是希臘的一個小島，考古學家發現這個島上在古代就有關於議會制度的記錄。島上的居民通過民主提議和投票的方式選出一個最終決議。不過，城邦居民都不願意把全部時間和精力放在這件事情上，只願意不定期來參與提議和投票。但他們制度能夠按照少數服從多數的原則，使得提議者最終達成一致意見。電腦科學家Leslie Lamport借鑒了這個議會制度，設計了分散式系統選舉的演算法，並直接稱之為Paxos演算法。

Paxos演算法中有兩個角色，一個是提議者(Proposer), 另一個是接受者(Acceptor)。當然，一個節點可以同時擁有這兩個角色，真實情況通常也都是如此。

Paxos選舉過程總共有兩個階段。

階段一：

a) 提議者給一半以上的接受者發送一個預提案(prepare proposal)，預提案中帶一個唯一編號n。

b) 接受者接收到一個編號為n的預提案後，就拿它跟之前接收到的預提案比較。

b-1) 如果n大於其它提案編號，它就發送「接受」回饋，並承諾以後不再接受編號<n的提案(含預提案和正式提案)。同時，把它曾經接受過的編號最大的提案資訊也回饋回去。

b-2)如果n小於等於其它提案，它就發送「拒絕」回饋。同時，把它曾經接受過的編號最大的提案資訊也回饋回去。

階段二：

a) 如果提議者從大多數(集群一半以上)接受者那裡得到了「接受」回饋，那麼它就發送一個正式提案(proposal)給所有節點。正式提案中包含兩項內容：編號n和值v。其中，n是它之前預提案的編號，而v是它得到的所有回饋中，編號最大的提案的v值。（v表示建議誰當master，可以是參選節點的機器名等）

b) 如果接受者收到正式提案(編號n), 他就接受這個提議，除非它已經給編號>n的預提案發送了「接受」回饋。

下面是一個例子以幫助理解，例子中里有兩個提議者和3個接受者。

第一步，提議者1向3個接受者發送預提案#1.