介紹

本文將從Raft共識(shí)演算法中的日誌開(kāi)始，並介紹分析etcd的Raft中Raft Log模組的設(shè)計(jì)與實(shí)作。目的是幫助讀者更好地理解etcd的Raft實(shí)現(xiàn)，並為實(shí)現(xiàn)類(lèi)似場(chǎng)景提供一個(gè)可能的方法。

筏日誌概述

Raft 共識(shí)演算法本質(zhì)上是一個(gè)複製狀態(tài)機(jī)，其目標(biāo)是在伺服器叢集中以相同的方式複製一系列日誌。這些日誌使叢集中的伺服器能夠達(dá)到一致的狀態(tài)。

在這種情況下，日誌指的是Raft Log。叢集中的每個(gè)節(jié)點(diǎn)都有自己的Raft Log，Raft Log由一系列日誌條目組成。日誌條目通常包含三個(gè)欄位：

• 索引：日誌條目的索引
• 任期：建立日誌條目時(shí)領(lǐng)導(dǎo)者的任期
• 資料：日誌條目中包含的數(shù)據(jù)，可以是特定的命令等

要注意的是，Raft Log 的索引從 1 開(kāi)始，只有 Leader 節(jié)點(diǎn)才能建立 Raft Log 並將其複製到 Follower 節(jié)點(diǎn)。

當(dāng)日誌條目持久儲(chǔ)存在叢集中的大多數(shù)節(jié)點(diǎn)（例如 2/3、3/5、4/7）上時(shí)，它被視為已提交。

當(dāng)日誌條目應(yīng)用於狀態(tài)機(jī)時(shí)，它被視為已套用。

etcd 的 raft 實(shí)作概述

etcd raft 是一個(gè)用 Go 編寫(xiě)的 Raft 演算法庫(kù)，廣泛應(yīng)用於 etcd、Kubernetes、CockroachDB 等系統(tǒng)。

etcd raft 的首要特點(diǎn)是它只實(shí)現(xiàn)了 Raft 演算法的核心部分。使用者必須自行實(shí)現(xiàn)網(wǎng)路傳輸、磁碟儲(chǔ)存以及Raft流程中涉及的其他元件（儘管etcd提供了預(yù)設(shè)實(shí)作）。

與 etcd raft 函式庫(kù)的互動(dòng)有些簡(jiǎn)單：它告訴您哪些資料需要持久化以及哪些訊息需要傳送到其他節(jié)點(diǎn)。您的責(zé)任是處理儲(chǔ)存和網(wǎng)路傳輸過(guò)程並相應(yīng)地通知它。它不關(guān)心如何實(shí)現(xiàn)這些操作的細(xì)節(jié)；它只是處理您提交的數(shù)據(jù)，並根據(jù) Raft 演算法告訴您接下來(lái)的步驟。

在etcd raft的程式碼實(shí)作中，這種互動(dòng)模型與Go獨(dú)特的通道特性無(wú)縫結(jié)合，使得etcd raft函式庫(kù)真正與眾不同。

如何實(shí)現(xiàn)Raft日誌

日誌和 log_unstable

在etcd raft中，Raft Log的主要實(shí)作位於log.go和log_unstable.go檔案中，主要結(jié)構(gòu)是raftLog和unstable。不穩(wěn)定結(jié)構(gòu)也是 raftLog 中的一個(gè)領(lǐng)域。

• raftLog負(fù)責(zé)Raft Log的主要邏輯。它可以透過(guò)提供給使用者的Storage介面存取節(jié)點(diǎn)的日誌儲(chǔ)存狀態(tài)。
• 不穩(wěn)定，顧名思義，包含尚未持久化的日誌條目，即未提交的日誌。

etcd raft透過(guò)協(xié)調(diào)raftLog和unstable來(lái)管理演算法內(nèi)的日誌。

raftLog和unstable的核心字段

為了簡(jiǎn)化討論，本文將只關(guān)注日誌條目的處理邏輯，而不涉及 etcd raft 中的快照處理。

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

raftLog的核心欄位：

