分布式一致性算法：Raft學習

1 什么是分布式系統？

分布式系統是由一組通過網絡進行通信、為了完成共同的任務而協調工作的計算機節點組成的系統。這些節點可能位于不同的物理位置，但它們協同工作以提供一個統一的計算平臺或服務。分布式系統的出現是為了用廉價的、普通的機器完成單個計算機無法完成的計算、存儲任務。其目的是利用更多的機器，處理更多的數據。例如，分布式計算系統、分布式存儲系統（緩存、數據庫、文件）等。

分布式和集群的區別

分布式是指多個系統協同合作完成一個特定任務的系統。是不同的系統部署在不同的服務器上，服務器之間相互調用。主要工作是分解任務，把職能拆解，解決中心化管理。
集群是指在幾個服務器上部署相同的應用程序來分擔客戶端的請求。是同一個系統部署在不同的服務器上，比如一個登陸系統部署在不同的服務器上。使用場景是為了分擔請求的壓力。

在這里插入圖片描述

分布式系統面臨的挑戰：

網絡延遲和分區

節點間通過網絡通信，而網絡是不可靠的。可能的網絡問題包括：網絡分割、延時、丟包、亂序，網絡的不可靠性和延遲可能導致節點之間的通信問題理。
普遍的節點故障

雖然單個節點的故障概率較低，但節點數目達到一定規模，出故障的概率就變高了。分布式系統需要保證故障發生的時候，系統仍然是可用的，這就需要監控節點的狀態，在節點故障的情況下將該節點負責的計算、存儲任務轉移到其他節點。
異構的機器與網絡

分布式系統中的機器，配置不一樣，其上運行的服務也可能由不同的語言、架構實現，因此處理能力也不一樣；節點間通過網絡連接，而不同網絡運營商提供的網絡的帶寬、延時、丟包率又不一樣。怎么保證大家齊頭并進，共同完成目標，這是個不小的挑戰。

2 CAP理論

C consistency 一致性
在分布式系統中有多個節點，整個系統對外提供的服務應該是一致的。即用戶在不同的系統節點訪問數據的時候應該是同樣的結果，不能出現1號節點是結果1， 2號節點是結果2這種不一致的情況。
A availability 可用性

分布式系統為用戶提供服務，需要保證能夠在一些節點異常的情況下仍然支持為用戶提供服務。
P partition tolerance 分區容錯性（容災）
分布式系統的部署可能跨省，甚至跨國。不同省份或者國家之間的服務器節點是通過網絡進行連接，此時如果兩個地域之間的網絡連接斷開，整個分布式系統的體現就是分區容錯性了。在這種系統出現網絡分區的情況下系統的服務就需要在一致性和可用性之間進行取舍。要么保持一致性，返回錯誤。要么是保證可用性，使得兩個地域之間的分布式系統不一致。

在這里插入圖片描述

CAP理論一定是無法全部滿足三者，只能滿足其中的兩者（CA、CP、AP）。

對于一個分布式系統而言，P是分布式的前提，必須保證，因為只要有網絡交互就一定會有延遲和數據丟失，這種狀況我們必須接受，必須保證系統不能掛掉。所以只剩下C、A可以選擇。要么保證數據一致性（保證數據絕對正確），要么保證可用性（保證系統不出錯）。

當選擇了C（一致性）時，如果由于網絡分區而無法保證特定信息是最新的，則系統將返回錯誤或超時。

當選擇了A（可用性）時，系統將始終處理客戶端的查詢并嘗試返回最新的可用的信息版本，即使由于網絡分區而無法保證其是最新的。

3 分布一致性

在這里插入圖片描述

分布式一致性是指在分布式環境中對某個副本數據進行更新操作時，必須確保其他副本也會更新，避免不同副本數據不一致。

總結來講，分布式一致性就是為了解決以下兩個問題：

數據不能存在單個節點（主機）上，否則可能出現單點故障。
多個節點（主機）需要保證具有相同的數據。

分布一致性可以分為弱一致性和強一致性：

**弱一致性 **（例如：DNS域名系統）

弱一致性體現的是最終一致性，即如上CAP理論中，兩個地域的請求分別通過兩地的節點寫入，可以不用立即進行同步，而是經過一段時間之后兩地的用戶數據變為一致。這種一致性成為弱一致性，即最終一致性。也就是用戶一地寫入之后從另外一個節點讀取，無法立即讀到剛才寫入的數據。
**強一致性 **（又被稱為共識，例如：銀行系統）

強一致性描述的是一個請求在一個節點寫入之后在其他節點讀取，則該數據的更新能夠被立刻讀到。

4 強一致性（共識）算法

共識需要滿足的性質：

