分布式存儲之 Raft概述介紹

分布式一致性是分布式系統(tǒng)中最基本的問題，用來保證分布式系統(tǒng)的高可靠。業(yè)界也有很多分布式一致性復(fù)制協(xié)議：Paxos、Zab、Viewstamped Replication、Raft 等。Raft 相比于其他共識算法簡化了協(xié)議中的狀態(tài)以及交互，更加清晰也更加容易理解實(shí)現(xiàn)。

1. Raft 概述

Raft 節(jié)點(diǎn)有 3 種角色：

Leader ：處理客戶端讀寫、復(fù)制 Log 給 Follower 等；

Candidate ：競選新的 Leader（由 Follower 超時轉(zhuǎn)換得來）；

Follower ：不發(fā)送任何請求，完全被動響應(yīng) Leader、Candidate 的 RPC。

Raft 信息有 3 種 RPC：

RequestVote RPC ：由 Candidate 發(fā)出，用于發(fā)送投票請求；

AppendEntries (Heartbeat) RPC ：由 Leader 發(fā)出，用于 Leader 向 Followers 復(fù)制日志條目，也會用作 Heartbea（日志條目為空即為 Heartbeat）；

InstallSnapshot RPC ：由 Leader 發(fā)出，用于快照傳輸。雖然多數(shù)情況都是每個服務(wù)器獨(dú)立創(chuàng)建快照，但是 Leader 有時候必須發(fā)送快照給一些落后太多的 Follower，這通常發(fā)生在 Leader 已經(jīng)丟棄了下一條要發(fā)給該 Follower 的日志條目（Log 壓縮時清除掉了的情況）。

1.1 Leader 選舉

Raft 將時間劃分為一個個的任期（Term），TermID 單調(diào)遞增，每個 Term 最多只有一個 Leader。

Candidate 先將本地的 currentTerm++，然后向其他節(jié)點(diǎn)發(fā)送 RequestVote 請求。其他節(jié)點(diǎn)根據(jù)本地數(shù)據(jù)版本、長度和之前選主的結(jié)果判斷應(yīng)答成功與否。具體處理規(guī)則如下：

如果 Time.Now() – lastLeaderUpdateTimestamp < electionTimeout，忽略請求；

如果 req.term < currentTerm，忽略請求；

如果 req.term > currentTerm，設(shè)置 currentTerm = req.term。如果是 Leader 和 Candidate 轉(zhuǎn)為 Follower；

如果 req.term == currentTerm，并且本地 voteFor 記錄為空或者是與 vote 請求中 term 和 CandidateId 一致，req.lastLogIndex > lastLogIndex，即 Candidate 數(shù)據(jù)新于本地則同意選主請求；

如果 req.term == currentTerm，如果本地 voteFor 記錄非空或者是與 vote 請求中 term 一致 CandidateId 不一致，則拒絕選主請求；

如果 req.term == currentTerm，如果 lastLogTerm > req.lastLogTerm，本地最后一條 Log 的 Term 大于請求中的 lastLogTerm，說明 candidate上數(shù)據(jù)比本地舊，拒絕選主請求。

currentTerm 只是用于忽略老的 Term 的 vote 請求，或者提升自己的 currentTerm，并不參與 Log 新舊的決策。Log 新舊的比較，是基于 lastLogTerm 和 lastLogIndex 進(jìn)行比較，而不是基于 currentTerm 和 lastLogIndex 進(jìn)行比較。

關(guān)于選舉有兩個很重要的隨機(jī)超時時間：心跳超時、選舉超時。

心跳超時 ：Leader 周期性的向 Follower 發(fā)送心跳（0.5ms – 20ms）。如果 Follower 在選舉超時時間內(nèi)沒有收到心跳，則觸發(fā)選舉；

選舉超時 ：如果存在兩個或者多個節(jié)點(diǎn)選主，都沒有拿到大多數(shù)節(jié)點(diǎn)的應(yīng)答，需要重新選舉。Raft 引入隨機(jī)的選舉超時時間（150ms – 300ms），避免選主活鎖。

心跳超時要小于選舉超時一個量級，Leader 才能夠發(fā)送穩(wěn)定的心跳消息來阻止 Follower 開始進(jìn)入選舉狀態(tài)?？梢栽O(shè)置：心跳超時=peers max RTT(round-trip time)，選舉超時=10 * 心跳超時。

1.2 Log 復(fù)制

大致流程是：更新操作通過 Leade r寫入 Log，復(fù)制到多數(shù)節(jié)點(diǎn)，變?yōu)?Committed，再 Apply 業(yè)務(wù)狀態(tài)機(jī)。

