學習分享｜Etcd-Raft 原理篇

本文是根據近期對 Etcd-Raft 的學習把自己的理解做個簡單整理和分享。

近期負責的項目中有一個場景需要依賴數據一致性算法，因此做了一些相關的調研。本文是根據近期對【Etcd-Raft】的學習把自己的理解做個簡單整理和分享。

注：本文並沒有對 Etcd/Raft 源碼和流程事無鉅細的解剖，更多地關注其核心功能以及過程中個人覺得值得學習的點。

前言





文章主要講解 etcd/raft——原理解析篇。

一、原理解析

1. 最小原則

etcd 中實現的 raft 實現本質上是提供了一個基於 raft 的 sdk，作爲 sdk 方式接入到 etcd 中，和 etcd 存儲系統是解耦的。同時 sdk 的實現非常巧妙，只實現了基本的功能，包括 leader 選舉、日誌處理、狀態變更等邏輯。上層的網絡傳輸、數據存儲等模塊，提供接口由上層應用者來實現：

簡單畫個圖來表達這種設計：

我暫且把這種設計原則稱之爲 “最小原則”，sdk 中只實現基本的核心功能，sdk 依賴的其他能力只定義好接口，通過參數或者其他的方式進行注入。

（後續的開發中可以借鑑這種思想，不一定大而全的 sdk 實現就是好用的，可能反而會冗餘或者互相依賴等，當然也要分具體的場景具體分析）

2. 核心功能

一條數據提交到 raft 集羣后，etcd/raft 內部保證數據在集羣各節點是一致的，其實現流程如下：

整個 etcd/raft 可以抽象概括爲 2 大模塊：

下面分別針對這兩大功能結合代碼做詳細介紹。

2.1. 日誌複製模塊

type raftLog struct {
  // storage存儲了從最後一次snapshot到現在的所有可靠的（stable）日誌（Entry),即保存到snapshot之後提交的數據，
    // 同時Storage定義爲接口，由上層使用者實現和維護的，raft需要訪問的時候直接讀取無需訪問上層持久化的存儲。
  storage Storage
  // 用於保存還沒有持久化的數據和快照，與storage形成了鮮明的對比，使用者沒有通知raft日誌持久化完畢前，這些日誌都還不可靠
    // 當使用者持久化完畢後，這些日誌就會從unstable刪除，最終都會保存到storage中
  unstable unstable
  // committed保存是寫入持久化存儲storage中的最高index，
    // 這裏提交索引是集羣的一個狀態，而不是某一節點的狀態，它是由leader統計出來的，並廣播給所有的節點。
  committed uint64
  // 已經提交的日誌要被使用者應用，applied就是該節點已經被應用的最大索引
  // 一條日誌首先要提交成功（即committed），才能被applied到狀態機中因此以下不等式一直成立：applied <= committed
  applied uint64
  logger Logger
}
type unstable struct {
  snapshot *pb.Snapshot // 保存還沒有持久化的快照數據
  entries []pb.Entry    // 還未持久化的日誌提交粒度的數據
  offset  uint64        // offset保存的爲entries數組中的數據的起始index
  logger Logger
}

raftLog 是節點上用來存儲日誌的結構，按照是否已持久化到穩定存儲，可分爲兩部分：已持久化到穩定存儲的部分（stable）和還未持久化到穩定存儲的部分（unstable）

對於 unstable，按照代碼邏輯推斷 (並不是 100% 確定)：快照和 entrise 數據不會同時存在，快照只會在啓動時進行快照數據恢復時存在，當應用層使用快照數據進行恢復之後，raft 切換爲可以接收日誌數據的狀態，後續的日誌數據都會寫到 entrise 數組中了，而兩者的分界線就是 offset 變量。

一條提交的日誌會首先寫入到 unstable 中，因爲 unstable 爲非未持久化數據的緩衝區，因此這其中的數據可能會發生回滾（rollback）現象，具體實現爲