在非拜占庭條件下保證共識的一致性（C）。非拜占庭條件就是可信的網絡條件，與你通信的節點的信息都是真實的，不存在欺騙。
在多數節點存活時，保持可用性（A）。“多數”永遠指的是配置文件中所有節點的多數，而不是存活節點的多數。多數等同于超過半數的節點，多數這個概念概念很重要，貫穿Raft算法的多個步驟。
不依賴于絕對時間。理解這點要明白共識算法是要應對節點出現故障的情況，在這樣的環境中網絡報文也很可能會受到干擾從而延遲，如果完全依靠于絕對時間，會帶來問題，Raft用自定的Term（任期）作為邏輯時鐘來代替絕對時間。
在多數節點一致后就返回結果，而不會受到個別慢節點的影響。這點與第二點聯合理解，只要**“大多數節點同意該操作”就代表整個集群同意該操作**。對于raft來說，”操作“是儲存到日志log中，一個操作就是log中的一個entry。

**常見的強一致性算法：**主從同步、多數派、Paxos、Raft、ZAB

5 Raft算法

5.1 概述

在這里插入圖片描述

Raft算法又被稱為基于日志復制的一致性算法，旨在解決分布式系統中多個節點之間的數據一致性問題。它通過選舉一個**領導者（Leader）**，讓領導者負責管理和協調日志復制，確保所有節點的數據一致。

復制日志

在分布式系統中，每個節點都維護著一份日志，記錄系統操作的歷史。為了保證數據一致性，這些日志需要在所有節點之間保持同步。 Raft通過領導者選舉和日志復制機制，確保所有節點的日志最終是一致的。
心跳機制與選舉

Raft使用心跳機制來觸發選舉。當系統啟動時，每個節點（Server）的初始狀態都是追隨者（Follower）。每個Server都有一個定時器，超時時間為選舉超時（Election Timeout），一般為150-300毫秒。如果一個Server在超時時間內沒有收到來自領導者或候選者的任何消息，定時器會重啟，并開始一次選舉。
選舉過程（投票）

當一個追隨者節點發現自己超過選舉超時沒有收到領導者的消息，就會變為候選者（Candidate），并開始新一輪選舉。候選者節點會增加自己的任期號，并向其他節點發送選票請求。每個節點只能在一個任期內投一票，并且通常會將票投給第一個請求投票的候選者。如果一個候選人在收到足夠多的選票后，就成為新的領導者。
多個候選者（選舉失敗—>重來）

在選舉過程中，可能會出現多個候選者同時競爭領導者的位置。這時，如果某個候選者無法在選舉超時前獲得大多數節點的支持，選舉就會失敗。失敗后，所有候選者會重置自己的定時器，并在下一輪超時后再次發起選舉，直到選出新的領導者為止。

5.2 工作模式：Leader-Follower 模式

Leader 一個集群只有一個leader，不斷地向集群其它節點發號施令(心跳、日志同步)，其它節點接到領導者日志請求后成為其追隨者
Follower 一個服從leader決定的角色，追隨領導者，接收領導者日志，并實時同步
Cadidate 當follower發現集群沒有leader，會重新選舉leader，參與選舉的節點會變成candidate

5.3 重要概念

狀態機：raft的上層應用，例如k-v數據庫
日志log：raft保存的外部命令是以日志保存
term 任期：Term作為內部的邏輯時鐘，使用Term的對比來比較日志、身份、心跳的新舊而不是用絕對時間
提交日志 commit：raft保存日志后，經過復制同步，才能真正應用到上層狀態機，這個“應用”的過程為提交
節點身份 follower、Candidate、Leader ：raft集群中不同節點的身份
選舉：follower變成leader需要選舉
心跳、日志同步：leader向follower發送心跳（AppendEntryRPC）用于告訴follower自己的存在以及通過心跳來攜帶日志以同步
日志的term：在日志提交的時候，會記錄這個日志在什么“時候”（哪一個term）記錄的，用于后續日志的新舊比較
日志條目 entry：日志條目是日志的基本單元。每個日志條目記錄了一次狀態變化或一個命令。日志條目包含了如下幾個關鍵信息：
- 索引（Index）：該日志條目在日志中的位置。
- 任期（Term）：該日志條目被創建時的任期號。
- 命令（Command）：要應用于狀態機的具體命令或操作。

5.4 日志 log

日志中保存客戶端發送來的命令，上層的狀態機根據日志執行命令，那么日志一致，自然上層的狀態機就是一致的。

核心思想：Raft算法可以讓多個節點的上層狀態機保持一致的關鍵是讓==各個節點的日志保持一致== 。

5.5 任期 term

