fzdwx

fzdwx

Hello , https://github.com/fzdwx
首頁封存

Raft Kv

#mit6.824#transaction89
AI 翻譯
這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文
AI 生成的摘要
這是一系列實驗中的第一個，我們將構建一個容錯的鍵/值存儲系統。在本實驗中，我們將實現Raft（一種複製的狀態機協議）。在下一個實驗中，我們將在Raft上構建一個鍵/值服務。然後，您將在有多個副本的狀態機上進行分片來提高性能。複製通過在多個複製伺服器上存儲其狀態（即數據）的完整副本來實現容錯。Raft將客戶端的請求組織成一個序列，被稱為日誌，並確保所有副本伺服器看到相同的日誌。每個副本按照日誌的順序來執行客戶端的請求，將它們應用於其本地的服務狀態副本。如果一個伺服器發生了故障但是後來又恢復了，Raft會負責將它的日誌更新到最新狀態。在本實驗

Lab2 文件翻譯#

由於我的英文不是很好，所以使用翻譯軟體進行翻譯，然後人工進行校對以便理解。

original 地址: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html

Introduction#

這是一系列實驗中的第一個，我們將構建一個 容錯的鍵 / 值存儲系統。
在本實驗中我們將實現 Raft (一種複製的狀態機協議)。在下一個實驗中，我們將在 Raft 上構建一個鍵 / 值服務。
然後，您將在有多個副本的狀態機上進行 shard（分片？根據鍵進行 hash 來決定路由到哪個副本上）來提高性能。

複製（replication）通過在多個複製伺服器上存儲其狀態（即數據）的完整副本來實現 容錯性。
即使有一些伺服器出現故障（崩潰或網絡斷開和抖動），複製也允許它們繼續運行。挑戰在於故障可能導致副本存在不同的數據。

Raft 將客戶端的請求組織成一個序列，稱為 log，並確保所有 replica servers 看到相同的 log。
每個 replica 按照日誌的順序來執行客戶端的請求，將它們應用於其本地的服務狀態副本（就是運行來自客戶端的命令）。
由於所有存活的副本讀取的日誌內容都是相同的，所以都以相同的順序來執行請求，因此它們都有相同的服務狀態。
如果一個伺服器發生了故障但是後來又恢復了，Raft 會負責將它的 log 更新到最新狀態。只要至少大多數的伺服器還活著，並且能夠繼續通信，
那麼 Raft 將持續運行。如果沒有達到這個數量，那麼 Raft 將會停止運行，直到達到這個數量才會重新開始運行。

在本 lab 中，你將把 Raft 實現為一個帶有相關方法的 GO 的對象類型，目的是為了能在更大的模塊中使用。
一組 Raft 實例通過 RPC 來維護 replicated logs。你的 Raft 實例將支持一連串不確定編號的 command，
也可以叫 log entries。這些 entity 通過 index（索引）來進行編號。具有給定索引的 log entry 將被 commit，
此時，您的 Raft 應該將這條 log 發送到 larger service 上執行。

你應該遵循extended Raft paper中設計，
特別是圖 2。你將實現論文中的大部分內容，包括保存持久化狀態和節點故障自動重啟後讀取狀態。
你將不會實現集群成員的變化（Section 6）。

你可能會發現這個指南很有用，
還有這個關於 concurrency 的鎖
和結構的建議，
如果需要更廣泛的視角，可以看看 Paxos, Chubby, Paxos Made Live, Spanner, Zookeeper, Harp, Viewstamped Replication
和Bolosky et al。

請記住，本 lab 中最具挑戰性的部分可能不是實現你的解決方案，而是調試它。為了幫助應對這一挑戰，你可能需要把事件花在如何使你的實現更容易調試。
你可以參考指導頁和這篇關於有效打印聲明的博文。

我們還提供了Raft 交互圖，
可以幫助闡明 Raft 代碼如何與上層（使用者？）交互。

The code#

通過向raft/raft.go添加代碼來實現 Raft。在該文件中，你會發現骨架代碼，以及如何發送和接收 RPC 的例子。
你的實現必須支持以下接口，測試者和（最終）你的鍵 / 值服務將使用該接口。你可以在raft.go的註釋中找到更多細節。

{{< block type="tip">}}
Raft 實例只能通過 rpc 進行通信且必須使用labrpc這個包（例如不能使用文件以及共享變量）。
{{< /block >}}

// create a new Raft server instance:
rf := Make(peers, me, persister, applyCh)

// start agreement on a new log entry:
rf.Start(command interface{}) (index, term, isleader)

// ask a Raft for its current term, and whether it thinks it is leader
rf.GetState() (term, isLeader)

// each time a new entry is committed to the log, each Raft peer
// should send an ApplyMsg to the service (or tester).
type ApplyMsg

Make#

Make(peers []*labrpc.ClientEnd, me int, persister *Persister, applyCh chan ApplyMsg)

用於創建 Raft server。

  1. 所有的 raft server 的端口都在peers[]存放（包括當前的服務），當前服務的端口可以通過peers[me]來獲取。
  2. 所有的服務的peers[]數組都具有相同的順序。
  3. persister是一個用來存放persistent state的地方，並且在初始的時候會保存最具的狀態，如果有。
  4. applyCh是 service 或 tester 發送消息給 raft 的通道。Make()
    必須快速返回，所以它應該為一些長時間運行的任務啟動goroutines。

Start#

