萬字長(zhǎng)文，深入淺出講解分布式數(shù)據(jù)庫TiDB架構(gòu)設(shè)計(jì)

作者：陳林 2024-05-20 08:00:00

TiDB 是一款開源分布式關(guān)系型數(shù)據(jù)庫，同時(shí)支持在線事務(wù)處理（OLTP）與在線分析處理（OLAP）的混合型（Hybrid Transactional and Analytical Processing, HTAP) 分布式數(shù)據(jù)庫，具備水平擴(kuò)容或縮容、金融級(jí)高可用、實(shí)時(shí) HTAP、Kubernetes 云原生的分布式數(shù)據(jù)庫、兼容 MySQL 5.7 協(xié)議和 MySQL 生態(tài)等重要特性。

TiDB概述

與傳統(tǒng)的單機(jī) MySQL 數(shù)據(jù)庫相比，TiDB 具有以下優(yōu)勢(shì)：

分布式架構(gòu)： 純分布式架構(gòu)，擁有良好的擴(kuò)展性，支持彈性的擴(kuò)縮容
兼容MySQL： 支持 SQL，對(duì)外暴露 MySQL 的網(wǎng)絡(luò)協(xié)議，并兼容大多數(shù) MySQL 的語法，在大多數(shù)場(chǎng)景下可以直接替換 MySQL
高可用部署： 默認(rèn)支持高可用，在少數(shù)副本失效的情況下，數(shù)據(jù)庫本身能夠自動(dòng)進(jìn)行數(shù)據(jù)修復(fù)和故障轉(zhuǎn)移，對(duì)業(yè)務(wù)透明
支持強(qiáng)一致性： 符合CAP理論的CP，支持 ACID 事務(wù)，對(duì)于一些有強(qiáng)一致需求的場(chǎng)景友好，例如：銀行轉(zhuǎn)賬
豐富的開源生態(tài)鏈： 具有豐富的工具鏈生態(tài)，覆蓋數(shù)據(jù)遷移、同步、備份等多種場(chǎng)景

TiDB組件

在內(nèi)核設(shè)計(jì)上，TiDB 分布式數(shù)據(jù)庫將整體架構(gòu)拆分成了多個(gè)模塊，各模塊之間互相通信，組成完整的 TiDB 系統(tǒng)。對(duì)應(yīng)的架構(gòu)圖如下：

計(jì)算引擎層：TiDB/TiSpark

OLTP計(jì)算引擎TiDB

TiDB Server 主要用于 OLTP 業(yè)務(wù)，屬于 SQL 層，對(duì)外暴露 MySQL 協(xié)議的連接 endpoint，負(fù)責(zé)接受客戶端的連接，執(zhí)行 SQL 解析和優(yōu)化，最終生成分布式執(zhí)行計(jì)劃。

TiDB 層本身是無狀態(tài)的，實(shí)踐中可以啟動(dòng)多個(gè) TiDB 實(shí)例，通過負(fù)載均衡組件（如 LVS、HAProxy 或 F5）對(duì)外提供統(tǒng)一的接入地址，客戶端的連接可以均勻地分?jǐn)傇诙鄠€(gè) TiDB 實(shí)例上，以達(dá)到負(fù)載均衡的效果。

TiDB Server 本身并不存儲(chǔ)數(shù)據(jù)，只是解析 SQL，將實(shí)際的數(shù)據(jù)讀取請(qǐng)求轉(zhuǎn)發(fā)給底層的存儲(chǔ)節(jié)點(diǎn) TiKV（或 TiFlash）。

OLAP計(jì)算引擎TiSpark

TiSpark 作為 TiDB 中解決用戶復(fù)雜 OLAP 需求的主要組件，它將 Spark SQL 直接運(yùn)行在分布式鍵值對(duì)存儲(chǔ)層 TiKV 上，同時(shí)融合 TiKV 分布式集群的優(yōu)勢(shì)，并融入大數(shù)據(jù)社區(qū)生態(tài)。至此，TiDB 可以通過一套系統(tǒng)，同時(shí)支持 OLTP 與 OLAP，免除用戶數(shù)據(jù)同步的煩惱。

TiFlash 和 TiSpark 都允許使用多個(gè)主機(jī)在 OLTP 數(shù)據(jù)上執(zhí)行 OLAP 查詢。TiFlash 是列式存儲(chǔ)，它提供了更高效的分析查詢。TiFlash 和 TiSpark 之間的關(guān)系，可類比于 Clickhouse 和 Spark。

分布式協(xié)調(diào)層：PD

