摘要：作者屈鵬本文為源碼解析系列的第二篇，按照計劃首先將為大家介紹依賴的周邊庫。值得注意的是，這個中并不包括持久化，也不會將應(yīng)用到應(yīng)用程序自己的狀態(tài)機(jī)的接口。在下一次這個節(jié)點(diǎn)調(diào)用時，便可以取出這部分被確認(rèn)的消息，并應(yīng)用到狀態(tài)機(jī)中了。

作者：屈鵬

本文為 TiKV 源碼解析系列的第二篇，按照計劃首先將為大家介紹 TiKV 依賴的周邊庫 raft-rs 。raft-rs 是 Raft 算法的 Rust 語言實(shí)現(xiàn)。Raft 是分布式領(lǐng)域中應(yīng)用非常廣泛的一種共識算法，相比于此類算法的鼻祖 Paxos，具有更簡單、更容易理解和實(shí)現(xiàn)的特點(diǎn)。

分布式系統(tǒng)的共識算法會將數(shù)據(jù)的寫入復(fù)制到多個副本，從而在網(wǎng)絡(luò)隔離或節(jié)點(diǎn)失敗的時候仍然提供可用性。具體到 Raft 算法中，發(fā)起一個讀寫請求稱為一次 proposal。本文將以 raft-rs 的公共 API 作為切入點(diǎn)，介紹一般 proposal 過程的實(shí)現(xiàn)原理，讓用戶可以深刻理解并掌握 raft-rs API 的使用， 以便用戶開發(fā)自己的分布式應(yīng)用，或者優(yōu)化、定制 TiKV。

文中引用的代碼片段的完整實(shí)現(xiàn)可以參見 raft-rs 倉庫中的 source-code 分支。

倉庫中的 examples/five_mem_node/main.rs 文件是一個包含了主要 API 用法的簡單示例。它創(chuàng)建了一個 5 節(jié)點(diǎn)的 Raft 系統(tǒng)，并進(jìn)行了 100 個 proposal 的請求和提交。經(jīng)過進(jìn)一步精簡之后，主要的類型封裝和運(yùn)行邏輯如下：

struct Node {
    // 持有一個 RawNode 實(shí)例
    raft_group: Option>,
    // 接收其他節(jié)點(diǎn)發(fā)來的 Raft 消息
    my_mailbox: Receiver,
    // 發(fā)送 Raft 消息給其他節(jié)點(diǎn)
    mailboxes: HashMap>,
}
let mut t = Instant::now();
// 在 Node 實(shí)例上運(yùn)行一個循環(huán)，周期性地處理 Raft 消息、tick 和 Ready。
loop {
    thread::sleep(Duration::from_millis(10));
    while let Ok(msg) = node.my_mailbox.try_recv() {
        // 處理收到的 Raft 消息
        node.step(msg); 
    }
    let raft_group = match node.raft_group.as_mut().unwrap();
    if t.elapsed() >= Duration::from_millis(100) {
        raft_group.tick();
        t = Instant::now();
    }
    // 處理 Raft 產(chǎn)生的 Ready，并將處理進(jìn)度更新回 Raft 中
    let mut ready = raft_group.ready();
    persist(ready.entries());  // 處理剛剛收到的 Raft Log
    send_all(ready.messages);  // 將 Raft 產(chǎn)生的消息發(fā)送給其他節(jié)點(diǎn)
    handle_committed_entries(ready.committed_entries.take());
    raft_group.advance(ready);
}

這段代碼中值得注意的地方是：

RawNode 是 raft-rs 庫與應(yīng)用交互的主要界面。要在自己的應(yīng)用中使用 raft-rs，首先就需要持有一個 RawNode 實(shí)例，正如 Node 結(jié)構(gòu)體所做的那樣。

RawNode 的范型參數(shù)是一個滿足 Storage 約束的類型，可以認(rèn)為是一個存儲了 Raft Log 的存儲引擎，示例中使用的是 MemStorage。

在收到 Raft 消息之后，調(diào)用 RawNode::step 方法來處理這條消息。

每隔一段時間（稱為一個 tick），調(diào)用 RawNode::tick 方法使 Raft 的邏輯時鐘前進(jìn)一步。

使用 RawNode::ready 接口從 Raft 中獲取收到的最新日志（Ready::entries），已經(jīng)提交的日志（Ready::committed_entries），以及需要發(fā)送給其他節(jié)點(diǎn)的消息等內(nèi)容。

在確保一個 Ready 中的所有進(jìn)度被正確處理完成之后，調(diào)用 RawNode::advance 接口。

接下來的幾節(jié)將展開詳細(xì)描述。

Raft 算法中的日志復(fù)制部分抽象了一個可以不斷追加寫入新日志的持久化數(shù)組，這一數(shù)組在 raft-rs 中即對應(yīng) Storage。使用一個表格可以直觀地展示這個 trait 的各個方法分別可以從這個持久化數(shù)組中獲取哪些信息：

值得注意的是，這個 Storage 中并不包括持久化 Raft Log，也不會將 Raft Log 應(yīng)用到應(yīng)用程序自己的狀態(tài)機(jī)的接口。這些內(nèi)容需要應(yīng)用程序自行處理。

