Raft算法精讀

目錄

• 摘要
• 算法描述
  • 概述
    • 狀态
    • RequestVote RPC
    • AppendEntries RPC
  • raft算法保證的性質
  • Leader選舉
  • Log拷貝
    • Entry格式
    • 日志拷貝的過程
      • 一緻性檢查
        • 執行個體分析
    • 什麼情況下Log Entry可以被commit？
• 不嚴格的raft正确性解釋

raft是一種比paxos容易了解的一緻性算法，實作起來比paxos簡單許多。本文前部分描述算法的細節，後部分嘗試探讨下該算法的原理。

raft算法之是以簡單的原因之一是它将問題分解成三個子問題，分别是：

2. Log複制
3. 安全性保證

raft協定中每個server都要維護一些狀态，并且對外提供兩個RPC調用分别是RequestVote RPC和AppendEntries RPC用于選舉和log複制。

要想了解raft，其實就是搞明白：

1. leader和follower需要維護哪些變量，每個變量的含義
2. leader什麼時候發送AppendEntries RPC，攜帶哪些參數，follower收到請求後做什麼？leader收到響應後做什麼？
3. candidate什麼時候發送RequestVote RPC，攜帶哪些參數，follower收到請求後做什麼？candidate收到響應後做什麼？

raft所有的操作都是為了保證如下這些性質。

1. Election Safety: at most one leader can be elected in a given term.
2. Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends new entries.
3. Log Matching: if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.
4. Leader Completeness: if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.
5. State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.

暫時可以先不看，需要知道的是raft所有的規則都是為了保證上面的這些性質，而這些性質又是保證raft正确的前提。

Election Safety性質說的在某個term中最多隻能選出一個leader。

有如下這些規則：

1. raft将時間劃分為term，每個term都有一個number，每個term以選舉一個leader開始。
2. 每個server有三種狀态：leader, follower, candidate。

   

3. 作為follower：有一個稱為election timeout的倒計時，如果在倒計時内沒有收到有效的AppendEntries RPC，将轉換為candidate，增加自己的term number，投自己一票，然後通過RequestVote RPC通知叢集中的其他server進行投票。當半數以上的RequestVote RPC傳回true後，這個candidate将轉換為leader。
4. 某個server收到RequestVote RPC後如何确定要不要投贊同票？同時滿足以下三個條件則投贊同，RequestVote RPC傳回成功：
   1. 在目前周期内還沒有投過票
   2. candidate中term不小于自己的term
   3. "選舉限制"(這是論文在5.4 Safety這一小節給的一個restriction補充) ：想要獲得投票，candidate的logs必須比目前follower的logs更up-to-date。如何比較兩個logs的up-to-date程度？最後一個log entry的term大的更up-to-date， 如果term一樣，index越大越up-to-date。（這一restriction保證了Leader Completeness Property，這個屬性說的是：作為leader必須要有已經被commit的log，很容易了解，leader作為log分發的源頭，如果leader自己都沒辦法保證自己的log包含了所有已經commit的log，那麼怎麼保證其他的follower的log能正确）
5. 作為leader：周期性的發送AppendEntries RPC。

Logs由Entries組成，每個Entry包含一個term和指令，格式如下：

1. leader接收用戶端的Entry，将Entry添加自己的logs中。
2. leader周期性使用AppendEntries RPC将新的entry備份到其它server。
3. follower收到AppendEntries RPC後做什麼？進行一緻性檢查。

follower收到AppendEntries RPCs後，會進行一緻性檢查。

leader為每個follower維護一個nextIndex變量，新上位的leader的nextIndex初始化為目前logs的最後一個log的index+1。

假設leader的logs為：[index1, term=1, cmd1]，[index=2, term=3, cmd2]， [index=3, term=3, cmd3]

假設某個follower的log為：[index1, term=1, cmd1]，[index=2, term=1, cmd4]

第一次leader的AppendEntries RPC發給某個follower的log為[index=3, term=3, cmd3]這一個log entry，那麼AppendEntries RPC同時會攜帶preLogIndex和preLogTerm兩個參數，preLogIndex為要發送的log的前一個index，這裡是2。preLogTerm為leader index為1位置的log的term，這裡是3。

follower在收到AppendEntries RPC後，根據參數中的prevLogIndex，檢查自己的log的prevLogIndex處的Entry的term和參數中的prevLogTerm是否相同，如果相同則将參數中的entries拷貝到自己的log中并且傳回true，否則傳回false。

follower在收到leader的AppendEntries RPC後，進行一緻性檢查，根據參數prevLogIndex=2，發現自己的index為2的log的term為1，和參數preLogTerm（這裡是3）不一緻。是以什麼也不做傳回false。

leader收到響應後如果發現是false，調整參數然後重新發送AppendEntries RPC。leader将要發送的log改為[index=2, term=3, cmd2]， [index=3, term=3, cmd3]，preLogIndex參數變為了1，preLogTerm參數變為了1。

