分布式選舉\共識算法之Bully、Raft與Paxos

注：本文章作為基礎入門了解

Bully Algorithm（選舉算法）  

簡述：

Bully算法是一種協調者（主節點）競選算法，主要思想是叢集的每個成員都可以聲明它是主節點并通知其他節點。别的節點可以選擇接受這個聲稱或是拒絕并進入主節點競争。被其他所有節點接受的節點才能成為主節點。節點按照一些屬性來判斷誰應該勝出。這個屬性可以是一個靜态ID，也可以是更新的度量像最近一次事務ID（最新的節點會勝出）

三種消息類型：

 Election消息：表示發起一次選舉

 Answer（Alive）消息：對發起選舉消息的應答

 Coordinator（Victory）消息：選舉勝利者向參與者發送選舉成功消息

選舉流程：

-如果P是最大的ID，直接向所有人發送Victory消息，成為新的Leader；否則向所有比它大的ID的程序發送Election消息

-如果P在發送Election消息後沒有收到Alive消息，則P向所有人發送Victory消息，成為新的Leader

-如果P收到了從比自己ID還要大的程序發來的Alive消息，P停止發送任何消息，等待Victory消息（如果過了一段時間沒有等到Victory消息，重新開始選舉流程）

-如果P收到了比自己ID小的程序發來的Election消息，回複一個Alive消息，然後重新開始選舉流程

-如果P收到Victory消息，把發送者當做Leader

應用場景舉例：

mongodb，elasticsearch（類Bully）

那mongodb是怎進行選舉的呢？官方這麼描述:

We use a consensus protocol to pick a primary. Exact details will be spared here but that basic process is:

1. get maxLocalOpOrdinal from each server.
2. if a majority of servers are not up (from this server’s POV), remain in Secondary mode and stop.
3. if the last op time seems very old, stop and await human intervention.
4. else, using a consensus protocol, pick the server with the highest maxLocalOpOrdinal as the Primary.

大緻翻譯過來為使用一緻協定選擇主節點。基本步驟為：

1. 得到每個伺服器節點的最後操作時間戳。每個mongodb都有oplog機制會記錄本機的操作，友善和主伺服器進行對比資料是否同步還可以用于錯誤恢複。
2. 如果叢集中大部分伺服器down機了，保留活着的節點都為 secondary狀态并停止，不選舉了。
3. 如果叢集中選舉出來的主節點或者所有從節點最後一次同步時間看起來很舊了，停止選舉等待人來操作。
4. 如果上面都沒有問題就選擇最後操作時間戳最新（保證資料是最新的）的伺服器節點作為主節點。

觸發條件：

1. 初始化一個副本集時。
2. 副本集和主節點斷開連接配接，可能是網絡問題。
3. 主節點宕掉。

Raft 共識算法

 簡述：

與Paxos不同Raft強調的是易懂（Understandability），Raft和Paxos一樣隻要保證n/2+1節點正常就能夠提供服務；衆所周知但問題較為複雜時可以把問題分解為幾個小問題來處理，Raft也使用了分而治之的思想把算法流程分為三個子問題：選舉（Leader election）、日志複制（Log replication）、安全性（Safety）三個子問題。

角色類型：

在Raft算法中節點存在Follower、Candidate、Leader三種狀态。

選舉流程：

 Raft 使用心跳（heartbeat）觸發Leader選舉。當伺服器啟動時，初始化為Follower。Leader向所有Followers周期性發送heartbeat。如果Follower在選舉逾時時間内沒有收到Leader的heartbeat，就會等待一段随機的時間後發起一次Leader選舉。每一個follower都有一個時鐘，是一個随機的值，表示的是follower等待成為leader的時間，誰的時鐘先跑完，則發起leader選舉。

  Follower将其目前term加一然後轉換為Candidate。它首先給自己投票并且給叢集中的其他伺服器發送 RequestVote RPC。結果有以下三種情況：

• 赢得了多數的選票，成功選舉為Leader；
• 收到了Leader的消息，表示有其它伺服器已經搶先當選了Leader；
• 沒有伺服器赢得多數的選票，Leader選舉失敗，等待選舉時間逾時後發起下一次選舉。

動圖過程展示：http://thesecretlivesofdata.com/raft/

日志複制（資料共識\保證資料一緻性）

1、日志複制的過程

  Leader選出後，就開始接收用戶端的請求。Leader把請求作為日志條目（Log entries）加入到它的日志中，然後并行的向其他伺服器發起 AppendEntries RPC複制日志條目。當這條日志被複制到大多數伺服器上，Leader将這條日志應用到它的狀态機并向用戶端傳回執行結果。

