跳至主要內容
論文精煉 · Distributed systems

In Search of an Understandable Consensus Algorithm (Extended Version)

一套以可理解性為設計目標的 leader 式共識演算法,安全性與效率等同 multi-Paxos,但教得會也寫得出來。

作者Diego Ongaro 與 John Ousterhout(Stanford University) 發表於Stanford 技術報告,2014 年 5 月 20 日發表;為 USENIX ATC 2014 論文的延伸版 年份2014
閱讀原始論文 PDF 所有論文

一口氣講完 — 整篇論文的濃縮

Raft 管理一份 replicated log,提供與 multi-Paxos 相同的保證,但它從第一天就是為了「讓人真的看得懂、也寫得出來」而設計。它選出唯一一位權威的 leader:客戶端只跟 leader 說話,log entry 只從 leader 單向流向 follower,而 AppendEntries 的一致性檢查搭配 Log Matching Property,會把分歧的 follower log 硬拉回與 leader 一致。時間被切成一段段 term 充當邏輯時鐘,選舉採用隨機化的 timeout 讓分票變得罕見,而選舉限制——候選人的 log 至少要跟投票給它的那個多數派一樣新——保證每位新 leader 在當選那一刻就已握有全部已提交的 entry,log 因此永遠不必倒流。論文另外規範了線上變更成員的 joint consensus、以 snapshot 為基礎的 log 壓縮合併,以及線性一致的客戶端語意。43 位學生的使用者研究中有 33 位 Raft 成績勝過 Paxos,滿分 60 分的平均是 25.7 對 20.8。

在這篇論文之前 — 它所降落的世界

這篇論文問世前的十年,共識幾乎等同於 Paxos:課堂上教的是它,幾乎每個實作也都拿它當起點。但 Lamport 的說明以 single-decree Paxos 為核心,那是一個被切成兩階段、兩階段都沒有簡單直觀解釋、也無法各自獨立理解的協定;而把多個實例組成 multi-Paxos 的規則只有草稿式的描述,業界始終沒有一套公認的 multi-Paxos 演算法。實務系統——Chubby、ZooKeeper,以及 GFS、HDFS、RAMCloud 底下的協調層——每一個都從 Paxos 出發,撞上缺失的細節,最後長成架構明顯不同的東西,而且細節多半沒有公開;Chubby 的實作者自己寫下:最終系統將建立在一個未經證明的協定之上。Ongaro 與 Ousterhout 提到他們在 NSDI 2012 做過一次非正式調查,即使在資深研究者之中,也很少人自認對 Paxos 感到自在;他們自己則是讀了好幾份簡化說明、又動手設計出一套替代協定之後才真正弄懂完整協定,前後花掉將近一年。他們的結論是:無論作為系統建構的基礎或教學的基礎,Paxos 都不夠好,而「對一整條 log 達成共識」這個問題值得換一種拆法重新來過。

問題 — 當時真正壞掉的地方

  • Paxos 極難理解:完整說明出了名地晦澀,連作者自己都是讀完數份簡化版說明、並動手設計出自己的替代協定之後才弄懂完整協定,前後將近一年。
  • 論文認為 Paxos 的晦澀源自它以 single-decree 子集為地基:那個子集既密又細微,被切成兩個階段,兩階段都沒有簡單直觀的解釋,也無法各自獨立理解。
  • multi-Paxos 沒有一套公認的演算法:Lamport 的描述主要停在 single-decree,組合方式只有粗略草稿,而後續各家補完的版本彼此不同,也和草稿不同。
  • Paxos 的架構本身就不適合拿來蓋系統:先各自獨立地選定一堆 log entry、再把它們併成一條有序的 log,只是徒增複雜度;而它核心的對稱式 peer-to-peer 結構,也不符合「必須連續做一長串決策」的系統實際運作方式。
  • 每個實作都會撞上實作困難、然後長成與論文明顯不同的架構,於是既有的正確性證明對真正跑在線上的程式碼幾乎沒有價值,這個過程既耗時又容易出錯。
  • 一個實用的共識演算法必須在所有非 Byzantine 狀況下保持安全——網路延遲、網路分割、封包遺失、重複與重排——只要任一多數派存活就維持可用,log 的一致性不得依賴時序,且常見情況下一輪 RPC 就能提交。

核心概念 — 主要貢獻,以及它們為何成立

把可理解性當成設計目標