使用 Raft 的服務（例如 kv 伺服器）希望就下個要附加到 Raft 日誌的命令開始協議。如果此伺服器不是領導者，則返回
false。否則啟動協議並立即返回。無法保證此命令將永遠提交到 Raft 日誌，因為領導者可能會失敗或失去選舉。即使 Raft
實例被殺死，這個函數也應該優雅地返回。第一個返回值是該命令在提交時將出現的索引。第二個返回值是當前任期。如果此伺服器認為它是領導者，則第三個返回值為
true。

Start(command interface{}) (int, int, bool)

使用 Raft 的服務（例如 kv 伺服器）希望就下個要追加到 Raft 日誌的命令開始協議。
如果當前 Raft server 不是 leader 則返回false。否則啟動協議並立即返回，無需等待日誌追加完成。
所以無法保證此命令將一定會被提交到 Raft 日誌中，因為 leader 可能會失敗或者在輸掉選舉。
即使 Raft 實例被 kill 這個函數也應該 return gracefully（優雅返回）。

第一個返回值是該命令在 commit 時將被設置的 index。第二個返回值是當前的 term（任期）。如果此伺服器認為自己是 leader
則第三個返回值是true。

每個新提交的Raft log entity都應該發送一個ApplyMsg到Make()的applyCh中。

2A - Leader Election#

實現 Raft leader election 以及 heartbeats（AppendEntries RPCs中不附帶 log entries）。

2A 的目標是：選出一個 leader，如果沒有 failure，它仍然是 leader，
如果 old leader 失敗或者與 old leader 之間的數據包發生丟失則由 new leader 接管。

{{< block type="tip">}}
這個失敗是 leader 出現故障的意思？就是說只要它沒出現運行故障或者網絡問題就永遠是 leader？
{{< /block >}}

要點：

  1. 通過運行go test -run 2A來進行測試你的實現。
  2. 按照論文的圖 2，主要關心發送和接收RequestVote RPCs
    ，與the Rules for Servers that relate to elections
    以及the State related to leader election。
  3. 添加圖 2中與 leader election 相關的狀態到Raft這個結構體中，且還需要定義一個結構來保存每個日誌的信息。
  4. 實現RequestVote()，這樣 raft 服務們就能互相投票了。添加RequestVoteArgs和RequestVoteReply這兩個結構體。修改Make()
    ，創建一個 goroutine，用於檢查心跳消息，如果有一段時間沒有收到 peer 的消息時將發送RequestVote RPCs來定期發起領導者選舉。這樣，如果有
    leader 了，peer 將知道誰是 leader，或者自己成為 leader。
  5. 實現心跳，需要定義一個AppendEntries RPC結構（儘管你可能還不需要所有參數），
    並且讓 leader 定期發送它。編寫一個AppendEntries RPC的 handle method，用於重置選舉超時，
    這樣當有一個人已經當選時，其他伺服器不會又成為 leader。
  6. 確保不同 peer 的選舉超時不在同一時間發生，否則所有 peer 將只為自己投票，這樣就沒有人會成為 leader 了。
  7. 在測試時，leader 每秒發送的 RPC 請求不能超過 10 次。
  8. 在測試時，要求 Raft 在 old leader 失敗後 5 秒內選舉 new leader（如果大多數節點仍然能繼續通訊）。
    但是請記住，如果出現split vote（如果數據包丟失或者候選人選擇了相同的隨機退避時間就有可能發生），leader 選舉可能需要多輪。
    所以必須設置足夠短的選舉超時（也就是心跳間隔），即使會選舉多輪，也有可能在 5 秒內完成。
  9. 論文的Leader election這一節中提到的選舉超時範圍是 150 到 300 毫秒。
    只有當 leader 發送心跳的頻率大大高於 150 毫秒一次時，上面提到的範圍才有意義。由於在測試時限制每秒 10 次心跳，
    所以必須使用比論文中更大的選舉超時，但不能太大，因為可能會無法在 5 秒內完成選舉。
  10. 如果您的代碼無法通過測試，請再次閱讀論文中的圖 2，leader 選舉的全部邏輯分布在圖中多個部分。
  11. 不要忘記實現GetState()。
  12. 在測試時，如果要關閉一個 raft 實例，會調用rf.kill()。我們可以調用rf.killed來檢查是否被調用kill()。您可能希望在所有的循環中都這樣
    做，以避免死亡的 Raft 實例打印混亂的信息。
  13. go RPC只發送名稱以大寫字母開頭的結構體字段。子結構體也必須擁有大寫的字段名。

2B - log#

實現 leader 以及 follower 的代碼來添加新的日誌。

要點：

  1. 你的首要目標就是通過TestBasicAgree2B。從實現Start()開始，根據圖 2，編寫代碼，
    通過AppendEntries發送和接收新的日誌。發送最近提交的日誌到對方的applyCh中。
  2. 需要實現election restriction。
  3. 在早期的 Lab 2B 測試中未能達成協議的一種方法是：即使 leader 還存活也要重複進行選舉。
    在 election timer 中找 bug，或者在贏得選舉後不立即發送心跳的問題。
  4. 你的代碼中可能有重複檢查某些事件的循環。不要讓這些循環連續的執行而沒有暫停，這將使你的實現慢到無法通過測試。
    使用 Go 的condition variables 或者加入time.sleep(10 * Millisecond)在每個循環中。
  5. 讀懂config.go以及test_test.go以便了解在測試什麼內容。

代碼實現思路#

大概記錄一下代碼的實現思路以及遇到的問題。

