【譯】Raft 學生指南

• 2020 年 2 月 17 日
• 筆記

在過去的幾個月中，我一直擔任MIT的 6.824 分散式系統課程的助教。 傳統上，該班級有許多基於 Paxos 共識演算法的實驗，但是今年，我們決定轉向 Raft。 Raft 的設計更易於理解，我們希望這種改變可以使學生的學習更輕鬆。

這篇文章，以及隨附的《Raft 教師指南》一文，記錄了我們使用 Raft 的旅程，並希望對 Raft 協議的教學者和試圖更好地了解 Raft 內部原理的學生有所幫助。 如果您想對 Paxos 與 Raft 進行比較，或者需要對 Raft 進行更多的教學分析，請閱讀《Raft 教師指南》。 這篇文章的底部包含 6.824 個學生常見的Q&A。 如果您遇到的問題未在本文的主要內容中列出，請查看Q&A。 這篇文章很長，但它提出的所有觀點都是許多 6.824 學生遇到的實際問題,這是值得一讀的。

背景

在我們深入研究 Raft 之前，有些背景可能會有用。 6.824 曾經有一組內置於 Go 中的基於 Paxos 的實驗；選擇 Go 是因為它語法簡單易於學習，而且非常適合編寫並發的分散式應用程式。 在四個實驗過程中，學生將構建了一個容錯的分散式 KV 存儲系統。 第一個實驗讓他們建立了一個基於共識的日誌庫，第二個實驗在此基礎上添加了一個鍵值存儲，第三個實驗通過多個容錯的分片主節點處理配置更改，在多個容錯集群之間分了鍵空間。 我們還有第四個實驗，學生必須在磁碟完好無損的情況下處理機器的故障和恢復。 該實驗可作為學生的默認最終項目使用。

今年，我們決定使用 Raft 重寫所有這些實驗。 前三個實驗都是相同的，但是第四個實驗被刪除了，因為 Raft 已經內置了持久性和故障恢復功能。 本文將主要討論我們在第一個實驗中的經驗，因為它是與 Raft 最直接相關的經驗，儘管我還將介紹如何在 Raft 之上構建應用程式。

Raft 是什麼呢？對於那些剛開始了解它的人，我們最好用 Raft 官網上的文字來描述：

Raft 是一種共識演算法，旨在使其易於理解。 在容錯和性能方面與 Paxos 相當。 區別在於它被分解為相對獨立的子問題，並且徹底地解決了實際系統所需的所有主要問題。 我們希望 Raft 將使共識能夠為更廣泛的受眾所接受，並且希望這個更廣泛的受眾能夠開發出更高品質的基於共識的系統。

像這樣的可視化文件很好地概述了協議的主要組成部分，並且更直觀的描述了 Raft 的各個階段。 如果您還沒有閱讀過 Raft 論文，那麼在繼續本文之前，您應該先閱讀該文檔，因為我假設您對 Raft 相當熟悉。

與所有分散式共識協議一樣，細節之處非常重要。 在沒有故障的穩定狀態下，Raft 的行為很容易理解，並且可以直觀地進行解釋。 例如，從可視化中很容易看出，假設沒有失敗，最終將選舉一名 leader ，並且最終發送給 leader 的所有操作將由 followers 按正確的順序進行。 但是，當引入延遲的消息，網路分區和故障伺服器時，每一個 if ， but 和 and 都變得至關重要。 特別是，由於閱讀本文時的誤解或疏忽，我們反覆看到許多錯誤。 這個問題並非 Raft 獨有，而是所有提供正確性的複雜分散式系統中都存在的問題。

Raft 協議的實現

Raft 的最終指南在Raft 論文的 Figure 2 中。 該圖指定了 Raft 伺服器之間交換的每個 RPC 的行為，給出了伺服器必須維護的各種不變數，並指定了何時應執行某些操作。 在本文的其餘部分中，我們將大量討論 Figure 2。如下文描述的一樣。

Figure 2 定義了每個伺服器在任何狀態下對於每個傳入的 RPC 應該做什麼，以及何時應該發生某些其他事情（例如，何時可以安全地在日誌中應用條目）。 剛開始，您可能會傾向於將 Figure 2 視為非正式指南。 您只需閱讀一次，然後開始編寫大致遵循其說要執行的實現的程式碼。 這樣做，您將快速啟動並運行大多數正常運行的 Raft 操作。 然後問題開始浮現了。