Leader 首先要把這個指令追加到 log 中形成一個新的 entry；

然后通過 AppendEntries RPC 并行地把該 entry 發(fā)給其他 servers；

其他 server 如果發(fā)現(xiàn)沒問題，復(fù)制成功后會給 Leader 一個表示成功的 ACK；

Leader 收到大多數(shù) ACK 后 Apply 該日志，返回客戶端執(zhí)行結(jié)果。

如果 Followers crash 或者丟包，Leader 會不斷重試 AppendEntries RPC。

Raft 要求所有的日志不允許出現(xiàn)空洞；

Raft 的日志都是順序提交的，不允許亂序提交；

Leader 不會覆蓋和刪除自己的日志，只會 Append；

Follower 可能會截斷自己的日志。存在臟數(shù)據(jù)的情況；

Committed 的日志最終肯定會被 Apply；

Snapshot 中的數(shù)據(jù)一定是 Applied，那么肯定是 Committed 的；

commitIndex、lastApplied 不會被所有節(jié)點(diǎn)持久化；

Leader 通過提交一條 Noop 日志來確定 commitIndex；

每個節(jié)點(diǎn)重啟之后，先加載上一個 Snapshot，再加入 RAFT 復(fù)制組。

每個 log entry 都存儲著一條用于狀態(tài)機(jī)的指令，同時保存著從 Leader 收到該 entry 時的 Term，此外還有 index 指明自己在 Log 中的位置?？梢员?Apply 的 entry 叫做 committed，一個 log entry 一旦復(fù)制給了大多數(shù)節(jié)點(diǎn)就成為 committed，committed 的 log 最終肯定會被 Apply。

如果當(dāng)前待提交 entry 之前有未提交的 entry，即使是以前過時的 leader 創(chuàng)建的，只要滿足已存儲在大多數(shù)節(jié)點(diǎn)上就一次性按順序都提交。

1.3 Log 恢復(fù)

Log Recovery 分為 currentTerm 修復(fù)和 prevTerm 修復(fù)。Log Recovery 就是要保證一定已經(jīng) Committed 的數(shù)據(jù)不會丟失，未 Committed 的數(shù)據(jù)轉(zhuǎn)變?yōu)?Committed，但不會因?yàn)樾迯?fù)過程中斷又重啟而影響節(jié)點(diǎn)之間一致性。

currentTerm 修復(fù)主要是解決某些 Follower 節(jié)點(diǎn)重啟加入集群，或者是新增 Follower 節(jié)點(diǎn)加入集群，Leader 需要向 Follower 節(jié)點(diǎn)傳輸漏掉的 Log Entry。如果 Follower 需要的 Log Entry 已經(jīng)在 Leader上Log Compaction 清除掉了，Leader 需要將上一個 Snapshot 和其后的 Log Entry 傳輸給 Follower 節(jié)點(diǎn)。Leader-Alive 模式下，只要 Leader 將某一條 Log Entry 復(fù)制到多數(shù)節(jié)點(diǎn)上，Log Entry 就轉(zhuǎn)變?yōu)?Committed。

prevTerm 修復(fù)主要是在保證Leader切換前后數(shù)據(jù)的一致性。通過上面 RAFT 的選主可以看出，每次選舉出來的 Leader 一定包含已經(jīng) committed 的數(shù)據(jù)（抽屜原理，選舉出來的 Leader 是多數(shù)中數(shù)據(jù)最新的，一定包含已經(jīng)在多數(shù)節(jié)點(diǎn)上 commit 的數(shù)據(jù)）。新的 Leader 將會覆蓋其他節(jié)點(diǎn)上不一致的數(shù)據(jù)。雖然新選舉出來的 Leader 一定包括上一個 Term 的 Leader 已經(jīng) Committed 的 Log Entry，但是可能也包含上一個 Term 的 Leader 未 Committed 的 Log Entry。這部分 Log Entry 需要轉(zhuǎn)變?yōu)?Committed，即通過 Noop。

Leader 為每個 Follower 維護(hù)一個 nextId，標(biāo)識下一個要發(fā)送的 logIndex。Leader 通過回溯尋找 Follower 上最后一個 CommittedId，然后 Leader 發(fā)送其后的 LogEntry。

重新選取 Leader 之后，新的 Leader 沒有之前內(nèi)存中維護(hù)的 nextId，以本地 lastLogIndex+1 作為每個節(jié)點(diǎn)的 nextId。這樣根據(jù)節(jié)點(diǎn)的 AppendEntries 應(yīng)答可以調(diào)整 nextId：