PD (Placement Driver) 是整個(gè) TiDB 集群的元信息管理模塊，負(fù)責(zé)存儲(chǔ)每個(gè) TiKV 節(jié)點(diǎn)實(shí)時(shí)的數(shù)據(jù)分布情況和集群的整體拓?fù)浣Y(jié)構(gòu)，提供 TiDB Dashboard 管控界面，并為分布式事務(wù)分配事務(wù) ID。

PD 不僅存儲(chǔ)集群元信息，同時(shí)還會(huì)根據(jù) TiKV 節(jié)點(diǎn)實(shí)時(shí)上報(bào)的數(shù)據(jù)分布狀態(tài)，下發(fā)數(shù)據(jù)調(diào)度命令給具體的 TiKV 節(jié)點(diǎn)，可以說是整個(gè)集群的“大腦” 。

此外，PD 本身也是由至少 3 個(gè)節(jié)點(diǎn)構(gòu)成，擁有高可用的能力。建議部署奇數(shù)個(gè) PD 節(jié)點(diǎn)。

存儲(chǔ)引擎層：TiKV/TiFlash

行存儲(chǔ)TiKV

用于存儲(chǔ) OLTP 數(shù)據(jù)，采用行存儲(chǔ)格式，支持事務(wù)機(jī)制，TiKV 本身是一個(gè) 分布式的 Key-Value 存儲(chǔ)引擎。

存儲(chǔ)數(shù)據(jù)的基本單位是 Region，每個(gè) Region 負(fù)責(zé)存儲(chǔ)一個(gè) Key Range（從 StartKey 到 EndKey 的左閉右開區(qū)間）的數(shù)據(jù)，每個(gè) TiKV 節(jié)點(diǎn)會(huì)負(fù)責(zé)多個(gè) Region。

TiKV 的 API 在 KV 鍵值對(duì)層面提供對(duì)分布式事務(wù)支持，默認(rèn)提供了 SI (Snapshot Isolation) 的隔離級(jí)別。
TiDB 的 SQL 層做完 SQL 解析后，會(huì)將 SQL 的執(zhí)行計(jì)劃轉(zhuǎn)換為對(duì) TiKV API 的實(shí)際調(diào)用。
TiKV 支持高可用和自動(dòng)故障轉(zhuǎn)移，所有數(shù)據(jù)都會(huì)自動(dòng)維護(hù)多副本（默認(rèn)為三副本）。

列存儲(chǔ)TiFlash

用于存儲(chǔ) OLAP 數(shù)據(jù)，和普通 TiKV 節(jié)點(diǎn)不一樣的是，在 TiFlash 內(nèi)部，數(shù)據(jù)是以列存儲(chǔ)格式，主要的功能是為分析型的場(chǎng)景加速。

上圖為 TiDB HTAP 形態(tài)架構(gòu)，其中包含 TiFlash 節(jié)點(diǎn)。TiFlash 提供列式存儲(chǔ)，且擁有借助 ClickHouse 高效實(shí)現(xiàn)的協(xié)處理器層。

TiFlash 以低消耗不阻塞 TiKV 寫入的方式，實(shí)時(shí)復(fù)制 TiKV 集群中的數(shù)據(jù)，并同時(shí)提供與 TiKV 一樣的一致性讀取，且可以保證讀取到最新的數(shù)據(jù)。TiFlash 中的 Region 副本與 TiKV 中完全對(duì)應(yīng)，且會(huì)跟隨 TiKV 中的 Leader 副本同時(shí)進(jìn)行分裂與合并。

TiFlash 可以兼容 TiDB 與 TiSpark 兩種計(jì)算引擎，TiDB 適合用于中等規(guī)模的 OLAP 計(jì)算，而 TiSpark 適合大規(guī)模的 OLAP 計(jì)算。

TiDB計(jì)算引擎

SQL層架構(gòu)

用戶的 SQL 請(qǐng)求會(huì)直接或者通過 Load Balancer 發(fā)送到 TiDB Server，TiDB Server 會(huì)解析 MySQL Protocol Packet，獲取請(qǐng)求內(nèi)容，對(duì) SQL 進(jìn)行語法解析和語義分析，制定和優(yōu)化查詢計(jì)劃，執(zhí)行查詢計(jì)劃并獲取和處理數(shù)據(jù)。整個(gè)流程如下圖所示：

