在上一篇文章中，我們介紹了 TiDB 如何存儲(chǔ)數(shù)據(jù)，也就是 TiKV 的一些基本概念。本篇將介紹 TiDB 如何利用底層的KV存儲(chǔ)，將關(guān)系模型映射為Key-Value 模型，以及如何進(jìn)行SQL計(jì)算。

[[192996]]

關(guān)系模型到 Key-Value 模型的映射

在這我們將關(guān)系模型簡(jiǎn)單理解為 Table 和 SQL 語(yǔ)句，那么問(wèn)題變?yōu)槿绾卧?KV 結(jié)構(gòu)上保存 Table 以及如何在 KV 結(jié)構(gòu)上運(yùn)行 SQL 語(yǔ)句。

假設(shè)我們有這樣一個(gè)表的定義：

CREATE TABLE User { 
    ID int, 
    Name varchar(20), 
    Role varchar(20), 
    Age int, 
    PRIMARY KEY (ID)， 
    Key idxAge (age) 
}; 

SQL 和 KV 結(jié)構(gòu)之間存在巨大的區(qū)別，那么如何能夠方便高效地進(jìn)行映射，就成為一個(gè)很重要的問(wèn)題。一個(gè)好的映射方案必須有利于對(duì)數(shù)據(jù)操作的需求。那么我們先看一下對(duì)數(shù)據(jù)的操作有哪些需求，分別有哪些特點(diǎn)。

對(duì)于一個(gè) Table 來(lái)說(shuō)，需要存儲(chǔ)的數(shù)據(jù)包括三部分：

1. 表的元信息
2. Table 中的 Row
3. 索引數(shù)據(jù)

表的元信息我們暫時(shí)不討論，會(huì)有專門的章節(jié)來(lái)介紹。

對(duì)于 Row，可以選擇行存或者列存，這兩種各有優(yōu)缺點(diǎn)。TiDB 面向的首要目標(biāo)是 OLTP 業(yè)務(wù)，這類業(yè)務(wù)需要支持快速地讀取、保存、修改、刪除一行數(shù)據(jù)，所以采用行存是比較合適的。

對(duì)于 Index，TiDB 不只需要支持 Primary Index，還需要支持 Secondary Index。Index 的作用的輔助查詢，提升查詢性能，以及保證某些 Constraint。查詢的時(shí)候有兩種模式，一種是點(diǎn)查，比如通過(guò) Primary Key 或者 Unique Key 的等值條件進(jìn)行查詢，

這種需要通過(guò)索引快速定位到某一行數(shù)據(jù);另一種是 Range 查詢，

這個(gè)時(shí)候需要通過(guò) idxAge 索引查詢 age 在 20 和 30 之間的那些數(shù)據(jù)。Index 還分為 Unique Index 和 非 Unique Index，這兩種都需要支持。

分析完需要存儲(chǔ)的數(shù)據(jù)的特點(diǎn)，我們?cè)倏纯磳?duì)這些數(shù)據(jù)的操作需求，主要考慮 Insert/Update/Delete/Select 這四種語(yǔ)句。

• 對(duì)于 Insert 語(yǔ)句，需要將 Row 寫入 KV，并且建立好索引數(shù)據(jù)。
• 對(duì)于 Update 語(yǔ)句，需要將 Row 更新的同時(shí)，更新索引數(shù)據(jù)(如果有必要)。
• 對(duì)于 Delete 語(yǔ)句，需要在刪除 Row 的同時(shí)，將索引也刪除。

上面三個(gè)語(yǔ)句處理起來(lái)都很簡(jiǎn)單。對(duì)于 Select 語(yǔ)句，情況會(huì)復(fù)雜一些。首先我們需要能夠簡(jiǎn)單快速地讀取一行數(shù)據(jù)，所以每個(gè) Row 需要有一個(gè) ID (顯示或隱式的 ID)。其次可能會(huì)讀取連續(xù)多行數(shù)據(jù)，

***還有通過(guò)索引讀取數(shù)據(jù)的需求，對(duì)索引的使用可能是點(diǎn)查或者是范圍查詢。

大致的需求已經(jīng)分析完了，現(xiàn)在讓我們看看手里有什么可以用的：一個(gè)全局有序的分布式 Key-Value 引擎。全局有序這一點(diǎn)重要，可以幫助我們解決不少問(wèn)題。比如對(duì)于快速獲取一行數(shù)據(jù)，假設(shè)我們能夠構(gòu)造出某一個(gè)或者某幾個(gè) Key，定位到這一行，我們就能利用 TiKV 提供的 Seek 方法快速定位到這一行數(shù)據(jù)所在位置。再比如對(duì)于掃描全表的需求，如果能夠映射為一個(gè) Key 的 Range，從 StartKey 掃描到 EndKey，那么就可以簡(jiǎn)單的通過(guò)這種方式獲得全表數(shù)據(jù)。操作 Index 數(shù)據(jù)也是類似的思路。接下來(lái)讓我們看看 TiDB 是如何做的。

