TiDB概述

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

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

• 分布式架構(gòu)： 純分布式架構(gòu)，擁有良好的擴(kuò)展性，支持彈性的擴(kuò)縮容
• 兼容MySQL： 支持 SQL，對(duì)外暴露 MySQL 的網(wǎng)絡(luò)協(xié)議，并兼容大多數(shù) MySQL 的語(yǔ)法，在大多數(shù)場(chǎng)景下可以直接替換 MySQL
• 高可用部署： 默認(rèn)支持高可用，在少數(shù)副本失效的情況下，數(shù)據(jù)庫(kù)本身能夠自動(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)賬
• 豐富的開(kāi)源生態(tài)鏈： 具有豐富的工具鏈生態(tài)，覆蓋數(shù)據(jù)遷移、同步、備份等多種場(chǎng)景

TiDB組件

在內(nèi)核設(shè)計(jì)上，TiDB 分布式數(shù)據(jù)庫(kù)將整體架構(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é)接受客戶(hù)端的連接，執(zhí)行 SQL 解析和優(yōu)化，最終生成分布式執(zhí)行計(jì)劃。

TiDB 層本身是 無(wú)狀態(tài)的，實(shí)踐中可以啟動(dòng)多個(gè) TiDB 實(shí)例，通過(guò) 負(fù)載均衡組件（如 LVS、HAProxy 或 F5）對(duì)外提供統(tǒng)一的接入地址，客戶(hù)端的連接可以均勻地分?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 中解決用戶(hù)復(fù)雜 OLAP 需求的主要組件，它將 Spark SQL 直接運(yùn)行在 分布式鍵值對(duì)存儲(chǔ)層 TiKV 上，同時(shí)融合 TiKV 分布式集群的優(yōu)勢(shì)，并融入 大數(shù)據(jù)社區(qū)生態(tài)。至此，TiDB 可以通過(guò)一套系統(tǒng)，同時(shí)支持 OLTP 與 OLAP，免除用戶(hù)數(shù)據(jù)同步的煩惱。

TiFlash 和 TiSpark 都允許使用多個(gè)主機(jī)在 OLTP 數(shù)據(jù)上執(zhí)行 OLAP 查詢(xún)。TiFlash 是列式存儲(chǔ)，它提供了更高效的分析查詢(xún)。TiFlash 和 TiSpark 之間的關(guān)系，可類(lèi)比于 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)，可以說(shuō)是 整個(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 的左閉右開(kāi)區(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 寫(xiě)入的方式，實(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)

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

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

表數(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ù)映射方案類(lèi)似，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ù) 鍵值范圍 查詢(xún)對(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ù)的新增、查詢(xún)和刪除等操作者，首先通過(guò)同一個(gè)哈希函數(shù)計(jì)算數(shù)據(jù)的哈希值，然后再哈希環(huán)上順時(shí)針尋址，找到第一個(gè)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)訪問(wèn)。如圖所示：

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

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

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，提供讀寫(xiě)服務(wù)。

TiKV 通過(guò) PD 對(duì)這些 Region 以及副本進(jìn)行調(diào)度，以保證 數(shù)據(jù)負(fù)載 和 讀寫(xiě)負(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 分片存在的問(wèn)題是，數(shù)據(jù)的寫(xiě)入、讀取可能集中在某一個(gè) Region 上，造成計(jì)算資源、存儲(chǔ)空間的傾斜。因此，當(dāng)一個(gè) Region 的數(shù)據(jù)量 超過(guò)閾值 時(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ù)的讀寫(xiě)沖突和事務(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 查詢(xún)的計(jì)算下推服務(wù)。

事務(wù)層

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

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

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

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

一致性層

接下來(lái)是一致性層，該層提供了最基本的 鍵值操作接口，如 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)分片。通過(guò) multi-raft 算法，每個(gè) Region 的大小可以保持在大約 96MB，而 PD（Placement Driver）則可以通過(guò)調(diào)度實(shí)現(xiàn)水平擴(kuò)展。

存儲(chǔ)層

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

每個(gè) TiKV 實(shí)例中有 兩個(gè) RocksDB 實(shí)例，一個(gè)用于存儲(chǔ) Raft 日志（通常被稱(chēng)為 raftdb），另一個(gè)用于存儲(chǔ) 用戶(hù)數(shù)據(jù) 以及 MVCC 信息（通常被稱(chēng)為 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ù)的開(kāi)始時(shí)間以及提交時(shí)間）。當(dāng)用戶(hù)寫(xiě)入了一行數(shù)據(jù)時(shí)，如果該行數(shù)據(jù)長(zhǎng)度小于 255 字節(jié)，那么會(huì)被存儲(chǔ) write 列中，否則該行數(shù)據(jù)會(huì)被存入到 default 列中。
• default 列： 用于存儲(chǔ)超過(guò) 255 字節(jié)長(zhǎng)度的數(shù)據(jù)。

