一、Raft演算法概述

當我們只有一個服務節點的情況下，是不存在節點共識的問題的，當存在多個不同服務節點時，才會引入分散式一致性的問題。

Raft是一種實現分散式共識的協議。所謂共識，就是多個節點對某個事情達成一致的看法，即使是在部分節點故障、網路延時、網路分割的情況下。

主要應用場景：

Redis Sentinel的選舉LeaderEtcd 主要是共享配置和服務發現，實現一致性使用了Raft演算法加密貨幣（比特幣、區塊鏈）的共識演算法

主要解決什麼問題？

分散式儲存系統通常透過維護多個副本來提高系統的可用性，帶來的代價就是分散式儲存系統的核心問題之一：維護多個副本的資料一致性。

二、Raft演算法實現流程

為了提高理解性，Raft將一致性演算法分為了幾個部分，包括領導選取（leader selection）、日誌複製（log replication）、安全（safety），並且使用了更強的一致性來減少了必須需要考慮的狀態。

本文透過一個小故事做示例，來便於大家快速理解。

2.1 Leader選舉

部門需要成立一個新的服務小組，現在有三名同學A，B，C。

為了便於後期統一調配資源及管理需要，現需要從三名同學中選舉出一名小組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（領導者）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節點怎麼辦？

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 匹配完整性

同一團隊內兩名同學假如目前手頭負責的事務是一致的，那之前他們的工作記錄應該也是一致的。即：相同的初始狀態+相同的操作=相同的結束狀態

Leader將客戶端請求封裝到一個個的log entry，將這些log entries複製到其他Follower節點，大家按順序應用這些請求，那最終狀態肯定是一致的。

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 -

Thanks for reading!