TiDB 對(duì)每個(gè)表分配一個(gè) TableID，每一個(gè)索引都會(huì)分配一個(gè) IndexID，每一行分配一個(gè) RowID(如果表有整數(shù)型的 Primary Key，那么會(huì)用 Primary Key 的值當(dāng)做 RowID)，其中 TableID 在整個(gè)集群內(nèi)唯一，IndexID/RowID 在表內(nèi)唯一，這些 ID 都是 int64 類型。

每行數(shù)據(jù)按照如下規(guī)則進(jìn)行編碼成 Key-Value pair：

Key： tablePrefix_rowPrefix_tableID_rowID 
Value: [col1, col2, col3, col4] 

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

對(duì)于 Index 數(shù)據(jù)，會(huì)按照如下規(guī)則編碼成 Key-Value pair：

Key: tablePrefix_idxPrefix_tableID_indexID_indexColumnsValue 
Value: rowID 

Index 數(shù)據(jù)還需要考慮 Unique Index 和非 Unique Index 兩種情況，對(duì)于 Unique Index，可以按照上述編碼規(guī)則。但是對(duì)于非 Unique Index，通過(guò)這種編碼并不能構(gòu)造出唯一的 Key，因?yàn)橥粋€(gè) Index 的 tablePrefix_idxPrefix_tableID_indexID_ 都一樣，可能有多行數(shù)據(jù)的ColumnsValue 是一樣的，所以對(duì)于非 Unique Index 的編碼做了一點(diǎn)調(diào)整：

Key: tablePrefix_idxPrefix_tableID_indexID_ColumnsValue_rowID 
Value：null 

這樣能夠?qū)λ饕械拿啃袛?shù)據(jù)構(gòu)造出唯一的 Key。

注意上述編碼規(guī)則中的 Key 里面的各種 xxPrefix 都是字符串常量，作用都是區(qū)分命名空間，以免不同類型的數(shù)據(jù)之間相互沖突，定義如下：

var( 
    tablePrefix     = []byte{'t'} 
    recordPrefixSep = []byte("_r") 
    indexPrefixSep  = []byte("_i") 
) 

另外請(qǐng)大家注意，上述方案中，無(wú)論是 Row 還是 Index 的 Key 編碼方案，一個(gè) Table 內(nèi)部所有的 Row 都有相同的前綴，一個(gè) Index 的數(shù)據(jù)也都有相同的前綴。這樣具體相同的前綴的數(shù)據(jù)，在 TiKV 的 Key 空間內(nèi)，是排列在一起。同時(shí)只要我們小心地設(shè)計(jì)后綴部分的編碼方案，保證編碼前和編碼后的比較關(guān)系不變，那么就可以將 Row 或者 Index 數(shù)據(jù)有序地保存在 TiKV 中。這種保證編碼前和編碼后的比較關(guān)系不變的方案我們稱為 Memcomparable，對(duì)于任何類型的值，兩個(gè)對(duì)象編碼前的原始類型比較結(jié)果，和編碼成 byte 數(shù)組后(注意，TiKV 中的 Key 和 Value 都是原始的 byte 數(shù)組)的比較結(jié)果保持一致。具體的編碼方案參見(jiàn) TiDB 的codec 包 。采用這種編碼后，一個(gè)表的所有 Row 數(shù)據(jù)就會(huì)按照 RowID 的順序排列在 TiKV 的 Key 空間中，某一個(gè) Index 的數(shù)據(jù)也會(huì)按照 Index 的 ColumnValue 順序排列在 Key 空間內(nèi)。

現(xiàn)在我們結(jié)合開(kāi)始提到的需求以及 TiDB 的映射方案來(lái)看一下，這個(gè)方案是否能滿足需求。首先我們通過(guò)這個(gè)映射方案，將 Row 和 Index 數(shù)據(jù)都轉(zhuǎn)換為 Key-Value 數(shù)據(jù)，且每一行、每一條索引數(shù)據(jù)都是有唯一的 Key。其次，這種映射方案對(duì)于點(diǎn)查、范圍查詢都很友好，我們可以很容易地構(gòu)造出某行、某條索引所對(duì)應(yīng)的 Key，或者是某一塊相鄰的行、相鄰的索引值所對(duì)應(yīng)的 Key 范圍。***，在保證表中的一些 Constraint 的時(shí)候，可以通過(guò)構(gòu)造并檢查某個(gè) Key 是否存在來(lái)判斷是否能夠滿足相應(yīng)的 Constraint。