作者的首要目標不是新穎、也不是把訊息數壓到最少,而是讓夠大的一群人能舒服地理解這個演算法,並對它建立直覺。每一個設計分岔口他們都問:這個選項有多難解釋、它的狀態空間有多複雜?而他們反覆使用兩種可複製的技巧:問題拆解,把共識切成 leader 選舉、log 複寫、安全性與成員變更;以及狀態空間縮減,消去不確定性,並禁止 log 出現空洞。這件事之所以重要,是因為論文上的形式從來不是最後上線的形式;開發者必然會偏離、也必然會擴充,唯有具備深層直覺,才可能在改動之後仍保住原有性質。隨機性只被保留在一個地方,正是因為它反而縮小狀態空間——所有可能的選擇都以同一種方式處理,讀者只要想「隨便挑一個,沒差」就好。

強 leader 與單向的 log 流動

Raft 採用比 Paxos 或 Viewstamped Replication 更強的領導形式:log entry 只從 leader 往外流,而 leader 從不覆寫或刪除自己 log 裡的 entry。新 entry 放在哪裡由 leader 一人決定,不需要跟任何人商量;於是「讓分歧的複本重新一致」這個問題塌縮成單一方向——強迫 follower 複製 leader 的 log——而不是一場對稱的合併。Viewstamped Replication 的 log entry 是雙向流動的,因為 leader 在選舉過程中可以接收 entry,這就多出額外機制與複雜度。這也是為什麼 Raft 的基本共識加上成員變更只需要四種訊息型別(兩個 RPC 請求與其回覆),而 VR 與 ZooKeeper 各自定義了十種。

term 作為邏輯時鐘

Raft 把時間切成長度任意的 term,以連續整數編號;每個 term 以一次選舉開場、最多只會有一位 leader,而若票被分散,這個 term 也可能自始至終沒有 leader。每台伺服器保存單調遞增的 currentTerm,而且每次 RPC 都交換當前 term:看到更大 term 的伺服器直接採用它,而發現自己 term 過期的 candidate 或 leader 會立刻退回 follower 狀態。帶著過期 term 的請求則一律被拒絕。這一個機制就同時偵測出過期 leader、過時訊息與癒合中的網路分割,完全不需要實體時鐘,並把「這份資訊還新嗎」化約成一次整數比較。

隨機化的選舉 timeout

Raft 不替候選人排名次,也不外掛一套獨立的選舉協定,而是讓每個 follower 從固定區間(例如 150–300ms)隨機抽一個 timeout 才轉成 candidate,並在每次選舉開始時重新抽一次。把各台伺服器在時間軸上散開,通常只有一台會先逾時、先勝出,並在其他人醒來前就送出心跳;真的發生分票時,重新抽出的隨機等待也讓下一輪再度分票的機率很低。作者原本試過一套決定性的排名方案,讓排名較低的候選人讓位給排名較高者,但每修好一個可用性的邊角情況,就又冒出新的邊角情況。最後隨機化以可理解性勝出:它對所有選擇一視同仁,讀者根本不必逐案推理。

一道檢查撐起 Log Matching

Raft 維持 Log Matching Property:若兩份 log 有 index 與 term 都相同的 entry,則該位置存的是同一個指令,而且兩份 log 在其之前的所有 entry 完全相同。前半成立,是因為 leader 在同一個 term、同一個 index 至多只會產生一個 entry,而 entry 的位置永不改變。後半則由單一道檢查保證:每個 AppendEntries 都帶上新 entry 前一格的 index 與 term,follower 若找不到相符的 entry 就拒絕這次追加。這道檢查其實是歸納法的推進步驟:空 log 天然滿足此性質,而每次延長 log 時檢查都會保住它;因此只要 AppendEntries 成功回覆,leader 就知道 follower 的 log 到新 entry 為止都與自己完全相同。

以選舉限制取代補齊機制

Raft 不是先隨便選一位 leader、再把它缺的 entry 補送過去,而是保證新 leader 在當選那一刻就已握有每一筆已提交的 entry。RequestVote 帶上候選人的 lastLogIndex 與 lastLogTerm,投票者若判定自己的 log 比較新就拒絕投票:最後一筆 entry 的 term 較大者較新,term 相同時則較長者較新。由於候選人需要一個多數派,而任何已提交的 entry 都存在於某個多數派上,兩個集合必然相交——至少有一位投票者持有該 entry,而它會拒絕投給缺少該 entry 的候選人。這正是單向 log 流動得以成立的原因,也省掉了 Viewstamped Replication 在選舉期間或選後補送 entry 的那整套機制。