func (u *unstable) truncateAndAppend(ents []pb.Entry) {
  // 先拿到這些數據的第一個索引
  after := ents[0].Index
  switch {
  case after == u.offset+uint64(len(u.entries)):
    // 如果正好是緊接着當前數據的，就直接append
    u.entries = append(u.entries, ents...)
  case after <= u.offset:
    // 如果比當前偏移量小，那用新的數據替換當前數據，需要同時更改offset和entries
    u.offset = after
    u.entries = ents
  default:
    // 到了這裏，說明 u.offset < after < u.offset+uint64(len(u.entries))
    // 那麼新的entries需要拼接而成
    u.entries = append([]pb.Entry{}, u.slice(u.offset, after)...)
    u.entries = append(u.entries, ents...)
  }
}

對於 Storage，前文提到 raft 中有個基於內存的實現 MemoryStorage，同時使用者可以在應用層自定義實現持久化存儲。Storage 的接口以及 MemoryStorage 的具體實現如下，MemoryStorage 增加了藍色部分的對數據的寫操作實現，這些都會在上層應用層用到，而 Raft 庫僅僅需要讀操作即可。

Storage 接口定義的是持久化存儲，之所以 etcd 使用了基於內存的 MemoryStorage，是因爲 etcd 在寫入 MemoryStorage 前，需要先寫入預寫日誌（Write Ahead Log，WAL）或快照。而預寫日誌和快照是保存在穩定存儲中的。這樣，在每次重啓時，etcd 可以基於保存在穩定存儲中的快照和預寫日誌恢復 MemoryStorage 的狀態。也就是說，etcd 的穩定存儲是通過快照、預寫日誌、MemoryStorage 三者共同實現的。

a. 首先，raft 庫會首先將日誌數據寫入 未持久化數據緩衝區。

b. 由於 未持久化數據緩衝區 中有新增的數據，會通過 Ready 結構體通知給應用層。