local.nextIndex?=?max(min(local.nextIndex-1,?resp.LastLogIndex+1),?1)

1.4 Log 壓縮

在實(shí)際系統(tǒng)中，Log 會無限制增長，導(dǎo)致 Log 占用太多的磁盤空間，需要更長的啟動時間來加載，將會導(dǎo)致系統(tǒng)不可用。需要對日志做壓縮。

Snapshot 是 Log Compaction 的常用方法，將系統(tǒng)的全部狀態(tài)寫入一個 Snapshot 中，并持久化到一個可靠存儲系統(tǒng)中，完成 Snapshot 之后這個點(diǎn)之前的 Log 就可以被刪除了。

Leader、Follower 獨(dú)立地創(chuàng)建快照；

Follower 與 Leader 差距過大，則 InstallSnapshot，Leader chunk 發(fā)送 Snapshot 給 Follower；

Snapshot 中的數(shù)據(jù)一定是 Applied，那么肯定是 Committed 的；

Log 達(dá)到一定大小、數(shù)量、超過一定時間可以做 Snapshot。；

如果底層存儲支持 COW，則可以使用 COW 做 Snapshot，減小對 Log Append 的影響。

1.5 成員變更

當(dāng) Raft 集群進(jìn)行節(jié)點(diǎn)變更時，新加入的節(jié)點(diǎn)可能會因?yàn)樾枰ㄙM(fèi)很長時間同步 Log 而降低集群的可用性，導(dǎo)致集群無法 commit 新的請求。

假設(shè)原來集群有 3 個節(jié)點(diǎn)，可以容忍 3 - (3/2+1) = 11 個節(jié)點(diǎn)出錯，這時由于機(jī)器維修、增加副本解決熱點(diǎn)讀等原因又新加入了一個節(jié)點(diǎn)，這時也是可以容忍 4 - (4/2+1) = 11 個節(jié)點(diǎn)出錯，恰好原來的一個節(jié)點(diǎn)出錯了，此時雖然可以 commit 但是得等到新的節(jié)點(diǎn)完全追上 Leader 的日志才可以，而新節(jié)點(diǎn)追上 Leader 日志花費(fèi)的時間比較長，在這期間就沒法 commit，會降低系統(tǒng)的可用性。

為了避免這個問題，引入了節(jié)點(diǎn)的 Learner 狀態(tài)，當(dāng)集群成員變更時，新加入的節(jié)點(diǎn)為 Learner 狀態(tài)，Learner 狀態(tài)的節(jié)點(diǎn)不算在 Quorum 節(jié)點(diǎn)內(nèi)，不能參與投票；只有 Leader 確定這個 Learner 節(jié)點(diǎn)接收完了 Snapshot，可以正常同步 Log 了，才可能將其變成可以正常的節(jié)點(diǎn)。

1.6 安全性

Election Safety ：一個 Term 下最多只有一個 Leader；

Leader Append-Only ：Leader 不會覆蓋或者是刪除自己的 Entry，只會進(jìn)行 Append；

Log Matching ：如果兩個 Log 擁有相同的 Term 和 Index，那么給定 Index 之前的 LogEntry 都是相同的；

Leader Completeness ：如果一條 LogEntry 在某個 Term 下被 Commit 了，那么這條 LogEntry 必然存在于后面 Term 的 Leader 中；

State Machine Safety ：如果一個節(jié)點(diǎn)已經(jīng) Apply 了一條 LogEntry 到狀態(tài)機(jī)，那么其他節(jié)點(diǎn)不會向狀態(tài)機(jī)中 Apply 相同 Index 下的不同的 LogEntry。

基于 Spring Boot + MyBatis Plus + Vue & Element 實(shí)現(xiàn)的后臺管理系統(tǒng) + 用戶小程序，支持 RBAC 動態(tài)權(quán)限、多租戶、數(shù)據(jù)權(quán)限、工作流、三方登錄、支付、短信、商城等功能

項目地址：https://github.com/YunaiV/ruoyi-vue-pro

視頻教程：https://doc.iocoder.cn/video/

2. 功能完善

2.1 預(yù)選舉

預(yù)選舉（Pre-Vote）主要避免了網(wǎng)絡(luò)分區(qū)節(jié)點(diǎn)加入集群時，引起集群中斷服務(wù)的問題。