用戶發(fā)起請(qǐng)求： 數(shù)據(jù)庫客戶端向指定的 TiDB 集群發(fā)起請(qǐng)求。
目標(biāo)數(shù)據(jù)庫響應(yīng)： TiDB 集群指定 TiDB 節(jié)點(diǎn)響應(yīng)用戶的請(qǐng)求。
兩者建立會(huì)話： TiDB 集群其中一個(gè) TiDB Server 節(jié)點(diǎn)與客戶端建立會(huì)話。
對(duì)象請(qǐng)求解析： TiDB Server 節(jié)點(diǎn)對(duì)接收到的請(qǐng)求進(jìn)行語法檢查、詞法分析、對(duì)象解析，并將其轉(zhuǎn)換為關(guān)系代數(shù)結(jié)構(gòu)，然后完成執(zhí)行計(jì)劃優(yōu)化。
調(diào)度并且執(zhí)行： TiDB Server 根據(jù) PD 尋找最合適的 TiKV 副本，根據(jù)優(yōu)先級(jí)執(zhí)行 SQL，按照內(nèi)存、緩存、數(shù)據(jù)快照、磁盤存儲(chǔ)的順序查詢。
監(jiān)測(cè)任務(wù)狀態(tài)： TiDB Server 監(jiān)測(cè)執(zhí)行中任務(wù)的狀態(tài)。
返回?cái)?shù)據(jù)結(jié)果： TiDB Server 將執(zhí)行結(jié)果返回給數(shù)據(jù)庫客戶端。

表數(shù)據(jù)映射到KV

由于 TiDB 底層基于鍵值對(duì)存儲(chǔ)數(shù)據(jù)，TiDB 表中的行數(shù)據(jù) 需要按照一定格式映射轉(zhuǎn)換為鍵值對(duì)：

為了保證同一張表的數(shù)據(jù)放在一起，方便查找，TiDB 會(huì)為每個(gè)表分配一個(gè) 表 ID，用 TableID 表示。表 ID 是一個(gè)整數(shù)，在整個(gè) 集群內(nèi)唯一。
TiDB 會(huì)為表中每行數(shù)據(jù)分配一個(gè) 行 ID，用 RowID 表示。行 ID 也是一個(gè)整數(shù)，在表內(nèi)唯一。對(duì)于行 ID，TiDB 做了一個(gè)小優(yōu)化，如果某個(gè)表有整數(shù)型的主鍵，TiDB 會(huì)使用主鍵的值當(dāng)做這一行數(shù)據(jù)的行 ID。

每行數(shù)據(jù)按照如下規(guī)則編碼成 (Key, Value) 鍵值對(duì)：

Key: tablePrefix{TableID}_recordPrefixSep{RowID}
Value: [col1, col2, col3, col4]

表索引映射到KV

TiDB 同時(shí)支持主鍵索引和二級(jí)索引。與表數(shù)據(jù)映射方案類似，TiDB 為表中每個(gè)索引分配了一個(gè) 索引 ID，用 IndexID 表示。

對(duì)于主鍵索引和唯一索引，需要根據(jù)鍵值快速定位到對(duì)應(yīng)的 RowID，因此，按照如下規(guī)則編碼成 (Key, Value) 鍵值對(duì)：

Key: tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue
Value: RowID

對(duì)于非唯一性約束的普通二級(jí)索引，一個(gè)鍵值可能對(duì)應(yīng)多行，需要根據(jù) 鍵值范圍查詢對(duì)應(yīng)的 RowID。因此，按照如下規(guī)則編碼成 (Key, Value) 鍵值對(duì)：

Key: tablePrefix{TableID}_indexPrefixSep{IndexID}indexedColumnsValue{RowID}
Value: null

KV映射示例

數(shù)據(jù)與 KV 的映射關(guān)系，定義如下：

tablePrefix     = []byte{'t'}
recordPrefixSep = []byte{'r'}
indexPrefixSep  = []byte{'i'}

假設(shè)表結(jié)構(gòu)如下：

CREATE_TABLE User (
    ID int,
    Name varchar(20),
    Role varchar(20),
    Age int,
    UID int,
    PRIMARY KEY (ID),
    KEY idxAge (Age),
    UNIQUE KEY idxUID (UID)
);

假設(shè)表數(shù)據(jù)如下：

1, "TiDB", "SQL Layer", 10, 10001
2, "TiKV", "KV Engine", 20, 10002
3, "PD", "Manager", 30, 10003

表數(shù)據(jù)映射到KV如下：

t10_r1 --> ["TiDB", "SQL Layer", 10, 10001]
t10_r2 --> ["TiKV", "KV Engine", 20, 10002]
t10_r3 --> ["PD",   "Manager",   30, 10003]

唯一索引映射到KV如下：

t10_i1_10001 --> 1
t10_i2_10002 --> 2
t10_i3_10003 --> 3

