1 概述

TiDB 是 PingCAP 公司自主設(shè)計、研發(fā)的開源分布式關(guān)系型數(shù)據(jù)庫，是一款同時支持在線事務(wù)處理與在線分析處理 (Hybrid Transactional and Analytical Processing, HTAP) 的融合型分布式數(shù)據(jù)庫產(chǎn)品，具備水平擴容或者縮容、金融級高可用、實時 HTAP、云原生的分布式數(shù)據(jù)庫、兼容 MySQL 5.7 協(xié)議和 MySQL 生態(tài)等重要特性。目標(biāo)是為用戶提供一站式 OLTP (Online Transactional Processing)、OLAP (Online Analytical Processing)、HTAP 解決方案。TiDB 適合高可用、強一致要求較高、數(shù)據(jù)規(guī)模較大等各種應(yīng)用場景。

總結(jié)一下，Tidb是個高度兼容MySQL的分布式數(shù)據(jù)庫，并擁有以下幾個特性：

• 高度兼容 MySQL：掌握MySQL，就可以零基礎(chǔ)使用TIDB

• 水平彈性擴展：自適應(yīng)擴展，基于Raft協(xié)議

• 分布式事務(wù)：悲觀鎖、樂觀鎖、因果一致性

• 真正金融級高可用：基于Raft協(xié)議

• 一站式 HTAP 解決方案：單個數(shù)據(jù)庫同時支持 OLTP 和 OLAP，進行實時智能處理的能力

其中TiDB的核心特性是：水平擴展、高可用。

本文主要從TiDB的各類組件為起點，了解它的基礎(chǔ)架構(gòu)，并重點分析它在存儲架構(gòu)方面的設(shè)計，探究其如何組織數(shù)據(jù)，Table中的每行記錄是如何在內(nèi)存和磁盤中進行存儲的。

2 組件

先看一張Tidb的架構(gòu)圖，里面包含 TiDB、Storage(TiKV、TiFlash)、TiSpark、PD。其中的TiDB、TiKV、PD是核心組件；TIFlash、TiSpark是為了解決復(fù)雜OLAP的組件。
TiDB是Mysql語法的交互入口，TiSpark是sparkSAL的交互入口。

2.1 TiDB Server

SQL 層，對外暴露 MySQL 協(xié)議的連接 endpoint，負(fù)責(zé)接受客戶端的連接，執(zhí)行 SQL 解析和優(yōu)化，最終生成分布式執(zhí)行計劃。

TiDB 層本身是無狀態(tài)的，實踐中可以啟動多個 TiDB 實例，通過負(fù)載均衡組件（如 LVS、HAProxy 或 F5）對外提供統(tǒng)一的接入地址，客戶端的連接可以均勻地分?jǐn)傇诙鄠€ TiDB 實例上以達到負(fù)載均衡的效果。TiDB Server 本身并不存儲數(shù)據(jù)，只是解析 SQL，將實際的數(shù)據(jù)讀取請求轉(zhuǎn)發(fā)給底層的存儲節(jié)點 TiKV（或 TiFlash）。

2.2 PD (Placement Driver) Server

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

PD 不僅存儲元信息，同時還會根據(jù) TiKV 節(jié)點實時上報的數(shù)據(jù)分布狀態(tài)，下發(fā)數(shù)據(jù)調(diào)度命令給具體的 TiKV 節(jié)點，可以說是整個集群的“大腦”。此外，PD 本身也是由至少 3 個節(jié)點構(gòu)成，擁有高可用的能力。建議部署奇數(shù)個 PD 節(jié)點。

2.3 存儲節(jié)點

2.3.1 TiKV Server

負(fù)責(zé)存儲數(shù)據(jù)，從外部看 TiKV 是一個分布式的提供事務(wù)的 Key-Value 存儲引擎。

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

TiKV 的 API 在 KV 鍵值對層面提供對分布式事務(wù)的原生支持，默認(rèn)提供了 SI (Snapshot Isolation) 的隔離級別，這也是 TiDB 在 SQL 層面支持分布式事務(wù)的核心。

