介紹

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

筏日志概述

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

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

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

需要注意的是，Raft Log 的索引從 1 開(kāi)始，只有 Leader 節(jié)點(diǎn)才能創(chuàng)建 Raft Log 并將其復(fù)制到 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í)，它被視為已應(yīng)用。

etcd 的 raft 實(shí)現(xiàn)概述

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)絡(luò)傳輸、磁盤存儲(chǔ)以及Raft流程中涉及的其他組件（盡管etcd提供了默認(rèn)實(shí)現(xiàn)）。

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

在etcd raft的代碼實(shí)現(xiàn)中，這種交互模型與Go獨(dú)特的通道特性無(wú)縫結(jié)合，使得etcd raft庫(kù)真正與眾不同。

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

日志和 log_unstable

在etcd raft中，Raft Log的主要實(shí)現(xiàn)位于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接口訪問(wèn)節(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)自客戶端的請(qǐng)求時(shí)，它會(huì)使用其 Term 創(chuàng)建一個(gè)日志條目并將其附加到不穩(wěn)定日志中。
• 已提交：在Raft論文中稱為commitIndex，它表示最后一個(gè)已知已提交日志條目的索引。
• 正在應(yīng)用：當(dāng)前正在應(yīng)用的日志條目的最高索引。
• applied:在Raft論文中被稱為lastApplied，它是已經(jīng)應(yīng)用到狀態(tài)機(jī)的日志條目的最高索引。

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

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

• entries： 未持久化的日志條目，作為切片存儲(chǔ)在內(nèi)存中。
• offset: 用于將entries中的日志條目映射到Raft Log，其中entries[i] = Raft Log[i offset]。
• offsetInProgress: 表示當(dāng)前正在持久化的條目。正在進(jìn)行的條目由條目[:offsetInProgress-offset]表示。

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

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

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)

由于我們只關(guān)注 Raft 日志處理邏輯，所以這里的“何時(shí)交互”是指 etcd raft 何時(shí)傳遞需要用戶持久化的日志條目。

用戶端

etcd raft 主要通過(guò) Node 接口中的方法與用戶交互。 Ready 方法返回一個(gè)通道，允許用戶從 etcd raft 接收數(shù)據(jù)或指令。

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

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

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

• 條目： 需要持久化的日志條目。一旦這些條目被持久化，就可以使用存儲(chǔ)接口檢索它們。
• ComfilledEntries： 需要應(yīng)用于狀態(tài)機(jī)的日志條目。

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

處理完Ready傳遞過(guò)來(lái)的日志、消息等數(shù)據(jù)后，我們可以調(diào)用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)體中的數(shù)據(jù)。在 etcd raft 方面，重點(diǎn)是確定何時(shí)將 Ready 結(jié)構(gòu)傳遞給用戶以及之后要采取的操作。

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

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

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

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

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

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

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

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

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

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

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

在 etcd raft 中調(diào)用 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)提交并應(yīng)用了三個(gè)日志條目，因此已提交和已應(yīng)用的日志條目都設(shè)置為 3。applying 字段保存前一個(gè)應(yīng)用程序的最高日志條目的索引，在本例中也是 3。

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

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

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

如圖所示，附加的日志條目存儲(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 的目的是創(chuàng)建要返回給用戶的 Ready 結(jié)構(gòu)體。由于我們有兩個(gè)未持久化的日志條目，readyWithoutAccept 會(huì)將這兩個(gè)日志條目包含在返回的 Ready 的 Entries 字段中。

接受準(zhǔn)備

acceptReady 在 Ready 結(jié)構(gòu)傳遞給用戶后被調(diào)用。

acceptReady 將正在持久化的日志條目的索引更新為 6，這意味著 [4, 6) 范圍內(nèi)的日志條目現(xiàn)在被標(biāo)記為正在持久化。

進(jìn)步

用戶將Entries持久化為Ready后，調(diào)用Node.Advance來(lái)通知etcd raft。然后，etcd raft 就可以執(zhí)行在acceptReady 中創(chuàng)建的“回調(diào)”了。

這個(gè)“回調(diào)”會(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è)到是否存在已提交但尚未應(yīng)用的日志條目，因此返回 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)記為已應(yīng)用于狀態(tài)機(jī)。

進(jìn)步

用戶調(diào)用 Node.Advance 后，etcd raft 執(zhí)行“回調(diào)”并將更新應(yīng)用于 5，表明索引 5 及之前的日志條目已全部應(yīng)用于狀態(tài)機(jī)。

最終狀態(tài)

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

概括

我們首先概述了 Raft Log，了解其基本概念，然后初步了解了 etcd raft 實(shí)現(xiàn)。然后我們深入研究了 etcd raft 中 Raft Log 的核心模塊，并考慮了重要的問(wèn)題。最后，我們通過(guò)對(duì)寫(xiě)入請(qǐng)求流的完整分析將所有內(nèi)容聯(lián)系在一起。

我希望這種方法可以幫助您清楚地了解 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í)現(xiàn)：深入研究 Raft 日志的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！