Follower 在轉(zhuǎn)變?yōu)?Candidate 之前，先與集群節(jié)點(diǎn)通信，獲得集群 Leader 是否存活的信息。如果當(dāng)前集群有 Leader 存活，F(xiàn)ollower 就不會轉(zhuǎn)變?yōu)?Candidate，也不會增加 Term，就不會引起 Leader StepDown，從而不會導(dǎo)致集群選主中斷服務(wù)。

2.2 Leader 轉(zhuǎn)移

Leader 轉(zhuǎn)移可以把當(dāng)前 Raft Group 中的 Leader 轉(zhuǎn)換給另一個 Follower，可用于負(fù)載均衡、重啟機(jī)器等。

在進(jìn)行 transfer leadership 時，先 block 當(dāng)前 Leader 的寫入，然后使 Transferee 節(jié)點(diǎn)日志達(dá)到 Leader 的最新狀態(tài)，進(jìn)而發(fā)送 TimeoutNow 請求，觸發(fā) Transferee 節(jié)點(diǎn)立即選主。

但是不能無限制的 block Leader 的寫入，會影響線上服務(wù)。通?？梢詾?transfer leadership 設(shè)置一個超時時間。超時之后如果發(fā)現(xiàn) Transferee 節(jié)點(diǎn) Term 沒有發(fā)生變化，說明 Transferee 節(jié)點(diǎn)沒有追上數(shù)據(jù)，沒有選主成功，transfer leadership 就失敗了。

2.3 網(wǎng)絡(luò)分區(qū)

網(wǎng)絡(luò)分區(qū)主要包含對稱網(wǎng)絡(luò)分區(qū)（Symmetric network partitioning）和非對稱網(wǎng)絡(luò)分區(qū)（Asymmetric network partitioning）。

對稱網(wǎng)絡(luò)分區(qū)

S1 為當(dāng)前 Leader，網(wǎng)絡(luò)分區(qū)造成 S2 和 S1、S3 心跳中斷。S2 既不會被選成 Leader，也不會收到 Leader 的消息，而是會一直不斷地發(fā)起選舉。Term 會不斷增大。為了避免網(wǎng)絡(luò)恢復(fù)后，S2 發(fā)起選舉導(dǎo)致正在工作的 Leader step-down，從而導(dǎo)致整個集群重新發(fā)起選舉，可以使用 pre-vote 來阻止對稱網(wǎng)絡(luò)分區(qū)節(jié)點(diǎn)在重新加入時，會中斷集群的問題。因?yàn)榘l(fā)生對稱網(wǎng)絡(luò)分區(qū)后的節(jié)點(diǎn)，pre-vote 不會成功，也就不會導(dǎo)致集群一段時間內(nèi)無法正常提供服務(wù)的問題。

非對稱網(wǎng)絡(luò)分區(qū)

S1、S2、S3 分別位于三個 IDC，其中 S1 和 S2 之間網(wǎng)絡(luò)不通，其他之間可以聯(lián)通。這樣一旦 S1 或者是 S2 搶到了 Leader，另外一方在超時之后就會觸發(fā)選主，例如 S1 為 Leader，S2 不斷超時觸發(fā)選主，S3 提升 Term 打斷當(dāng)前 Lease，從而拒絕 Leader 的更新。

可以增加一個 trick 的檢查，每個 Follower 維護(hù)一個時間戳記錄收到 Leader 上數(shù)據(jù)更新的時間，只有超過 ElectionTimeout 之后才允許接受 Vote 請求。這個類似 ZooKeeper 中只有 Candidate 才能發(fā)起和接受投票，就可以保證 S1 和 S3 能夠一直維持穩(wěn)定的 quorum 集合，S2 不能選主成功。

2.4 SetPeer

Raft 只能在多數(shù)節(jié)點(diǎn)存活的情況下才可以正常工作，在實(shí)際環(huán)境中可能會存在多數(shù)節(jié)點(diǎn)故障只存活一個節(jié)點(diǎn)的情況，這個時候需要提供服務(wù)并修復(fù)數(shù)據(jù)。因?yàn)橐呀?jīng)不能達(dá)到多數(shù)，不能寫入數(shù)據(jù)，也不能做正常的節(jié)點(diǎn)變更。Raft 庫需要提供一個 SetPeer 的接口，設(shè)置每個節(jié)點(diǎn)的復(fù)制組節(jié)點(diǎn)列表，便于故障恢復(fù)。

假設(shè)只有一個節(jié)點(diǎn) S1 存活的情況下，SetPeer 設(shè)置節(jié)點(diǎn)列表為 {S1}，這樣形成一個只有 S1 的節(jié)點(diǎn)列表，讓 S1 繼續(xù)提供讀寫服務(wù)，后續(xù)再調(diào)度其他節(jié)點(diǎn)進(jìn)行 AddPeer。通過強(qiáng)制修改節(jié)點(diǎn)列表，可以實(shí)現(xiàn)最大可用模式。

