TiDB 數據庫的計算
TiDB 在 TiKV 提供的分布式存儲能力基礎上，構建了兼具優異的交易處理能力與良好的數據分析能力的計算引擎。本文首先從數據映射算法入手介紹 TiDB 如何將庫表中的數據映射到 TiKV 中的 (Key, Value) 鍵值對，然后描述 TiDB 元信息管理方式，最后介紹 TiDB SQL 層的主要架構。
對于計算層依賴的存儲方案，本文只介紹基于 TiKV 的行存儲結構。針對分析型業務的特點，TiDB 推出了作為 TiKV 擴展的列存儲方案 。
表數據與 Key-Value 的映射關系
本小節介紹 TiDB 中數據到 (Key, Value) 鍵值對的映射方案。這里的數據主要包括以下兩個方面：
表數據與 Key-Value 的映射關系
在關系型數據庫中，一個表可能有很多列。要將一行中各列數據映射成一個 (Key, Value) 鍵值對，需要考慮如何構造 Key。首先，OLTP 場景下有大量針對單行或者多行的增、刪、改、查等操作，要求數據庫具備快速讀取一行數據的能力。因此，對應的 Key 最好有一個唯一 ID（顯示或隱式的 ID），以方便快速定位。其次，很多 OLAP 型查詢需要進行全表掃描。如果能夠將一個表中所有行的 Key 編碼到一個區間內，就可以通過范圍查詢高效完成全表掃描的任務。
基于上述考慮，TiDB 中的表數據與 Key-Value 的映射關系作了如下設計：
每行數據按照如下規則編碼成 (Key, Value) 鍵值對：
Key: tablePrefix{TableID}_recordPrefixSep{RowID}Value: [col1, col2, col3, col4]
其中 和 都是特定的字符串常量，用于在 Key 空間內區分其他數據。其具體值在后面的小結中給出。
索引數據和 Key-Value 的映射關系
TiDB 同時支持主鍵和二級索引（包括唯一索引和非唯一索引）。與表數據映射方案類似，TiDB 為表中每個索引分配了一個索引 ID，用 表示。
對于主鍵和唯一索引，需要根據鍵值快速定位到對應的 RowID，因此，按照如下規則編碼成 (Key, Value) 鍵值對：
Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValueValue: RowID
對于不需要滿足唯一性約束的普通二級索引，一個鍵值可能對應多行，需要根據鍵值范圍查詢對應的 RowID。因此，按照如下規則編碼成 (Key, Value) 鍵值對：
Key: tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue_{RowID}Value: null
映射關系小結
上述所有編碼規則中的 、 和 都是字符串常量，用于在 Key 空間內區分其他數據，定義如下：
tablePrefix = []byte{'t'}recordPrefixSep = []byte{'r'}indexPrefixSep = []byte{'i'}
另外請注意，上述方案中，無論是表數據還是索引數據的 Key 編碼方案，一個表內所有的行都有相同的 Key 前綴，一個索引的所有數據也都有相同的前綴。這樣具有相同的前綴的數據，在 TiKV 的 Key 空間內，是排列在一起的。因此只要小心地設計后綴部分的編碼方案，保證編碼前和編碼后的比較關系不變，就可以將表數據或者索引數據有序地保存在 TiKV 中。采用這種編碼后，一個表的所有行數據會按照 RowID 順序地排列在 TiKV 的 Key 空間中，某一個索引的數據也會按照索引數據的具體的值（編碼方案中的 ）順序地排列在 Key 空間內。
Key-Value 映射關系示例
最后通過一個簡單的例子，來理解 TiDB 的 Key-Value 映射關系。假設 TiDB 中有如下這個表：
CREATE TABLE User (ID int,Name varchar(20),Role varchar(20),Age int,PRIMARY KEY (ID),KEY idxAge (Age));
假設該表中有 3 行數據：
1, "TiDB", "SQL Layer", 102, "TiKV", "KV Engine", 203, "PD", "Manager", 30
首先每行數據都會映射為一個 (Key, Value) 鍵值對，同時該表有一個 int 類型的主鍵，所以 RowID 的值即為該主鍵的值。假設該表的 為 10，則其存儲在 TiKV 上的表數據為：
t10_r1 --> ["TiDB", "SQL Layer", 10]t10_r2 --> ["TiKV", "KV Engine", 20]t10_r3 --> ["PD", "Manager", 30]
除了主鍵外，該表還有一個非唯一的普通二級索引 ，假設這個索引的 為 1，則其存儲在 TiKV 上的索引數據為：
t10_i1_10_1 --> nullt10_i1_20_2 --> nullt10_i1_30_3 --> null
以上例子展示了 TiDB 中關系模型到 Key-Value 模型的映射規則，以及選擇該方案背后的考量。
元信息管理
TiDB 中每個 和 Table 都有元信息，也就是其定義以及各項屬性。這些信息也需要持久化，TiDB 將這些信息也存儲在了 TiKV 中。
每個 /Table 都被分配了一個唯一的 ID，這個 ID 作為唯一標識sql 數據庫關系圖，并且在編碼為 Key-Value 時，這個 ID 都會編碼到 Key 中，再加上 m_ 前綴。這樣可以構造出一個 Key，Value 中存儲的是序列化后的元信息。
除此之外，TiDB 還用一個專門的 (Key, Value) 鍵值對存儲當前所有表結構信息的最新版本號。這個鍵值對是全局的，每次 DDL 操作的狀態改變時其版本號都會加 1。目前，TiDB 把這個鍵值對持久化存儲在 PD 中，其 Key 是 “/tidb/ddl/n”，Value 是類型為 int64 的版本號值。TiDB 采用 變更算法，有一個后臺線程在不斷地檢查 PD 中存儲的表結構信息的版本號是否發生變化，并且保證在一定時間內一定能夠獲取版本的變化。
SQL 層簡介
TiDB 的 SQL 層，即 TiDB ，負責將 SQL 翻譯成 Key-Value 操作，將其轉發給共用的分布式 Key-Value 存儲層 TiKV，然后組裝 TiKV 返回的結果，最終將查詢結果返回給客戶端。
這一層的節點都是無狀態的，節點本身并不存儲數據，節點之間完全對等。
SQL 運算
最簡單的方案就是通過上一節所述的方案，將 SQL 查詢映射為對 KV 的查詢，再通過 KV 接口獲取對應的數據，最后執行各種計算。
比如 count(*) from user where name = "TiDB" 這樣一個 SQL 語句，它需要讀取表中所有的數據，然后檢查 name 字段是否是 TiDB，如果是的話，則返回這一行。具體流程如下：
構造出 Key Range：一個表中所有的 RowID 都在 [0, ) 這個范圍內，使用 0 和 根據行數據的 Key 編碼規則，就能構造出一個 [, )的左閉右開區間。掃描 Key Range：根據上面構造出的 Key Range，讀取 TiKV 中的數據。過濾數據：對于讀到的每一行數據，計算 name = "TiDB" 這個表達式，如果為真，則向上返回這一行，否則丟棄這一行數據。計算 Count(*)：對符合要求的每一行，累計到 Count(*) 的結果上面。
整個流程示意圖如下：
這個方案是直觀且可行的，但是在分布式數據庫的場景下有一些顯而易見的問題：
分布式 SQL 運算
為了解決上述問題，計算應該需要盡量靠近存儲節點，以避免大量的 RPC 調用。首先，SQL 中的謂詞條件 name = "TiDB" 應被下推到存儲節點進行計算，這樣只需要返回有效的行，避免無意義的網絡傳輸。然后，聚合函數 Count(*) 也可以被下推到存儲節點，進行預聚合，每個節點只需要返回一個 Count(*) 的結果即可，再由 SQL 層將各個節點返回的 Count(*) 的結果累加求和。
以下是數據逐層返回的示意圖：
SQL 層架構
通過上面的例子，希望大家對 SQL 語句的處理有一個基本的了解。實際上 TiDB 的 SQL 層要復雜得多，模塊以及層次非常多，下圖列出了重要的模塊以及調用關系：
用戶的 SQL 請求會直接或者通過 Load 發送到 TiDB ，TiDB 會解析 MySQL ，獲取請求內容，對 SQL 進行語法解析和語義分析，制定和優化查詢計劃sql 數據庫關系圖，執行查詢計劃并獲取和處理數據。數據全部存儲在 TiKV 集群中，所以在這個過程中 TiDB 需要和 TiKV 交互，獲取數據。最后 TiDB 需要將查詢結果返回給用戶。