非唯一索引映射到KV如下：

# 假設(shè) IndexID 為 1
t10_i1_10_1 --> null
t10_i1_20_2 --> null
t10_i1_30_3 --> null

TiKV存儲(chǔ)引擎

TiKV Region

TiKV 可以看做是一個(gè) 巨大的、有序的 KV Map，為了實(shí)現(xiàn)存儲(chǔ)的水平擴(kuò)展，數(shù)據(jù)將被分散在多臺(tái)機(jī)器上。對(duì)于一個(gè) KV 系統(tǒng)，為了將數(shù)據(jù) 均衡分散 在多臺(tái)機(jī)器上，通常有兩種方案：

一致性哈希（Hash）： 按照 Key 做 Hash，根據(jù) Hash 值選擇對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)

利用哈希函數(shù)將數(shù)據(jù)節(jié)點(diǎn)均勻打散到一個(gè) 0 ~ 2^32 - 1 的順時(shí)針哈希環(huán)上面，對(duì)于數(shù)據(jù)的新增、查詢和刪除等操作者，首先通過同一個(gè)哈希函數(shù)計(jì)算數(shù)據(jù)的哈希值，然后再哈希環(huán)上順時(shí)針尋址，找到第一個(gè)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)訪問。如圖所示：

連續(xù)分段哈希（Range）： 按照 Key 分 Range，某一段連續(xù)的 Key 都保存在一個(gè)存儲(chǔ)節(jié)點(diǎn)上

TiKV 選擇了連續(xù)分段哈希（Range），將整個(gè) Key-Value 空間分成很多段，每一段是一系列連續(xù)的 Key，將每一段叫做一個(gè) Region，可以用 [StartKey，EndKey) 這樣一個(gè) 左閉右開區(qū)間來描述。每個(gè) Region 中保存的數(shù)據(jù)量默認(rèn)在 96 MiB 左右（可以通過配置修改）。

TiKV集群架構(gòu)

TiKV 參考 Google Spanner 論文設(shè)計(jì)了 multi-raft-group 的副本機(jī)制。它將數(shù)據(jù) 按照 key 的范圍劃分成大致相等的分片 Region，每一個(gè) Region 會(huì)有多個(gè)副本（默認(rèn)是 3 個(gè)），其中一個(gè)副本是 Leader，提供讀寫服務(wù)。

TiKV 通過 PD 對(duì)這些 Region 以及副本進(jìn)行調(diào)度，以保證數(shù)據(jù)負(fù)載和讀寫負(fù)載都均勻分散在各個(gè) TiKV 節(jié)點(diǎn)上，保證了整個(gè)集群資源的充分利用，并且可以隨著機(jī)器數(shù)量的增加水平擴(kuò)展。

上圖示意了一個(gè)典型的 TiKV 集群，中間有 4 個(gè)對(duì)等的 TiKV 節(jié)點(diǎn)，負(fù)責(zé)存放數(shù)據(jù)。其中一個(gè) Region 存在3個(gè)副本，每個(gè)副本分布在不同的 TiKV 節(jié)點(diǎn)上。

右邊是PD 集群，負(fù)責(zé)提供集群的元數(shù)據(jù)服務(wù)，比如 TiKV 節(jié)點(diǎn)信息和數(shù)據(jù)的路由信息，即數(shù)據(jù)存放在哪個(gè) TiKV 節(jié)點(diǎn)上。

TiKV數(shù)據(jù)架構(gòu)

按 Range 分片存在的問題是，數(shù)據(jù)的寫入、讀取可能集中在某一個(gè) Region 上，造成計(jì)算資源、存儲(chǔ)空間的傾斜。因此，當(dāng)一個(gè) Region 的數(shù)據(jù)量超過閾值時(shí)，TiKV 自動(dòng)將其分裂成多個(gè)更小的 Region；當(dāng)一個(gè) Region 的數(shù)據(jù)量低于閾值時(shí)，TiKV 自動(dòng)將其與相鄰的 Region 合并。

TiKV 采用了分層架構(gòu)設(shè)計(jì)，將功能劃分為四個(gè)層級(jí)，每一層都只負(fù)責(zé)自己的事情。

TiKV API 負(fù)責(zé) gRPC KV API 邏輯，Coprocessor API 負(fù)責(zé) TiDB 的算子下推計(jì)算
Transaction 負(fù)責(zé)數(shù)據(jù)的讀寫沖突和事務(wù)的隔離性
Raft 負(fù)責(zé)節(jié)點(diǎn)間數(shù)據(jù)同步，保證數(shù)據(jù)的安全性
RocksDB 負(fù)責(zé)數(shù)據(jù)的存儲(chǔ)