實際上，Figure 2 是非常精確的，並且應以規範任期將其所作的每個陳述都視為必須，而不應視為應該。 例如，每當您收到 AppendEntries 或 RequestVote RPC 時，您都可以合理地重置對等方的選舉計時器，因為這兩者都表明其他一些伺服器要麼認為自己是 leader，要麼正試圖成為 leader。 這意味著我們不應該干涉。 但是，如果您仔細閱讀 Figure 2，如 Raft 論文所示：

如果在沒有收到當前 leader 的 AppendEntries RPC 或未向候選人授予投票的情況下經過選舉超時，請轉換為候選人。

事實證明，區別非常重要，因為在某些情況下，前一種實現可能導致活動性大大降低。

Raft 協議實現的細節

為了使討論更加具體，讓我們考慮一個例子，該例子使上 6.828 課程的學生人數增加了。 Raft 論文在許多地方提到了心跳 RPC。 具體來說，leader 會每個心跳間隔至少一次向所有對等方發送一個 AppendEntries RPC，以防止他們開始新的選舉。 如果領導者沒有新條目要發送到特定對等方，則 AppendEntries RPC 不包含任何條目，並被視為心跳。

我們的許多學生都認為心跳在某種程度上是「特殊的」。 當對等方收到心跳時，應將其與非心跳 AppendEntries RPC 區別對待。 特別是，許多人在接收到心跳訊號後便會簡單地重置其選舉計時器，然後返回成功，而無需執行 Figure 2 中指定的任何檢查。這非常危險。 通過接受 RPC，followers 可以隱式告訴 leader，他們的日誌與領導者的日誌相匹配，並且包括並包括在 AppendEntries 參數中的 prevLogIndex。 收到答覆後，領導者可能錯誤地認為某些條目已被複制到大多數伺服器，然後開始提交。

許多人遇到的另一個問題（通常是在解決上述問題後立即發生）是，一旦收到心跳，他們就會在 prevLogIndex 之後截斷 followers 的日誌，然後附加 AppendEntries 參數中包含的所有條目。 這也是不正確的。 我們可以再次轉到 Figure 2：

如果現有條目與新條目（索引相同但任期不同）衝突，則刪除現有條目及其後的所有條目。

如果在這裡至關重要。 如果 followers 具有 leader 發送的所有條目，則 followers 務必不要截斷其日誌。 領導者發送的條目之後的任何元素都必須保留。 這是因為我們可能會從領導者那裡收到過時的 AppendEntries RPC，而截斷日誌意味著「收回」我們可能已經告訴領導者我們在日誌中的條目。

調試 Raft 協議

不可避免地，您的 Raft 實現的第一個迭代會出現錯誤。 第二個也是如此。 第三。 第四。 總的來說，每個錯誤都比前一個錯誤少，並且根據經驗，大多數錯誤是由於不忠實地遵循 Figure 2 而導致的。

在調試 Raft 時，通常有四個主要的 bug 來源：死鎖，錯誤或不完整的 RPC 處理程式，未遵循規則以及任期混亂。 死鎖也是一個普遍的問題，但是通常可以通過記錄所有鎖和解鎖並找出要使用但不釋放的鎖來調試死鎖。 讓我們依次考慮以下每個方面：

未釋放鎖

當系統發生動態鎖定時，系統中的每個節點都在做某事，但是總的來說，您的節點都處於沒有進展的狀態。 在 Raft 中，這很容易發生，特別是如果您不認真地遵循 Figure 2 。 一種死鎖情況特別經常出現。 沒有選舉任何 leader ，或者一旦選舉了 leader，其他節點開始選舉，迫使最近當選的 leader 立即退位。

出現這種情況的原因有很多，但我們已經看到許多學生犯了一些錯誤：

• 確保您按照 Figure 2 所述正確地重置了選舉計時器。具體來說，您僅應在以下情況下重新啟動選舉計時器：a）從當前 leader 那裡獲得了 AppendEntries RPC（如果AppendEntries參數中的任期已過時，則不應重置計時器）； b）您正在開始選舉；c）您給另一位 followers 投票。 在不可靠的網路中，後一種情況尤為重要，在這種網路中，followers 可能擁有不同的日誌。在這種情況下，您通常只會獲得少數伺服器，而大多數伺服器都願意投票。如果您在有人要求您投票給他們投票時重置選舉計時器，則日誌過時的伺服器和日誌較長的伺服器一樣有可能前進。 實際上，由於只有很少的伺服器具有足夠的最新日誌，因此這些伺服器不太可能能夠以足夠的和平度進行選舉。如果您遵循 Figure 2 中的規則，則具有最新日誌的伺服器將不會因過時的伺服器選舉而中斷，因此更有可能完成選舉並成為 leader。
• 請按照 Figure 2 的指示進行何時開始選舉。 特別要注意的是，如果您是候選人（即您當前正在進行選舉），但是選舉計時器觸發了，則應該重新進行選舉。 這對於避免由於RPC延遲或丟失而導致的系統停頓非常重要。
• 在處理傳入的RPC之前，請確保遵循「伺服器規則」中的第二條規則。 第二條規則指出： 如果RPC請求或響應包含條件 T > currentTerm ：設置 currentTerm = T，則轉換為 followers