• storage：使用者實(shí)現(xiàn)的儲(chǔ)存接口，用於檢索已經(jīng)持久化的日誌條目。
• 不穩(wěn)定：儲(chǔ)存未持久化的日誌。例如，當(dāng) Leader 收到來(lái)自客戶(hù)端的請(qǐng)求時(shí)，它會(huì)使用其 Term 建立日誌條目並將其附加到不穩(wěn)定日誌中。
• 已提交：在Raft論文中稱(chēng)為commitIndex，它表示最後一個(gè)已知已提交日誌條目的索引。
• 正在套用：目前正在套用的日誌條目的最高索引。
• applied:在Raft論文中被稱(chēng)為lastApplied，它是已經(jīng)應(yīng)用到狀態(tài)機(jī)的日誌條目的最高索引。

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

unstable 的核心領(lǐng)域：

• entries： 未持久化的日誌條目，作為切片儲(chǔ)存在記憶體中。
• offset: 用於將entries中的日誌條目對(duì)應(yīng)到Raft Log，其中entries[i] = Raft Log[i offset]。
• offsetInProgress: 表示目前正在持久化的條目。正在進(jìn)行的條目由條目[:offsetInProgress-offset]表示。

raftLog 中的核心欄位很簡(jiǎn)單，可以輕鬆地與 Raft 論文中的實(shí)作相關(guān)聯(lián)。然而，unstable 中的欄位可能看起來(lái)更抽象。以下範(fàn)例旨在幫助闡明這些概念。

假設(shè)我們的 Raft 日誌中已經(jīng)儲(chǔ)存了 5 個(gè)日誌條目?，F(xiàn)在，我們?cè)趗nstable中儲(chǔ)存了3個(gè)日誌條目，而這3個(gè)日誌條目目前正在持久化。情況如下圖：

offset=6表示unstable.entries中位置0、1、2的日誌條目分別對(duì)應(yīng)實(shí)際Raft Log中的位置6（0 6）、7（1 6）、8（2 6）。當(dāng)offsetInProgress=9時(shí)，我們知道unstable.entries[:9-6]，包括位置0、1和2的三個(gè)日誌條目，都被持久化了。

在unstable中使用offset和offsetInProgress的原因是unstable並沒(méi)有儲(chǔ)存所有的Raft Log條目。

何時(shí)互動(dòng)

由於我們只專(zhuān)注於 Raft 日誌處理邏輯，所以這裡的「何時(shí)互動(dòng)」是指 etcd raft 何時(shí)傳遞需要使用者持久化的日誌條目。

使用者端

etcd raft 主要透過(guò) Node 介面中的方法與使用者互動(dòng)。 Ready 方法傳回一個(gè)通道，讓使用者可以從 etcd raft 接收資料或指令。

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

從此通道接收的 Ready 結(jié)構(gòu)包含需要處理的日誌條目、應(yīng)傳送到其他節(jié)點(diǎn)的訊息、節(jié)點(diǎn)的目前狀態(tài)等等。

對(duì)於Raft Log的討論，我們只需要關(guān)注Entries和ComfilledEntries欄位：

• 條目： 需要持久化的日誌條目。一旦這些條目被持久化，就可以使用儲(chǔ)存介面檢索它們。
• ComfilledEntries： 需要套用於狀態(tài)機(jī)的日誌項(xiàng)目。

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

處理完Ready傳遞過(guò)來(lái)的日誌、訊息等資料後，我們可以呼叫Node介面中的Advance方法來(lái)通知etcd raft我們已經(jīng)完成了它的指令，讓它可以接收並處理下一個(gè)Ready。

etcd raft 提供了 AsyncStorageWrites 選項(xiàng)，可在一定程度上增強(qiáng)節(jié)點(diǎn)效能。然而，我們?cè)谶@裡不考慮這個(gè)選項(xiàng)。

etcd 筏側(cè)

在使用者端，重點(diǎn)是處理接收到的 Ready 結(jié)構(gòu)體中的資料。在 etcd raft 方面，重點(diǎn)是確定何時(shí)將 Ready 結(jié)構(gòu)傳遞給使用者以及之後要採(cǎi)取的操作。

我在下圖中總結(jié)了這個(gè)過(guò)程中涉及到的主要方法，圖中展示了方法調(diào)用的大致順序（注意，這僅代表大概的調(diào)用順序）：

可以看到整個(gè)過(guò)程是一個(gè)循環(huán)。這裡我們先概述一下這些方法的大致功能，在後續(xù)的寫(xiě)流分析中，我們會(huì)深入研究這些方法是如何作用於raftLog和unstable等核心欄位的。