2A#

  1. 根據圖 2 中的 state 這一節添加對應的屬性。
  2. 添加RaftRole屬性，代表當前的角色：leader, candidate, follower。
  3. 實現ticker這個函數：
    • 可以使用兩個time.timer來作為觸發器。
    • 判斷是否很久沒有收到心跳，來發起選舉。
    • 判斷是否需要發送心跳，來維持自己的權威。
  4. 這個時候要注意這條規則： 如果 RPC 的請求或者響應中包含一個 term T 大於 currentTerm，則 currentTerm 赋值為 T，
    並切換狀態為 follower。
  5. 實現發起選舉的流程：
    • 根據圖 2 中的Rules for Servers的candidate流程一步一步實現。
    • 並行發起RequestVote RPC，如果票數大於 1/2 則轉換為 leader（可能需要廣播心跳）。
  6. 實現RequestVote：
    • 根據圖 2 中的RequestVote RPC一步一步實現就好。
  7. 實現AppendEntries：
    • 只需要簡單的實現轉換為 follower 以及刷新選舉超时时間即可。
  8. 所有節點收到響應後刷新選舉超时时間（具體情況具體判斷）。
  9. 成為 leader 後開始刷新心跳超时时間（來刷新 follower 的選舉超时时間）。

遇到的問題：

  1. 第一次測試會有warning: Term changed even though there were no failures出現。

就是在有一個 leader 的時候其他 follower 還是發起了選舉。猜測原因是election timeout和AppendEntries的時間點很鄰近，這個只能調試
兩種超时时間，我的選舉超时时間是 200~350ms，心跳固定在 125ms。

然後我在轉換角色的時候加了一個if new role == old role then return的判斷，這裡導致election timeout沒有刷新。

  1. 在響應或請求時要第一時間處理第 4 條。

Raft 論文翻譯#

選取一些重要的片段進行翻譯。

original 地址: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf

Abstract#

Raft 是一種為了管理複製日誌的共識算法。它提供了和 Paxos 算法相同的功能和性能，但它的算法結構和 Paxos 不同，
Raft 更容易理解並且更容易構建實際的系統。為了提升可理解性，Raft 將共識算法分成了幾個關鍵的模塊，例如領導人選舉、日誌複製和安全性。
同時它通過實施一個更強的一致性來減少需要考慮的狀態的數量。Raft 還包括一個機制來允許集群成員的動態改變，它利用重疊的大多數來保證安全性。

Introduction#

Raft 算法和已經存在的共識算法在某些地方很相似（主要是 Oki 以及 Liskov's Viewstamped Replication），但是它有以下新特性：

  • 強領導者：Raft 使用一種比其他共識算法更強的領導形式。例如，日誌只從 leader 發送給其他伺服器。
    這簡化了對複製日誌的管理並使得 Raft 更容易理解。
  • 領導選舉：Raft 使用隨機的計時器來選取 leader。這種方式僅僅是在所有共識算法都需要改進的心跳機制上有些許改進，然而這使得
    Raft 在解決衝突時更簡單和快速。
  • 成員調整：Raft 使用了新的聯合共識（join consensus）算法來處理集群成員變換的問題，
    在處於調整過程中的兩種不同的配置的大多數集群會有重疊（overlap），這就允許集群在成員變更的時候，持續正常運行。

Replicated State Machine#

Replicated State Machine（複製狀態機）在分布式系統中被用於解決各種容錯問題。例如 GFS、HDFS、RAMCloud 等單 leader 的大型集群系統，
通常使用獨立的複製狀態機來管理領導選舉和存儲配置信息來保證在 leader 崩潰的情況下也要存活下來，複製狀態機的例子包括 Chubby
以及 Zookeeper。

共識算法是在複製狀態機的背景下提出的，在這種方法中，在一組伺服器上的狀態機對同一個的狀態會計算出相同的副本，並且在一些伺服器宕機的情況下也可以繼續運行。

如圖一所示，複製狀態機是通過複製日誌實現的。每個伺服器保存著一個包含一系列命令的日誌，其狀態機按照順序來執行它們。
每個日誌包含相同順序的相同命令，所以每個狀態機都執行相同的命令序列。因為狀態機是確定的，所以每個狀態機會計算出相同的狀態和相同順序的輸出。

共識算法的任務是保證複製日誌的一致性。伺服器上的共識模塊接收來自客戶端的命令並把它們添加到日誌中，
並與其他伺服器上的共識模塊進行通訊以確保它們的每一條日誌最終都相同（相同的請求有相同的順序），即使有一些服務發生故障。
一旦命令被正確的複製，每一個服務的狀態機將按照日誌的順序去處理它們，然後將結果返回給客戶端。

因此，這些服務似乎成為了一個單一的，高度可靠的狀態機。

在實際的共識算法通常有以下屬性：

  • 確保非拜占庭（non-Byzantine）條件下的安全性（永遠不返回錯誤的結果），包括網絡延遲、分區以及網絡數據包丟失、冗餘、亂序。
  • 只要大多數的服務都在運行並能相互通信且和客戶端通信，它們就能發揮出全部的功能（可用性）。因此，一個 5 台服務的集群能容忍 2 台服務出現故障。
    假定服務應為停機而出現故障，它們可能稍後會從stable storage中恢復狀態並重新加入集群。
  • 不依賴與時序來保證日誌的一致性：錯誤的時鐘和極端的信息延遲在最壞的情況下會導致可用性問題。
  • 在一般情況下，一個命令的完成在於集群中的大多數對單輪遠程調用作出響應，少數比較慢的服務不會影響系統的整體性能。

The Raft consensus algorithm#

Raft 就是用於管理上一解描述的複製日誌的算法。圖 2
是對該算法的精簡型式的總結，圖 3列出來該算法的關鍵屬性，接下來對這些部分進行逐一討論。

