分佈式系統為了保證其可靠性，一般都會多節點提供服務，各別節點的故障不會影響系統的可用性。對於分佈式的存儲系統來說，在保證可用性的同時，數據的可靠性（不丟失）也是其要解決的核心問題。目前通用的方案是使用多副本存儲。這就會引入一個新的問題，分佈式存儲系統的又一核心問題——多個副本間的數據一致性保障。所以就有了各種數據一致性協議。例如：Zookeeper的Zab、Etcd使用的Raft和無比複雜的Paxos等等。這些一致性協議都有一個共同的特點，那就是都有一個主節點（Leader）負責數據的同步。
本文不討論這些一致性協議的工作原理，我們重點聊一聊它們的選主策略——當Leader掛掉後，集群必須有能力選出一個新的Leader。為什麼只討論選主呢？因為在我們的工作中幾乎不太可能去設計實現一致性協議，但"選主"這個事兒還是有可能需要我們去做的。例如之前文章介紹的時間輪，我們有多個節點提供服務，但只能有一個節點去轉動輪子（一秒移動一次當前指針），這個時候就需要系統中始終有一個Leader負責轉動輪子。業務上類似的需求還有很多，這裡就不舉例了，接下來我們介紹下幾種選主策略。
首先明確下選主的時機：一般發生在集群的Leader宕機或者集群剛剛啟動時，集群中沒有Leader，這時就會觸發選主。這裡有兩個技術點：
1、集群中節點需要能夠感知到Leader的存在；
2、從剩餘的活躍節點中選出一個新的Leader；
選主常用的方式有兩種：投票和競爭，下面我們分別介紹下。
1. 投票選主
在投票選主方式中，一般集群中會有兩種角色：Leader和Follower，Leader和各Follower間保持心跳，Follower通過心跳判斷Leader是否存活，如果Follower感知不到Leader，則觸發選舉。獲得集群半數以上節點投票的Follower將成為集群新的Leader。為了提高選舉的效率，集群節點數一般都為奇數個。
那麼Leader是如何選出來的呢？不同的一致性協議，有不同的玩法，下面簡單瞭解下Zookeeper和Etcd的選主方式（為了便於理解對模型做了簡化，只描述核心算法和思路）：
ZooKeeper
ZK的節點在投票時是通過比較兩個“ID”來決定把票投給誰的：
1、ZXID：ZooKeeper事務Id，越大表示數據越新；
2、SID：集群中每個節點的唯一編號；
投票時的比較算法為：誰的ZXID大誰勝出，ZXID相同情況誰的SID大誰勝出（簡單理解：誰的數據新勝出，數據一樣誰的編號大誰勝出）。
選舉算法如下：
1、集群失去Leader後，所有節點進入Looking狀態，向集群中廣播（第一輪投票）自身選舉值(SID,ZXID)，投自己一票；
2、每個節點都會將自身選舉值與收到的所有其它節點的選舉值作比較，選出“最大”的，如果最大的不是自己，則改投最"大“節點，廣播變更(第二輪投票)；
3、集群中節點收到第二輪結果後，統計超過半數的選舉值，其對應的節點將成為集群新的Leader；選舉過程入下圖所示：
圖1 ZooKeeper選主過程
Etcd
Etcd使用Raft一致性協議，集群中每個節點都有自己的倒計時器，且時間隨機。Follower每次收到心跳後都會重置倒計時器，當某個Follower的倒計時結束，說明長時間沒有收到心跳，就可以認為Leader掛了，需要選舉新的Leader了。這個Follower就會觸發選舉，想成集群為新的Leader。
Follower首先會將自身狀態改為Candidate，並向所有節點發起投票，如果得到半數以上節點的同意則成為集群新的Leader。否則，在下次倒計時結束後發起新一輪選舉。
Raft選舉過程中，投票節點通過對比任期（Term，一個連續遞增的整型值）和CommitId（類似ZK的事務Id）來判斷是否投“同意”票。選舉過程如下：
1、Candidate發起投票時將自身當前任期加1(NewTerm)，並向集群中所有節點發起投票請求（請求中包含新的任期值）；
2、Follower節點將自身當前任期(CurrentTerm)和收到的Candidate投票請求中帶來的NewTerm比較，如果NewTerm大就投“同意”票（這裡忽略的CommitId的比較是為了更好理解和強調Term的作用，比較方法與ZK類似）；
3、Candidate得到大於半數節點的”同意“後成為Leader，與其他節點建立心跳，並更新所有節點的當前任期為NewTerm;
4、如果不夠半數，則選舉失敗，等待倒計時器下次到期發起下一輪選舉;
選舉過程如圖2、圖3所示：
圖2 Leader心跳中斷，進入下一任期
集群正常情況下，各節點處於同一任期，Leader節點定時發送心跳重置各Follower倒計時器，當Leader心跳中斷後，Follower倒計時器不再被重置，則會必然會有節點到期，觸發選舉，圖2中Follower 1先到期，變為Candidate併發起選舉，進入下一任期。
圖3 完成選舉
選舉成功，原Follower成為集群新的主節點，開始向各Follower發送心跳，並更新其它節點的任期。
上面介紹的流程只是最簡單的場景，實際情況會複雜些，例如有可能會有產生多個Candidate，因為只要有Follower節點到期，就會發起投票，進入Candidate狀態，Reft是如何儘量避免產生多個Candidate的呢？
首先各節點倒計時時間隨機，儘量避免同時到期。其次Follower收到Candidate的投票請求時會重置自己的倒計時器，這樣就儘量保證了在選舉失敗後Candidate能夠率先到期，可以下一任期繼續由它發起投票。
但是肯定還存在產生多個Candidate的情況，所以協議規定一個Follower在一個任期只能投一次票，這樣就夠不可能有兩個Candidate同時獲得半數以上的投票（不可能選出兩個Leader來）。如果選舉失敗，由於節點倒計時器時間隨機，所以幾乎可以肯定會有一個Candidate先到期，並且大概率在下一輪選舉中成為Leader。
2. 競爭選主
上面介紹的投票選舉方式需要集群各節點互相感知對方的存在，實現相對複雜，下面介紹一種比較簡單的方案——競爭選主。
競爭選主需要藉助外部存儲服務來實現，各節點通過對某個約定的Key-Value數據的訪問，來決定誰是Leader，假設KV數據為Leader：UUID(寫入前生成的唯一Id)，具體”搶主“邏輯如下：
1、嘗試獲取Leader：UUID數據，判斷數據是否存在；
2、如果Leader不存在，則將Leader:UUID寫入到存儲服務中並設置其TTL（如果存儲服務不支持TTL，可以將TTL作為Value的一部分一起寫入），本地保存UUID值，當前進程為主節點；
3、如果Leader存在，通過TTL判斷是否過期，如果過期，當做Leader不存在處理，否則對比Leader的UUID和本地存儲的UUID是否一致；
3.1、如果一致則刷新”數據“TTL，當前進程為Leader；
3.2、如果不一致則不作任何操作，當前節點不是Leader；
集群內所有的進程，都保證以小於TTL的週期執行上述邏輯，Leader就會不停的“刷新”Leader:UUID的TTL，始終保持自己是Leader，如果想更安全，刷新時可以使用CAS的方式每次更新UUID。當Leader宕機不能繼續刷新後，數據必然會過期，其它節點將會競爭寫入，成為集群新的Leader（和分佈式鎖很像，可以理解為一把長期持有的鎖，新的玩法）。
圖4 競爭Leader
我們分析下上述邏輯，當約定的Key不存在時，集群處於沒有主或主掛了的狀態，其他節點可以通過判斷這個Key感知到Leader是否存在，從而觸發選主，寫入Key的過程相當於競爭選主的過程，誰寫入成功誰就是新的Leader。
3. 總結
本文介紹了兩種選主方式，競爭的方式很好理解，實現也非常簡單，但為什麼存儲系統很少選擇競爭選主方案？如果我們的業務模塊要實現選舉使用那種方案好一些？歡迎大家在留言區討論。
閱讀更多 Java從算法到架構 的文章