• HasReady： 顧名思義，它檢查是否有一個(gè) Ready 結(jié)構(gòu)體需要傳遞給使用者。例如，如果unstable中有未持久化的日誌條目目前不在持久化過(guò)程中，HasReady將傳回true。
• readyWithoutAccept: HasReady 傳回 true 後調(diào)用，該方法會(huì)建立要傳回給使用者的 Ready 結(jié)構(gòu)體，包括需要持久化的日誌條目和標(biāo)記為已提交的日誌條目。
• acceptReady: 在etcd raft 將readyWithoutAccept 建立的Ready 結(jié)構(gòu)傳遞給使用者後呼叫。它將Ready傳回的日誌條目標(biāo)記為正在持久化和應(yīng)用，並建立一個(gè)“回調(diào)”，當(dāng)使用者調(diào)用Node.Advance時(shí)調(diào)用，將日誌條目標(biāo)記為已持久化和應(yīng)用。
• Advance： 在使用者呼叫 Node.Advance 後執(zhí)行在 AcceptReady 中建立的「回呼」。

如何定義承諾和應(yīng)用

這裡有兩點(diǎn)要考慮：

1。堅(jiān)持≠承諾

如最初所定義的，只有當(dāng)日誌條目被 Raft 叢集中的大多數(shù)節(jié)點(diǎn)持久化時(shí)，該日誌條目才被視為已提交。因此，即使我們透過(guò) Ready 持久化 etcd raft 傳回的條目，這些條目仍然無(wú)法被標(biāo)記為已提交。

但是，當(dāng)我們呼叫 Advance 方法通知 etcd raft 我們已經(jīng)完成持久化步驟時(shí)，etcd raft 將評(píng)估叢集中其他節(jié)點(diǎn)的持久化狀態(tài)，並將一些日誌條目標(biāo)記為已提交。然後，這些條目透過(guò) Ready 結(jié)構(gòu)的 CommiedEntries 欄位提供給我們，以便我們可以將它們套用到狀態(tài)機(jī)。

因此，在使用 etcd raft 時(shí)，將條目標(biāo)記為已提交的時(shí)間由內(nèi)部管理，使用者只需滿(mǎn)足持久性先決條件即可。

內(nèi)部透過(guò)呼叫 raftLog.commitTo 方法實(shí)現(xiàn)承諾，該方法會(huì)更新 raftLog.comfilled，對(duì)應(yīng) Raft 論文中的 commitIndex。

2。承諾≠應(yīng)用

在 etcd raft 中呼叫 raftLog.commitTo 方法後，直到 raft.comfilled 索引的日誌條目都被視為已提交。然而，索引在lastApplied

將條目標(biāo)記為已應(yīng)用的時(shí)間也在 etcd raft 內(nèi)部處理；使用者只需要將Ready中提交的條目應(yīng)用到狀態(tài)機(jī)即可。

另一個(gè)微妙之處是，在 Raft 中，只有 Leader 可以提交條目，但所有節(jié)點(diǎn)都可以應(yīng)用它們。

寫(xiě)入請(qǐng)求處理流程

在這裡，我們將透過(guò)分析 etcd raft 處理寫(xiě)入請(qǐng)求時(shí)的流程來(lái)連接先前討論的所有概念。

初始狀態(tài)

為了討論更一般的場(chǎng)景，我們將從一個(gè) 已經(jīng)提交並應(yīng)用了三個(gè)日誌條目的 Raft 日誌開(kāi)始。

圖中，綠色代表raftLog欄位和儲(chǔ)存在Storage中的日誌條目，而紅色代表不穩(wěn)定欄位和儲(chǔ)存在entry中的未持久化日誌條目。

由於我們已經(jīng)提交並套用了三個(gè)日誌條目，因此已提交和已套用的日誌條目都設(shè)定為 3。 applying 欄位保存前一個(gè)應(yīng)用程式的最高日誌條目的索引，在本例中也是 3。

此時(shí)，還沒(méi)有發(fā)起任何請(qǐng)求，因此unstable.entries為空。 Raft Log 中的下一個(gè)日誌索引是 4，偏移量為 4。由於目前沒(méi)有日誌被持久化，所以 offsetInProgress 也設(shè)定為 4。

發(fā)出請(qǐng)求

現(xiàn)在，我們發(fā)起一個(gè)請(qǐng)求，將兩個(gè)日誌條目追加到 Raft Log 中。