例如，如果您已經對當任期進行了投票，而傳入的 RequestVote RPC 具有較高的任期，那麼您應該首先卸任並採用其任期（從而重置votedFor），然後處理 RPC，這將導致您同意投票！

不正確的RPC處理程式

即使 Figure 2 清楚地說明了每個 RPC 處理程式應該做什麼，但仍然有些微妙的地方容易遺漏。 這是我們不斷反覆看到的少數幾個，您在實施時應格外注意：

• 如果某個步驟說「答覆錯誤」，則意味著您應立即答覆，而不要執行任何後續步驟。
• 如果您獲得帶有指向日誌末尾的prevLogIndex的AppendEntries RPC，則應像處理該條目但該任期不匹配一樣處理它（即，回復false）。
• 選中#2，即使領導者未發送任何條目，也應執行 AppendEntries RPC 處理程式。
• AppendEntries 的最後一步（＃5）中的最小值是必需的，並且需要使用最後一個新條目的索引進行計算。 僅具有在日誌到達末尾時在 lastApplied 和 commitIndex 停止之間應用日誌中的內容的功能還不夠。 這是因為在領導者發送給您的條目之後，您的日誌中可能有與領導者的日誌不同的條目（所有條目都與您的日誌中的條目匹配）。 由於＃3要求您僅在條目衝突時才截斷日誌，因此不會刪除這些條目，並且如果 LeaderCommit 超出了領導者發送給您的條目，則您可能會應用錯誤的條目。
• 嚴格按照第5.4節中的描述實施「最新日誌」檢查很重要。 沒有作弊，只是檢查長度！

不遵守規則

儘管 Raft 論文非常明確地說明了如何實現每個 RPC 處理程式，但它也保留了許多未指定的規則和不變數的實現。 它們在 Figure 2 右側的「伺服器規則」塊中列出。儘管其中一些是不言自明的，但也有一些需要非常仔細地設計應用程式，以使其不違反The Rules：

• 在執行過程中的任何時候執行 go if commitIndex> lastApplied，則應應用特定的日誌條目。 立即執行操作（例如，在AppendEntries RPC處理程式中）不是至關重要的，但是確保此應用程式僅由一個實體完成很重要。 具體來說，您將需要一個專用的「應用程式」，或者鎖定這些應用程式，以便其他一些常式也不會檢測到需要應用條目並嘗試應用。
• 確保您定期或在更新 commitIndex 之後（即在 matchIndex 更新之後）檢查 commitIndex> lastApplied。 例如，如果在將 AppendEntries 發送給對等對象的同時檢查 commitIndex，則可能必須等到下一個條目追加到日誌之後才能應用剛剛發送並得到確認的條目。
• 如果領導者發出一個 AppendEntries RPC 並被拒絕，但不是由於日誌不一致（只有在我們的任期過去時才可能發生），那麼您應該立即下台，而不要更新 nextIndex。 如果這樣做的話，如果立即連任，您可以與 nextIndex 的重置競爭。
• 領導不允許將commitIndex更新到上一個任期（或就此而言，將來的任期）中的某個位置。 因此，按照規則所說，您特別需要檢查 log[N].term == currentTerm。 這是因為 Raft 領導者如果不是從其當前任期開始，就無法確定該條目是否確實已提交（將來也不會更改）。 Raft 論文的 Figure 8 對此進行了說明。

造成混淆的一個常見原因是 nextIndex 和 matchIndex 之間的差異。 特別是，您可能會注意到 matchIndex = nextIndex-1，而根本沒有實現 matchIndex。 這不安全。 通常通常將 nextIndex 和 matchIndex 同時更新為相似的值（具體來說，nextIndex = matchIndex + 1），但兩者的作用卻截然不同。 nextIndex 是對領導者與給定關注者共享的前綴的猜測。 它通常是相當樂觀的（我們共享一切），並且僅在負面響應時才向後移動。 例如，當剛剛選擇一個領導者時，將 nextIndex 設置為日誌末尾的索引索引。 在某種程度上，nextIndex 用於提高性能–您只需要將這些內容發送給該對等方即可。

