Scalable Open Financial Architecture Stack
是螞蟻金服自主研發的金融級分布式架構，包含了建構金融級雲原生架構所需的各個元件，是在金融場景裡錘煉出來的最佳實踐。
本文為《剖析 | SOFAJRaft 實作原理》第二篇，本篇作者米麒麟，來自陸金所。《剖析 | SOFAJRaft 實作原理》系列由 SOFA 團隊和源碼愛好者們出品，項目代号：，目前領取已經完成，感謝大家的參與。
SOFAJRaft 是一個基于 Raft 一緻性算法的生産級高性能 Java 實作，支援 MULTI-RAFT-GROUP，适用于高負載低延遲的場景。
SOFAJRaft ：
https://github.com/sofastack/sofa-jraft前言
SOFAJRaft-RheaKV 是 SOFAJRaft 的一個子產品，基于 SOFAJRaft 和 RocksDB 實作的嵌入式、分布式、高可用、強一緻的 KV 存儲類庫，SOFAJRaft 是基于 Raft 一緻性算法的生産級高性能 Java 實作，支援 MULTI-RAFT-GROUP。SOFAJRaft-RheaKV 叢集主要包括三個核心元件：PD，Store 和 Region。
本文将圍繞 SOFAJRaft-RheaKV 架構設計，存儲概覽，核心子產品，使用場景以及基于 Raft 實作等方面剖析 SOFAJRaft-RheaKV 基于 SOFAJRaft 實作原理，闡述如何使用 Raft 協定支援 KV 存儲類庫功能特性：
- SOFAJRaft-RheaKV 基礎架構如何設計？核心元件負責哪些功能？子產品内部處理流程是怎樣？
- 基于 SOFAJRaft 如何使用 Raft 實作 SOFAJRaft-RheaKV 強一緻性和自驅動等特性？
SOFAJRaft-RheaKV 是如何使用 Raft 的 | SOFAJRaft 實作原理
SOFAJRaft-RheaKV 概覽
SOFAJRaft-RheaKV 是一個輕量級的分布式的嵌入式的 KV 存儲 Library， RheaKV 包含在 SOFAJRaft 項目裡，是 SOFAJRaft 的子子產品。SOFAJRaft-RheaKV 定位是嵌入式 jar 包方式嵌入到應用中，涵蓋以下功能特性：
- 強一緻性，基于 Multi-Raft 分布式一緻性協定保證資料可靠性和一緻性；
- 自驅動，自診斷，自優化，自決策，自恢複；
- 可監控基于節點自動上報到 PD 的元資訊和狀态資訊；
- 基本 API get/put/delete 和跨分區 scan/batch put，distributed lock 等。
| 架構設計
SOFAJRaft-RheaKV 存儲類庫主要包括 PD，Store 和 Region 三個核心元件，支援輕量級的狀态/元資訊存儲以及叢集同步，分布式鎖服務使用場景：
PD 是全局的中心總控節點，負責整個叢集的排程管理，維護 RegionRouteTable 路由表。一個 PDServer 管理多個叢集，叢集之間基于 clusterId 隔離；PD Server 需要單獨部署，很多場景其實并不需要自管理，RheaKV 也支援不啟用 PD，不需要自管理的叢集可不啟用 PD，設定 PlacementDriverOptions 的 fake選項為 true 即可。
Store 是叢集中的一個實體存儲節點，一個 Store 包含一個或多個 Region。
Region 是最小的 KV 資料單元，可了解為一個資料分區或者分片，每個 Region 都有一個左閉右開的區間 [startKey, endKey)，能夠根據請求流量/負載/資料量大小等名額自動分裂以及自動副本搬遷。Region 有多個副本 Replication 建構 Raft Groups 存儲在不同的 Store 節點，通過 Raft 協定日志複制功能資料同步到同 Group 的全部節點。
| 存儲設計
SOFAJRaft-RheaKV 存儲層為可插拔設計，實作 RawKVStore 存儲接口，目前 StoreEngine 存儲引擎支援 MemoryDB 和 RocksDB 兩種實作：
- MemoryRawKVStore：MemoryDB 基于 ConcurrentSkipListMap 實作，有更好的性能，但是單機存儲容量受記憶體限制；
- RocksRawKVStore：RocksDB 在存儲容量上隻受磁盤限制，适合更大資料量的場景。
SOFAJRaft-RheaKV 存儲引擎基于 MemoryDB 和 RocksDB 實作 KV 存儲入口：
com.alipay.sofa.jraft.rhea.storage.RawKVStore
com.alipay.sofa.jraft.rhea.storage.MemoryRawKVStore
com.alipay.sofa.jraft.rhea.storage.RocksRawKVStore SOFAJRaft-RheaKV 資料強一緻性依靠 SOFAJRaft 同步資料到其他副本 Replication, 每個資料變更都會落地為一條 Raft 日志, 通過 Raft 協定日志複制功能将資料安全可靠地同步到同 Raft Group 的全部節點裡。
| 核心設計
SOFAJRaft-RheaKV 核心子產品包括：KV 子產品和PD 子產品。
KV 子產品：
[RheaKVStore 基于 RegionRouteTable 路由表使用 RaftRawKVStore 存儲 KeyValue]；
PD 子產品：
[PlacementDriverServer 基于 StoreHeartbeat/RegionHeartbeat 心跳平衡節點分區 Leader 以及分裂]。
KV 子產品内部處理
1、RheaKVStore：最上層 User API，預設實作為 DefaultRheaKVStore， RheaKVStore 為純異步實作，是以通常阻塞調用導緻的用戶端出現瓶頸，理論上不會在 RheaKV 上遭遇，DefaultRheaKVStore 實作包括請求路由、Request 分裂、Response 聚合以及失敗重試等功能。
2、PlacementDriverClient：非必須，作為與 PlacementDriver Server 叢集溝通的用戶端，通過它擷取叢集完整資訊包括但不僅限于"請求路由表"，對于無 PD 場景， RheaKV 提供 Fake PD Client。
3、RegionRouteTable：分片邏輯基于 RegionRouteTable 路由表結構，最适合的資料結構便是跳表或者二叉樹(最接近比對項查詢)。作為本地路由表緩存元件，RegionRouteTable 根據 KV 請求的具體失敗原因來決策是否從 PD Server 叢集重新整理資料，并且提供對單個 Key、多個 Key 清單以及 Key Range 進行計算傳回對應的分區 ID。選擇 Region 的 StartKey 作為 RegionRouteTable 的 Key ，主要取決于 Region Split 的方式，父 Region 分裂成兩個子 Region 導緻其中一個子 Region 的 StartKey 為 SplitKey。
4、LoadBalancer：在提供 Follower 線性一緻讀的配置下有效，目前僅支援 RR 政策。
5、RheaKVRpcService：針對 KV 存儲服務的 RPC Client 用戶端封裝，實作 Failover 邏輯。
6、RegionKVService：KV Server 服務端的請求處理服務，一個 StoreEngine 中包含很多 RegionKVService, 每個 RegionKVService 對應一個 Region，隻處理本身 Region 範疇内的請求。
7、MetricsRawKVStore：攔截請求做名額度量。
8、RaftRawKVStore：RheaKV 的 Raft 入口，從這裡開始 Raft 流程。
9、KVStoreStateMachine：實作 Raft 狀态機。
10、RocksRawKVStore：RocksDB API 封裝， 目前 RheaKV 也支援可插拔的 MemoryDB 存儲實作。
PD 子產品内部處理
PD 子產品主要參考 TIKV 的設計理念，目前隻實作自動平衡所有節點的分區 Leader 以及自動分裂。
1、PlacementDriverClient -> MetadataClient：MetadataClient 負責從 PD 擷取叢集元資訊以及注冊元資訊。
2、StoreEngine -> HeartbeatSender：
- HeartbeatSender 負責發送目前節點的心跳，心跳中包含一些狀态資訊，分為兩類：StoreHeartbeat 和 RegionHeartbeat；
- PD 不斷接受 RheaKV 叢集這兩類心跳消息，PD 在對 Region Leader 的心跳回複裡面包含具體排程指令，再以這些資訊作為決策依據。除此之外，PD 還應該可以通過管理接口接收額外的運維指令，用來人為執行更準确的決策。
- 兩類心跳包含的狀态資訊詳細内容如下：
StoreHeartbeat 包括存儲節點 Store 容量，Region 數量，Snapshot 數量以及寫入/讀取資料量等 StoreStats 統計明細；
RegionHeartbeat 包括目前 Region 的 Leader 位置，掉線 Peer 清單，暫時不 Work 的 Follower 以及寫入/讀取資料量/Key 的個數等 RegionStats 統計明細。
3、Pipeline：是針對心跳上報 Stats 的計算以及存儲處理流水線，處理單元 Handler 可插拔非常友善擴充。
4、MetadataStore：負責叢集元資訊存儲以及查詢，存儲方面基于内嵌的 RheaKV。
SOFAJRaft-RheaKV 剖析
RheaKV 是基于 SOFAJRaft 實作的嵌入式、分布式、高可用、強一緻的 KV 存儲類庫，TiKV 是一個分布式的 KV 系統，采用 Raft 協定保證資料的強一緻性，同時使用 MVCC + 2PC 方式實作分布式事務的支援，兩者如何基于 Raft協定實作 KV 存儲？
| RheaKV 基于 JRaft 實作
RaftRawKVStore 是 RheaKV 基于 Raft 複制狀态機 KVStoreStateMachine 的 RawKVStore 接口 KV 存儲實作，調用 applyOperation(kvOperation,kvStoreClosure) 方法根據讀寫請求申請指定 KVOperation 操作，申請鍵值操作處理邏輯：
1、檢查目前節點的狀态是否為 STATELEADER，如果目前節點不是 Leader 直接失敗通知 Done Closure，通知失敗(NOTLEADER)後用戶端重新整理 Leader 位址并且重試。
Raft 分組 Leader 節點調用 Node#apply(task) 送出申請基于鍵值操作的任務到相應 Raft Group，向 Raft Group 組成的複制狀态機叢集送出新任務應用到業務狀态機，Raft Log 形成 Majority 後 StateMachine#onApply(iterator) 接口應用到狀态機的時候會被擷取調用。Node 節點建構申請任務日志封裝成事件釋出回調，釋出節點服務事件到隊列 applyQueue，依靠 Disruptor 的 MPSC 模型批量消費，對整體吞吐性能有着極大的提升。日志服務事件處理器以單線程 Batch 攢批的消費方式批量運作鍵值存儲申請任務；
2、Raft 副本節點 Node 執行申請任務檢查目前狀态是否為 STATE_LEADER，必須保證 Leader 節點操作申請任務。循環周遊節點服務事件判斷任務的預估任期是否等于目前節點任期，Leader 沒有發生變更的階段内送出的日志擁有相同的 Term 編号，節點 Node 任期滿足預期則 Raft 協定投票箱 BallotBox 調用 appendPendingTask(conf, oldConf, done) 日志複制之前儲存應用上下文，即基于目前節點配置以及原始配置建立選票 Ballot 添加到選票雙向隊列 pendingMetaQueue；
3、日志管理器 LogManager 調用底層日志存儲 LogStorage#appendEntries(entries) 批量送出申請任務日志寫入 RocksDB，用于 Leader 向 Follower 複制日志包括心跳存活檢查等。日志管理器釋出 Leader 穩定狀态回調 LeaderStableClosure 事件到隊列 diskQueue 即 Disruptor 的 Ring Buffer，穩定狀态回調事件處理器通過MPSC Queue 模型攢批消費觸發送出節點選票；
4、投票箱 BallotBox 送出目前 PeerId 節點選票到 Raft Group通過調用 commitAt(firstLogIndex, lastLogIndex, peerId) 方法實作，更新日志索引在[firstlogindex, lastlogindex]範疇。通過 Node#apply(task) 送出的申請任務最終将會複制應用到所有 Raft 節點上的狀态機，RheaKV 狀态機通過繼承 StateMachineAdapter 狀态機擴充卡的 KVStoreStateMachine 表示；
5、Raft 狀态機 KVStoreStateMachine 調用 onApply(iterator) 方法按照送出順序應用任務清單到狀态機。當 onApply(iterator) 方法傳回時認為此批申請任務都已經成功應用到狀态機上，假如成功應用到狀态機産生了異常(比如 IO 異常)，将被當做 Critical 級别錯誤報告給狀态機的 onError(raftException) 方法，錯誤類型為 ERRORTYPESTATE_MACHINE。Critical 錯誤導緻終止狀态機，為什麼這裡需要終止狀态機，非業務邏輯異常的話(比如磁盤滿了等 IO 異常)，代表可能某個節點成功應用到狀态機，但是目前節點卻應用狀态機失敗，是不是代表出現不一緻的錯誤？ 解決辦法隻能終止狀态機，需要手工介入重新開機，重新開機後依靠 Snapshot + Raft log 恢複狀态機保證狀态機資料的正确性。送出的任務在 SOFAJRaft 内部用來累積批量送出，應用到狀态機的是 Task 疊代器，通過 com.alipay.sofa.jraft.Iterator 接口表示；
6、KVStoreStateMachine 狀态機疊代狀态輸出清單積攢鍵值狀态清單批量申請 RocksRawKVStore 調用 batch*(kvStates) 方法運作相應鍵值操作存儲到 RocksDB，為啥 Batch 批量存儲呢？ 刷盤常用伎倆，攢批刷盤優于多次刷盤。通過 RecycleUtil 回收器工具回收狀态輸出清單，其中KVStateOutputList 是 Pooled ArrayList 實作，RecycleUtil 用于釋放清單對象池化複用避免每次建立 List。
RheaKV 基于狀态機 KVStoreStateMachine 的 RaftRawKVStore 存儲 Raft 實作入口：
com.alipay.sofa.jraft.rhea.storage.RaftRawKVStore RheaKV 運作在每個 Raft 節點上面的狀态機 KVStoreStateMachine 實作入口：
com.alipay.sofa.jraft.rhea.storage.KVStoreStateMachine RheaKV 是一個要保證線性一緻性的分布式 KV 存儲引擎，所謂線性一緻性，一個簡單的例子是在 T1 的時間寫入一個值，那麼在 T1 之後讀一定能讀到這個值，不可能讀到 T1 之前的值。因為 Raft 協定是為了實作分布式環境下面線性一緻性的算法，是以通過 Raft 非常友善的實作線性 Read，即将任何的讀請求走一次 Raft Log，等 Log 日志送出之後在 apply 的時候從狀态機裡面讀取值，一定能夠保證此讀取到的值是滿足線性要求的。因為每次 Read 都需要走 Raft 流程，是以性能是非常的低效的，SOFAJRaft 實作 Raft 論文提到 ReadIndex 和 Lease Read 優化，提供基于 Raft 協定的 ReadIndex 算法的更高效率的線性一緻讀實作，ReadIndex 省去磁盤的開銷，結合 SOFAJRaft 的 Batch + Pipeline Ack + 全異步機制大幅度提升吞吐。
RaftRawKVStore 在處理 get、multiGet、scan、getSequence 等所有隻讀請求都使用 Node#readIndex(requestContext, readIndexClosure) 發起一次線性一緻讀請求，當能夠安全讀取的時候傳入的 ReadIndexClosure 将被調用，正常情況從狀态機中讀取資料傳回給用戶端，readIndex 讀取失敗嘗試走 raft log 執行讀請求，SOFAJRaft 保證讀取的線性一緻性。線性一緻讀在任何叢集内的節點發起，并不需要強制要求放到 Leader 節點上面，将請求散列到叢集内的所有節點上，降低 Leader 節點的讀取壓力。RaftRawKVStore 的 get 讀操作發起一次線性一緻讀請求的調用：
| TiKV 基于 Raft 實作
TiDB 是 PingCAP 公司設計的開源分布式 HTAP (Hybrid Transactional and Analytical Processing) 資料庫，TiDB 叢集主要包括三個核心元件：TiDB Server，PD Server 和 TiKV Server。TiKV Server 負責存儲資料，從外部看 TiKV 是一個分布式的提供事務的 Key-Value 存儲引擎。存儲資料的基本機關是 Region，每個 Region 負責存儲一個 Key Range（從 StartKey 到 EndKey 的左閉右開區間）的資料，每個 TiKV 節點負責多個 Region。
TiKV 使用 Raft 協定做複制，保持資料的一緻性和容災。副本以 Region 為機關進行管理，不同節點上的多個 Region 構成一個 Raft Group，互為副本。資料在多個 TiKV 之間的負載均衡由 PD 排程，這裡也是以 Region 為機關進行排程。TiKV 利用 Raft 來做資料複制，每個資料變更都會落地為一條 Raft 日志，通過 Raft 的日志複制功能，将資料安全可靠地同步到 Group 的多數節點。TiKV 整體架構包括 Placement Driver，Node，Store 以及 Region 元件：
- Placement Driver : Placement Driver (PD) 負責整個叢集的管理排程。
- Node : Node 可以認為是一個實際的實體機器，每個 Node 負責一個或者多個 Store。
- Store : Store 使用 RocksDB 進行實際的資料存儲，通常一個 Store 對應一塊硬碟。
- Region : Region 是資料移動的最小單元，對應的是 Store 裡面一塊實際的資料區間。每個 Region 有多個副本（Replica），每個副本位于不同的 Store ，而這些副本組成了一個 Raft group。
TiKV 使用 Raft 一緻性算法來保證資料的安全，預設提供的是三個副本支援，這三個副本形成了一個 Raft Group。當 Client 需要寫入 TiKV 資料的時候，Client 将操作發送給 Raft Leader，在 TiKV 裡面稱做 Propose，Leader 将操作編碼成一個 Entry，寫入到自己的 Raft Log 裡面，稱做 Append。Leader 也會通過 Raft 算法将 Entry 複制到其他的 Follower 上面，叫做 Replicate。Follower 收到這個 Entry 之後也會同樣進行 Append 操作，順帶告訴 Leader Append 成功。當 Leader 發現此 Entry 已經被大多數節點 Append，認為此 Entry 已經是 Committed 的，然後将 Entry 裡面的操作解碼出來，執行并且應用到狀态機裡面，叫做 Apply。
TiKV 提供 Lease Read，對于 Read 請求直接發給 Leader，如果 Leader 确定自身的 Lease 沒有過期，那麼直接提供 Read 服務不用執行一次 Raft 流程。如果 Leader 發現 Lease 已經過期，就會強制執行一次 Raft 流程進行續租然後再提供 Read 服務。
TiKV 是以 Region 為機關做資料的複制，也就是一個 Region 的資料儲存多個副本，将每一個副本叫做一個 Replica。Replica 之間是通過 Raft 來保持資料的一緻，一個 Region 的多個 Replica 儲存在不同的節點上構成一個 Raft Group，其中一個 Replica 作為此 Group 的 Leader，其他的 Replica 作為 Follower。所有的讀和寫都是通過 Leader 進行，再由 Leader 複制給 Follower。
總結
本文圍繞 SOFAJRaft-RheaKV 架構存儲，子產品流程以及基于 Raft 實作細節方面闡述 SOFAJRaft-RheaKV 基本原理，剖析 SOFAJRaft-RheaKV 如何使用 JRaft 一緻性協定日志複制功能保證資料的安全和容災，參考 TiKV 基于 Raft 算法實作了分布式環境資料的強一緻性。