至此我們已經(jīng)聊完了如何將 Table 映射到 KV 上面，這里再舉個(gè)簡(jiǎn)單的例子，便于大家理解，還是以上面的表結(jié)構(gòu)為例。假設(shè)表中有 3 行數(shù)據(jù)：

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

那么首先每行數(shù)據(jù)都會(huì)映射為一個(gè) Key-Value pair，注意這個(gè)表有一個(gè) Int 類型的 Primary Key，所以 RowID 的值即為這個(gè) Primary Key 的值。假設(shè)這個(gè)表的 Table ID 為 10，其 Row 的數(shù)據(jù)為：

t_r_10_1  --> ["TiDB", "SQL Layer", 10] 
t_r_10_2 --> ["TiKV", "KV Engine", 20] 
t_r_10_3 --> ["PD", "Manager", 30] 

除了 Primary Key 之外，這個(gè)表還有一個(gè) Index，假設(shè)這個(gè) Index 的 ID 為 1，則其數(shù)據(jù)為：

t_i_10_1_10_1 —> null 
t_i_10_1_20_2 --> null 
t_i_10_1_30_3 --> null 

大家可以結(jié)合上述編碼規(guī)則來(lái)理解上面這個(gè)例子，希望大家能理解我們?yōu)槭裁催x擇了這個(gè)映射方案，這樣做的目的是什么。

元信息管理

上節(jié)介紹了表中的數(shù)據(jù)和索引是如何映射為 KV，本節(jié)介紹一下元信息的存儲(chǔ)。Database/Table 都有元信息，也就是其定義以及各項(xiàng)屬性，這些信息也需要持久化，我們也將這些信息存儲(chǔ)在 TiKV 中。每個(gè) Database/Table 都被分配了一個(gè)唯一的 ID，這個(gè) ID 作為唯一標(biāo)識(shí)，并且在編碼為 Key-Value 時(shí)，這個(gè) ID 都會(huì)編碼到 Key 中，再加上 m_ 前綴。這樣可以構(gòu)造出一個(gè) Key，對(duì)應(yīng)的 Value 中存儲(chǔ)的是序列化后的元信息。


除此之外，還有一個(gè)專門的 Key-Value 存儲(chǔ)當(dāng)前 Schema 信息的版本。TiDB 使用 Google F1 的 Online Schema 變更算法，有一個(gè)后臺(tái)線程在不斷的檢查 TiKV 上面存儲(chǔ)的 Schema 版本是否發(fā)生變化，并且保證在一定時(shí)間內(nèi)一定能夠獲取版本的變化(如果確實(shí)發(fā)生了變化)。

SQL on KV 架構(gòu)

TiDB 的整體架構(gòu)如下圖所示：

TiKV Cluster 主要作用是作為 KV 引擎存儲(chǔ)數(shù)據(jù)，上篇文章已經(jīng)介紹過(guò)了細(xì)節(jié)，這里不再敷述。本篇文章主要介紹 SQL 層，也就是 TiDB Servers 這一層，這一層的節(jié)點(diǎn)都是無(wú)狀態(tài)的節(jié)點(diǎn)，本身并不存儲(chǔ)數(shù)據(jù)，節(jié)點(diǎn)之間完全對(duì)等。TiDB Server 這一層最重要的工作是處理用戶請(qǐng)求，執(zhí)行 SQL 運(yùn)算邏輯，接下來(lái)我們做一些簡(jiǎn)單的介紹。

SQL 運(yùn)算

理解了 SQL 到 KV 的映射方案之后，我們可以理解關(guān)系數(shù)據(jù)是如何保存的，接下來(lái)我們要理解如何使用這些數(shù)據(jù)來(lái)滿足用戶的查詢需求，也就是一個(gè)查詢語(yǔ)句是如何操作底層存儲(chǔ)的數(shù)據(jù)。

能想到的最簡(jiǎn)單的方案就是通過(guò)上一節(jié)所述的映射方案，將 SQL 查詢映射為對(duì) KV 的查詢，再通過(guò) KV 接口獲取對(duì)應(yīng)的數(shù)據(jù)，***執(zhí)行各種計(jì)算。