follower在收到這個AppendEntries RPC後，發現自己的index為1的log的term為1，和參數preLogTerm（這裡是1）一緻。于是就将preLogIndex(這裡是1)後的Log（[index=2, term=1, cmd4]）删除，将AppendEntries RPC參數中的log [index=2, term=3, cmd2]， [index=3, term=3, cmd3]加到自己的log後。

現在follower的log變為了：[index1, term=1, cmd1]，[index=2, term=3, cmd2]， [index=3, term=3, cmd3]。和leader一緻。

Entry如果已經确定可以安全apply到狀态機的情況下，将被标志為commited。看上面state圖中，每個server都維護兩個變量commitIndex和lastApplied。這兩個變量都是初始化為0，比如Figure 6中leader的commitIndex就是6，這個值會在

AppendEntries RPC中以leaderCommit參數通知followers修改自己的commitIndex。

commitIndex和lastApplied有什麼差別呢？lastApplied總是<=commitIndex，commitIndex表明的是到commitIndex為止可以被apply，lastApplied表明的是到lastApplied為止已經被apply。

什麼情況下Entry可以被commit？滿足以下兩個條件：

1. A log entry is committed once the leader that created the entry has replicated it on a majority of the servers.（leader将該entry拷貝到大部分server中）

2. 不能commit term比目前leader的term小的Entry。和前面leader選舉限制一樣，這也是論文在5.4 Safety這一小節給的一個restriction。不是很好了解，論文在5.4.2節給出了解釋。

   如下圖：

   

   (a):S1是leader(term=2)，entry 2隻拷貝到了S2就奔潰了。

   (b):S5成為新的leader(term=3)，并且接收了entry 3，但是還沒進行拷貝也崩潰了。

   (c):S1重新成為leader(這時term=4)，并且将entry 2拷貝到了S3。如果沒有條件2的限制，隻看條件1，Entry 2已經被複制到了大部分的server中，就可以被commit了。那麼問題來了，如果Entry 2被commit後S1又奔潰了，這時S5重新成為leader（根據上文給出的選舉規則，S5最後一個Entry的term是3，可以獲得S2, S3, S4和自己的投票，是以可以成為leader），并将Entry 3拷貝到其它的server（情況(d)），并且commit，這樣之前commit的Entry 2就被覆寫了，這是絕對不允許的，已經被commit的Entry不能被覆寫。再次回到情況(c)，這時如果S1不僅複制了Entry 2還複制了Entry 4（term=4）（情況(e)），這種情況下同時滿足條件1和條件2，是以可以commit Entry 2和Entry 4，因為和之前不同的是，如果S1現在奔潰了，S5不可能成為leader（S5的最後一個Entry的term=3，S1, S2, S3都會拒絕投票，因為它們的logs更up-to-date），也就不可能出現commit的Entry被覆寫的情況。

這個圖畫的有點歧義，我總結下，(c)如果不考慮條件2的限制，可能會出現(d)，(d)是不允許出現的。(c)如果同時考慮條件1和條件2，那麼可能出現(e)，(e)是合法的，絕不可能出現(d)這種情況。是以條件2是必要的。

論文中指出raft正确性已經使用TLA+ specification language進行了證明，順便搜了下這個TLA+ specification language，由Leslie Lamport發明，用來驗證設計的正确性的語言，這個Leslie Lamport也是NB的一塌糊塗，Paxos算法也是他設計出來的。我沒有仔細研究嚴格的證明，隻是以一種不嚴格的方式試圖解釋下為什麼raft可以保證一緻性。

raft中所有的log都是由leader流向follower的，是以你leader首先得保證擁有所有的committed log吧，這就是Leader Completeness屬性。那麼如何保證Leader Completeness屬性呢。我認為以下這些規則保證了該屬性：

1. Entry需要被大部分server接收才能被commit。
2. leader需要大部分server投贊成票才能成為leader。
3. "選舉限制"：想要獲得投票，candidate的logs必須比目前follower的logs更up-to-date。

可以用反證法來證明：

假設Leader Completeness屬性不成立，term T的leader(T) commit了一個Entry，但是新的term U的leader(U)沒有包含該Entry。

leader(T)已經commit了該Entry，是以該Entry肯定被大部分server接受了，leader(T)成為leader肯定收到了大部分server的投票，那麼必定存在一個server既接受了該這個Entry也投了leader(U)一票。顯然該server包含的log比leader(T)的要up-to-date，是以和規則3沖突，是以假設不成立，Leader Completeness屬性成立。

保證了源頭log的正确性後，拷貝過程中也要保證和leader的log一緻。Log Matching屬性保證了這一點，該屬性描述的是：如果兩個server中logs中的某個index對應的log entry的term相同，那麼這個index以及之前對應的log entry都應該保證一樣。一緻性檢查規則可以保證該屬性。

raft這些性質中最重要的就是保證State Machine Safety屬性，該屬性描述的是任何一個server在某個index apply一個Entry，其它server不會在該index處apply一個不同的Entry。Leader Completeness + Log Matching可以推出State Machine Safety。

參考資料：

1. raft論文
2. 6.824 raft相關lecture
3. raft faq
4. students-guide-to-raft