用 joint consensus 變更成員

讓伺服器直接從舊組態切換到新組態並不安全,因為各台切換的時刻不同,叢集可能短暫裂成「Cold 的一個多數派」與「Cnew 的一個多數派」,兩邊各自為同一個 term 選出一位 leader。Raft 改為先提交一個過渡組態 Cold,new:entry 要複寫到兩個組態的所有伺服器,兩個組態的伺服器都可以當 leader,而任何一致決定——包含選舉與 entry 提交——都必須同時取得新舊兩個組態各自的多數派。多數派彼此重疊,意味著任一組態都無法單方面下決定,於是根本不存在分歧視窗,而叢集在整個變更過程中照常服務客戶端。組態以普通 log entry 的形式傳播,而且伺服器一把它追加進 log 就立即生效,不管提交與否——這正是允許各台在不同時間點跨越、卻仍然安全的關鍵。

運作方式 — 具體的機制

伺服器狀態、term 與兩種 RPC

每台伺服器在任一時刻是 leader、follower 或 candidate 三者之一;follower 是被動的,只回應 RPC,客戶端若連到 follower 會被導向 leader。所有伺服器都必須在回覆任何 RPC 之前寫進穩定儲存的持久狀態有三項:currentTerm、votedFor 與 log[],其中每個 entry 存著狀態機指令以及 leader 收到它時的 term;揮發狀態是 commitIndex 與 lastApplied,leader 另外為每個 follower 維護 nextIndex[] 與 matchIndex[]。基本共識只需要兩種 RPC:candidate 發出的 RequestVote,以及 leader 發出、既負責複寫 entry 也充當心跳的 AppendEntries;第 7 節再加上 InstallSnapshot。RPC 平行送出並持續重試到有回應為止,而任何伺服器只要看到比自己大的 term,就把 currentTerm 更新過去並轉為 follower。

leader 選舉與時序要求

follower 在一個選舉 timeout 內收不到任何有效 RPC,就把 currentTerm 加一、轉成 candidate、投自己一票,並平行對其他所有伺服器送出 RequestVote。接下來只有三種結局:在該 term 取得整個叢集的多數票而當選,隨即以心跳壓制其他競爭者;收到某台 term 不小於自己的伺服器送來的 AppendEntries,於是退回 follower;或是 timeout 到期仍無人勝出,就以更高的 term 重啟一次選舉。每台伺服器在同一個 term 內先到先得、至多投一票,光是這條規則就給出 Election Safety——每個 term 至多一位 leader。安全性從不依賴時序,可用性卻完全依賴:Raft 只有在 broadcastTime 遠小於 electionTimeout、而 electionTimeout 又遠小於 MTBF 時才維持得住穩定的 leader;論文估計 broadcastTime 約 0.5–20ms(因為 RPC 通常要落到穩定儲存)、electionTimeout 約 10–500ms,而典型伺服器 MTBF 為數個月以上。

log 複寫與分歧修復

leader 把客戶端指令追加到自己的 log,平行送出 AppendEntries,等到該 entry 提交——也就是由產生它的 leader 複寫到多數派——才套用到狀態機並回覆客戶端;這同時也提交了它前面所有 entry,包括先前 leader 留下的 entry。leader 把 commitIndex 夾帶在後續的 AppendEntries 與心跳裡,讓 follower 知道可以套用到哪;而所有伺服器一律嚴格依 log index 順序套用。leader 當機會讓 follower 缺 entry、多出未提交的 entry、或兩者兼有,而且可能橫跨多個 term(Figure 7 把各種情形都列了出來);leader 靠 nextIndex 修復,初始值設為自己最後 index 加一,每被一致性檢查拒絕一次就遞減並重試,直到雙方對上為止——此時 AppendEntries 會刪掉 follower 衝突的尾段並補上 leader 的 entry。可選的最佳化是讓拒絕的 follower 回報衝突 entry 的 term 以及它為該 term 存的第一個 index,讓 leader 一個 RPC 跳過一整個 term,而不是一個 RPC 只退一格。follower 與 candidate 當機則完全不需要特別處理:leader 無限重試,而 Raft 的 RPC 是冪等的,重送的 AppendEntries 若帶的 entry 已在 log 裡就直接忽略。

提交規則與安全性論證