每個節點都有自己的term，Term用連續的數字進行表示。Term會在follower發起選舉（成為Candidate從而試圖成為Leader ）的時候加1，對于一次選舉可能存在兩種結果：
- 勝利當選：超過半數的節點認為當前Candidate有資格成為Leader，即超過半數的節點給當前Candidate投了選票。
- 失敗：如果沒有任何Candidate（一個Term的Leader只有一位，但是如果多個節點同時發起選舉，那么某個Term的Candidate可能有多位）獲得超半數的選票，那么選舉超時之后又會開始另一個Term（Term遞增）的選舉。
對于節點，當發現自己的Term小于其他節點的Term時，這意味著“自己已經過期”，不同身份的節點的處理方式有所不同：
- leader、Candidate：退回follower并更新term到較大的那個Term
- follower：更新Term信息到較大的那個Term
這里解釋一下為什么自己的Term小于其他節點的Term時leader、Candidate會退回follower 而不是延續身份，因為通過Term信息知道自己過期，意味著自己可能發生了網絡隔離等故障，那么在此期間整個Raft集群可能已經有了新的leader、 提交了新的日志 ，此時自己的日志是有缺失的，如果不退回follower，那么可能會導致整個集群的日志缺失，不符合安全性。
相反，如果發現自己的Term大于其他節點的Term，那么就會忽略這個消息中攜帶的其他信息（這個消息是過期的）。

5.6 工作機制

主要有以下四大模塊，組成Raft算法：

領導者選舉
日志同步、心跳
持久化
日志壓縮，快照

5.7 領導者選舉

節點需要通過集群元數據信息與其它節點進行溝通，而溝通的方式是**RPC請求**

節點之間通過網絡通信，其他節點（follower）如何知道leader出現故障？

leader會定時向集群中剩下的節點（follower）發送AppendEntry（作為心跳，hearbeat ）以通知自己仍然存活。如果follower在一段時間內沒有接收leader發送的AppendEntry，那么follower就會認為當前的leader 出現故障，從而發起選舉。
AppendEntry的作用？
1. 心跳
2. 攜帶日志entry及其輔助信息，以控制日志的同步和日志向狀態機提交
3. 通告leader的index和term等關鍵信息以便follower對比確認follower自己或者leader是否過期
follower知道leader出現故障后如何選舉出leader？

系統中的追隨者(follower)未收到日志同步(也可理解為心跳)轉變成為候選者(Candidate)，在成為候選者(Candidate)后，不滿足于自己現在狀態，迫切的想要成為領導者(leader)，雖然它給自己投了1票，但很顯然1票是不夠，它需要其它節點的選票才能成為領導者，所以通過RPC請求其它節點給自己投票。
符合什么條件的節點可以成為leader？（選舉限制）
目的：保證選舉出的 leader 一定包含了整個集群中目前已 committed 的所有日志

方法：當 candidate 發送 RequestVoteRPC 時，會帶上最后一個 entry 的信息。所有的節點收到該請求后，都會**比對自己的日志，如果發現自己的日志更新一些，則會拒絕投票給該 candidate**。

如何判斷日志的新舊：最新日志entry的term和對應的index。（index即日志entry在整個日志的索引）
- term大的日志更加新
- term相同的日志index大的更加新

5.8 日志同步、心跳

raft日志的兩個特點
- 兩個節點的日志中，有兩個 entry 擁有相同的 index 和 term，那么它們一定記錄了相同的內容/操作，即兩個日志匹配
- 兩個節點的日志中，有兩個 entry 擁有相同的 index 和 term，那么它們前面的日志entry也相同
  
  如何保證這兩點：
  
  保證第一點：僅有 leader 可以生成 entry
  
  保證第二點：leader 在通過 AppendEntriesRPC 和 follower 通訊時，除了帶上自己的term等信息外，還會帶上entry的index和對應的term等信息，follower在接收到后通過對比就可以知道自己與leader的日志是否匹配，不匹配則拒絕請求。leader發現follower拒絕后就知道entry不匹配，那么下一次就會嘗試匹配前一個entry，直到遇到一個entry匹配，并將不匹配的entry給刪除（覆蓋）。
  
  注意：raft為了避免出現一致性問題，要求 leader 絕不會提交過去的 term 的 entry （即使該 entry 已經被復制到了多數節點上）。leader 永遠只提交當前 term 的 entry，過去的 entry 只會隨著當前的 entry 被一并提交。
raft日志同步方式

先找到日志不匹配的那個點，然后只同步那個點之后的日志。

一個follower，如果leader認為其日志已經和自己匹配了，那么在AppendEntryRPC中不用攜帶日志（其他信息依然要攜帶），反之如果follower的日志只有部分匹配，那么就需要在AppendEntryRPC中攜帶對應的日志。心跳RPC可以看成是沒有攜帶日志的特殊的日志同步RPC。