Raft 通過選出一位 leader 然後給予它完全管理日誌複製的責任來實現共識。leader 接收來自客戶端的日誌，然後複製給其他服務，並且通知在何時
它們可以安全的消費（作用到狀態機上）這些日誌。leader 簡化了日誌複製的管理。例如： leader 可以自主確定新日誌存放在哪個位置而不用詢問其他服務，
並且數據都從 leader 流向其他伺服器。leader 可能會發生故障，或者和其他伺服器失去連接，這個時候需要重新選舉 leader。

基於 leader 的方法，Raft 將一致性問題為了三個子過程來解決：

  • leader 選舉：當 leader 失敗（宕機）時需要選舉新 leader。
  • 日誌複製：leader 接收來自客戶端的日誌，並複製給集群中的其他機器，強制其他伺服器與自己的一致。
  • 安全：Raft 的安全就在於圖 3中的安全屬性：如果任何伺服器消費了一個日誌，那麼其他任何伺服器就不
    能在相同的日誌索引消費不同的日誌。

Figure 2#

state：

  • 在所有伺服器上持久化（在響應 RPC 請求之前，已經更新到了穩定的存儲設備）
    • currentTerm: 伺服器已知最新的任期（在伺服器首次啟動時初始化為 0，單調遞增）
    • votedFor: 當前任期內收到選票的 candidate Id，如果沒有投給任何候選人則為空
    • log[]: 日誌條目，每個條目包含了用於狀態機的命令，以及領導人接收到該條目時的任期（初始索引為 1）
  • 所有伺服器上的易失性狀態
    • commitIndex: 已知的提交的日誌中的最大索引（初始 0，單調遞增）
    • lastApplied: 狀態機已經執行的日誌中的最大索引（初始 0，單調遞增）
  • 在 leader 上不穩定存在（在每次重新選舉後初始化）
    • nextIndex[]: 對於每一個伺服器，發送到該伺服器的下一個日誌條目的索引（初始為 leader 的最後一條日誌索引 + 1）
    • matchIndex[]: 對於每一個伺服器，已知的已經複製到該伺服器的最高日誌條目的索引（初始 0，單調遞增）

AppendEntries RPC

由 leader 發起調用來複製日誌，同時也用於心跳檢測。

  • Arguments:
    • term: leader 的任期
    • leaderId: 用於 follower 找到 leader（有時 client 把請求發送給了 follower）
    • prevLogIndex: 緊鄰新日誌條目之前的那個日誌條目的索引
    • prevLogTerm: 緊鄰新日誌條目之前的那個日誌條目的任期
    • entries[]: 需要被保存的日誌（為空時是心跳檢測，可能一次會發送多條來提升效率）
    • leaderCommit: leader 已提交的最高的日誌條目的索引
  • Results:
    • term: currentTerm，用於 leader 更新自己的term
    • success: 如果 follower 的prevLogIndex以及prevLogTerm能夠匹配上則為 true
  • Receiver implementation:
    • if term < currentTerm then return false（如果 leader 的任期小於接收者的當前任期，接收者可以是 follower 以及
      candidate）
    • if log[prevLogIndex].term != prevLogTerm then return false（在接收者日誌中 如果能找到一個和 prevLogIndex 以及
      prevLogTerm 一樣的索引和任期的日誌條目則繼續執行下面的步驟否則返回假）
    • if log[oldIndex].term != log[newIndex].term then remove log[oldIndex,lastIndex]（
      如果一個已經存在的日誌與新的日誌（請求中的日誌條目）衝突（索引相同，任期不同），則刪除該索引處以及之後的所有日誌）
    • 添加在日誌列表中不存在的新日誌
    • if leaderCommit > commitIndex then commitIndex=min(leaderCommit,log[].last.commitIndex)（
      如果 leader 的已知已提交的最高日誌條目的索引大於接收者的已知已提交最高日誌條目的索引，則把接收者的已知已經提交的最高的日誌條目的索引 commitIndex
      重置為 leader 的已知已經提交的最高的日誌條目的索引 leaderCommit 或者是 上一個新條目的索引 取兩者的最小值）

RequestVote RPC

候選人調用，收集選票。

  • Arguments:
    • term: candidate 的任期號
    • candidateId: 發起請求的 candidate 的 id
    • lastLogIndex: candidate 的最後一條日誌的索引
    • lastLogTerm: candidate 最後一條日誌對應的任期號
  • Results:
    • term: 當前任期號，用於 candidate 更新自己的term
    • voteGranted: true 表示候選人獲得了選票
  • Receiver implementation:
    • if term < currentTerm then return false（如果 term < currentTerm 返回 false）
    • if (votedFor==null||votedFor==candidateId)&&(lastLogIndex,lastLogTerm)==log[].last then return true
      （如果 votedFor 為空或者與 candidateId 相同，並且候選人的日誌和自己的日誌一樣新，則給該候選人投票）