TiDB 的 SQL 層做完 SQL 解析后，會將 SQL 的執(zhí)行計劃轉(zhuǎn)換為對 TiKV API 的實際調(diào)用。所以，數(shù)據(jù)都存儲在 TiKV 中。另外，TiKV 中的數(shù)據(jù)都會自動維護多副本（默認(rèn)為三副本），天然支持高可用和自動故障轉(zhuǎn)移。

2.3.2 TiFlash

TiFlash 是一類特殊的存儲節(jié)點。和普通 TiKV 節(jié)點不一樣的是，在 TiFlash 內(nèi)部，數(shù)據(jù)是以列式的形式進行存儲，主要的功能是為分析型的場景加速。假如使用場景為海量數(shù)據(jù)，且需要進行統(tǒng)計分析，可以在數(shù)據(jù)表基礎(chǔ)上創(chuàng)建TiFlash存儲結(jié)構(gòu)的映射表，以提高查詢速度。

以上組件互相配合，支撐著Tidb完成海量數(shù)據(jù)存儲、同時兼顧高可用、事務(wù)、優(yōu)秀的讀寫性能。

3 存儲架構(gòu)

3.1 TiKV的模型

前文所描述的Tidb架構(gòu)中，其作為存儲節(jié)點的有兩個服務(wù)，TiKV和TiFlash。其中TiFlash為列式存儲的形式實現(xiàn)的，可以參考ClickHouse的架構(gòu)思路，二者具有相似性。本章節(jié)主要討論TiKV的實現(xiàn)。

在上圖中，TiKV node所描述的就是OLTP場景下Tidb的存儲組件，而TiFlash則是應(yīng)對的LOAP場景。TiKV選擇的是Key-Value模型，作為數(shù)據(jù)的存儲模型，并提供有序遍歷方法進行讀取。

TiKV數(shù)據(jù)存儲有兩個關(guān)鍵點：

1. 是一個巨大的Map（可以參考HashMap），也就是存儲的是Key-Value Pairs（鍵值對）。

2. 這個Map中的Key-Value pair按照Key的二進制順序有序，也就是可以Seek到某一個Key的位置，然后不斷地調(diào)用Next方法，以遞增的順序獲取比這個Key大的Key-Value。

需要注意的是，這里描述的TiKV的KV存儲模型，與SQL中的Table無關(guān)，不要有任何代入。

在圖中TiKV node內(nèi)部，有store、Region的概念，這是高可用的解決方案，TiDB采用了Raft算法實現(xiàn)，這里細(xì)分析。

3.2 TiKV的行存儲結(jié)構(gòu)

在使用Tidb時，依然以傳統(tǒng)“表”的概念進行讀寫，在關(guān)系型數(shù)據(jù)庫中，一個表可能有很多列。而Tidb是以Key-Value形式構(gòu)造數(shù)據(jù)的，因此需要考慮，將一行記錄中，各列數(shù)據(jù)映射成一個key-value鍵值對。

首先，在OLTP場景，有大量針對單行或者多行的增、刪、改、查操作，要求數(shù)據(jù)庫具備快速讀取一行數(shù)據(jù)的能力。因此，對應(yīng)的 Key 最好有一個唯一 ID（顯示或隱式的 ID），以方便快速定位。

其次，很多 OLAP 型查詢需要進行全表掃描。如果能夠?qū)⒁粋€表中所有行的 Key 編碼到一個區(qū)間內(nèi)，就可以通過范圍查詢高效完成全表掃描的任務(wù)。

3.2.1 表數(shù)據(jù)的KV映射

Tidb中表數(shù)據(jù)與Key-Value的映射關(guān)系，設(shè)計如下：

• 為了保證同一個表的數(shù)據(jù)會放在一起，方便查找，TiDB會為每個表分配一個表ID，用TableID表示，整數(shù)、全局唯一。

• TiDB會為每行數(shù)據(jù)分配一個行ID，用RowID表示，整數(shù)、表內(nèi)唯一。如果表有主鍵，則行ID等于主鍵。

基于以上規(guī)則，生成的Key-Value鍵值對為：

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

其中 tablePrefix 和 recordPrefixSep 都是特定的字符串常量，用于在 Key 空間內(nèi)區(qū)分其他數(shù)據(jù)。