網(wǎng)絡(luò)層

首先是網(wǎng)絡(luò)層，TiKV 使用了高性能的 gRPC 作為網(wǎng)絡(luò)通信框架。TiKV 對(duì)外暴露了多種形式的接口，包括支持事務(wù)的 KV 服務(wù)、高性能但不支持事務(wù)的純 KV 服務(wù)，還有用于加速 SQL 查詢的計(jì)算下推服務(wù)。

事務(wù)層

在網(wǎng)絡(luò)層之下，是事務(wù)層。TiKV 實(shí)現(xiàn)了一個(gè)基于 Percolator 算法的事務(wù)處理機(jī)制，支持樂觀事務(wù)。此外，TiKV 還對(duì) Percolator 做了改進(jìn)，加入了對(duì) 悲觀事務(wù) 的支持。

用戶可以根據(jù)業(yè)務(wù)負(fù)載特點(diǎn)，靈活選擇事務(wù)模式：

如果業(yè)務(wù)依賴于 MySQL 事務(wù) 的行為，可以選擇悲觀事務(wù)模式
如果業(yè)務(wù)沖突較少，則可以選擇樂觀事務(wù)，以獲得更高的吞吐量和較低的延遲

事務(wù)層提供了快照隔離的特性和事務(wù) ACID 屬性中的 ACI（原子性、一致性、隔離性）特性，而 D（持久性）特性由下一層實(shí)現(xiàn)。

一致性層

接下來是一致性層，該層提供了最基本的鍵值操作接口，如 kv put/kv delete/kv get/snapshot。在一致性層內(nèi)部，TiKV 實(shí)現(xiàn)了 Raft 一致性算法，保證強(qiáng)一致性。

TiKV 還擴(kuò)展了 Raft 算法，并引入了 multi-raft 算法，使數(shù)據(jù)能夠自動(dòng)分片。通過 multi-raft 算法，每個(gè) Region 的大小可以保持在大約 96MB，而 PD（Placement Driver）則可以通過調(diào)度實(shí)現(xiàn)水平擴(kuò)展。

存儲(chǔ)層

最底層是 RocksDB，作為高效的鍵值存儲(chǔ)引擎，它是 TiKV 真正存儲(chǔ)數(shù)據(jù)的地方。RocksDB 提供了持久化存儲(chǔ)的能力，并被 TiKV 內(nèi)部的各個(gè)層級(jí)用來讀寫數(shù)據(jù)。

每個(gè) TiKV 實(shí)例中有兩個(gè) RocksDB 實(shí)例，一個(gè)用于存儲(chǔ) Raft 日志（通常被稱為 raftdb），另一個(gè)用于存儲(chǔ) 用戶數(shù)據(jù) 以及 MVCC 信息（通常被稱為 kvdb）。kvdb 中有四個(gè) ColumnFamily：raft、lock、default 和 write：

raft 列： 存儲(chǔ)各個(gè) Region 的元信息，僅占極少量空間。
lock 列： 存儲(chǔ)悲觀事務(wù)的悲觀鎖，以及分布式事務(wù)的一階段 Prewrite 鎖。當(dāng)分布式事務(wù)提交之后，lock cf 中的數(shù)據(jù)會(huì)被快速刪除。因此，大部分情況下 lock cf 中的數(shù)據(jù)也很少（少于 1GB）。
write 列： 存儲(chǔ) 表數(shù)據(jù) 以及 MVCC 信息（該數(shù)據(jù)所屬事務(wù)的開始時(shí)間以及提交時(shí)間）。當(dāng)用戶寫入了一行數(shù)據(jù)時(shí)，如果該行數(shù)據(jù)長(zhǎng)度小于 255 字節(jié)，那么會(huì)被存儲(chǔ) write 列中，否則該行數(shù)據(jù)會(huì)被存入到 default 列中。
default 列： 用于存儲(chǔ)超過 255 字節(jié)長(zhǎng)度的數(shù)據(jù)。

把 TiKV 集群架構(gòu) 和數(shù)據(jù)架構(gòu) 整合起來，TiKV 集群的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)大致如圖所示：

RocksDB原理

TiKV 使用 RocksDB 作為底層存儲(chǔ)引擎，RocksDB 是一種內(nèi)嵌式的 KV 存儲(chǔ)引擎，因此可以將 RocksDB 理解為一個(gè) 單機(jī)持久化 Key-Value Map。