2.5 Noop

在分布式系統(tǒng)中，對于一個請求都有三種返回結(jié)果：成功、失敗、超時。

在 failover 時，新的 Leader 由于沒有持久化 commitIndex，所以并不清楚當(dāng)前日志的 commitIndex 在哪，也即不清楚 log entry 是 committed 還是 uncommitted 狀態(tài)。通常在成為新 Leader 時提交一條空的 log entry 來提交之前所有的 entry。

RAFT 中增加了一個約束：對于之前 Term 的未 Committed 數(shù)據(jù)，修復(fù)到多數(shù)節(jié)點(diǎn)，且在新的 Term 下至少有一條新的 Log Entry 被復(fù)制或修復(fù)到多數(shù)節(jié)點(diǎn)之后，才能認(rèn)為之前未 Committed 的 Log Entry 轉(zhuǎn)為 Committed。即最大化 commit 原則：Leader 在當(dāng)選后立即追加一條 Noop 并同步到多數(shù)節(jié)點(diǎn)，實(shí)現(xiàn)之前 Term uncommitted 的 entry 隱式 commit。

保證 commit 的數(shù)據(jù)不會丟。

保證不會讀到 uncommitted 的數(shù)據(jù)。

2.6 MultiRaft

元數(shù)據(jù)相比數(shù)據(jù)來說整體數(shù)據(jù)量要小的多，通常單臺機(jī)器就可以存儲。我們也通常借助于 Etcd 等使用單個 Raft Group 來進(jìn)行元數(shù)據(jù)的復(fù)制和管理。但是單個 Raft Group，存在以下兩點(diǎn)弊端：

集群的存儲容量受限于單機(jī)存儲容量（排除使用分布式存儲）；

集群的性能受限于單機(jī)性能（讀寫都由 Leader 處理）。

對于集群元數(shù)據(jù)來說使用單個 Raft Group 是夠了，但是如果想讓 Raft 用于數(shù)據(jù)的復(fù)制，那么必須得使用 MultiRaft，也即有多個復(fù)制組，類似于 Ceph 的 PG，每個 PG、Raft Group 是一個復(fù)制組。

但是 Raft Group 的每個副本間都會建立鏈接來保持心跳，如果多個 Raft Group 里的副本都建立鏈接的話，那么物理節(jié)點(diǎn)上的鏈接數(shù)就太多了，需要復(fù)用物理節(jié)點(diǎn)的鏈接。如下圖 cockroachdb multi raft 所示：

MultiRaft 還需要解決以下問題：

負(fù)載均衡 ：可以通過 Transfer Leadership 的功能保持每個物理節(jié)點(diǎn)上 Leader 個數(shù)大致相當(dāng)；

鏈接復(fù)用 ：一個物理節(jié)點(diǎn)上的所有 Raft Group 復(fù)用鏈接。會有心跳合并、Lease 共用等；

中心節(jié)點(diǎn) ：用來管理集群包括 MultiRaft，使用單個 Raft Group 做高可靠，類似 Ceph Mon。

基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 實(shí)現(xiàn)的后臺管理系統(tǒng) + 用戶小程序，支持 RBAC 動態(tài)權(quán)限、多租戶、數(shù)據(jù)權(quán)限、工作流、三方登錄、支付、短信、商城等功能

項目地址：https://github.com/YunaiV/yudao-cloud

視頻教程：https://doc.iocoder.cn/video/

3. 性能優(yōu)化

3.1 Batch

Batch 寫入落盤 ：對每一條 Log Entry 都進(jìn)行 fsync 刷盤效率會比較低，可以在內(nèi)存中緩存多個 Log Entry Batch 寫入磁盤，提高吞吐量，類似于 Ceph FileStore 批量寫 Journal；

Batch 網(wǎng)絡(luò)發(fā)送 ：Leader 也可以一次性收集多個 Log Entry，批量的發(fā)送給 Follower；

Batch Apply ：批量的 Apply 已經(jīng) commit Log 到業(yè)務(wù)狀態(tài)機(jī)。

Batch 并不會對請求做延遲來達(dá)到批量處理的目的，對單個請求的延遲沒有影響。

3.2 PipeLine

Raft 依賴 Leader 來保持集群的數(shù)據(jù)一致性，數(shù)據(jù)的復(fù)制都是從 Leader 到 Follower。一個簡單的寫入流程如下，性能是完全不行的：

