TiDB概述

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

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

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

TiDB組件

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

計算引擎層：TiDB/TiSpark

OLTP計算引擎TiDB

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

TiDB 層本身是 無狀態(tài)的，實踐中可以啟動多個 TiDB 實例，通過 負載均衡組件（如 LVS、HAProxy 或 F5）對外提供統(tǒng)一的接入地址，客戶端的連接可以均勻地分攤在多個 TiDB 實例上，以達到 負載均衡 的效果。

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

OLAP計算引擎TiSpark

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

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

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

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

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

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

存儲引擎層：TiKV/TiFlash

行存儲TiKV

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

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

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

列存儲TiFlash

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

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

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

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

TiDB計算引擎

SQL層架構(gòu)

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

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

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

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

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

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

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

表索引映射到KV

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

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

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

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

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存儲引擎

TiKV Region

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

• 一致性哈希（Hash）： 按照 Key 做 Hash，根據(jù) Hash 值選擇對應的存儲節(jié)點

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

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

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

TiKV集群架構(gòu)

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

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

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

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

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

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

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

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

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

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

事務層

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

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

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

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

一致性層

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

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

存儲層

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

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

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

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

RocksDB原理

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

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

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

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

LSM 樹的核心思想是順序 IO 遠快于隨機 IO，因此適用于寫多讀少的業(yè)務場景。

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

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

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

WAL（預寫日志）

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

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

Memtable（內(nèi)存表）

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

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

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

Memtable 存儲的數(shù)據(jù)達到一定數(shù)量后，就會把它拷貝一份出來成為 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é)構(gòu)，由于鍵是有序的，查找鍵可以采用 二分搜索。

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

SSTable 的基本組成部分包括：

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

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

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

RocksDB寫操作

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

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

RocksDB讀操作

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

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 錯誤。

Compaction操作

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

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

通過這種方式，將磁盤的 隨機寫入 轉(zhuǎn)換為 順序?qū)懭?，提高了寫入性能，但也帶來了以下問題：

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

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

Compaction的機制

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

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

Compaction的作用

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

Compaction的類型

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

• Minor Compaction

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

• Major Compaction

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

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

當 L0 層 SSTable 文件數(shù) 超過預定的上限（默認為4個）

當 L(N) 層文件的 總大小 超過(10 ^ i) MB

當某個 SSTable 文件 無效讀取 的次數(shù)過多

布隆過濾器（Bloom Filter）

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

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

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

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

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

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

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

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

結(jié)語

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

作者介紹

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