如圖所示，附加的日誌條目?jī)?chǔ)存在unstable.entries中。在此階段，核心欄位中記錄的索引值不會(huì)發(fā)生任何變更。

已準(zhǔn)備好

還記得HasReady方法嗎？ HasReady 檢查是否有未持久化的日誌條目，如果有，則傳回 true。

判斷是否存在未持久化日誌條目的邏輯是基於unstable.entries[offsetInProgress-offset:]的長(zhǎng)度是否大於0。顯然，在我們的例子中：

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

表示有兩個(gè)未持久化的日誌條目，因此 HasReady 傳回 true。

準(zhǔn)備好但不接受

readyWithoutAccept 的目的是建立要回傳給使用者的 Ready 結(jié)構(gòu)體。由於我們有兩個(gè)未持久化的日誌條目，readyWithoutAccept 會(huì)將這兩個(gè)日誌條目包含在傳回的 Ready 的 Entries 欄位中。

接受準(zhǔn)備

acceptReady 在 Ready 結(jié)構(gòu)傳遞給使用者後被呼叫。

acceptReady 將正在持久化的日誌條目的索引更新為 6，這表示 [4, 6) 範(fàn)圍內(nèi)的日誌條目現(xiàn)在被標(biāo)記為正在持久化。

進(jìn)步

使用者將Entries持久化為Ready後，呼叫Node.Advance來(lái)通知etcd raft。然後，etcd raft 就可以執(zhí)行在acceptReady 中建立的「回呼」了。

這個(gè)「回呼」會(huì)清除unstable.entries中已經(jīng)持久化的日誌條目，然後將偏移量設(shè)為Storage.LastIndex 1，即6。

提交日誌條目

我們假設(shè)這兩個(gè)日誌條目已經(jīng)被 Raft 叢集中的大多數(shù)節(jié)點(diǎn)持久化，因此我們可以將這兩個(gè)日誌條目標(biāo)記為已提交。

已準(zhǔn)備好

繼續(xù)我們的循環(huán)，HasReady 偵測(cè)到是否存在已提交但尚未套用的日誌條目，因此傳回 true。

準(zhǔn)備好但不接受

readyWithoutAccept 傳回一個(gè) Ready，其中包含已提交但尚未應(yīng)用於狀態(tài)機(jī)的日誌條目 (4, 5)。

這些條目的計(jì)算方式為：低、高：= 在左開(kāi)、右閉區(qū)間內(nèi)應(yīng)用 1、提交 1。

接受準(zhǔn)備

acceptReady 然後將 Ready 中傳回的日誌條目 [4, 5] 標(biāo)記為已套用於狀態(tài)機(jī)。

進(jìn)步

使用者呼叫 Node.Advance 後，etcd raft 執(zhí)行「回呼」並將更新應(yīng)用於 5，表示索引 5 及先前的日誌項(xiàng)目已全部應(yīng)用於狀態(tài)機(jī)。

最終狀態(tài)

這樣就完成了寫(xiě)入請(qǐng)求的處理流程。最終狀態(tài)如下圖，可以和初始狀態(tài)進(jìn)行比較。

概括

我們首先概述了 Raft Log，了解其基本概念，然後初步了解了 etcd raft 實(shí)作。然後我們深入研究了 etcd raft 中 Raft Log 的核心模組，並考慮了重要的問(wèn)題。最後，我們透過(guò)對(duì)寫(xiě)入請(qǐng)求流的完整分析將所有內(nèi)容連結(jié)在一起。

我希望這種方法可以幫助您清楚地了解 etcd Raft 實(shí)現(xiàn)，並形成您自己對(duì) Raft Log 的見(jiàn)解。

本文到此結(jié)束。如有錯(cuò)誤或疑問(wèn)，歡迎私訊或留言。

順便說(shuō)一句，raft-foiver 是我實(shí)現(xiàn)的 etcd raft 的簡(jiǎn)化版本，保留了 Raft 的所有核心邏輯，並根據(jù) Raft 論文中的流程進(jìn)行了優(yōu)化。以後我會(huì)單獨(dú)發(fā)一篇文章介紹這個(gè)函式庫(kù)。如果你有興趣，請(qǐng)隨時(shí) Star、Fork 或 PR！

參考

• https://github.com/B1NARY-GR0UP/raft
• https://github.com/etcd-io/raft

以上是了解 etcd 的 Raft 實(shí)作：深入研究 Raft 日誌的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！