leader 不能因為某個舊 term 的 entry 現在剛好存在於多數派上,就斷定它已提交:Figure 8 展示 S1 把 term 2 的 entry 複寫到多數派後,S5 在更晚的 term 當選並把它覆寫掉。因此 Raft 絕不以「數複本」的方式提交先前 term 的 entry——提交規則要求 log[N].term 等於 currentTerm——而一旦當前 term 的任一 entry 提交,前面所有 entry 就透過 Log Matching 間接提交。新 leader 重新複寫舊 entry 時,entry 保留原本的 term 編號,這讓推理更容易,也比那些必須先重編號才能提交的演算法少送許多冗餘 entry。Leader Completeness 的證明梗概是一個反證:若大於 T 的最小 term U 的 leader 缺少 term T 的 leader 已提交的某個 entry,那麼必有一位投票者既接受過該 entry、又投票給 leader U;而 up-to-date 檢查會逼出兩種情況之一——要嘛 leader U 的 log 涵蓋投票者的全部 entry,要嘛 leader U 最後一筆 entry 的 term 來自某個本身就持有該 entry 的更早 leader——兩者都導致矛盾。State Machine Safety 隨之成立,因為伺服器依 index 順序套用,而所有更晚的 leader 在該 index 上存的都是同一筆 entry。

叢集成員變更

收到重組態請求時,leader 追加一個 Cold,new entry 並複寫出去;伺服器只要在自己 log 裡看到某個組態就立刻採用,不管它是否已提交,因此 leader 判斷 Cold,new 是否提交時,用的正是 Cold,new 自己的規則——新舊兩個組態各自的多數派。若 leader 在變更中途當機,新 leader 可能在 Cold 之下、也可能在 Cold,new 之下產生,但這段期間 Cnew 絕不可能單方面下決定。Cold,new 一旦提交,Leader Completeness 就確保只有持有該 entry 的伺服器能當選,於是 leader 可以安全地追加 Cnew;當 Cnew 依自己的規則提交後,不在新組態內的伺服器就可以關機。論文另外處理了三個實務細節:新伺服器先以不計入多數派的 non-voting 成員身分加入並接收 entry,避免它追進度的期間卡住提交;不在 Cnew 內的 leader 會繼續複寫但不把自己算進多數派,並在 Cnew 提交後退位;而被移除的伺服器因為不再收到心跳,本會逾時並用越來越高的 term 把現任 leader 拉下來,因此規定:伺服器若在距離上次聽到現任 leader 不到最小選舉 timeout 的期間內收到 RequestVote,一律忽略。

以 snapshot 做 log 壓縮合併

每台伺服器各自為自己 log 中已提交的前段拍 snapshot:由狀態機寫出當前狀態,再加上少量 metadata——last included index、last included term,以及該 index 當下 log 中最新的組態——然後就可以刪掉該 index 以前的全部 log entry 以及任何舊 snapshot。保留 last included index 與 term,是為了讓 snapshot 之後第一個 entry 仍有前一格可供 AppendEntries 的一致性檢查比對。當 leader 已經丟掉某個落後 follower 需要的 entry(可能是異常緩慢的伺服器,或是剛加入叢集的新機器),就改送 InstallSnapshot:分塊、依序傳送,每一塊同時也是給 follower 的生命跡象,讓它重設選舉計時器;follower 收到後通常直接丟棄整份 log,只有在 snapshot 恰好只涵蓋自己 log 的前綴時,才僅刪掉被涵蓋的部分、保留其後的 entry。各自獨立拍 snapshot 是有意偏離強 leader 原則的,理由是這些 entry 早已達成共識、不可能再有衝突的決定;而只讓 leader 拍再送給所有人,既浪費頻寬也讓 leader 實作更複雜。以「log 超過固定位元組大小」作為拍照時機可讓磁碟開銷維持很小,而 copy-on-write(作者的實作使用 Linux 的 fork)則讓寫 snapshot 不會拖慢正常操作。

客戶端互動與線性一致讀

客戶端一開始隨機挑一台伺服器連線;若對方不是 leader,它會拒絕請求並附上自己最近聽過的 leader 是誰——因為 AppendEntries 請求本身就帶著 leader 的網路位址。leader 當機後的重試可能讓同一個指令執行兩次,因為舊 leader 可能已提交該 entry 卻在回覆前掛掉;解法是每個指令帶一個唯一的客戶端序號,狀態機為每個客戶端記住最新處理過的序號與對應回應,遇到重複序號就直接回覆而不重新執行。唯讀操作可以完全不寫 log,但需要兩道額外防護才不會讀到過期資料:leader 在 term 開始時提交一筆空白的 no-op entry,好知道究竟哪些 entry 真的已提交;而且在回覆唯讀請求前,先與多數派交換一輪心跳,確認自己還沒被取代。若改用以心跳間隔為基礎的 lease 就能省下這一趟往返,但那會讓安全性依賴有界的時鐘偏移,而這是 Raft 在其他地方一律避免的。

