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

作者：屈鵬

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

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

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

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

struct Node {
    // 持有一個(gè) RawNode 實(shí)例
    raft_group: Option>,
    // 接收其他節(jié)點(diǎn)發(fā)來(lái)的 Raft 消息
    my_mailbox: Receiver,
    // 發(fā)送 Raft 消息給其他節(jié)點(diǎn)
    mailboxes: HashMap>,
}
let mut t = Instant::now();
// 在 Node 實(shí)例上運(yùn)行一個(gè)循環(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 庫(kù)與應(yīng)用交互的主要界面。要在自己的應(yīng)用中使用 raft-rs，首先就需要持有一個(gè) RawNode 實(shí)例，正如 Node 結(jié)構(gòu)體所做的那樣。

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

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

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

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

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

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

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

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

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

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

這個(gè)接口返回一個(gè) 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...
}

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

對(duì)照 examples/five_mem_node/main.rs 中的示例，可以知道應(yīng)用程序在 propose 一個(gè)消息之后，應(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……對(duì)于 propose 過(guò)程而言，當(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 方法中。在下一次這個(gè) Raft 節(jié)點(diǎn)調(diào)用 RawNode::ready 時(shí)，便可以取出這部分被確認(rèn)的消息，并應(yīng)用到狀態(tài)機(jī)中了。

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

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

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

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