文章地址

簡介

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 以及相關學習資料：

• Raft 入門動畫

• 可視化的 Raft

• 剖析-sofajraft-實現原理

• MIT 6.824 2020 Raft 實現細節備忘 | 木鳥雜記 (qtmuniao.com)

• Raft算法之日志復制 - 觸不可及` - 博客園 (cnblogs.com)

• SOFAJRaft 源碼分析二（日志復制、心跳） - 個人文章 - SegmentFault 思否

• 關于 DDIA 上對 Raft 協議的這種極端場景的描述，要如何理解？ - 知乎 (zhihu.com)

• 為什么 Raft 的 ApplyIndex 和 CommitIndex 不需要持久化？ - 知乎 (zhihu.com)

• stateIs0/lu-raft-kv: this is raft java project. raft-kv-storage (github.com)

• wenweihu86/raft-java: Raft Java implementation which is simple and easy to understand. (github.com)

總結

以上是生活随笔為你收集整理的实现 Raft 协议的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。