論文證明了什麼 — 量測數據與證明

  • 使用者研究招募了 Stanford 與 U.C. Berkeley 的 43 位高年級大學生與研究生,每人以對照平衡的順序各看一段 Raft 與 Paxos 講解影片並各考一次;33 位 Raft 分數較高,滿分 60 分下 Raft 平均 25.7、Paxos 平均 20.8,配對 t 檢定顯示有 95% 信心認為 Raft 的真實平均至少高出 2.5 分。
  • 另建的線性迴歸模型控制了「考哪一份」、既有 Paxos 經驗與學習順序三個因素,預測 Raft 的優勢達 12.5 分,遠大於實測的 4.9 分,因為 43 人中有 15 人本來就有 Paxos 經驗;模型同時預測先考 Paxos 的人 Raft 分數會低 6.3 分,作者說這在統計上顯著,但他們不知道原因。
  • 考後問卷中,41 位受訪者有 33 位認為 Raft 較容易實作成一個正確且高效的系統,也有 33 位認為 Raft 較容易向資工研究生解釋;不過作者提醒,這類自陳感受可能因為受試者知道研究假設而有偏誤。
  • 正確性方面,作者用約 400 行的 TLA+ 規格把 Figure 2 完全精確化;Log Completeness 已用 TLA proof system 機器證明,而僅依賴該規格、完整的 State Machine Safety 非形式化證明約 3500 字。
  • leader 選舉的實測在五台伺服器、broadcast time 約 15ms 的環境下進行:完全不做隨機化時,選舉因反覆分票而一貫超過 10 秒;只加入 5ms 的隨機化,停機時間中位數就降到 287ms;加入 50ms 隨機化後,1000 次試驗中的最差情況為 513ms。
  • 把選舉 timeout 壓到 12–24ms 可讓選出 leader 的平均時間降到 35ms、最久的一次為 152ms,但作者仍建議採用保守的 150–300ms,因為更緊的 timeout 會違反 broadcastTime 的餘裕而造成不必要的 leader 更替;他們自己的實作是 RAMCloud coordinator 內約 2000 行 C++,當時另有約 25 個獨立的第三方實作。

限制與取捨 — 論文自承的,以及後來被發現的

  • 論文自己承認:強 leader 簡化了演算法,卻也排除了某些效能最佳化。作者點名 Egalitarian Paxos——只要同時提出的指令彼此可交換,任何伺服器都能在一輪通訊內提交指令,因此在 WAN 環境下負載更平均、延遲比 Raft 更低,代價是替 Paxos 加上可觀的複雜度。後來的實務也證實單一 leader 是吞吐量天花板,這正是產品系統要切成多個 Raft group 的原因。
  • 論文自己承認:提交規則刻意保守。確實存在 leader 可以安全斷定舊 entry 已提交的情況(例如該 entry 已存在於每一台伺服器上),但 Raft 一律不以數複本的方式提交先前 term 的 entry,寧可多背幾條規則,換取推理上的簡單。
  • 論文自己承認:安全性從不依賴時序,可用性卻完全依賴。leader 當機大約會造成一個選舉 timeout 長度的不可用;timeout 若壓到低於 broadcastTime 的餘裕,會造成不必要的 leader 更替並拉低可用性;而較省事的 lease 式唯讀路徑被明確否決,正因為它會假設時鐘偏移有界。
  • 論文自己承認:形式保證是局部的。只有 Log Completeness 經過機器證明,而該證明仰賴一些未經機器檢查的不變式——作者自陳並未證明規格的型別安全——State Machine Safety 則只有非形式化證明。snapshot 機制也明知故犯地違背了強 leader 原則,因為 follower 可以在 leader 不知情的情況下自行拍照。
  • 後續研究揭露:成員變更比論文呈現的更棘手。Ongaro 在 2014 年的博士論文以「一次只增減一台」取代 joint consensus,而該做法本身後來又被發現必須要求 leader 先提交一筆當前 term 的 entry 才能開始變更;同時他也補上明確的 Pre-Vote 階段,因為論文防止被移除伺服器搗亂的那條規則只寫在成員變更那一節裡,實作者普遍漏掉了。

它後來變成什麼 — 繼承這個想法的系統

