2019獨角獸企業重金招聘Python工程師標準>>>

???一個高可用的集群里，一般都會存在主節點的選舉機制。這里以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.

? ? 第二步，接受者之前從沒有接受過其它預提案，所以提案編號1就是最大編號，因此三個都接受預提案#1.

? ? 第三步，提議者1向接受者1發送正式提案，編號=1,v＝A (它建議A節點做master節點)

? ? 第四步，接受者1之前沒有給任何編號>1的提案反饋過，所以接受提案1，并把v值設置為提案1的值，即v＝A。注意：此后，接受者1永遠不可能改變它的v值，也就是說它的v值永遠都是A。

? ? 第五步，提議者2給兩個接受者發送預提案。

? ? 第六步，接受者1發現這個預提案編號(2)大于之前的最大編號(1) , 于是接受該預提案。同時，把它接受過的編號最大的正式提案(#1)的v值也反饋回去。見規則 b-1。?提議者2改變自己提案中的v值，從B變為A。接受者2因為之前沒有收到過正式提案，所以只返回“接受”。

? ? 第七步，提議者1給接受者2和接受者3發送正式提案，編號=1,v＝A (它建議A節點做master節點)

? ? 第八步，接受者2發現提案#1的編號小于它接受過的最大編號(#2),就拒絕該提案。

????接受者3發現它接受過的最大編號是1，于是就接受該提案，并將提案值v=A記下來。

?

? ? 第九步，提議者2給接受者1和接受者2發送正式提案。編號＝2，v值＝A。注意，現在提議者2已經不是發送它最初的提案，而是發送新提案。它的新提案來自第六步，從接受者1那里得到的新提案（v=A）。

? ? 第十步，接受者接受1和接受者2都發現之前最大的編號是2，于是接受提案。至此，選舉結束。所有的接受者得到的提案都是v＝A，于是A當選為master。

?

????如果任何一個接受者的v值不是A而是其它值，那么集群就會出現問題。相當于集群出現了多個master。而Paxos是不會讓這樣的情況發生的。

????不過，Paxos算法理論上會出現“活鎖”的問題。具體什么是“活鎖”，有興趣的讀者可以自己去研究一下。

轉載于:https://my.oschina.net/stanleysun/blog/1605904

總結

以上是生活随笔為你收集整理的高可用集群中的选举机制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。