matchIndex 用於安全。 這是對領導者與給定跟隨者共享日誌的前綴的保守度量。 matchIndex 永遠不能設置為太高的值，因為這可能導致 commitIndex 移得太遠。 這就是為什麼將 matchIndex 初始化為-1（即我們沒有前綴），並且僅在關注者肯定地確認 AppendEntries RPC 時才進行更新的原因。

任期不一致

任期混淆是指伺服器被來自舊任期的 RPC 混淆。通常，在接收 RPC 時這不是問題，因為 Figure 2 中的規則明確說明了您看到舊任期時應採取的措施。但是，Figure 2 通常不會討論收到舊的 RPC 答覆時應採取的措施。根據經驗，到目前為止，最簡單的方法是首先在答覆中記錄該任期（該任期可能高於您當前的任期），然後將當前任期與您在原始RPC中發送的任期進行比較。如果兩者不同，請放棄答覆並返回。僅當兩個任期相同時，您才可以繼續處理答覆。您可以使用一些聰明的協議推理在此處進行進一步的優化，但是這種方法似乎很好用。不這樣做會導致眼淚和絕望的漫長曲折道路。

一個相關但不完全相同的問題是，假設在您發送 RPC 的時間與收到回復之間的狀態沒有發生變化。一個很好的例子是在收到對 RPC 的響應時設置 matchIndex = nextIndex-1 或 matchIndex = len（log）。這是不安全的，因為自發送 RPC 以來，這兩個值都可能已更新。相反，正確的做法是將 matchIndex 更新為您最初在 RPC 中發送的參數的 prevLogIndex + len（entries []）。

先把優化放在一邊

Raft 包括幾個有趣的可選功能。 在 6.824 中，我們要求學生實施其中兩個：日誌壓縮（第7節）和加速日誌回溯（第8頁左上角）。 前者對於避免日誌無限制增長是必要的，而後者對於使過時的 follower 快速更新很有用。

這些功能不是 Raft 最核心的一部分，因此在本文中沒有像主要共識協議那樣受到足夠的重視。 日誌壓縮已經相當全面地介紹了（在論文圖13中），但是省略了一些設計細節，如果您隨便閱讀它可能會錯過：

• 對應用程式狀態進行快照時，需要確保應用程式狀態與 Raft 日誌中某個已知索引之後的狀態相對應。 這意味著應用程式需要與 Raft 通訊該快照所對應的索引，或者 Raft 需要延遲應用其他日誌條目，直到快照完成為止。
• 本文不討論伺服器崩潰時的恢復協議，並且由於涉及快照而重新出現。特別是，如果筏狀態和快照分別提交，則伺服器可能在持久快照和持久更新更新的筏狀態之間崩潰。這是一個問題，因為論文的圖13中的步驟7指示必須刪除快照覆蓋的Raft日誌。 如果在伺服器恢復時讀取了更新的快照，但讀取了過時的日誌，則可能最終應用了快照中已包含的一些日誌條目。發生這種情況是因為 commitIndex 和 lastApplied 未持久保存，因此 Raft 不知道這些日誌條目已被應用。解決此問題的方法是在 Raft 中引入一個持久狀態，該狀態記錄 Raft 持久日誌中第一個條目所對應的「真實」索引。然後可以將其與載入的快照的 lastIncludedIndex 進行比較，以確定要丟棄日誌開頭的哪些元素。

加速日誌回溯優化的規格非常少，可能是因為作者認為對於大多數部署而言，它不是必需的。 從文本中不清楚不清楚領導者應如何使用從客戶端發送回的衝突索引和任期來確定要使用的 nextIndex 。 我們認為作者可能希望您遵循的協議是：

• If a follower does not have prevLogIndex in its log, it should return with conflictIndex = len(log) and conflictTerm = None.
• If a follower does have prevLogIndex in its log, but the term does not match, it should return conflictTerm = log[prevLogIndex].Term, and then search its log for the first index whose entry has term equal to conflictTerm.
• Upon receiving a conflict response, the leader should first search its log for conflictTerm. If it finds an entry in its log with that term, it should set nextIndex to be the one beyond the index of the last entry in that term in its log.
• If it does not find an entry with that term, it should set nextIndex = conflictIndex.

一個半途而廢的解決方案是只使用衝突索引（並忽略衝突term），這簡化了實現，但是領導者有時最終會向追隨者發送比嚴格更新最新日誌條目更多的日誌條目。

參考

Students』 Guide to Raft