由于 RocksDB 是 TiKV 底層存儲(chǔ)的核心引擎，所以接下來會(huì)花大篇幅介紹 RocksDB 的內(nèi)部構(gòu)造和部分優(yōu)化原理。

RocksDB 是由 Facebook 基于 Google LevelDB 開發(fā)的一款提供鍵值存儲(chǔ)和讀寫功能的 LSM-tree 架構(gòu)引擎。

可見，RocksDB 底層基于 LSM-tree 實(shí)現(xiàn)。LSM Tree（Log Structured Merge Tree，日志結(jié)構(gòu)合并樹）是一種數(shù)據(jù)存儲(chǔ)模型，而不是某一種具體的樹型的數(shù)據(jù)結(jié)構(gòu)。

LSM 樹的核心思想是順序 IO 遠(yuǎn)快于隨機(jī) IO，因此適用于寫多讀少的業(yè)務(wù)場(chǎng)景。

LSM Tree結(jié)構(gòu)

LSM樹是一種用于鍵值存儲(chǔ) 的數(shù)據(jù)結(jié)構(gòu)。LSM 的基本思想是將所有的數(shù)據(jù)修改操作（如插入、更新、刪除）都記錄在一個(gè) 順序日志文件中，這個(gè)日志文件又稱為預(yù)寫日志（Write-Ahead Log，WAL）。順序日志文件的好處是順序?qū)懭耄啾?nbsp;隨機(jī)寫入的性能更好。

除了TiKV以外，Hbase、Cassandra和MongoDB等NoSQL底層的存儲(chǔ)模型用的是LSM。

WAL（預(yù)寫日志）

為了防止內(nèi)存斷電而丟失，LSM 在寫入 Memtable 之前，會(huì)先將增刪查改操作備份到 WAL 磁盤日志，在系統(tǒng)故障時(shí)，WAL 可以用來恢復(fù)丟失的數(shù)據(jù)。

WAL 是一個(gè)只允許追加的文件，包含一組更改記錄序列。每個(gè)記錄包含鍵值對(duì)、記錄類型（Put / Merge / Delete）和校驗(yàn)和（checksum）。

Memtable（內(nèi)存表）

Memtable 是內(nèi)存數(shù)據(jù)結(jié)構(gòu)，可以使用跳躍表或紅黑樹來實(shí)現(xiàn)，以保持?jǐn)?shù)據(jù)的有序性。當(dāng) Memtable 達(dá)到一定的數(shù)據(jù)量后，Memtable 會(huì)轉(zhuǎn)化成為 ****Immutable Memtable，同時(shí)會(huì)創(chuàng)建一個(gè)新的 Memtable 來存儲(chǔ)新數(shù)據(jù)。

跳表：跳表是一種非常簡(jiǎn)單的鏈狀二分搜索結(jié)構(gòu)，期望時(shí)間復(fù)雜度 O(log n) ，最壞 O(n)

Immutable Memtable（不可變內(nèi)存表）

Memtable 存儲(chǔ)的數(shù)據(jù)達(dá)到一定數(shù)量后，就會(huì)把它拷貝一份出來成為 Immutable Memtable。

Immutable Memtable 在內(nèi)存中是不可修改的數(shù)據(jù)結(jié)構(gòu)，它是處于 Memtable 和 SSTable 之間的一種中間狀態(tài)，目的是避免在轉(zhuǎn)存過程中不阻塞寫操作。寫操作可以由新的 Memtable 處理，避免由于 Memtable 直接寫入磁盤造成的 IO 阻塞。

SSTable

內(nèi)存中的 Immutable Memtable 是有大小限制的，需要定期持久化到磁盤上的 SSTable。

SSTable 是 Sorted String Table 的簡(jiǎn)稱，是一種高性能的有序鍵值對(duì) 存儲(chǔ)結(jié)構(gòu)，由于鍵是有序的，查找鍵可以采用二分搜索。

為了優(yōu)化讀取性能，LSM 樹使用了多層級(jí) 的 SSTable 文件。具體來說，RocksDB 的 SSTable 從 Level 0 到 Level N 分為多層，每層包含多個(gè) SSTable 文件。層級(jí)越高的 SSTable 數(shù)據(jù)越新，層級(jí)越低的 SSTable 數(shù)據(jù)越舊。

SSTable 的基本組成部分包括：

