一、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!