Leader 收到 Client 請求；

Leader 將數(shù)據(jù) Append 到自己的 Log；

Leader 將數(shù)據(jù)發(fā)送給其他的 Follower；

Leader 等待 Follower ACK，大多數(shù)節(jié)點(diǎn)提交了 Log，則 Apply；

Leader 返回 Client 結(jié)果；

重復(fù)步驟 1。

Leader 跟其他節(jié)點(diǎn)之間的 Log 同步是串行 Batch 的方式，如果單純使用 Batch，每個Batch 發(fā)送之后 Leader 依舊需要等待該 Batch 同步完成之后才能繼續(xù)發(fā)送下一個 Batch，這樣會導(dǎo)致較長的延遲?？梢酝ㄟ^ Leader 跟其他節(jié)點(diǎn)之間的 PipeLine 復(fù)制來改進(jìn)，會有效降低延遲。

3.3 并行

順序提交

將 Leader Append 持久化日志和向 Followers 發(fā)送日志并行處理。Leader 只需要在內(nèi)存中保存未 Committed 的 Log Entry，在多數(shù)節(jié)點(diǎn)已經(jīng)應(yīng)答的情況下，無需等待 Leader 本地 IO 完成，直接將內(nèi)存中的 Log Entry 直接 Apply 給狀態(tài)機(jī)即可。

亂序提交

亂序提交要滿足以下兩點(diǎn)：

Log Entry 之間不存在覆蓋寫，則可以亂序 Commit、Apply；

Log Entry 之間存在覆蓋寫，不可以亂序，只能順序 Commit、Apply。

上層不同的應(yīng)用場景限制了提交的方式：

對 IO 保序要求比較嚴(yán)格，那么只能使用順序提交；

對 IO 保序沒有要求，可以 IO 亂序完成，那么可順序提交、亂序提交都可以使用。

不同的分布式存儲需要的提交方式：

分布式數(shù)據(jù)庫（亂序提交） ：其上層可串行化的事物就可以保證數(shù)據(jù)一致性，可以容忍底層 IO 亂序完成的情況；

分布式 KV 存儲（亂序提交） ：多個 KV 之間（排除上層應(yīng)用語義）本身并無相關(guān)性，也不需要 IO 保序，可以容忍 IO 亂序；

分布式對象存儲（亂序提交） ：本來就不保證同一對象的并發(fā)寫入一致性，那么底層也就沒必要順序接收順序完成 IO，天然容忍 IO 亂序；

分布式塊存儲（順序提交） ：由于在塊存儲上可以構(gòu)建不同的應(yīng)用，而不同的應(yīng)用對 IO 保序要求也不一樣，所以為了通用性只能順序提交；

分布式文件存儲（順序提交） ：由于可以基于文件存儲（POSIX 等接口）構(gòu)建不同的應(yīng)用，而不同的應(yīng)用對 IO 保序要求也不一樣，所以為了通用性只能順序提交，當(dāng)然特定場景下可以亂序提交，比如 PolarFS 適用于數(shù)據(jù)庫；

分布式存儲 ：具體能否亂序提交最終依賴于應(yīng)用語義能否容忍存儲 IO 亂序完成。

簡單分析

單個 Raft Group 只能順序提交日志，多個 Raft Group 之間雖然可以做到并行提交日志，但是受限于上層應(yīng)用（數(shù)據(jù)庫等）的跨 Group 分布式事物，可能導(dǎo)致其他不相關(guān)的分布式事物不能并行提交，只能順序提交。

上層應(yīng)用比如數(shù)據(jù)庫的分布式事物是跨 Group(A、B、C) 的，Group A 被阻塞了，分布式事務(wù)不能提交， 那么所有的參與者 Group(B、C) 就不能解鎖，進(jìn)而不能提交其他不相關(guān)的分布式事物，從而引發(fā)多個 Group 的鏈?zhǔn)椒磻?yīng)。

Raft 不適用于多連接的高并發(fā)環(huán)境中。Leader 和 Follower 維持多條連接的情況在生產(chǎn)環(huán)境也很常見，單條連接是有序的，多條連接并不能保證有序，有可能發(fā)送次序靠后的 Log Entry 先于發(fā)送次序靠前的 Log Entry 達(dá)到 Follower。但是 Raft 規(guī)定 Follower 必須按次序接受 Log Entry，就意味著即使發(fā)送次序靠后的 Log Entry 已經(jīng)寫入磁盤了（實(shí)際上不能落盤得等之前的 Log Entry 達(dá)到）也必須等到前面所有缺失的 Log Entry 達(dá)到后才能返回。如果這些 Log Entry 是業(yè)務(wù)邏輯順序無關(guān)的，那么等待之前未到達(dá)的 Log Entry 將會增加整體的延遲。