數(shù)據(jù)： 這是存儲(chǔ)在 SSTable 中的實(shí)際數(shù)據(jù)。數(shù)據(jù)被組織成鍵值對(duì)，并且每個(gè)鍵值對(duì)都被寫入到磁盤中。
索引： 除了數(shù)據(jù)，SSTable 還包含一個(gè)索引，這個(gè)索引用于快速查找數(shù)據(jù)。索引包含了所有鍵的列表，以及每個(gè)鍵在數(shù)據(jù)中的位置。
元數(shù)據(jù)： SSTable還包含一些元數(shù)據(jù)，如創(chuàng)建時(shí)間、最后修改時(shí)間等。

SSTable 的優(yōu)點(diǎn)包括：

數(shù)據(jù)的有序性： SSTable 中的數(shù)據(jù)是有序的，這使得查找數(shù)據(jù)變得非常快速。
數(shù)據(jù)的持久性： SSTable 中的數(shù)據(jù)被寫入到磁盤中，因此即使在系統(tǒng)重啟后，數(shù)據(jù)也不會(huì)丟失。
數(shù)據(jù)的壓縮： SSTable 中的數(shù)據(jù)被壓縮，這使得存儲(chǔ)的數(shù)據(jù)量更小，提高了存儲(chǔ)效率。
數(shù)據(jù)的恢復(fù)： SSTable 中的數(shù)據(jù)可以被恢復(fù)，這使得數(shù)據(jù)庫的備份和恢復(fù)變得非常簡(jiǎn)單。

RocksDB寫操作

RocksDB 中寫入操作的原理見下圖：

寫入時(shí)首先寫 WAL 日志文件，方便進(jìn)程閃崩時(shí)可以根據(jù)日志快速恢復(fù)。
將請(qǐng)求寫入到內(nèi)存中的跳表 SkipList 即 Memtable 中，立即返回給客戶端。當(dāng) Memtable 寫滿后，將其轉(zhuǎn)換成 Immutable Memtable，并切換到新的 Memtable 提供寫入。
RocksDB 在后臺(tái)會(huì)通過一個(gè) flush 進(jìn)程將這個(gè) Memtable 刷新到磁盤，生成一個(gè) Sorted String Table(SST) 文件，放在 Level 0 層，刪除對(duì)應(yīng)的 WAL 日志。L0 層的文件，是由內(nèi)存中的 Memtable dump 到磁盤上生成的，單個(gè) 文件內(nèi)部按 key 有序，文件之間無序，而 L1 ~ L6 層的文件都是按照 key 有序；
當(dāng) Level 0 層的 SST 文件個(gè)數(shù)超過閾值之后，就會(huì)通過 Compaction 策略將其放到 Level 1 層，以此類推。每一層的數(shù)據(jù)是上一層的 10 倍（因此 90% 的數(shù)據(jù)存儲(chǔ)在最后一層）。

RocksDB讀操作

RocksDB 中讀取操作的原理見下圖：

首先在 Memtable 中查找指定的 key，如果查到符合條件的數(shù)據(jù)，結(jié)束查找。
然后在 Immutable Memtable 中查找指定的 key，如果查到符合條件的數(shù)據(jù)，結(jié)束查找。
按低層至高層的順序，從 level 0 層到 level 1 層的 SST文件中查找指定的 key，如果查到符合條件的數(shù)據(jù)，結(jié)束查找，否則返回 Not Found 錯(cuò)誤。

Compaction操作

RocksDB 通過追加寫的方式記錄數(shù)據(jù)修改操作：

Insert 操作： 直接寫入新的 KV
Update 操作： 寫入修改后的 KV
Delete 操作： 寫入一條 tombstone 標(biāo)記刪除的記錄

通過這種方式，將磁盤的隨機(jī)寫入轉(zhuǎn)換為順序?qū)懭耄岣吡藢懭胄阅埽矌砹艘韵聠栴}：

大量的冗余和無效數(shù)據(jù) 占用磁盤空間，造成空間放大。
如果在內(nèi)存中沒有讀取到數(shù)據(jù)，需要從 L0 層開始查找 SST 文件，造成讀放大。

因此，RocksDB 引入了 compaction 操作，依次將 L(N) 層的數(shù)據(jù)合并到下一層 L(N+1) 層，同時(shí)清理標(biāo)記刪除的數(shù)據(jù)，從而降低空間放大、讀放大的影響。

Compaction的機(jī)制

RocksDB 在邏輯上把 SSTable 文件劃分成多個(gè)層級(jí)（7 層），并且滿足以下性質(zhì)：

