聊聊分布式算法 Raft
二哥的編程知識星球 （點擊了解詳情）正式上線了，來和 180 多名 小伙伴一起打怪升級吧！這是一個 Java 學習指南 + 編程實戰(zhàn)的私密圈子，你可以向二哥提問、幫你制定學習計劃、跟著二哥一起做實戰(zhàn)項目，沖沖沖。
大名鼎鼎的 Paxos 算法可能不少人都聽說過，幾乎壟斷了一致性算法領域，在 Raft 協議誕生之前，Paxos 幾乎成了一致性協議的代名詞。但是對于大多數人來說，Paxos 算法太難以理解了，而且難以實現。因此斯坦福大學的兩位教授 Diego Ongaro 和 John Ousterhout 決定設計一種更容易理解的一致性算法，最終提出了 Raft 算法！
Raft 是一種更為簡單方便易于理解的分布式算法，主要解決了分布式中的一致性問題。相比傳統(tǒng)的 Paxos 算法，Raft 將大量的計算問題分解成為了一些簡單的相對獨立的子問題，并有著和 Multi-Paxos 同樣的性能，下面我們通過動圖，以后還原 Raft 內部原理。
Raft 基礎
名詞解釋
Raft協議一共包含如下3類角色：
Leader（領袖）：領袖由群眾投票選舉得出，每次選舉，只能選出一名領袖； Candidate（候選人）：當沒有領袖時，某些群眾可以成為候選人，然后去競爭領袖的位置； Follower（群眾）：這個很好理解，就不解釋了。
然后在進行選舉過程中，還有幾個重要的概念：
Leader Election（領導人選舉）：簡稱選舉，就是從候選人中選出領袖； Term（任期）：它其實是個單獨遞增的連續(xù)數字，每一次任期就會重新發(fā)起一次領導人選舉； Election Timeout（選舉超時）：就是一個超時時間，當群眾超時未收到領袖的心跳時，會重新進行選舉。
角色轉換
這幅圖是領袖、候選人和群眾的角色切換圖，我先簡單總結一下：
群眾 -> 候選人：當開始選舉，或者“選舉超時”時 候選人 -> 候選人：當“選舉超時”，或者開始新的“任期” 候選人 -> 領袖：獲取大多數投票時 候選人 -> 群眾：其它節(jié)點成為領袖，或者開始新的“任期” 領袖 -> 群眾：發(fā)現自己的任期ID比其它節(jié)點分任期ID小時，會自動放棄領袖位置 備注：后面會針對每一種情況，詳細進行講解。
選舉
情況 1：領導人選舉
為了便于后續(xù)的講解，我畫了一副簡圖，“選舉定時器”其實就是每個節(jié)點的“超時時間”。
成為候選人：每個節(jié)點都有自己的“超時時間”，因為是隨機的，區(qū)間值為150~300ms，所以出現相同隨機時間的概率比較小，因為節(jié)點B最先超時，這時它就成為候選人。
選舉領導人：候選人B開始發(fā)起投票，群眾A和C返回投票，當候選人B獲取大部分選票后，選舉成功，候選人B成為領袖。
心跳探測：為了時刻宣誓自己的領導人地位，領袖B需要時刻向群眾發(fā)起心跳，當群眾A和C收到領袖B的心跳后，群眾A和C的“超時時間”會重置為0，然后重新計數，依次反復。
這里需要說明一下，領袖廣播心跳的周期必須要短于“選舉定時器”的超時時間，否則群眾會頻繁成為候選者，也就會出現頻繁發(fā)生選舉，切換Leader的情況。
情況 2：領袖掛掉情況
當領袖B掛掉，群眾A和C會的“選舉定時器”會一直運行，當群眾A先超時時，會成為候選人，然后后續(xù)流程和“領導人選舉”流程一樣，即通知投票 -> 接收投票 -> 成為領袖 -> 心跳探測。
情況 3：出現多個候選者情況
當出現多個候選者A和D時，兩個候選者會同時發(fā)起投票，如果票數不同，最先得到大部分投票的節(jié)點會成為領袖；如果獲取的票數相同，會重新發(fā)起新一輪的投票。
當C成為新的候選者，此時的任期Term為5，發(fā)起新一輪的投票，其它節(jié)點發(fā)起投票后，會更新自己的任期值，最后選擇新的領袖為C節(jié)點。
日志復制
復制狀態(tài)機
復制狀態(tài)機的基本思想是一個分布式的狀態(tài)機，系統(tǒng)由多個復制單元組成，每個復制單元均是一個狀態(tài)機，它的狀態(tài)保存在操作日志中。如下圖所示，服務器上的一致性模塊負責接收外部命令，然后追加到自己的操作日志中，它與其他服務器上的一致性模塊進行通信，以保證每一個服務器上的操作日志最終都以相同的順序包含相同的指令。一旦指令被正確復制，那么每一個服務器的狀態(tài)機都將按照操作日志的順序來處理它們，然后將輸出結果返回給客戶端。
數據同步流程
數據同步流程，借鑒了“復制狀態(tài)機”的思想，都是先“提交”，再“應用”。當Client發(fā)起數據更新請求，請求會先到領袖節(jié)點C，節(jié)點C會更新日志數據，然后通知群眾節(jié)點也更新日志，當群眾節(jié)點更新日志成功后，會返回成功通知給領袖C，至此完成了“提交”操作；當領袖C收到通知后，會更新本地數據，并通知群眾也更新本地數據，同時會返回成功通知給Client，至此完成了“應用”操作，如果后續(xù)Client又有新的數據更新操作，會重復上述流程。
日志復制原理
每一個日志條目一般包括三個屬性：整數索引Log Index、任期號Term和指令Commond。每個條目所包含的“整數索引”即該條目在日志文件中的槽位，“任期號”對應到圖中就是每個方塊中的數字，用于檢測在不同服務器上日志的不一致問題，指令即用于被狀態(tài)機執(zhí)行的外部命令，圖中就是帶箭頭的數字。
領導人決定什么時候將日志條目應用到狀態(tài)機是安全的，即可被提交的呢？一旦領導人創(chuàng)建的條目已經被復制到半數以上的節(jié)點上了，那么這個條目就稱為可被提交的。例如，圖中的9號條目在其中4節(jié)點（一共7個節(jié)點）上具有復制，所以9號條目是可被提交的；但條目10只在其中3個節(jié)點上有復制，因此10號條目不是可被提交的。
一般情況下，Leader和Follower的日志都是保存一致的，如果Leader節(jié)點在故障之前沒有向其它節(jié)點完全復制日志文件之前的所有條目，會導致日志不一致問題。在Raft算法中，Leader會強制Follower和自己的日志保存一致，因此Follower上與Leader的沖突日志會被領導者的日志強制覆寫。為了實現上述邏輯，就需要知道Follower上與Leader日志不一致的位置，那么Leader是如何精準找到每個Follower日志不一致的那個槽位呢？
Leader為每一個Follower維護了一個nextlndex，它表示領導人將要發(fā)送給該追隨者的下一條日志條目的索引，當一個Leader贏得選舉時，它會假設每個Follower上的日志都與自己的保持－致，于是先將 nextlndex初始化為它最新的日志條目索引數+1，在上圖中，由于Leader最新的日志條目index是10 ，所以nextlndex的初始值是11。當Leader向Follower發(fā)送AppendEntries RPC時，它攜帶了（item_id，nextIndex - 1）二元組信息，item_id即為nextIndex - 1這個槽位的日志條目的term。Follower接收到AppendEntries RPC消息后，會進行一致性檢查，即搜索自己的日志文件中是否存在這樣的日志條目，如果不存在，就像Leader返回AppendEntries RPC失敗，然后領導人會將nextIndex遞減，然后進行重試，直到成功為止。之后的邏輯就比較簡單，Follower將nextIndex之前的日志全部保留，之后的全部刪除，然后將Leader的nextIndex之后的日志全部同步過來。
上面只是講述了方法，下面舉個例子，加深一下理解，還是以上面的圖為例。Leader的nextlndex為11，向b發(fā)送AppendEntries RPC(6,10)，發(fā)現b沒有，繼續(xù)發(fā)送(6,9)(6,8) (5,7) (5,6) (4,5)，最后發(fā)送(4,4)才找到，所以對于b，nextlndex=4之后的日志全部刪除，然后將Leader的nextlndex=4的日志全部追加過來。
腦裂情況
當網絡問題導致腦裂，出現雙Leader情況時，每個網絡可以理解為一個獨立的網絡，因為原先的Leader獨自在一個區(qū)，所以向他提交的數據不可能被復制到大多數節(jié)點上，所以數據永遠都不會提交，這個可以在第4幅圖中提現出來（SET 3沒有提交）。
當網絡恢復之后，舊的Leader發(fā)現集群中的新Leader的Term比自己大，則自動降級為Follower，并從新Leader處同步數據達成集群數據一致，同步數據的方式可以詳見“日志原理”。
沒有什么使我停留——除了目的，縱然岸旁有玫瑰、有綠蔭、有寧靜的港灣，我是不系之舟。
推薦閱讀：