Rules for Servers

  • All Servers:
    • if commitIndex > lastApplied then incr lastApplied and exec log[lastApplied]（如果 commitIndex >
      lastApplied,lastApplied 自增，將 log [lastApplied] 應用到狀態機）
    • if appendEntries.logs exist (log.term > currentTerm) then currentTerm = log.term and set status = follower（如果
      RPC 的請求或者響應中包含一個 term T 大於 currentTerm，則 currentTerm 赋值為 T，並切換狀態為 follower）
  • Followers:
    • 不會發出任何請求，只會對來自 candidates 以及 leader 的請求做出響應
    • 選舉超時後，如果未收到當前 leader（term 相同）的AppendEntries RPC或投票給了 candidate，則轉換為 candidate
  • Candidates:
    • 轉換成 candidate 之後開始選舉
      • incr currentTerm
      • 投票給自己
      • reset election timer
      • 發送RequestVote RPC給其他所有伺服器
    • 如果收到了多數的選票則成為 leader
    • 如果收到 new leader 的AppendEntries RPC則成為 follower
    • 如果選舉超時則開始新一輪的選舉
  • Leaders:
    • 一旦成為 leader 則向其他伺服器發送空的AppendEntries RPC，在空閒時重複發送以防止選舉超時
    • 如果收到來自 client 的命令：添加到本地日誌，在執行並作用到狀態機後作出響應給 client
    • 對於 follower if last log index >= nextIndex（最後日誌條目的索引值大於等於 nextIndex）：
      則通過AppendEntries RPC將 nextIndex 之後的所有日誌都發送發送出去
      • 如果成功：將該 follower 的nextIndex以及matchIndex更新
      • 如果因為日誌不一致導致失敗：nextIndex遞減並重新發送
    • 如果存在一數 N，滿足N > commitIndex，大多數的matchIndex[i] >= N
      以及log[N].term == currentTerm：set commitIndex = N

Figure 3#

  • Election Safety: 在給定 term 內只能選出一個 leader
  • Leader Append-Only: leader 永遠不覆蓋或刪除日誌，只會添加
  • Log Matching: 如果兩個日誌在包含相同的 index 以及 term，那麼就認定它們完全相同
  • Leader Completeness: 如果一條日誌在給定的 term 內提交，那麼它一定會出現在 term 更大的 leader 的日誌中
  • State Machine Safety: 如果一個伺服器已經將給定索引位置的日誌條目應用到狀態機之中，則其他所有伺服器不會在相同索引處出現不同的日誌

Raft basics#

一個 Raft 集群可以包含多個伺服器；5 是一個典型的數量，它允許系統容忍 2 次故障（有兩台服務宕機）。
在給定的時間中每個服務都處在以下三種狀態之一：
leader，follower，candidate。正常情況下，恰好只有一個 leader，所有其他伺服器都是 follower。

  • follower 是被動的：它們不會自己發出請求，而只是響應來自 leader 和 candidate 的請求。
  • leader 處理所有 client 的請求（如果 client 聯繫到 follower，則 follower 重定向到 leader）。
  • candidate 用於選舉出一個新的 leader（可以看圖 4）。

Figure 4#

如圖 5 所示： Raft 將時間分為任意長度的 terms。terms 的編號是連續的整數。每一個 term 開始於 election，一個或多個 candidate
嘗試成為 leader。如果一個 candidate 贏得了選舉，那麼它將在剩下的 term 內擔任 leader。

在某些特殊情況下選舉的結果是 split vote。在這種情況下，term 將會結束並且沒有 leader。一個新的 term（伴隨新一輪的選舉）將很快開始。
Raft 保證在給定的 term 內最多只有一個 leader。

Figure 5#

不同的伺服器可能會在不同的時間觀察到 term 之間的轉換，在某些情況下，一個伺服器可能不會觀察到選舉甚至整個 term 的全程。
term 在 Raft 中充當了邏輯時鐘，term 使得可以伺服器檢測過時的信息：如過時的 leader。

每個伺服器都存儲一個當前的 term 編號，該編號隨時間單調地增加。每當伺服器進行通信時，就會交換當前 term；
如果一個伺服器的當前 term 比另一個伺服器的小，那麼它就會將其當前 term 更新為較大的值。

如果一個 candidate 或 leader 發現它的 term 已經過時，它將立即恢復到 follower 的狀態。

如果一個伺服器收到的請求是一個過時的 term 編號，它將拒絕該請求。

Raft 伺服器使用 RPC 進行通信，而基本的共識算法只需要兩種類型的 RPC。RequestVote RPCs由 candidate 在選舉期間發起；
AppendEntries RPCs由 leader 發起，用於複製日誌條目並提供一種心跳機制。在下面的章節還增加了第三個 RPC，用於在伺服器之間傳輸快照。
如果伺服器沒有及時收到響應，它們會重試 RPC，並且為了獲得最佳性能，它們會並行地發出 RPC。

Leader election#

Raft 使用心跳機制來觸發 leader 選舉。當伺服器啟動時，初始狀態都是 follower。只要伺服器收到來自 leader 或 candidate 的有效 RPC，
它就一直處於 follower 狀態。 leader 定期向所有 follower 發送心跳（AppendEntries RPCs，不攜帶日誌條目），以保持他們的權威。
如果 follower 在一段時間內沒有收到任何通信（election timeout），那麼它就認為沒有可用的 leader，並開始選舉以選擇一個新的
leader。

要開始一場選舉，follower 要增加它的當前 term 並轉換到 candidate 狀態。
然後，它為自己投票，並行的向集群中的每個其他伺服器發出RequestVote RPCs。
candidate 將一直處於這種狀態，直到發生以下三種情況之一：

  1. 它贏得了選舉
  2. 另一個伺服器確立了自己的領導地位
  3. 一段時間之後沒有任何人獲勝。

接下來就對這些結果進行討論：

它贏得了選舉

如果一個 candidate 在同一任期（ term ）內獲得了整個集群中大多數伺服器的投票，那麼它就贏得了選舉。
每台伺服器在給定的 term 內最多為一名 candidate 投票，以先來後到為原則。

少數服從多數的原則保證了最多只有一名 candidate 能夠在某一 term 內贏得選舉
（圖 3中的選舉 Safety 屬性）。
一旦一個 candidate 在選舉中獲勝，它就成為 leader。然後，它向所有其他伺服器發送心跳信息（不攜帶日誌的AppendEntries RPC），
以建立其權威並防止新的選舉發生。