把 TiKV 集群架構(gòu) 和 數(shù)據(jù)架構(gòu) 整合起來(lái)，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ǔ)的核心引擎，所以接下來(lái)會(huì)花大篇幅介紹 RocksDB 的 內(nèi)部構(gòu)造 和部分 優(yōu)化原理。

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

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

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

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

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

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

WAL（預(yù)寫(xiě)日志）

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

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

Memtable（內(nèi)存表）

Memtable 是 內(nèi)存數(shù)據(jù)結(jié)構(gòu)，可以使用 跳躍表 或 紅黑樹(shù) 來(lái)實(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 來(lái)存儲(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ì)把它拷貝一份出來(lái)成為 Immutable Memtable。

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

SSTable

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

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

為了優(yōu)化讀取性能，LSM 樹(shù)使用了 多層級(jí) 的 SSTable 文件。具體來(lái)說(shuō)，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ì)都被寫(xiě)入到磁盤(pán)中。
• 索引： 除了數(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ù)被寫(xiě)入到磁盤(pán)中，因此即使在系統(tǒng)重啟后，數(shù)據(jù)也不會(huì)丟失。
• 數(shù)據(jù)的壓縮： SSTable 中的數(shù)據(jù)被壓縮，這使得存儲(chǔ)的數(shù)據(jù)量更小，提高了存儲(chǔ)效率。
• 數(shù)據(jù)的恢復(fù)： SSTable 中的數(shù)據(jù)可以被恢復(fù)，這使得數(shù)據(jù)庫(kù)的備份和恢復(fù)變得非常簡(jiǎn)單。

RocksDB寫(xiě)操作

RocksDB 中寫(xiě)入操作的原理見(jiàn)下圖：

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

RocksDB讀操作

RocksDB 中讀取操作的原理見(jiàn)下圖：

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

Compaction操作

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

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

通過(guò)這種方式，將磁盤(pán)的 隨機(jī)寫(xiě)入 轉(zhuǎn)換為 順序?qū)懭?，提高了?xiě)入性能，但也帶來(lái)了以下問(wèn)題：

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

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

Compaction的機(jī)制

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

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

Compaction的作用

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

Compaction的類(lèi)型

RocksDB 的 Compaction 操作分為兩類(lèi)，分別是 Minor Compaction 和 Major Compaction。

• Minor Compaction

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

• Major Compaction

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

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

當(dāng) L0 層 SSTable 文件數(shù) 超過(guò)預(yù)定的上限（默認(rèn)為4個(gè)）

當(dāng) L(N) 層文件的 總大小 超過(guò)(10 ^ i) MB

當(dāng)某個(gè) SSTable 文件 無(wú)效讀取 的次數(shù)過(guò)多

布隆過(guò)濾器（Bloom Filter）

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

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

布隆過(guò)濾器底層使用一個(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：

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

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

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

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

結(jié)語(yǔ)

本文詳細(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ù)庫(kù) RocksDB 的原理，一定程度讓大家知其然也知其所以然。本文拋磚引玉，關(guān)于 TiDB 內(nèi)部的分布式通信、一致性原理、MVCC、GC清理算法、一些巧妙數(shù)據(jù)結(jié)構(gòu)，仍需大家深入研究方可融會(huì)貫通，活學(xué)活用。

作者介紹

陳林，51CTO社區(qū)編輯，某零售銀行龍頭DevOps持續(xù)集成平臺(tái)技術(shù)負(fù)責(zé)人，主導(dǎo)核心業(yè)務(wù)方案設(shè)計(jì)落地，推動(dòng)產(chǎn)品架構(gòu)持續(xù)演進(jìn)。