• 用戶端的每一個請求都包含被複制狀态機執行的指令。
• leader把這個指令作為一條新的日志條目添加到日志中，然後并行發起 RPC 給其他的伺服器，讓他們複制這條資訊。
• 假如這條日志被安全的複制，上司人就應用這條日志到自己的狀态機中，并傳回給用戶端。
• 如果 follower 當機或者運作緩慢或者丢包，leader會不斷的重試，直到所有的 follower 最終都複制了所有的日志條目。

  簡而言之，leader選舉的過程是：1、增加term号；2、給自己投票；3、重置選舉逾時計時器；4、發送請求投票的RPC給其它節點。

應用場景舉例：

Etcd、Consul

Consul中的Raft

隻有以server模式運作的Consul節點，才會被認為是Raft節點集的一部分。所有的client節點會把收到的請求轉發到server節點中。這麼設計的原因主要是出于性能方面的考慮：節點集中的個數越多，那麼法定個數的值也就越大，這會導緻leader節點可能需要等待數百個follower節點對一條log entry的agree資訊。

在開始的時候，單個Consul server進入到bootstrap模式，這種模式允許它把自己選舉為leader。當leader被選舉出來之後，别的server就可以被加入到節點集中，進而保障了一緻性和安全性。最終，當最初的幾台server被加進來後，bootstrap模式可以被關閉。

consul server加入節點集之後，他們會知道哪台機器是目前的leader。當一個RPC請求到達一台非leader server上時，這個請求會被轉發到leader上。如果這個請求是一個查詢類型（隻讀），leader會基于現在的狀态機生成結果。如果這個請求是一個事物類型的請求（會修改狀态），leader會生成一個新的log entry，并用Raft的方法去處理它。當這個log entry被送出并且被應用到狀态機上時，這個事物就算完成了。

Raft會把log entry複制到多台機器上，是以網絡延遲對于性能的影響很大。因為這個原因，每個資料中心選出一個獨立的leader并且維護一份不相交的節點集。資料通過資料中心的方式做分割，是以每個leader隻對自己這個資料中心内的資料負責。當一個請求到達一個資料中心，這個請求會被轉發到正确的leader那裡。這種設計下，我們可以做到低延遲事物以及高可用，而不用犧牲一緻性。

補充：

螞蟻金服開源SOFAJRaft，生産級Java Raft算法庫，基于 Raft 一緻性算法的生産級高性能 Java 實作，支援 MULTI-RAFT-GROUP，适用于高負載低延遲的場景。

Paxos算法

Paxos不太容易了解，這裡隻是簡單叙述，後續會詳解。

簡述：

Paxos是能夠基于一大堆完全不可靠的網絡條件下卻能可靠确定地實作共識一緻性的算法。也就是說：它允許一組不一定可靠的處理器（伺服器）在某些條件得到滿足情況下就能達成确定的安全的共識，如果條件不能滿足也確定這組處理器（伺服器）保持一緻。

在Paxos算法中，有三種角色：

• Proposer
• Acceptor
• Learners

Paxos算法的過程（算法描述）

Paxos算法類似于兩階段提送出，其算法執行過程分為兩個階段。具體如下：

階段一（prepare階段）：

(a) Proposer選擇一個提案編号N，然後向半數以上的Acceptor發送編号為N的Prepare請求。Pareper（N）

(b) 如果一個Acceptor收到一個編号為N的Prepare請求，如果小于它已經響應過的請求，則拒絕，不回應或回複error。若N大于該Acceptor已經響應過的所有Prepare請求的編号（maxN），那麼它就會将它已經接受過（已經經過第二階段accept的提案）的編号最大的提案（如果有的話，如果還沒有的accept提案的話傳回{pok，null，null}）作為響應回報給Proposer，同時該Acceptor承諾不再接受任何編号小于N的提案。

階段二（accept階段）：

(a) 如果一個Proposer收到半數以上Acceptor對其發出的編号為N的Prepare請求的響應，那麼它就會發送一個針對[N,V]提案的Accept請求給半數以上的Acceptor。注意：V就是收到的響應中編号最大的提案的value（某個acceptor響應的它已經通過的{acceptN，acceptV}），如果響應中不包含任何提案，那麼V就由Proposer自己決定。

(b) 如果Acceptor收到一個針對編号為N的提案的Accept請求，隻要該Acceptor沒有對編号大于N的Prepare請求做出過響應，它就接受該提案。如果N小于Acceptor以及響應的prepare請求，則拒絕，不回應或回複error（當proposer沒有收到過半的回應，那麼他會重新進入第一階段，遞增提案号，重新提出prepare請求）。

應用場景舉例：

Zookeeper