技術文章 » 實現 Raft 協定

實現 Raft 協定

2023-12-19 18:01:14

文章地址

簡介

Raft 是一個分散式共識演演算法，用於保證所有機器對一件事達成一個看法。本文用於記錄實現 Raft 選舉和紀錄檔複製的程式碼細節。

選舉

節點啟動時首先是跟隨者狀態，如果到達選舉超時時間就嘗試選舉，為了預防對稱網路分割區帶來的任期不斷增加問題，需要使用預投票機制。

選舉超時時間：跟隨者在這段時間內沒有搜到領導者的訊息，就觸發選舉超時，轉變為候選者開始競選

對稱網路分割區：以 3 臺機器為例，其中一臺機器與另外兩臺機器（這兩臺中有一個領導者）的網路隔離開了，此時跟隨者會觸發選舉超時，導致其不斷增加任期，在網路恢復正常時，領導者會因任期小而下線，叢集因此觸發重新選舉

預投票機制：觸發選舉超時先詢問其他節點是否同意當前節點進行投票，當多數節點同意時再進行投票，即正式投票

上面介紹了選舉需要注意的問題，下面說具體流程。

  1. 節點啟動時開啟一個選舉超時時間檢測定時任務，用於在當前節點是跟隨者時不斷檢測是否發生了選舉超時，發生超時就開始競選。每一次定時任務的觸發時間都是變化的，以防止所有節點一起選舉，所有人都不投票後死迴圈。
  2. 任務內容：如果當前節點不是跟隨者或選舉超時時間內收到了來自領導者的訊息就跳過這輪檢測，否則就代表領導者可能下線了，開始競選。
  3. 競選的第一階段是預投票：發起預投票 RPC，內容有想競選的任期以及當前的最新紀錄檔的任期和索引，如果只有少數節點同意投票就結束這輪任務，否則開始正式投票，RPC 內容與上次相同，但這次需要改變當前節點任期號為想競選的任期號了，同時也要更改狀態為候選者，如果只有少數節點同意投票就結束這輪任務（同時回滾狀態為跟隨者），否則就更改狀態成為領導者，開始傳送心跳等等（成為領導者的一些事後面再說）。

到這裡跟隨者如何選舉成為候選者以及領導者就大致完成了，還缺少其他節點如何處理投票請求：

  1. 請求的任期比當前節點小就拒絕。
  2. 領導者有效（選舉超時時間內有收到了心跳）就拒接。
  3. 該任期已經投過票就拒絕。
  4. 最新的本地紀錄檔任期大就拒絕，紀錄檔任期相同但本地最新紀錄檔的索引更大也拒絕。

如果上面 4 個條件全通過就投票。投票過程中還有一些節點狀態的變更處理，比如收到正式投票的任期比當前節點任期大需要轉變為跟隨者等等，當然這些不算是重點。

紀錄檔複製

紀錄檔複製是 Raft 的核心，這裡涉及到狀態機的執行，也就是共識的關鍵，比較複雜。

在完成選舉後叢集有了領導者，由領導者負責與使用者端溝通，在領導者收到使用者端請求時，領導者將這條待狀態機執行的命令和當前任期組合成一條紀錄檔寫入本地磁碟，並向其他節點傳送該條紀錄檔，如果多數節點都表示收到了，也就表明達成共識了，那麼領導者就會將這個命令放到狀態機中執行，那麼什麼時候叢集中的其他跟隨者節點的狀態機執行該條紀錄檔的命令呢？答案是由定時的心跳負責，每次心跳都會攜帶領導者狀態機最後執行的紀錄檔索引，當跟隨者收到後就會將當前節點狀態機最後執行的紀錄檔索引和心跳中領導者的紀錄檔索引之間的紀錄檔放到狀態機中執行，也就是說紀錄檔中命令的執行是一個二階段的過程。

選舉中我們忽略了一個地方，就是成為領導者後需要詢問叢集的節點紀錄檔複製情況，以此來將當前領導者多的紀錄檔複製到其他跟隨者，大概過程如下：領導者拿著最新紀錄檔的任期和索引和跟隨者對比，如果相同，等著領導者新的紀錄檔複製就行了，如果不同，說明這個紀錄檔是髒的（紀錄檔沒被複制給大多數），此時領導者拿著該條紀錄檔的前一條紀錄檔繼續對比，直到相同，然後領導者將相同的紀錄檔之後的所有紀錄檔複製給跟隨者，跟隨者將相同紀錄檔後的紀錄檔都刪掉，再追加上領導者發來的紀錄檔，這樣跟隨者的紀錄檔就正確了。跟隨者與領導者紀錄檔的對齊後就可以等待領導者發心跳了（即通知跟隨者將哪些紀錄檔放到狀態機中執行）。

關於狀態機執行紀錄檔還有很重要的一點，就是節點需不需要儲存當前狀態機執行過的最後一條紀錄檔的索引，比如機器重啟了，從頭執行所有紀錄檔對狀態機有沒有影響。可以思考下，如果是一個 KV 資料庫狀態機，不儲存也沒問題，因為紀錄檔不管從哪裡執行，資料庫中的資料也不會變，但如果是 id 生成器，就會出現多執行一次 id 就會變化，多執行很多次甚至可能出現 id 分配完無法繼續分配的問題，所以命令執行多次有問題就需要儲存，並且需要滿足儲存執行過的索引和執行狀態機命令是一個原子性的操作。

讀請求優化（讀索引讀）

紀錄檔複製是需要刷盤的，這個操作非常耗時，寫請求只能通過領導者進行紀錄檔複製處理，但讀請求不同，可以像 ReentrantReadWriteLock 讀寫鎖一樣，將讀請求負載到跟隨者上，也就是實現跨機器的 volatile 語意（和跨程序類似），即讀跟隨者時確保跟隨者的狀態機已經和領導者的狀態機一樣，具體過程如下：跟隨者收到讀請求，跟隨者請求領導者同步紀錄檔以及狀態機應該執行到那條紀錄檔，領導者收到請求後向所有的節點發一個 RPC 確認領導者地位（防止領導者所在的少部分節點分割區後還能正常讀），確認後同步紀錄檔並回復該跟隨者，收到回覆後的跟隨者的狀態機再執行讀命令。

對於領導者的讀請求同樣也不需要走紀錄檔複製，只需要和其他跟隨者確認自己的領導者地位就可以執行讀命令了。

最後

coding 時要注意節點任期的變化，剛開始可以先用一個全域性鎖來回避這個問題，等後面到一定的複雜程度再細化鎖。完整的 Raft 還需要考慮很多，比如快照、批次、pipeline、刪減節點等等。最後貼上我的實現 raft/README.md 以及相關學習資料：