這個接口處理從該 Raft group 中其他節(jié)點(diǎn)收到的消息。比如，當(dāng) Follower 收到 Leader 發(fā)來的日志時，需要把日志存儲起來并回復(fù)相應(yīng)的 ACK；或者當(dāng)節(jié)點(diǎn)收到 term 更高的選舉消息時，應(yīng)該進(jìn)入選舉狀態(tài)并回復(fù)自己的投票。這個接口和它調(diào)用的子函數(shù)的詳細(xì)邏輯幾乎涵蓋了 Raft 協(xié)議的全部內(nèi)容，代碼較多，因此這里僅闡述在 Leader 上發(fā)生的日志復(fù)制過程。

當(dāng)應(yīng)用程序希望向 Raft 系統(tǒng)提交一個寫入時，需要在 Leader 上調(diào)用 RawNode::propose 方法，后者就會調(diào)用 RawNode::step，而參數(shù)是一個類型為 MessageType::MsgPropose 的消息；應(yīng)用程序要寫入的內(nèi)容被封裝到了這個消息中。對于這一消息類型，后續(xù)會調(diào)用 Raft::step_leader 函數(shù)，將這個消息作為一個 Raft Log 暫存起來，同時廣播到 Follower 的信箱中。到這一步，propose 的過程就可以返回了，注意，此時這個 Raft Log 并沒有持久化，同時廣播給 Follower 的 MsgAppend 消息也并未真正發(fā)出去。應(yīng)用程序需要設(shè)法將這個寫入掛起，等到從 Raft 中獲知這個寫入已經(jīng)被集群中的過半成員確認(rèn)之后，再向這個寫入的發(fā)起者返回寫入成功的響應(yīng)。那么， 如何能夠讓 Raft 把消息真正發(fā)出去，并接收 Follower 的確認(rèn)呢？

這個接口返回一個 Ready 結(jié)構(gòu)體：

pub struct Ready {
    pub committed_entries: Option>,
    pub messages: Vec,
    // some other fields...
}
impl Ready {
    pub fn entries(&self) -> &[Entry] {
        &self.entries
    }
    // some other methods...
}

一些暫時無關(guān)的字段和方法已經(jīng)略去，在 propose 過程中主要用到的方法和字段分別是：

對照 examples/five_mem_node/main.rs 中的示例，可以知道應(yīng)用程序在 propose 一個消息之后，應(yīng)該調(diào)用 RawNode::ready 并在返回的 Ready 上繼續(xù)進(jìn)行處理：包括持久化 Raft Log，將 Raft 消息發(fā)送到網(wǎng)絡(luò)上等。

而在 Follower 上，也不斷運(yùn)行著示例代碼中與 Leader 相同的循環(huán)：接收 Raft 消息，從 Ready 中收集回復(fù)并發(fā)回給 Leader……對于 propose 過程而言，當(dāng) Leader 收到了足夠的確認(rèn)這一 Raft Log 的回復(fù)，便能夠認(rèn)為這一 Raft Log 已經(jīng)被確認(rèn)了，這一邏輯體現(xiàn)在 Raft::handle_append_response 之后的 Raft::maybe_commit 方法中。在下一次這個 Raft 節(jié)點(diǎn)調(diào)用 RawNode::ready 時，便可以取出這部分被確認(rèn)的消息，并應(yīng)用到狀態(tài)機(jī)中了。

在將一個 Ready 結(jié)構(gòu)體中的內(nèi)容處理完成之后，應(yīng)用程序即可調(diào)用這個方法更新 Raft 中的一些進(jìn)度，包括 last index、commit index 和 apply index 等。

這是本文最后要介紹的一個接口，它的作用是驅(qū)動 Raft 內(nèi)部的邏輯時鐘前進(jìn)，并對超時進(jìn)行處理。比如對于 Follower 而言，如果它在 tick 的時候發(fā)現(xiàn) Leader 已經(jīng)失聯(lián)很久了，便會發(fā)起一次選舉；而 Leader 為了避免自己被取代，也會在一個更短的超時之后給 Follower 發(fā)送心跳。值得注意的是，tick 也是會產(chǎn)生 Raft 消息的，為了使這部分 Raft 消息能夠及時發(fā)送出去，在應(yīng)用程序的每一輪循環(huán)中一般應(yīng)該先處理 tick，然后處理 Ready，正如示例程序中所做的那樣。

最后用一張圖展示在 Leader 上是通過哪些 API 進(jìn)行 propose 的：

本期關(guān)于 raft-rs 的源碼解析就到此結(jié)束了，我們非常鼓勵大家在自己的分布式應(yīng)用中嘗試 raft-rs 這個庫，同時提出寶貴的意見和建議。后續(xù)關(guān)于 raft-rs 我們還會深入介紹 Configuration Change 和 Snapshot 的實(shí)現(xiàn)與優(yōu)化等內(nèi)容，展示更深入的設(shè)計原理、更詳細(xì)的優(yōu)化細(xì)節(jié)，方便大家分析定位 raft-rs 和 TiKV 使用中的潛在問題。