另一個伺服器確立了自己的領導地位

在等待投票的過程中，candidate 可能會收到另一個伺服器的AppendEntries RPC，聲稱自己是領導者。
如果這個 leader 的 term（會攜帶在 RPC 中）不小於 candidate 當前的 term，
那麼 candidate 就會承認 leader 是合法的並返回到 follower 狀態。
如果 RPC 中的 term 比 candidate 當前的 term 小，那麼候選者會拒絕 RPC，並繼續處於 candidate 狀態。

一段時間之後沒有任何人獲勝

第三個可能的結果是 candidate 既沒有贏得選舉，也沒有輸掉選舉：如果許多 follower 同時成為 candidate，那麼票數可能被分割，
因此沒有 candidate 能獲得足夠的投票。
當這種情況發生時，每個 candidate 都會超時，然後通過增加其 term 和發起新一輪的RequestVote RPC來開始新的選舉。
然而，如果沒有額外的措施，split vote可能會無限期地重複。

Raft 使用隨機的選舉超時來確保 split vote 很少發生，並能迅速解決。
為了從一開始就防止 split vote，選舉超時是從一個固定的時間間隔（例如 150-300ms）中隨機選擇的。
這樣每個伺服器的選舉超時就不同了，所以在大多數情況下，只有一個伺服器會超時。

如果一個服務贏得了選舉，就在其他服務超時之前發送心跳，split vote就是使用這樣的機制來處理。
每個 candidate 在選舉開始時重新啟動其隨機選舉超時（重新計時？），並等待超時過後再開始下一次選舉；
這減少了在新的選舉中再次出現 split vote 的可能性。

選舉是一個用於說明可理解性是如何指導我們在設計方案做權衡的例子。
最初我們計劃使用一個排名系統：每個 candidate 被分配一個唯一的排名，用來在競爭的 candidate 之間進行選擇。
如果一個候選人發現了另一個排名更高的候選人，它就會回到 follower 的狀態，這樣排名更高的候選人就能更容易地贏得下一次選舉。
我們發現這種方法在可用性方面產生了一些微妙的問題（如果一個排名較高的服務發生故障了，一個排名較低的伺服器可能需超時並再次成為
candidate，但如果它過早地這樣做，它可能會重置選舉 leader 的進展）。我們對算法進行了多次調整，但每次調整後都會出現新的角落案例。
最終我們得出結論，隨機重試的方法更明顯，更容易理解。

Log replication#

一旦一個領導者被選出，它就開始為 client 的請求提供服務。每個 client 的請求都包含一個要由複製的狀態機執行的 command。
leader 將該 command 作為一個新的條目附加到它的日誌中，然後並行發起AppendEntries RPC給其他每個伺服器以複製該條日誌。
當條目被安全的複製後（下面會介紹），leader 將這條日誌應用於其狀態機，並將執行結果返回給 client。
如果 follower 崩潰或運行緩慢，又或者網絡數據包丟失，leader 會無限期地重試AppendEntries RPC（甚至在它回應了客戶端之後），
直到所有 follower 最終存儲所有日誌條目。

日誌的組織方式如圖 6所示。每個日誌條目都存儲了一個狀態機命令，
以及 leader 收到該條目時的 term 編號。日誌條目中的 term 編號被用來檢測日誌之間的不一致，
並確保圖 3中的一些屬性。每個日誌條目也有一個整數的索引來標識它在日誌中的位置。

leader 決定何時將日誌條目應用於狀態機是安全的，這樣的條目被稱為 committed。
Raft 保證所提交的條目是持久化的並且最終會被所有可用的狀態機執行。
一旦創建該條目的 leader 將其複製到大多數伺服器上，該日誌條目就會被提交（例如，圖 6 中的條目 7）。
這也會提交 leader 日誌中所有之前的條目，包括之前領導者創建的條目。
leader 會跟蹤它所知道的已提交的最大索引，並且它在未來的AppendEntries RPC（包括心跳）中包括該索引，以便其他伺服器最終發現。
一旦 follower 得知一個日誌條目被提交，它就會將該條目應用於其本地狀態機（按日誌順序）。

我們設計的 Raft 日誌機制在不同伺服器上的日誌之間保持高度的一致性。這不僅簡化了系統的行為，使其更具可預測性，而且是確保安全的重要組成部分。
Raft 維護了以下特性，它們共同構成了圖 3中的Log Matching特性：

如果不同的兩個日誌具有相同的 index 以及 term

  • 那麼就認為它們存儲的是同一個 command
  • 那麼就認為它們之前的所有日誌也是相同的

第一個屬性來自於這樣一個事實，即一個 leader 在一個 term 內只能在一個 index 上創建一個日誌條目，並且日誌條目永遠不會改變它們在日誌中的位置。
第二個屬性由AppendEntries RPC執行的簡單一致性檢查來保證。
當發送AppendEntries RPC時，leader 會包含其日誌中緊接新條目之前的條目的 index 和 term。
如果 follower 在其日誌中沒有找到具有相同 index 和 term 的條目，那麼它將拒絕新條目。
一致性檢查就像一個歸納步驟：日誌的初始狀態是肯定滿足Log Matching屬性的，
並且每當日誌被擴展時，一致性檢查都會保留Log Matching屬性。
因此，每當AppendEntries成功返回時，leader 知道 follower 的日誌與自己的日誌在新條目之前是相同的。