其實(shí) Raft 的日志復(fù)制和 Ceph 基于 PG Log 的復(fù)制一樣，都是順序提交的，雖然可以通過 Batch、PipeLine 優(yōu)化，但是在并發(fā)量大的情況下延遲和吞吐量仍然上不去。

具體 Raft 亂序提交的實(shí)現(xiàn)可參考：PolarFS: ParallelRaft

http://www.vldb.org/pvldb/vol11/p1849-cao.pdf

3.4 異步

我們知道被 committed 的日志肯定是可以被 Apply 的，在什么時候 Apply 都不會影響數(shù)據(jù)的一致性。所以在 Log Entry 被 committed 之后，可以異步的去 Apply 到業(yè)務(wù)狀態(tài)機(jī)，這樣就可以并行的 Append Log 和 Apply Log 了，提升系統(tǒng)的吞吐量。

其實(shí)就和 Ceph BlueStore 的 kv_sync_thread 和 kv_finalize_thread 一樣，每個線程都有其隊列。kv_sync_thread 去寫入元數(shù)據(jù)到 RocksDB（請求到此已經(jīng)成功），kv_finalize_thread 去異步的回調(diào)上層應(yīng)用通知請求成功。

3.5 ReadIndex

Raft 的寫入流程會走一遍 Raft，保證了數(shù)據(jù)的一致性。為了實(shí)現(xiàn)線性一致性讀，讀流程也可以走一遍 Raft，但是會產(chǎn)生磁盤 IO，性能不好。Leader 具有最新的數(shù)據(jù)，理論上 Leader 可以讀取到最新的數(shù)據(jù)。但是在網(wǎng)絡(luò)分區(qū)的情況下，無法確定當(dāng)前的 Leader 是不是真的 Leader，有可能當(dāng)前 Leader 與其他節(jié)點(diǎn)發(fā)生了網(wǎng)絡(luò)分區(qū)，其他節(jié)點(diǎn)形成了一個 Group 選舉了新的 Leader 并更新了一些數(shù)據(jù)，此時如果 Client 還從老的 Leader 讀取數(shù)據(jù)，便會產(chǎn)生 Stale Read。

讀流程走一遍 Raft、ReadIndex、Lease Read 都是用來實(shí)現(xiàn)線性一致性讀，避免 Stale Read。

當(dāng)收到讀請求時，Leader 先檢查自己是否在當(dāng)前 Term commit 過 entry，沒有否則直接返回；

然后，Leader 將自己當(dāng)前的 commitIndex 記錄到變量 ReadIndex 里面；

向 Follower 發(fā)起 Heartbeat，收到大多數(shù) ACK 說明自己還是 Leader；

Leader 等待 applyIndex >= ReadIndex，就可以提供線性一致性讀；

返回給狀態(tài)機(jī)，執(zhí)行讀操作返回結(jié)果給 Client。

線性一致性讀 ：在 T1 時刻寫入的值，在 T1 時刻之后肯定可以讀到。也即讀的數(shù)據(jù)必須是讀開始之后的某個值，不能是讀開始之前的某個值。不要求返回最新的值，返回時間大于讀開始的值就可以。

注意 ：在新 Leader 剛剛選舉出來 Noop 的 Entry 還沒有提交成功之前，是不能夠處理讀請求的，可以處理寫請求。也即需要步驟 1 來防止 Stale Read。

原因 ：在新 Leader 剛剛選舉出來 Noop 的 Entry 還沒有提交成功之前，這時候的 commitIndex 并不能夠保證是當(dāng)前整個系統(tǒng)最新的 commitIndex。

考慮這個情況 ：

w1->w2->w3->noop| commitIndex 在 w1；

w2、w3 對 w1 有更新；

應(yīng)該讀的值是 w3。

因?yàn)?commitIndex 之后可能還有 Log Entry 對該值更新，只要 w1Apply 到業(yè)務(wù)狀態(tài)機(jī)就可以滿足 applyIndex >= ReadIndex，此時就可以返回 w1 的值。但是此時 w2、w3 還未 Apply 到業(yè)務(wù)狀態(tài)機(jī)，就沒法返回 w3，就會產(chǎn)生 Stale Read。必須等到 Noop 執(zhí)行完才可以執(zhí)行讀，才可以避免 Stale Read。

3.6 Follower Read

