一、Raft 算法概述
當我們隻有一個服務節點的情況下，是不存在節點共識的問題的，當存在多個不同服務節點時，才會引入分布式一緻性的問題。
Raft 是一種實作分布式共識的協定。所謂共識，就是多個節點對某個事情達成一緻的看法，即使是在部分節點故障、網絡延時、網絡分割的情況下。
主要應用場景：
- Redis Sentinel 的選舉 Leader
- Etcd 主要是共享配置和服務發現，實作一緻性使用了 Raft 算法
- 加密貨币（比特币、區塊鍊）的共識算法
主要解決什麼問題？
分布式存儲系統通常通過維護多個副本來提高系統的可用性，帶來的代價就是分布式存儲系統的核心問題之一：維護多個副本的資料一緻性。
二、Raft 算法實作流程
為了提高了解性，Raft 将一緻性算法分為了幾個部分，包括上司選取（leader selection）、日志複制（log replication）、安全（safety），并且使用了更強的一緻性來減少了必須需要考慮的狀态。
本文通過一個小故事做示例，來便于大家快速了解。
2.1 Leader 選舉
為了便于後期統一調配資源及管理需要，現需要從三名同學中選舉出一名小組 Leader。
A 覺得自己有能力做好 Leader 職務，就向 B、C 說“來投票給我，我想當 Leader”，這時候 A 成了候選人，并為自己事先投了一票。
1）假如 B、C 之前都沒有想過要自己當 Leader，那就說“好吧，投給你” → A 獲得 3 張選票，當選 Leader
2）假如 B 之前想過自己當 Leader，B 投了自己一票 而 C 投了一票給 A → A 獲得 2 張選票（3 人中已超過半數），當選 Leader
3）假如 B、C 都已經把票投給了自己 → A、B、C 各獲得自己的一票，選舉失敗重新發起
4）假如 B 之前想過自己當 Leader，而且 C 已經把票投給了 B → B 獲得 2 張選票（3 人中已超過半數），當選 Leader
Leader 選舉示意
從以上選舉流程可以發現，一個節點任一時刻肯定處于以下三狀态之一：
- Leader（上司者）
- Follower（跟随者）
- Candidate（候選人）
這三個狀态的轉移過程如下圖所示：
選舉過程
第一步：Follower 成為 Candidate
如果 Follower 聽不到 Leader 的意見，他們就可以成為 Candidate
第二步：候選人争取票
投自己一票，并發送投票請求到其他節點，節點收到請求後進行回應
第三步：等待其他節點回複
如果候選人得到了超半數的節點的投票（包含自己的一票），它就成為 Leader
如果候選人被告知 Leader 已産生，則自行切換為 Follower
一段時間内沒有收到超半數投票，保持候選人狀态，重新發起選舉
第四步：候選人 赢得選舉
新 Leader 會立刻給所有節點發消息，避免其他節點觸發新的選舉。
2.2 日志同步
在經過上述 2.1 的 Leader 選舉之後，已經標明了小組 Leader，這裡我們假定 A 已當選 Leader。可以承擔一些對接方同學（稱為 Client 端）提出的操作任務了。
規定每次需求對接，必須要經過小組 Leader 才可以。那員工提出操作請求，Leader 接收到後記錄下來，同時向組内其他同學進行同步，直到其他同學都确認了此需求後 Leader 才會确認操作并同步執行結果到員工（Follower 節點）。
請求處理日志同步
Log Replication（日志複制）
經過 Leader 選舉流程，産生了新的 Leader 節點，系統的所有變更都要通過 Leader 節點來實作。
第一步：Leader 追加日志項（append log entry）
系統的每個更改都作為一個 entry 添加到節點的日志中
第二步：Leader 并行發出 Append Entries RPC，并等待響應
Leader 會一直等到超半數節點都寫入 entry，Leader 節點送出，然後 Leader 通知 Follower entry 已送出。
第三步：Leader 得到大多數回應，向狀态機應用 entry
狀态機：可了解為一個确定的應用程式，所謂确定是指隻要是相同的輸入，那麼任何狀态機都會計算出相同地輸出。
第四步：Leader 回複 Client，同時通知 Follower 應用 log
目前叢集已就系統狀态達成了共識
log-based replicated state machine 示意圖：
關于應用過程中的幾個問題
Q1：假如 Client 請求通路到了 Follower 節點怎麼辦？
解答：Follower 節點會轉發請求到 Leader 節點。
Q2：當 Leader 與 Follower 的日志不一緻，需要如何處理？
解答：
1）Leader 通過強制 Followers 複制它的日志來處理日志的不一緻，Followers 上的不一緻的日志會被 Leader 的日志覆寫。
2）Leader 為了使 Followers 的日志同自己的一緻，Leader 需要找到 Followers 同它的日志一緻的地方，然後覆寫 Followers 在該位置之後的條目。
3）Leader 會從後往前試，每次 AppendEntries 失敗後嘗試前一個日志條目，直到成功找到每個 Follower 的日志一緻位點，然後向後逐條覆寫 Followers 在該位置之後的條目。
2.3 安全性保障
為了保證團隊運作的穩定，有幾個預設的要求：
2.3.1 選舉安全
即任一任期内最多一個 leader 被選出。假如系統中同時有多于一個 leader，被稱之為腦裂（brain split），這會導緻資料的覆寫丢失。
一個團隊某個時期内僅允許存在一個 Leader（選舉失敗情況特殊情況除外），否則多個 Leader 同時處理需求發号施令，容易造成團隊内步調不一緻情況。
在 raft 中，兩點保證了這個屬性：
1）一個節點某一任期内最多隻能投一票；
2）隻有獲得 majority 投票的節點才會成為 leader。
2.3.2 Log 比對完整性
同一團隊内兩名同學假如目前手頭負責的事務是一緻的，那之前他們的工作記錄應該也是一緻的。即：相同的初始狀态+相同的操作=相同的結束狀态
Raft 日志同步結論：
1）如果不同日志中的兩個條目有着相同的索引和任期号（term），則它們所存儲的指令是相同的。
2）如果不同日志中的兩個條目有着相同的索引和任期号（term），則它們之前的所有條目都是完全一樣的。
2.3.3 leader 資料完整性
團隊内後繼的 leader，肯定應該知曉這個團隊之前的工作内容，因為所有 Leader 任期内的工作記錄是會做交接的。
如果一個 log entry 在某個任期被送出，那麼這條 log 一定會出現在所有更高 term 的 leader 的日志裡面。
Raft 日志覆寫規則：
1）一個日志被複制到 majority 節點才算 committed
2）一個節點得到 majority 的投票才能成為 leader，而節點 A 給節點 B 投票的其中一個前提是，B 的日志不能比 A 的日志舊。
三、總結
所有的算法實作原理，其實都是真實社會工作模式的影射，聯系生活中的實際案例來了解複雜的一緻性算法，可以讓我們達到事半功倍的效果。
本文是讓大家對 raft 協定有一個簡單了解入門，如有興趣去更深入了解，推薦給大家兩個不錯的連結：
1）Raft 可視化測試以及各語言版本實作的 Raft：
https://raft.github.io/2）Raft 算法-動畫示範（很好的入門教程）：
http://thesecretlivesofdata.com/raft/- END -
作者：架構精進之路，十年研發風雨路，大廠架構師，CSDN 部落格專家，專注架構技術沉澱學習及分享，職業與認知更新，堅持分享接地氣兒的幹貨文章，期待與你一起成長。
關注并私信我回複“01”，送你一份程式員成長進階大禮包，歡迎勾搭。
Thanks for reading!