這樣一個(gè)語(yǔ)句，我們需要讀取表中所有的數(shù)據(jù)，然后檢查 Name 字段是否是 TiDB，如果是的話，則返回這一行。這樣一個(gè)操作流程轉(zhuǎn)換為 KV 操作流程：

• 構(gòu)造出 Key Range：一個(gè)表中所有的 RowID 都在 [0, MaxInt64) 這個(gè)范圍內(nèi)，那么我們用 0 和 MaxInt64 根據(jù) Row 的 Key 編碼規(guī)則，就能構(gòu)造出一個(gè) [StartKey, EndKey) 的左閉右開(kāi)區(qū)間

• 掃描 Key Range：根據(jù)上面構(gòu)造出的 Key Range，讀取 TiKV 中的數(shù)據(jù)

• 過(guò)濾數(shù)據(jù)：對(duì)于讀到的每一行數(shù)據(jù)，計(jì)算 name="TiDB" 這個(gè)表達(dá)式，如果為真，則向上返回這一行，否則丟棄這一行數(shù)據(jù)

• 計(jì)算 Count：對(duì)符合要求的每一行，累計(jì)到 Count 值上面


這個(gè)方案肯定是可以 Work 的，但是并不能 Work 的很好，原因是顯而易見(jiàn)的：

1. 在掃描數(shù)據(jù)的時(shí)候，每一行都要通過(guò) KV 操作同 TiKV 中讀取出來(lái)，至少有一次 RPC 開(kāi)銷，如果需要掃描的數(shù)據(jù)很多，那么這個(gè)開(kāi)銷會(huì)非常大;
2. 并不是所有的行都有用，如果不滿足條件，其實(shí)可以不讀取出來(lái);
3. 符合要求的行的值并沒(méi)有什么意義，實(shí)際上這里只需要有幾行數(shù)據(jù)這個(gè)信息就行。

分布式 SQL 運(yùn)算

如何避免上述缺陷也是顯而易見(jiàn)的，首先我們需要將計(jì)算盡量靠近存儲(chǔ)節(jié)點(diǎn)，以避免大量的 RPC 調(diào)用。其次，我們需要將 Filter 也下推到存儲(chǔ)節(jié)點(diǎn)進(jìn)行計(jì)算，這樣只需要返回有效的行，避免無(wú)意義的網(wǎng)絡(luò)傳輸。***，我們可以將聚合函數(shù)、GroupBy 也下推到存儲(chǔ)節(jié)點(diǎn)，進(jìn)行預(yù)聚合，每個(gè)節(jié)點(diǎn)只需要返回一個(gè) Count 值即可，再由 tidb-server 將 Count 值 Sum 起來(lái)。

這里有一個(gè)數(shù)據(jù)逐層返回的示意圖：

SQL 層架構(gòu)

上面幾節(jié)簡(jiǎn)要介紹了 SQL 層的一些功能，希望大家對(duì) SQL 語(yǔ)句的處理有一個(gè)基本的了解。實(shí)際上 TiDB 的 SQL 層要復(fù)雜的多，模塊以及層次非常多，下面這個(gè)圖列出了重要的模塊以及調(diào)用關(guān)系：

用戶的 SQL 請(qǐng)求會(huì)直接或者通過(guò) Load Balancer 發(fā)送到 tidb-server，tidb-server 會(huì)解析 MySQL Protocol Packet，獲取請(qǐng)求內(nèi)容，然后做語(yǔ)法解析、查詢計(jì)劃制定和優(yōu)化、執(zhí)行查詢計(jì)劃獲取和處理數(shù)據(jù)。數(shù)據(jù)全部存儲(chǔ)在 TiKV 集群中，所以在這個(gè)過(guò)程中 tidb-server 需要和 tikv-server 交互，獲取數(shù)據(jù)。*** tidb-server 需要將查詢結(jié)果返回給用戶。

小結(jié)

到這里，我們已經(jīng)從 SQL 的角度了解了數(shù)據(jù)是如何存儲(chǔ)，如何用于計(jì)算。SQL 層更詳細(xì)的介紹會(huì)在今后的文章中給出，比如優(yōu)化器的工作原理，分布式執(zhí)行框架的細(xì)節(jié)。

下一篇文章我們將會(huì)介紹一些關(guān)于 PD 的信息，這部分會(huì)比較有意思，里面的很多東西是在使用 TiDB 過(guò)程中看不到，但是對(duì)整體集群又非常重要。主要會(huì)涉及到集群的管理和調(diào)度。

【本文是51CTO專欄作者“PingCAP”的原創(chuàng)文章，轉(zhuǎn)載請(qǐng)聯(lián)系作者本人獲取授權(quán)】

戳這里，看該作者更多好文