日志同步（復制）的過程：

在這里插入圖片描述

-------------------------------------------------------------------------------------------Raft算法的核心步驟👇------------------------------------------------------------------------------------------------

接收到客戶端請求之后，領導者會根據用戶指令和自身任期以及日志索引等信息生成一條新的日志項，并附加到本地日志中。
領導者通過日志復制 RPC，將日志復制到其他跟隨者節點。
跟隨者將日志附加到本地日志成功之后，便返回 success，此時新的日志項還沒有被跟隨者提交。
當領導者接收到**大多數（超過集群數量的一半）**跟隨者節點的 success 響應之后，便將此日志提交(commit)到它的狀態機中。
領導者將執行的結果返回給客戶端。
當跟隨者收到下一次領導者的心跳請求或者新的日志復制請求之后，如果發現領導者已經應用了之前的日志，但是它自己還沒有之后，那么它便會把這條日志項應用到本地狀態機中。（類似于二階段提交的方式）

-------------------------------------------------------------------------------------------Raft算法的核心步驟👆------------------------------------------------------------------------------------------------

安全性保障

Election Safety：每個 term 最多只會有一個 leader

Leader Append-Only：Leader絕不會覆蓋或刪除自己的日志，只會追加

Log Matching：如果兩個日志的 index 和 term 相同，那么這兩個日志相同 —— raft日志的特點1

? 如果兩個日志相同，那么他們之前的日志均相同 —— raft日志的特點2

Leader Completeness：一旦一個操作被提交了，那么在之后的 term 中，該操作都會存在于日志中

State Machine Safety：狀態機一致性，一旦一個節點應用了某個 index 的 entry 到狀態機，那么其他所有節點應用的該 index 的操作都是一致的（各個節點之間一致，使得上層狀態機都一致）
為什么不直接讓follower拷貝leader的日志|leader發送全部的日志給follower？

會攜帶大量的無效的日志（因為這些日志follower本身就有）
leader如何知道follower的日志是否與自己完全匹配？

在AppendEntryRPC中攜帶上entry的index和對應的term（日志的term），可以**通過比較最后一個日志的index和term**來得出某個follower日志是否匹配。
如果發現不匹配，那么如何知道哪部分日志是匹配的，哪部分日志是不匹配的呢？

leader每次發送AppendEntryRPC后，follower都會根據其entry的index和對應的term來判斷某一個日志是否匹配。在leader剛當選，會從最后一個日志開始判斷是否匹配，如果匹配，那么后續發送AppendEntryRPC就不需要攜帶日志entry了。

如果不匹配，那么下一次就發送 倒數第2個 日志entry的index和其對應的term來判斷匹配，

如果還不匹配，那么依舊重復這個過程，即發送倒數第3個日志entry的相關信息

重復這個過程，直到遇到一個匹配的日志。
優化：尋找匹配加速（可選）

在尋找匹配日志的過程中，在最后一個日志不匹配的話就嘗試倒數第二個，然后不匹配繼續倒數第三個。。。

leader和follower 日志存在大量不匹配的時候這樣會太慢，可以用一些方式一次性的多倒退幾個日志，就算回退稍微多了幾個也不會太影響，具體實現參考 7.3 快速恢復（Fast Backup） - MIT6.824 (gitbook.io)

5.9 持久化

Raft的一大優勢就是Fault Tolerance（容災），即能夠在部分節點宕機、失聯或者出現網絡分區的情況下依舊讓系統正常運行。為了保證這一點，除了領導選舉與日志復制外，還需要定期將一些數據持久化到磁盤中，以實現在服務器重啟時利用持久化存儲的數據恢復節點上一個工作時刻的狀態。持久化的內容僅僅是Raft層, 其應用層不做要求。

在這里插入圖片描述

論文中提到需要持久化的數據包括:

voteFor：

voteFor記錄了一個節點在某個term內的投票記錄, 因此如果不將這個數據持久化, 可能會導致如下情況:
- 在一個Term內某個節點向某個Candidate投票, 隨后故障
- 故障重啟后, 又收到了另一個RequestVote RPC, 由于其沒有將votedFor持久化, 因此其不知道自己已經投過票, 結果是再次投票, 這將導致同一個Term可能出現2個Leader。
currentTerm:
currentTerm的作用也是實現一個任期內最多只有一個Leader, 因為如果一個節點重啟后不知道現在的Term時多少, 其無法再進行投票時將currentTerm遞增到正確的值, 也可能導致有多個Leader在同一個Term中出現
Log:
這個很好理解, 需要用Log來恢復自身的狀態