在正常運行期間，leader 和 follower 的日誌保持一致，所以AppendEntries一致性檢查不會失敗。
然而，leader 崩潰會使日誌不一致（old leader 可能沒有完全複製其日誌中的所有條目）。
這些不一致會在一系列 leader 和 follower 的崩潰中加劇。圖 7 說明了 follower 的日誌可能與 new leader 的日誌不同的方式。

  • follower 可能會丟失 leader 的條目
  • follower 可能會有 leader 沒有的額外條目
  • 或者兩者都有

日誌中缺失和多餘的條目可能跨越多個 term。

在 Raft 中，leader 通過強迫 follower 的日誌重複自己的日誌來處理不一致的情況。這意味著 follower 日誌中的衝突條目將被 leader
日誌中的條目覆蓋。在下一節將表明，如果再加上一個限制，這就是安全的。

為了使 follower 的日誌與自己的日誌保持一致，leader 必須找到兩個日誌一致的最新日誌條目，刪除該點之後 follower 日誌中的所有條目，
並將該點之後的所有 leader 條目發送給 follower。所有這些操作都是為了響應AppendEntries RPC執行的一致性檢查而發生的。
leader 為每個 follower 維護一個 nextIndex，這是 leader 將發送給該 follower 的下一個日誌條目的 index。
當 leader 當選時，它會初始化所有 nextIndex 的值為自己最後一條日誌的 index + 1（圖 7 中的 11）。
如果 follower 的日誌與 leader 的日誌不一致，則AppendEntries一致性檢查將在下一個AppendEntries RPC中失敗。
follower 拒絕後，leader 會減少 nextIndex 的值並重試AppendEntries RPC。
最終nextIndex將達到 leader 和 follower 日誌匹配的點。
發生這種情況時，AppendEntries將成功，這將刪除 follower 日誌中的任何衝突條目，並從 leader 日誌中添加條目（如果有）。
一旦AppendEntries成功，follower 的 log 就會和 leader 的一致，並且在接下來的任期內保持這種狀態。

如果需要，可以優化協議以減少被拒絕的AppendEntries RPC的數量。例如，當拒絕AppendEntries請求時，
follower 可以包含衝突條目的 term 以它在 term 中存儲的第一個索引。
有了這些信息，leader 可以減少 nextIndex 以繞過該 term 中的所有衝突條目；
每個有日誌衝突的 term 都只需要一個AppendEntries RPC，而不是每個日誌條目一個 RPC。
在實踐中，我們懷疑這種優化是否必要，因為失敗很少發生，而且不太可能有很多不一致的條目。

通過這種機制，leader 在上台時無需採取任何特殊措施來恢復日誌一致性。它剛剛開始正常運行，
並且日誌會自動收斂以響應AppendEntries一致性檢查的失敗。
leader 永遠不會覆蓋或刪除自己日誌中的條目（圖 3中的Leader Append-Only）。

理想的 Raft：

  • 只要大多數伺服器啟動，Raft 就可以接受、複製和應用新的日誌條目
  • 可以通過單輪 RPC 將新條目複製到集群的大部分；
  • 並且單個慢速 follower 不會影響性能。

Safety#

在前面的章節裡面介紹了 Raft 怎樣選舉領導以及複製日誌。
然而，這些機制還遠不夠來保證每個狀態機以相同的順序來執行相同的 command。
例如，一個 follower 可能是不可用狀態（unavailable）而 leader 提交了若干個日誌，然後它可能會被選為 leader 然後覆蓋這些日誌；
結果就是不同的狀態機可能執行了不同的 command sequence。

在這一節通過添加對哪些伺服器可以被選舉為 leader 的限制來完善 Raft。
這個限制確保 leader 在任意給定 term 內，包含了之前任職期間的所有被提交的日誌（圖 3中的Leader Completeness Property）
增加這個選舉限制，讓我們使提交時的規則更加準確。
最後，我們會展示一個簡要的證明為Leader Completeness Property並且說明是怎樣引導出正確行為的複製狀態機。

Election restriction#

在任何基於 leader 的共識算法中，leader 必須將已提交的日誌存儲。在一些共識算法中，比如Viewstamped Replication，
一個節點能當選 leader，即使它一開始沒有包含所有已提交的日誌。
這些算法都有額外的機制來識別丟失的日誌並發送給 new leader，要麼在選舉的過程中或者在選舉之後不久。
不幸的是，這種方法會導致相當大的額外的機制和複雜性。

Raft 使用了一種更加簡單的方法，它可以保證在選舉的時候新的 leader 擁有所有之前任期中已經提交的日誌條目，
而不需要傳送這些日誌條目給 leader。這意味著日誌條目的傳送是單向的，只從 leader 傳給 follower，
並且 leader 從不會覆蓋自身本地日誌中已經存在的條目。

Raft 使用投票的過程來阻止 candidate 贏得選舉，除非它的日誌包含所有已提交的條目。candidate 為了被選舉必須聯繫集群中的大部分節點，這意味著每個被提交的日誌在這些服務上至少存在一個節點上。
如果 candidate 的日誌至少與大多數日誌中的任何其他日誌一樣最新（“最新” 的定義在下面），那麼它一定保存了所有已提交的日誌。

RequestVote RPC實現的限制：RPC 會包含關於 candidate 的日誌信息，如果 voter 自己的日誌比 candidate 的日誌更新，
那麼 vote 會拒絕投票。

Raft 通過比較最後一個日誌的 index 以及 term 來決定兩個日誌中的那個是最新的。
如果最後一條日誌的 term 不同，則更大的那份就是更新的。
如果日誌有相同的 term，那麼哪個日誌長（日志數組的長度？還是 index 的大小？），哪個就是最新的。