這個例子中，是完全基于RowID形成的Key，可以類比MySQL的聚集索引。

3.2.2 索引數(shù)據(jù)的KV映射

對于普通索引，在MySQL中是有非聚集索引概念的，尤其innodb中，通過B+Tree形式，子節(jié)點記錄主鍵信息，再通過回表方式得到結(jié)果數(shù)據(jù)。

在Tidb中是支持創(chuàng)建索引的，那么索引信息如何存儲？ 它同時支持主鍵和二級索引（包括唯一索引和非唯一索引），且與表數(shù)據(jù)映射方式類似。

設(shè)計如下：

• Tidb為表中每個索引，分配了一個索引ID，用IndexID表示。

• 對于主鍵和唯一索引，需要根據(jù)鍵值快速定位到RowID，這個會存儲到value中

因此生成的key-value鍵值對為：

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

由于設(shè)計的key中存在indexedColumnsValue，也就是查詢的字段值，因此可以直接命中或模糊檢索到。再通過value中的RowID，去表數(shù)據(jù)映射中，檢索到RowID對應(yīng)的行記錄。

對于普通索引，一個鍵值可能對應(yīng)多行，需要根據(jù)鍵值范圍查詢對應(yīng)的RowID。

Key: ? tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue_{RowID}Value: null

根據(jù)字段值，可以檢索到具有相關(guān)性的key的列表，在根據(jù)key中包含的RowID，再拿到行記錄。

3.2.3 映射中的常量字符串

上述所有編碼規(guī)則中的 tablePrefix、recordPrefixSep 和 indexPrefixSep 都是字符串常量，用于在 Key 空間內(nèi)區(qū)分其他數(shù)據(jù)，定義如下：

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

在上述映射關(guān)系中，一個表內(nèi)所有的行都有相同的 Key 前綴，一個索引的所有數(shù)據(jù)也都有相同的前綴。這樣具有相同的前綴的數(shù)據(jù)，在 TiKV 的 Key 空間內(nèi)，是排列在一起的。

因此，只需要設(shè)計出穩(wěn)定的后綴，則可以保證表數(shù)據(jù)或索引數(shù)據(jù)，有序的存儲在TiKV中。而有序帶來的價值就是能夠高效的讀取。

3.2.4 舉例

假設(shè)數(shù)據(jù)庫的一張表，如下：

CREATE TABLE User ( ? ?ID int, ? ?Name varchar(20), ? ?Role varchar(20), ? ?Age int, ? ?PRIMARY KEY (ID), ? ?KEY idxAge (Age) );

表中有3行記錄：

1, "TiDB", "SQL Layer", 10 2, "TiKV", "KV Engine", 20 3, "PD", "Manager", 30 4, "TiFlash", "OLAP", 30

這張表中有一個主鍵ID、一個普通索引idxAge，對應(yīng)的是列Age.

假設(shè)該表的TableID=10，則其表數(shù)據(jù)的存儲如下：

t10_r1 --> ["TiDB", "SQL Layer", 10]t10_r2 --> ["TiKV", "KV Engine", 20]t10_r3 --> ["PD", "Manager", 30]t10_r4 --> ["TiFlash", "OLAP", 30]

其普通索引idxAge的存儲如下：

t10_i1_10_1 --> nullt10_i1_20_2 --> nullt10_i1_30_3 --> nullt10_i1_30_4 --> null

3.3 SQL與KV映射

TiDB 的 SQL 層，即 TiDB Server，負(fù)責(zé)將 SQL 翻譯成 Key-Value 操作，將其轉(zhuǎn)發(fā)給共用的分布式 Key-Value 存儲層 TiKV，然后組裝 TiKV 返回的結(jié)果，最終將查詢結(jié)果返回給客戶端。

舉例，“select count(*) from user where name=’tidb’;”這樣的SQL語句，在Tidb中進行檢索，流程如下：

1. 根據(jù)表名、所有的RowID，結(jié)合表數(shù)據(jù)的Key編碼規(guī)則，構(gòu)造出一個[StartKey,endKey)的左閉右開區(qū)間。