層級(jí)越高說明其數(shù)據(jù)寫入越早，即先往上層進(jìn)行 “放”（minor compaction），上層 “滿”（達(dá)到容量限制）之后 “溢”（major compaction）到下層進(jìn)行合并。
每層文件總大小都有限制，層級(jí)大小成指數(shù)級(jí)增長(zhǎng)。比如 L0 層文件總大小上限為 10MB，L1 層為 100MB，L21 層為 1000MB。依次類推，最下層（L6 層）沒有限制。
由于 L0 層每個(gè) SSTable 文件都是直接由 Memtable 落盤而來，因此 L0 層多個(gè) SSTable 文件的 key 范圍可能會(huì)有重合。而其他層（L1 ~ L6）的多個(gè) SSTable 文件，則通過一些規(guī)則保證沒有重合。

Compaction的作用

數(shù)據(jù)持久化： 將內(nèi)存中的數(shù)據(jù)持久化到磁盤中的 SSTable 文件
提高讀寫效率： 將 L0 層的 SSTable 文件合并為若干個(gè) 沒有數(shù)據(jù)重合的 L1 ~L6 層文件，避免多層無效遍歷
平衡讀寫差異： 當(dāng) L0 層SSTable 文件數(shù)量過多時(shí)，暫停寫入操作，直到 compaction 完成為止
節(jié)約磁盤空間： 同一個(gè) key 可能存在著多條數(shù)據(jù)，對(duì)不同版本進(jìn)行合并可以節(jié)省磁盤空間。

Compaction的類型

RocksDB 的 Compaction 操作分為兩類，分別是 Minor Compaction 和 Major Compaction。

Minor Compaction

Minor Compaction 是指將 Immutable MemTable 轉(zhuǎn)存為 SSTable 文件寫入 L0 層

Major Compaction

Major Compaction 是指合并壓縮第 L(N) 層的多個(gè) SSTable 文件到第 L(N+1) 層

Major Compaction 的觸發(fā)條件：

當(dāng) L0 層 SSTable 文件數(shù) 超過預(yù)定的上限（默認(rèn)為4個(gè)）
當(dāng) L(N) 層文件的總大小超過(10 ^ i) MB
當(dāng)某個(gè) SSTable 文件無效讀取的次數(shù)過多

布隆過濾器（Bloom Filter）

為了減小 讀放大 導(dǎo)致性能下降，RocksDB 采取了以下兩種策略：

通過 major compaction 盡量減少 SSTable 文件數(shù)
使用布隆過濾器，快速判斷 key 是否在某個(gè) SSTable 文件中

布隆過濾器底層使用一個(gè) 位數(shù)組（bit array），初始集合為空時(shí)，所有位都為 0：

當(dāng)往集合中插入一個(gè) 數(shù)據(jù) x 時(shí)，利用 k 個(gè) 獨(dú)立的哈希函數(shù) 分別對(duì) x 進(jìn)行散列，然后將 k 個(gè)散列值按數(shù)組長(zhǎng)度取余后，分別將位數(shù)組位置置為 1：

查找過程和插入過程類似，也是利用同樣的 k 個(gè)哈希函數(shù) 對(duì)待查找數(shù)據(jù) 按順序進(jìn)行哈希，得到 k 個(gè)位置。

如果位數(shù)組中 k 個(gè)位置上的位均為 1，則該元素有可能存在
如果任意一位置上值為位為0，則該值一定不存在。

布隆過濾器用于快速判斷一條數(shù)據(jù)是否在集合中。其本質(zhì)上是通過容忍一定的錯(cuò)誤率，來換取時(shí)空的高效性。

RocksDB 并未使用 k 個(gè)哈希函數(shù)，而是用了 double-hashing 方法，利用一個(gè)哈希函數(shù)達(dá)到近似 k 個(gè)哈希函數(shù)的效果。

結(jié)語

本文詳細(xì)介紹了 TiDB 的核心組件，尤其是用于 OLTP 的分布式計(jì)算引擎 TiDB 和分布式存儲(chǔ)引擎 TiKV。一方面闡述了 TiDB 是如何將關(guān)系型表數(shù)據(jù) 、索引數(shù)據(jù) 轉(zhuǎn)換為鍵值對(duì) 數(shù)據(jù)；另一方面，深度剖析了 TiKV 內(nèi)部的架構(gòu)設(shè)計(jì)和原理，尾篇大幅介紹了 TiKV 底層引入的單機(jī)鍵值對(duì) 數(shù)據(jù)庫 RocksDB 的原理，一定程度讓大家知其然也知其所以然。本文拋磚引玉，關(guān)于 TiDB 內(nèi)部的分布式通信、一致性原理、MVCC、GC清理算法、一些巧妙數(shù)據(jù)結(jié)構(gòu)，仍需大家深入研究方可融會(huì)貫通，活學(xué)活用。