原文連結: https://thesquareplanet.com/blog/students-guide-to-raft/
原文標題：Students' Guide to Raft
公眾號: Rust碎碎念
寫在前面: 原文是MIT6.824分布式系統課程中，lab2說明中給出的guide，文章是該課程的助教所寫，翻譯這篇文章希望能對正在學習這門課的童鞋或者對Raft感興趣的同學有所幫助。原文發表於2016年3月16日。
過去的幾個月裡，我擔任了 MIT 的6.824 分布式系統[1]課程的助教。這門課在早期有一些基於 Paxos 一致性算法的實驗，但是今年，我們決定將其轉移到Raft[2]。Raft 是「以易於理解為目標而被設計出來的」，並且，我們的期望這個改變可以使學生的生活變得更加輕鬆。
本文中，以及一起的Instructors』 Guide to Raft[3]文章，記錄了我們的 Raft 之旅，並且希望能對那些 Rust 協議的實現者以及想要對 Raft 內部原理進行更深入地了解的學生有用。如果你正在尋找 Paxos vs Raft 的比較，或者對 Raft 進行更多的教學分析，你應該去閱讀 Instructors』 Guide to Raft 這篇文章。文章的底部包含了一個列表，列表裡是經常被 6.824 學生問到的問題以及其答案。如果你遇到了未在本文主要內容中列出的問題，請去查看Q&A[4]。本文篇幅較長，但是文中提到的所有的點都是6.824學生(和助教)遇到的真實問題。本文值得一讀。
在我們深入了解Raft之前，一些背景知識可能會有用。6.824過去有一系列使用Go[5]構建的基於Paxos的實驗[6]。選擇Go是因為它對於學生來說簡單易學，還因為它很適合寫並發的，分布式應用(goroutine相當便利)。在課程的四個實驗中，學生構建一個容錯(fault-tolerant)，分片式(shared)鍵值(key-value)存儲。第一個實驗要求他們構建一個基於一致性(consensus-based)的日誌庫，第二個實驗在前者基礎上添加一個鍵值存儲，第三個則在多個容錯集群之間對鍵空間(key space)分片，通過一個容錯分片master處理配置變更。我們還有第四個實驗，在該實驗中，學生必須處理機器的故障和恢復而不管磁碟是否完好。該實驗室可作為學生默認的期末項目。
今年，我們決定用Raft重寫所有的實驗。前三個實驗都是相同的，但是第四個實驗被丟棄，因為持久化和故障恢復已經內置於Raft之中。這篇文章主要討論我們關於第一個實驗的經驗，因為它是和Raft最直接相關的，儘管我也會涉及關於在Raft之上構建應用的內容(正如第二個實驗)。
Raft，對於你們當中那些剛剛接觸到它的人來說，這個協議網站[7]上的文字是最好的描述:
Raft是一個以易於理解為目標而被設計的一致性算法。它在容錯和性能方面和Paxos是等效的。區別是它被分解為相對獨立的子問題，並且它乾淨利落地解決了實際系統中需要的所有主要部分。我們希望Raft能夠被更多的人使用，這些使用者將會能開發出大量的質量更高的基於一致性的系統 。
類似這樣[8]的可視化可以給你帶來關於協議的主要部分的較好的概述，並且這篇論文對於為什麼各個部分是被需要的給出了較好的直觀感受。如果你還沒有閱讀extended Raft paper[9]，你應該在繼續閱讀本文之前先去讀一下，因為我假定(你們)對Raft已經比較熟悉。
與所有的分布式一致性協議一樣，細節十分關鍵(the devil is very much in the details)。在沒有故障的穩定狀態下，Raft的行為很容易理解，並且可以以一種直觀的方式來解釋。例如，從可視化中可以簡單地看出，假定沒有故障，一個leader最終將被選出來，並且最終所有發送給leader的操作都會以正確的順序被follower應用(applied)。但是，當把延遲消息、網絡分區和發生故障的伺服器納入考慮範圍後，每一個如果(if)、但是(but)、以及和(and)都變得至關重要。尤其是，我們看到的Bug一再地重複出現，僅僅是因為閱讀論文時的誤解和疏忽。這個問題不是Raft所獨有的，而是會出現在所有提供正確性的複雜分布式系統之中。
實現RaftRaft的終極指南在Raft論文中的Figure 2中。這個figure指定了raft servers之間互相通信的每個RPC的行為，給出了servers必須維護的各種不變量(invariant)，以及指定了特定行為應該在什麼時候發生。我們將會在文章的剩下部分詳細討論Figure 2。(Figure 2)需要嚴格遵守。
Figure 2定義了每個server應該做什麼，在每個狀態，對每個即將到來的RPC，以及特定的其他事情應該在什麼時間發生(比如，什麼時候在log中應用(apply)一個條目(entry))。最初，你可能嘗試把Figure 2作為一種非正式的指南；你把它讀了一遍，然後開始按照寫代碼實現，大致按照它說的去做。這麼做，你很快能得到並運行一個大概能工作的Raft實現。緊接著，問題就開始出現了。
事實上，Figure 2相當地細緻，並且它的每一個聲明(statement)，在規範上都應該作為MUST，而不是SHOULD 。例如，每當你收到一個AppendEntries或RequestVote RPC時， 你可能會合理地重置一個peer的選舉定時器，這表明其他某個peer認為它是leader，或者正在嘗試變成leader。直觀地，這意味著我們不應該幹涉其中。但是，如果你仔細閱讀了Figure 2，它說：
如果選舉超時耗盡而沒有收到來自當前leader的AppendEntries RPC或者對candidate給予投票：轉為candidate。
這個區別是很重要的，因為前者的實現可以導致特定情況下的活性(liveness)大大降低。
細節的重要性(The importance of details)為了使討論更加具體，讓我們來考慮一個絆住了許多6.824學生的例子。Raft論文在很多地方都提及了心跳(heartbeat) RPC。具體來說，一個leader會不定期(每個心跳間隔內至少一次)向所有的peers發出一個AppendEntries RPC以組織他們開啟新一輪選舉。如果leader沒有新的條目要發生給特定的peer，AppendEntries RPC就不包含任何條目，且被當做是一個心跳(消息)。
我們的學生中很多人認為心跳消息是「特殊的(special)」；當一個peer收到一個心跳消息的時候，它應該把這個消息當做不同於一個非心跳的AppendEntries RPC來處理。具體來說，當收到一個心跳消息的時候，它們(譯者註：指peers)簡單地重置其選舉定時器，然後返回成功，而沒有執行任何Figure 2中要求的檢查。這是相當危險的。通過接受RPC，follower隱式地告訴leader它們的日誌和leader的日誌一直到且包括AppendEntries參數中的prevLogIndex都是匹配的。一旦收到回復，leader可能就認為(不正確地)，某個條目已經被複製到servers中的大多數，然後開始提交。
另一個經常出現(通常在修復上面的問題之後)的問題是，一旦收到一個心跳，它們將會截斷follower中緊隨prevLogIndex之後的日誌，並且接著將AppendEntries參數中的條目進行追加。這也是不正確的，我們可以再次查看Figure 2:
如果(if)一個已存在的條目和一個新條目衝突(相同的index但是不同的terms)，刪除已存在的條目以及其之後的條目。
這裡的如果(if)很關鍵。如果follower擁有leader發送的所有條目，follower必須不(MUST NOT) 截斷它的日誌。Leader發送的條目之後的任何元素必須(MUST) 被保留。這是因為我們可能會收到一個過期的來自leader的AppendEntriesRPC，而且截斷日誌將意味著「收回(take back)」那些我們已經告訴leader自己在日誌中擁有的條目。
參考資料[1]6.824分布式系統: https://pdos.csail.mit.edu/6.824/
[2]Raft: https://raft.github.io/
[3]Instructors』 Guide to Raft: https://thesquareplanet.com/blog/instructors-guide-to-raft/
[4]Q&A: https://thesquareplanet.com/blog/raft-qa/
[5]Go: https://golang.org/
[6]基於Paxos的實驗: http://nil.csail.mit.edu/6.824/2015/labs/lab-3.html
[7]網站: https://raft.github.io/
[8]這樣: http://thesecretlivesofdata.com/raft/
[9]extended Raft paper: https://raft.github.io/raft.pdf