Raft 成為 2010 年代基礎設施的預設共識演算法,很大一部分原因是 Figure 2 本身就是一份開發者幾乎可以逐行照抄實作的規格。CoreOS 依本文草稿寫出的 etcd,是 Kubernetes 存放全部叢集狀態的地方,而它的 Go raft 函式庫被 CockroachDB 與 TiKV 整套沿用——兩者都採用每個 key range 或 region 各跑一個 Raft group 的 multi-Raft 設計,藉此繞開單一 leader 的吞吐量天花板。HashiCorp 的 Consul、Nomad 與 Vault,MongoDB 的 replication protocol version 1,Apache Kafka 用來取代 ZooKeeper 的 KRaft 模式,Neo4j 的 causal clustering,以及 RethinkDB、Hazelcast、Apache Ratis,全都採用同一套「leader 加 term 加 log」的骨架。joint consensus 反而是最少被照抄的部分:多數系統改用 Ongaro 2014 年博士論文裡「一次只增減一台」的做法,而且幾乎都自行補上 Pre-Vote 與明確的 leadership transfer。那份 400 行的 TLA+ 規格給了社群一個可機器檢查的參考基準,後續的模型檢查與驗證工作都建立在它之上;而像 MIT 6.824 這類課程,如今教共識的方式已經是讓學生動手實作 Raft,而不是去讀 Paxos。它最廣泛的影響或許是:讓「可理解性」正式成為系統論文裡站得住腳、而且可以量測的設計目標——背後有一個對照式的使用者研究,而不只是一句主張。

論文原文 — 逐字引用

“In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforces a stronger degree of coherency to reduce the number of states that must be considered.”

摘要

“It was important not just for the algorithm to work, but for it to be obvious why it works.”

§1

“To eliminate problems like the one in Figure 8, Raft never commits log entries from previous terms by counting replicas.”

§5.4.2

術語 — 依本篇論文的用法

Replicated state machine(複寫狀態機)
一組伺服器各自從一份 replicated log 執行相同的確定性指令序列,因而算出完全相同的狀態複本,即使部分成員故障整體仍可運作。Raft 的全部工作就是讓這些 log 保持一模一樣。
Term(任期)
以連續整數編號、長度任意的一段時期,以一次選舉開場,其中至多只有一位 leader;有些 term 因為分票而自始至終沒有 leader。term 扮演 Raft 的邏輯時鐘,讓伺服器偵測出過期 leader 與過時資訊。
Committed entry(已提交的 entry)
由產生它的那位 leader 複寫到多數派伺服器上的 log entry,因而具備持久性,並保證最終會被所有可用的狀態機執行。提交一筆 entry 也等於提交了 leader log 中它前面的所有 entry。
Log Matching Property
若兩份 log 含有 index 與 term 都相同的 entry,則該位置存的是同一個指令,而且兩份 log 在其之前的每一筆 entry 都相同。它由 AppendEntries 的一致性檢查維持——該檢查帶上新 entry 前一格的 index 與 term。
Leader Completeness Property
若某筆 log entry 在某個 term 被提交,它必定存在於所有更大編號 term 的 leader 的 log 中。這是 entry 得以只從 leader 流向 follower 的前提,而它由選舉限制保證,而非靠任何補齊協定。
State Machine Safety Property
若某台伺服器已把某個 index 的 log entry 套用到狀態機,就不會有另一台伺服器在同一個 index 套用不同的 entry。這是 Raft 最上層的正確性目標,由 Leader Completeness 加上「依 index 順序套用」推導而來。
Up-to-date(誰的 log 比較新)
投票者在 RequestVote 中採用的比較規則:兩份 log 中最後一筆 entry 的 term 較大者較新;若最後的 term 相同,則較長的 log 較新。只要候選人的 log 沒有自己新,投票者就拒絕投票。
Joint consensus(Cold,new)
過渡組態:entry 要複寫到新舊兩個組態的所有伺服器,兩個組態的伺服器都可以擔任 leader,而每一次選舉與每一次提交都必須同時取得兩個組態各自的多數派。它以普通 log entry 的形式寫入,且伺服器一追加就立即生效。
Last included index / term
snapshot 的 metadata,指出這份 snapshot 取代掉的最後一筆 log entry 及其 term。它們把 snapshot 定位在 log 中的正確位置,讓 snapshot 之後第一筆 entry 仍有前一格可供 AppendEntries 的一致性檢查比對。

在時間軸上的位置 — 這篇論文在整段故事中的座標

在時間軸上查看