如果是熱點(diǎn)數(shù)據(jù)么可以通過提供 Follower Read 來減輕 Leader 的讀壓力，可用非常方便的通過 ReadIndex 實(shí)現(xiàn)。

Follower 向 Leader 請求 ReadIndex；

Leader 執(zhí)行完 ReadIndex 章節(jié)的前 4 步（用來確定 Leader 是真正的 Leader）；

Leader 返回 commitIndex 給 Follower 作為 ReadIndex；

Follower 等待 applyIndex >= ReadIndex，就可以提供線性一致性讀；

返回給狀態(tài)機(jī)，執(zhí)行讀操作返回結(jié)果給 Client。

3.7 Lease Read

Lease Read 相比 ReadIndex 更進(jìn)一步，不僅省去了 Log ?的磁盤開銷，還省去了Heartbeat的網(wǎng)絡(luò)開銷，提升讀的性能。

基本思路

Leader 獲取一個比 election timeout 小的租期（Lease）。因?yàn)?Follower 至少在 election timeout 時間之后才會發(fā)送選舉，那么在 Lease 內(nèi)是不會進(jìn)行 Leader 選舉。就可以跳過 ReadIndex 心跳的環(huán)節(jié)，直接從 Leader 上讀取。但是 Lease Read 的正確性是和時間掛鉤的，如果時鐘漂移比較嚴(yán)重，那么 Lease Read 就會產(chǎn)生問題。

Leader 定時發(fā)送（心跳超時時間）Heartbeat 給 Follower， 并記錄時間點(diǎn) start；

如果大多數(shù)回應(yīng)，那么新的 Lease 到期時間為 start + Lease(

Leader 確認(rèn)自己是 Leader 后，等待 applyIndex >= ReadIndex，就可以提供線性一致性讀；

返回給狀態(tài)機(jī)，執(zhí)行讀操作返回結(jié)果給 Client。

3.8 Double Write-Store

我們知道 Raft 把數(shù)據(jù) Append 到自己的 Log 的同時發(fā)送請求給 Follower，多數(shù)回復(fù) ACK 就認(rèn)為 commit，就可以 Apply 到業(yè)務(wù)狀態(tài)機(jī)了。如果業(yè)務(wù)狀態(tài)機(jī)（分布式 KV、分布式對象存儲等）也把數(shù)據(jù)持久化存儲，那么數(shù)據(jù)便 Double Write-Store，集群中存在兩份相同的數(shù)據(jù)。如果是三副本，那么就會有 6 份。

接下來主要思考元數(shù)據(jù)、數(shù)據(jù)做的一點(diǎn)點(diǎn)優(yōu)化。

通常的一個優(yōu)化方式就是先把數(shù)據(jù)寫入 Journal（環(huán)形隊列、大小固定、空間連續(xù)、使用 3D XPoint、NVME），然后再把數(shù)據(jù)寫入內(nèi)存即可返回，最后異步的把數(shù)據(jù)刷入 HDD（最好帶有 NVME 緩存）。

元數(shù)據(jù)

元數(shù)據(jù)通常使用分布式 KV 存儲，數(shù)據(jù)量比較小，Double Write-Store 影響不是很大，即使存儲兩份也不會浪費(fèi)太多空間，而且以下改進(jìn)也相比數(shù)據(jù)方面的改進(jìn)更容易實(shí)現(xiàn)。

可以擼一個簡單的 Append-Only 的單機(jī)存儲引擎 WAL 來替代 RocksDB 作為 Raft Log 的存儲引擎，Apply 業(yè)務(wù)狀態(tài)機(jī)層的存儲引擎可以使用 RocksDB，但是可以關(guān)閉 RocksDB 的 WAL，因?yàn)閿?shù)據(jù)已經(jīng)存儲在 Append-Only 的 Raft Log 了，細(xì)節(jié)仍需考慮。

數(shù)據(jù)

這里的數(shù)據(jù)通常指非結(jié)構(gòu)化數(shù)據(jù)：圖片、文檔、音視頻等。非結(jié)構(gòu)化數(shù)據(jù)通常使用分布式對象存儲、塊存儲、文件存儲等來存儲，由于數(shù)據(jù)量比較大，Double Store 是不可接受的，大致有兩種思路去優(yōu)化：

Raft Log、User Data 分開存：Raft Log 只存 op-cmd，不存 data。類似于 Ceph 的 PG Log。

Raft Log、User Data 一起存：作為同一份數(shù)據(jù)來存儲。Bitcask 模型 Append 操作天然更容易實(shí)現(xiàn)。

編輯：黃飛

?