Committing entries from previous terms#

如Log replication介紹的那樣，
只要日誌被存儲到大多數節點中，leader 就知道這條日誌是可以在當前 term 內被提交的。
如果 leader 在提交日誌之前崩潰了，未來的 leader 將會嘗試完成這條日誌的複製。
然而，leader 不能立即推斷出在前一 term 的日誌在保存到大多數伺服器上時就一定被提交了。
圖 8 說明了一種情況：一條已經被存儲到大多數節點上的老日誌條目，也依然有可能會被未來的領導者覆蓋掉。

為了消除圖 8 中的問題，Raft 永遠不使用通過計算副本數量的方式去提交前一 term 的日誌。
只有 leader 當前 term 內的日誌條目才會通過計算副本數量的方式來提交；
一旦當前 term 的日誌以這種方式提交，那麼由於Log Matching則之前的所有日誌條目也被間接提交。
在某些情況下，leader 能安全的知道一個老的日誌是否已經被提交（例如，該日誌是否存儲到伺服器上），
但是 Raft 為了簡化問題使用了一種更加保守的方法。

當 leader 複製之前任期裡的日誌時，Raft 會為所有日誌保留原始的任期號，這在提交規則上產生了額外的複雜性。
在其他的共識算法中，如果一個新的 leader 要重新複製之前的任期裡的日誌時，它必須使用當前新的任期號。
Raft 使用的方法更加容易辨別出日誌，因為它可以隨著時間和日誌的變化對日誌維護著同一個任期編號。
另外，和其他的算法相比，Raft 中的 new leader 只需要發送更少日誌條目（
其他算法中必須在他們被提交之前發送更多的冗餘日誌條目來為他們重新編號）。
但是，這在實踐中可能並不十分重要，因為領導者更換很少會發生。

Follower and candidate crashes#

如果 follower 或者 candidate 崩潰了，那麼後續發給他們的 RPC 都會失敗。
Raft 的處理方式就是無限重試，如果後續它們恢復了，這些請求就會成功。
如果一個節點在接收了一個 RPC 請求後，但是還沒有響應的時候崩潰了，那麼它在恢復的時候會再次收到同樣的請求。
Raft 的 RPC 都是幂等的，所以重試不會造成任何問題。
如果一個 follower 收到AppendEntries RPC中包含已經存在的日誌，那麼它會直接忽略這個新的請求。

Timing and availability#

Raft 的要求之一就是安全性不能依賴時間：整個系統不能因為某些事件運行的比預期快一點或者慢一點就產生了錯誤的結果。
但是，可用性（系統可以及時的響應客戶端）不可避免的要依賴於時間。
例如，如果消息交換比伺服器故障間隔時間長，候選人將沒有足夠長的時間來贏得選舉；沒有一個穩定的領導人，Raft 將無法工作。

領導人選舉是 Raft 中對時間要求最為關鍵的方面。Raft 可以選舉並維持一個穩定的領導人，只要系統滿足下面的時間要求：

{{< center >}}
broadcastTime ≪ electionTimeout ≪ MTBF（平均故障時間）
{{< /center >}}

  1. broadcastTime: 從一個伺服器並行的發送 RPC 給集群中的其他伺服器並接收響應的平均時間
  2. electionTimeout: 選舉超時時間
  3. MTBF: 對一台伺服器而言，兩次故障之間的平均時間

broadcastTime 必須比 electionTimeout 小一個數量級才能夠發送穩定的心跳消息來阻止 follower 進入選舉狀態。
通過隨機生成的 electionTimeout，這個不等式使得 split vote 的情況變為不可能。
electionTimeout 應該比 MTBF 小上幾個數量級，這樣系統才能穩定的運行。
當 leader 崩潰後，整個系統會在一個 electionTimeout 內不可用，我們希望這種情況在整個系統的運行中很少出現。

broadcastTime 和 MTBF 是由系統決定的，但是 electionTimeout 是我們自己選擇的。Raft 的 RPCs 需要接收方將信息持久化的保存到穩定存儲中去，
所以 broadcastTime 大約是 0.5 毫秒到 20 毫秒，取決於存儲的技術。
因此，electionTimeout 可能需要在 10 毫秒到 500 毫秒之間。大多數的伺服器的 MTBF 都在幾個月甚至更長，很容易滿足時間的需求。

Cluster membership changes#

Links#

  1. 項目地址: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
  2. Raft 官網: https://raft.github.io/
  3. GFS 相關資料: https://fzdwx.github.io/posts/2022-10-07-gfs/#links
  4. Raft paper: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
  5. Raft paper 中文翻譯: https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
  6. Diagram of Raft interactions： https://pdos.csail.mit.edu/6.824/notes/raft_diagram.pdf
  7. Students guid to Raft: https://thesquareplanet.com/blog/students-guide-to-raft/
  8. Raft locking: https://pdos.csail.mit.edu/6.824/labs/raft-locking.txt
  9. Raft structure: https://pdos.csail.mit.edu/6.824/labs/raft-structure.txt
  10. Paxos Replicated State Machines as the Basis of a High-Performance Data
    Store https://static.usenix.org/event/nsdi11/tech/full_papers/Bolosky.pdf
  11. TiKV 對於 Raft 優化 https://cn.pingcap.com/blog/optimizing-raft-in-tikv
  12. https://www.cnblogs.com/niejunlei/p/9719557.html
  13. https://blog.csdn.net/viskaz/article/details/124232474
  14. https://www.cnblogs.com/brianleelxt/p/13251540.html
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。