2. 根據(jù)[StartKey,endKey)這個區(qū)間內(nèi)的值，到TiKV中讀取數(shù)據(jù)

3. 得到每一行記錄后，過濾出name=’tidb’的數(shù)據(jù)

4. 將結(jié)果進行統(tǒng)計，計算出count(*)的結(jié)果，進行返回。

在分布式環(huán)境下，為了提高檢索效率，實際運行過程中，上述流程是會將name=’tidb’和count( *)下推到集群的每個節(jié)點中，減少無異議的網(wǎng)絡(luò)傳輸，每個節(jié)點最終將count(?*)的結(jié)果，再由SQL層將結(jié)果累加求和。

4 RockDB 持久化

4.1 概述

前文所描述的Key-Value Pairs只是存儲模型，是存在于內(nèi)存中的，任何持久化的存儲引擎，數(shù)據(jù)終歸要保存在磁盤上。TiKV 沒有選擇直接向磁盤上寫數(shù)據(jù)，而是把數(shù)據(jù)保存在 RocksDB 中，具體的數(shù)據(jù)落地由 RocksDB 負(fù)責(zé)。

這個選擇的原因是開發(fā)一個單機存儲引擎工作量很大，特別是要做一個高性能的單機引擎，需要做各種細(xì)致的優(yōu)化，而 RocksDB 是由 Facebook 開源的一個非常優(yōu)秀的單機 KV 存儲引擎，可以滿足 TiKV 對單機引擎的各種要求。這里可以簡單的認(rèn)為 RocksDB 是一個單機的持久化 Key-Value Map。

4.2 RocksDB

TiKV Node的內(nèi)部被劃分成多個Region，這些Region作為數(shù)據(jù)切片，是數(shù)據(jù)一致性的基礎(chǔ)，而TiKV的持久化單元則是Region，也就是每個Region都會被存儲在RocksDB實例中。

以Region為單元，是基于順序I/O的性能考慮的。而TiKV是如何有效的組織Region內(nèi)的數(shù)據(jù)，保證分片均勻、有序，這里面用到了LSM-Tree，如果有HBase經(jīng)驗一定不模式。

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

LSM-Tree（log structured merge-tree）字面意思是“日志結(jié)構(gòu)的合并樹”，LSM-Tree的結(jié)構(gòu)是橫跨磁盤和內(nèi)存的。它將存儲介質(zhì)根據(jù)功能，劃分磁盤的WAL(write ahead log)、內(nèi)存的MemTable、磁盤的SST文件；其中SST文件又分為多層，每一層數(shù)據(jù)達到閾值后，會挑選一部分SST合并到下一層，每一層的數(shù)據(jù)是上一層的10倍，因此90%的數(shù)據(jù)會存儲在最后一層。

WAL：是預(yù)寫Log的實現(xiàn)，當(dāng)進行寫操作時，會將數(shù)據(jù)通過WAL方式備份到磁盤中，防止內(nèi)存斷電而丟失。

Memory-Table：是在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，用以保存最近的一些更新操作；memory-table可以使用跳躍表或者搜索樹等數(shù)據(jù)結(jié)構(gòu)來組織數(shù)據(jù)，以保持?jǐn)?shù)據(jù)的有序性。當(dāng)memory-table達到一定的數(shù)據(jù)量后，memory-table會轉(zhuǎn)化成為immutable memory-table，同時會創(chuàng)建一個新的memory-table來處理新的數(shù)據(jù)。

Immutable Memory-Table：immutable memory-table在內(nèi)存中是不可修改的數(shù)據(jù)結(jié)構(gòu)，它是將memory-table轉(zhuǎn)變?yōu)镾STable的一種中間狀態(tài)。目的是為了在轉(zhuǎn)存過程中不阻塞寫操作。寫操作可以由新的memory-table處理，而不用因為鎖住memory-table而等待。

SST或SSTable：有序鍵值對集合，是LSM樹組在磁盤中的數(shù)據(jù)的結(jié)構(gòu)。如果SSTable比較大的時候，還可以根據(jù)鍵的值建立一個索引來加速SSTable的查詢。SSTable會存在多個，并且按Level設(shè)計，每一層級會存在多個SSTable文件。