c. 應用層收到 Ready 結構體之後，將其中的數據寫入 WAL 持久化存儲，然後更新這塊數據到 ` 已持久化數據緩衝區

e. 持久化完畢之後，除了通知刪除 未持久化數據緩衝區，還講數據通過網絡同步給集羣中其他節點。

對於存儲結構 raftLog、storage 和 unstable 等和相關的代碼函數細節這裏不再展開解析，感興趣的可以通過最後給的地址去翻閱，整體上這塊實現不算複雜。

在 etcd-raft 中，tracker 是 raft 代碼目錄下單獨的一個包，核心實現就包括一個 ProgressTracker。

瞭解核心類是 ProgressTracker 之前，需要先看其變量 Progress，根據註釋不難理解，Leader 節點除了要維護未持久化緩衝區之外，還需要維護一個數據結構，用於保存集羣中其他節點的進度，簡稱 Progress，簡單描述就是作爲集羣的 leader，需要知道其他節點日誌同步的具體情況。

其結構定義解釋如下：

type Progress struct {
  // Next保存的是下一次leader發送append消息時傳送過來的日誌索引
  // 當選舉出新的leader時，首先初始化Next爲該leader最後一條日誌+1
  // 如果向該節點append日誌失敗，則遞減Next回退日誌，一直回退到索引匹配爲止
  // Match保存在該節點上保存的日誌的最大索引，初始化爲0
  // 正常情況下，Next = Match + 1
  // 以下情況下不是上面這種情況：
  // 1. 切換到Probe狀態時，如果上一個狀態是Snapshot狀態，即正在接收快照，那麼Next = max(pr.Match+1, pendingSnapshot+1)
  // 2. 當該follower不在Replicate狀態時，說明不是正常的接收副本狀態。
  //    此時當leader與follower同步leader上的日誌時，可能出現覆蓋的情況，即此時follower上面假設Match爲3，但是索引爲3的數據會被
  //    leader覆蓋，此時Next指針可能會一直回溯到與leader上日誌匹配的位置，再開始正常同步日誌，此時也會出現Next != Match + 1的情況出現
  Match, Next uint64
  // 三種狀態
  // ProgressStateProbe：探測狀17
  // ProgressStateReplicate：副本狀態
  // ProgressStateSnapshot：快照狀態
  State ProgressStateType
    // 探測狀態時纔有用，表示探測消息是否已經發送了，如果發送了就不會再發了，避免不必要的IO。
  ProbeSent bool
  // 如果向該節點發送快照消息，PendingSnapshot用於保存快照消息的索引
  // 當PendingSnapshot不爲0時，該節點也被標記爲暫停狀態。
  // raft只有在這個正在進行中的快照同步失敗以後，纔會重傳快照消息
  PendingSnapshot uint64
  // 如果進程最近處於活躍狀態則爲 true（收到來自跟隨者的任意消息都認爲是活動狀態）。在超時後會重置重置爲false
  RecentActive bool
  // 用於實現滑動窗口，用來做流量控制，後邊會展開單獨作爲一個額外福利介紹
  Inflights *Inflights
}

瞭解完 Progress 後會發現 ProgressTracker 就是 Progress 的一個管理器，其整體實現比較簡單本文不再介紹。

總結來說，Progress 結構體做的工作：

  1. 維護 follower 節點的 match、next 索引，(0, Next) 的日誌已經發送給節點了，(0,Match] 是節點的已經接收到的日誌。

  2. 維護着 follower 節點當前的狀態 3 中狀態，不同的狀態，其會採取不同的行爲：



  1. 流量控制 Inflights，避免 follower 節點超載

Inflights 主要用於 StateReplicate 狀態下在日誌複製時可以控制數據傳輸速度，具體大小用戶可以在應用層指定。設計上非常的巧妙，其思想類似於 “往池子注水和放水” 的過程，通過給定池子的大小控制流速。而 raft 在實現上沒有使用 queue，而是在一個內存塊上採用循環方式模擬 queue 的特性，這樣效率會更高。

2.2. 選主模塊

對於選舉算法有很多實現，我之前開發中也實現過一個 raft 選舉算法傳送門，一般節點包含三種不同的角色 candidate、follower、leader。每種角色對不同類型的日誌數據需要有不同的處理，這裏選主流程不展開，本節的目的主要在於發現 etcd/raft 中我理解與衆不同的地方。

在 etcd/raft 的實現中，巧妙之處在於針對三種不同的角色，通過修改函數指針的方式在切換了不同角色時的處理，大概意思如下圖所示：

也就是說在於其很好地剝離了各模塊的職責。在 etcd/raft 的實現中，raft 結構體是一個 Raft 狀態機，其通過 Step 方法進行狀態轉移。只要涉及到 Raft 狀態機的狀態轉移，最終都會通過 Step 方法完成。可能我也解釋的不是很到位，具體可以看下代碼實現：

//Step爲節點收到應用層發來的消息，就會執行對應邏輯
func (r *raft) Step(m pb.Message) error {
    //...
    switch m.Type {
        case pb.MsgHup: //準備選舉時觸發
        //...
        case pb.MsgVote, pb.MsgPreVote: //在選舉中觸發
        //...
        default:
            r.step(r, m)
    }
}

Step 其實就是根據消息類型的不同（MsgHup/MsgVote/MsgPreVote）而去執行對應的邏輯（狀態機）。而對於其他狀態，此時則會執行 default 中的 step（函數指針，根據節點角色執行不同的函數 stepLeader/stepFollower/stepCandidate）

對其他執行選擇的流程，本文不再介紹。

2.3. 變更模塊

etcd/raft 採用將修改集羣配置的命令放在日誌條目中來處理，也就是一個配置變更其實是一次日誌數據的提交，不過是一種特殊類型的日誌這樣做的好處是：

成員刪減：操作作爲日誌的特殊類型，當可以進行 commit 的情況下，各個節點拿出該消息進行節點內部的成員刪減操作。

leader 轉讓：

二、總結思考

參考文檔：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/sSZ6v-k81QtwfoalLhuYDw

猜你喜歡