golang-raft 算法理論與實踐
前言
- 我計劃寫 raft 的一系列文章,包含從理論到代碼實踐,此文章依託於 MIT 的研究生課程。
背景
-
raft 是一種分佈式的共識算法,其目的是要實現多個節點集羣的容錯性, 一致性從而能夠構建大規模的軟件系統。
-
在 raft 之前,比較有名的是 Paxos。但是 paxos 難於理解。
-
raft 的誕生是爲了讓共識算法更容易理解, 在工程上更容易實現。
-
leader:raft 中會有一個領導者具有超級權限,可以把自己的 log 複製到其他節點中。
-
leader election:raft 每隔一段隨機的時間就會進行 leader 的選舉
-
raft 允許集羣配置變化時正常運行。
Replicated state machine
-
狀態機是分佈式系統中的一個重要概念,任何一個系統的最終狀態都可以看成是每一個操作的集合。因此,算法會維護一份 replicated log,將每一份操作都存儲起來。
-
每一個節點只要按順序執行 log 中的命令,就會到達相同的最終狀態。這樣,即便是系統奔潰也可以快速的恢復。
-
共識算法需要保證 relicated log 的一致性, 服務器收到客戶端發出來的執行命令 Command 後,會將其加入到 log 中。
-
服務器之間會相互的交流,保證最後的 log 的一致性(即便服務器奔潰),即 Command 會複製到其他服務器的 log 中,所有服務器的 log 是相同的,有序的。
-
其他服務器會執行此 log,即會執行此命令。最後,所有的服務器都會到達同一個狀態。
分佈式共識算法必須滿足下面的屬性:
-
在極端情況下(丟包、奔潰)仍然能夠保證安全性
-
大多數節點正常的情況下能夠保證可用
-
不能依靠時間戳去保證 log 的一致性, 因爲時間戳是不準確的, 特別是時間的微小變化受到很多擾動
-
當大部分的節點通過 RPC 遠程調用交流 達成共識後,command 就可以被確認和執行。小部分節點的不穩定不會影響整個系統
raft basic
-
raft 集羣一般保持奇數個數量(5 個節點比較普遍). 從而只要大部分節點存活,即可用。
-
raft 中的節點有 3 種狀態。leader, Candidates, follower。
-
一般的狀態只會存在一個 leader,其餘的節點都是 follower。
-
leader 會處理所有的客戶端請求, 如果是客戶端請求 follower,也會被轉發到 leader 處理。
-
Candidates 是一種選舉時候的過渡狀態,用於自身拉票選舉 leader。
-
在 raft 中會有一個叫做 term 的時間週期。term 是以選舉 leader 開始的,如果 Candidates 選舉成爲了 leader,那麼其會成爲這個 term 剩下時間的 leader。
-
有時候,在整個 term 週期都沒有選舉出 leader。這時一個新的選舉會在不久後開始。
-
Terms 在 raft 中類似於一種時間戳,後一個一定比前一個後發生,這一點和比特幣中的區塊鏈很類似。
-
每一個服務器會存儲一個當前的 term,其會隨着時間的增加而增長。如果某一個節點的當前 term 小於其他節點,那麼節點會更新自己的 term 爲最大的 term。
-
如果一個 candidate 發現自己當前的 term 過時了,那麼其會立即變爲 follower。
-
raft 節點之間通過 RPC(遠程過程調用)來進行通信。RequestVote 方法用於 candidate 在選舉時候使用,AppendEntries 用於 leader 在通知其他節點複製 log 時使用。同時也用於心跳檢測。
-
RPC 是併發的,並支持失敗重試。
選舉
-
在 raft 中會有一套心跳檢測,只要 follower 收到來自 leader 或者 Candidates 的數據,那麼其會保持 follower 的狀態。
-
如果 follower 一段時間內沒有收到 RPC 請求,這意味着選舉超時( election timeout )。
-
這時 follower 會將 current term 加 1,過渡到 Candidates 狀態。其會給自己投票,併發送 RequestVote RPC 請求給其他的節點,拉票!
-
Candidates 狀態會持續,直到下面的 3 種情況發生:
-
當其獲得了大部分節點的支持後,其贏得了選舉,變爲了 leader。一旦其變爲了 leader,其會向其他節點發送 AppendEntries RPC, 確認其 leader 的地位,阻止選舉。
-
其他節點成爲了 leader。如果其收到了其他節點的 AppendEntries RPC. 並發現其他節點的 current term 比自己的大, 則其變爲 follower 狀態。
-
一段時間過去任然沒有參與者。
-
如果有許多的節點同時變爲了 candidate, 則可能會出現一段時間內都沒有節點能夠選舉成功的情況。
-
在 raft 中,爲了快速解決並修復這個問題,規定了每一個 candidate 在選舉前會重置一個隨機的選舉超時( election timeout )時間,此隨機時間會在一個區間內(eg.150-300ms)
-
隨機時間保證了在大部分的情況下,有一個唯一的節點首先選舉超時,其在大部分節點選舉超時前發送心跳檢測,贏得了選舉。
-
當一個 leader 在心跳檢測中發現另一個節點有更高的 term 時,會轉變爲 follower。否則其將一直保持 leader 狀態。
日誌複製 (Log replication)
-
當成爲 leader 後,其會接受來自客戶端的請求。每一個客戶端請求都包含一個將要被節點的狀態機執行的 command。
-
leader 其會將這個 command 包裝爲一個 entry 放入到 log 中,並通過 AppendEntries RPC 發送給其他節點,要求其添加此 entry 到 log 中。
-
當 entry 被 大部分的節點接受並複製後,這個 entry 的狀態變爲了 committed. raft 算法保證了 commited entry 到最後一定能夠會被所有節點的狀態機執行。
-
一旦 follower 知道(AppendEntries RPC)某一個 entry 被 commit 之後,follower 會按順序執行 log 中的 entry
-
如圖所示,我們可以把 log 理解爲 entry 的集合。在 entry 中包含了 common 命令、entry 所在的 term 以及每一個 entry 的順序編號 index。
-
raft 的一致性保證了下面的屬性:
-
如果在不同節點中 log 中的 entry 有相同的 index 和 term, 那麼一定存儲的是相同的 command。
-
如果在不同節點中 log 中的 entry 有相同的 index 和 term, 那麼此 entry 之前的所有 entry 都是相同的。
-
節點 f 可能會發生,如果其是 term 2 的 leader, 添加 entry 到 log 中,但是沒有 commit 時就奔潰了,其快速恢復後又變爲了 term 3 的 leader, 添加 entry 到 log 中,沒有 commit 又繼續奔潰了。
-
在正常的情況下,上面的兩個屬性都能滿足,但是異常情況下,這種情況會被打破,可能會出現如上圖所示的情形,
-
在 raft 中,爲了處理這樣的不一致性,強制要求 follower 的 log 與 leader 的 log 要一致。
-
因此 leader 必須要發現一個 entry,在這個 entry 之後的都是不相同的 entry。在這個 entry 之前的都是一致的 entry。在 leader 中會爲每一個 follower 維護一份 nextIndex 數組。標誌了將要發送給 follower 的下一個 index。最後,follower 會刪除掉所有不同的 entry,並用和 leader 一致的 log。這一過程,都會通過 AppendEntries RPC 執行完畢。當 AppendEntries RPC 返回 success,就表明 follower 與 leader 的 log 是一致的。
安全性
-
上圖要說明的是,一個已經被 commit 的 entry 在目前的情況下是有可能被覆蓋掉的。
-
例如在 a 階段 s1 成爲了 leader,其 entry 還沒有 commit。在 b 階段, s1 奔潰,s5 成爲了 leader ,添加 log 但是任然沒有 commit。在 c 階段,s5 奔潰,s1 成爲了 leader。其 entry 成爲了 commit。在 d 階段 s1 奔潰,s5 成爲了 leader,其會將本已 commit 的 entry 給覆蓋掉。
-
raft 使用一種更簡單的方式來解決這個難題,raft 爲 leader 添加了限制:
-
要成爲 leader 必須要包含過去所有的 commit entry。
-
Candidates 要想成爲 leader,必須要經過大部分 follower 節點的同意。
-
而 commit entry 也表明其已經存在於大部分的服務器中。因此 commit entry 至少會出現在這些 follower 節點中的至少有一個節點。因此我們可以證明,在大部分的 follower 中,至少有一個是包含了 leader 的所有 commit entry 的。
-
因此 如果一個 candidate 的 log 是最新的(即他與其他的節點對比時,如果 term 更大的,最新。如果 term 相同的,那麼越長的那個 log 越新。)其纔可以成爲 leader。
-
因此可知,一個 leader 一定包含了以前 leader 的 commit entry。
todo
-
配置改變
-
日誌壓縮快照(log compaction / snapshotting )
總結
上面對於 raft 的描述,保證了存在 5 點:
-
Election Safety:在一個 term 週期內只會存在一個 leader。
-
Leader Append-Only:leader 只會添加 log,而不會刪除或者覆蓋 log。
-
Log Matching:如果兩個 log 有一個相同 index 與 term 的 entry,那麼他們之前的 log 都是相同的。
-
Leader Completeness:如果一個 log entry 在一個 term 週期成爲 commit, 那麼其一定會存在於下一個 leader 的 log 中。
-
State Machine Safety:如果某節點已經將 index A 應用於其狀態機。則以後其他節點不可能在同一 index A 卻具有不同的 log entry。因爲應用到狀態機說明已經被 commit,而藉助於第 4 點得證。
參考資料
-
my blog
-
raft 論文
-
raft 可視化
-
知乎,寫得一般但是有借鑑地方
-
閱讀 raft 理論與實踐 [2]-lab2a
-
閱讀 raft 理論與實踐 [3]-lab2a 講解
-
閱讀 raft 理論與實踐 [4]-lab2b 日誌複製
-
閱讀 raft 理論與實踐 [5]-lab2c 持久化
go 語言交流 2 羣:713385260
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/QeHnuQhHQUhfBtN05f1qBw