4.2.2 LSM-Tree執(zhí)行過程

寫入過程

1. 首先會檢查每個區(qū)域的存儲是否達到閾值，未達到會直接寫入；

2. 如果Immutable Memory-Table存在，會等待其壓縮過程。

3. 如果Memory-Table已經(jīng)寫滿，Immutable Memory-Table 不存在，則將當(dāng)前Memory-Table設(shè)置為Immutable Memory-Table，生成新的Memory-Table，再觸發(fā)壓縮，隨后進行寫入。

4. 寫的過程會先寫入WAL，成功后才會寫Memory-Table，此刻寫入才完成。

數(shù)據(jù)存在的位置，按順序會依次經(jīng)歷WAL、Memory-Table、Immutable Memory-Table、SSTable。其中SSTable是數(shù)據(jù)最終持久化的位置。而事務(wù)性寫入只需要經(jīng)歷WAL和Memory-Table即可完成。

查找過程

1.根據(jù)目標(biāo)key，逐級依次在Memory-Table、Immutable Memory-Table、SSTable中查找
2.其中SSTable會分為幾個級別，也是按Level中進行查找。

• Level-0級別，RocksDB會采用遍歷的方式，所有為了查找效率，會控制Level-0的文件個數(shù)。

• 而Level-1及以上層級的SSTable，數(shù)據(jù)不會存在交疊，且由于存儲有序，會采用二分查找提高效率。

RocksDB為了提高查找效率，每個Memory-Table和SSTable都會有相應(yīng)的Bloom Filter來加快判斷Key是否可能在其中，以減少查找次數(shù)。

刪除和更新過程

當(dāng)有刪除操作時，并不需要像B+樹一樣，在磁盤中的找到相應(yīng)的數(shù)據(jù)后再刪除。

1. 首先會在通過查找流程，在Memory-Table、Immuatble Memory-Table中進行查找。

2. 如果找到則對結(jié)果標(biāo)記為“刪除”。

3. 否則會在結(jié)尾追加一個節(jié)點，并標(biāo)記為“刪除”
   在真正刪除前，未來的查詢操作，都會先找到這個被標(biāo)記為“刪除”的記錄。

4. 之后會在某一時刻，通過壓縮過程真正刪除它。

更新操作和刪除操作類似，都是只操作內(nèi)存區(qū)域的結(jié)構(gòu)，寫入一個標(biāo)志，隨后真正的更新操作被延遲在合并時一并完成。由于操作是發(fā)生在內(nèi)存中，其讀寫性能也能保障。

4.3 RockDB 的優(yōu)缺點

優(yōu)點

1. 將數(shù)據(jù)拆分為幾百M大小的塊，然后順序?qū)懭?/p>

2. 首次寫入的目的地是內(nèi)存，采用WAL設(shè)計思路，加上順序?qū)?，提高寫入的能力，時間復(fù)雜度近似常數(shù)

3. 支持事務(wù)，但L0層的數(shù)據(jù)，key的區(qū)間有重疊，支持較差

缺點

1. 讀寫放大嚴(yán)重

2. 應(yīng)對突發(fā)流量的時候，削峰能力不足

3. 壓縮率有限

4. 索引效率較低

5. 壓縮過程比較消耗系統(tǒng)資源，同時對讀寫影響較大

5 總結(jié)

以上針對TiDB的整體架構(gòu)進行建單介紹，并著重描述了TiKV是如何組織數(shù)據(jù)、如何存儲數(shù)據(jù)。將其Key-Value的設(shè)計思路，與MySQL的索引結(jié)構(gòu)進行對比，識別相似與差異。TiDB依賴RockDB實現(xiàn)了持久化，其中的Lsm-Tree，作為B+Tree的改進結(jié)構(gòu)，其關(guān)注中心是“如何在頻繁的數(shù)據(jù)改動下保持系統(tǒng)讀取速度的穩(wěn)定性”，以順序?qū)懘疟P作為目標(biāo)，假設(shè)頻繁地對數(shù)據(jù)進行整理，力求數(shù)據(jù)的順序性，帶來讀性能的穩(wěn)定，同時也帶來了一定程度的讀寫放大問題。