考慮做一個存儲系統(tǒng)，首先要考慮的就是數(shù)據(jù)的存儲模型。TiKV選擇的是Key-Value模型，并且這個模型提供有序遍歷的方法。簡單來講，TiKV就是一個巨大的Map，其中Key和Value都是原始的Byte數(shù)組，在這個Map中，Key按照Byte數(shù)組二進(jìn)制比特位比較排列。

• TiKV是一個巨大的Map，存儲的是Key-Value Pair。
• TiKV Map中的Key-Value pair按照Key的二進(jìn)制順序有序?？梢?code>Seek到某一個Key的位置，然后不斷的調(diào)用Next方法，以遞增的順序獲取比這個Key大的Key-Value。

實現(xiàn)上，TiKV沒有直接向磁盤上寫數(shù)據(jù)，而是把數(shù)據(jù)寫入RocksDB中，具體的數(shù)據(jù)落地由RocksDB負(fù)責(zé)?？梢院唵蔚恼J(rèn)為，TiKV是一個分布式Key-Value Map，RocksDB是一個單機的Key-Value Map。

有了這個存儲模型，接下來就需要考慮如何在KV模型上保存關(guān)系型數(shù)據(jù)以及如何在KV上運行SQL語句。

一、SQL到KV模型的存儲

創(chuàng)建一個表結(jié)構(gòu)：

CREATE TABLE User {
        ID int,
        Age int,
        Name varchar(20),
        Gender varchar(20),
        PRIMARY KEY (ID),
        UNIQUE index idxName (Name),  //唯一索引
        index idxGender (Gender)
};

接著插入數(shù)據(jù)：

image.png

那么到底需要存儲哪些數(shù)據(jù)，做哪些映射？為了方便理解，我們拿SQL到B+樹模型（MySQL默認(rèn)數(shù)據(jù)引擎InnoDB數(shù)據(jù)存儲模型）來做說明。

1.表數(shù)據(jù)以及主索引存儲

InnoDB中，表數(shù)據(jù)本身就是按B+樹組織的一個索引結(jié)構(gòu)，B+樹葉節(jié)點的data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)本身就是主索引。表數(shù)據(jù)以及主索引實際存儲如下圖：

image.png

TiDB也采用了這個方式，即表數(shù)據(jù)本身也就是主索引。data域即value:[col1,col2,col3,col4]保存完整的數(shù)據(jù)記錄，這里的難點是key的設(shè)計。
TiKV使用了RocksDB的Column Families(CF)特性，默認(rèn) RocksDB 實例將 KV 數(shù)據(jù)存儲在內(nèi)部的 default、write 和 lock 3 個 CF 內(nèi)：

• default CF存儲的是真正的數(shù)據(jù)，與其對應(yīng)的參數(shù)位于[rocksdb.defaultcf]項中；
• write CF存儲的是數(shù)據(jù)的版本信息 (MVCC)以及索引相關(guān)的數(shù)據(jù)，相關(guān)的參數(shù)位于[rocksdb.writecf]項中；
• lock CF存儲的是鎖信息，系統(tǒng)使用默認(rèn)參數(shù)。

表數(shù)據(jù)文件數(shù)據(jù)存儲在rocksdb.defaultcf中，索引存儲在rocksdb.writecf。所以KEY中需要包含識別Database/Table的tableID，識別的行的rowID(Primary Key)，識別索引的indexID。每行數(shù)據(jù)按照規(guī)則進(jìn)行編碼成KV pair:

Key: tablePrefix{tableID}_recordPrefixSep{rowID}
Value: [col1,col2,col3,col4]

注：tablePrefix/recordPrefixSep 都是特定的字符串常量，用于區(qū)分其他數(shù)據(jù)。

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

假設(shè)TiDB分配的tableId為10，表數(shù)據(jù)以及主索引實際存儲如下：

t10_r15--->[34,Bob,Female]
t10_r18--->[77,Alice,Male]
t10_r20--->[5,Jim,Female]
t10_r30--->[91,Eric,Female]
t10_r49--->[22,Tom,Male]
t10_r50--->[89,Rose,Male]

2.輔助索引存儲

InnoDB中除了主索引以外還有輔助索引。InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值，而不是完整的數(shù)據(jù)記錄。主索引key是唯一的，而輔助索引的key可以重復(fù)。但是B+樹要求鍵的值必須唯一，所以這里把輔助鍵的值和主鍵的值合并起來作為在B+樹中的真正鍵值，保證了唯一性。輔助索引存儲如下圖：

image.png

TiDB與InnoDB輔助索引的設(shè)計基本保持一致，但是區(qū)分了重復(fù)輔助索引和唯一輔助索引，并且為每個輔助索引分配了一個indexID。
唯一輔助索引：

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
Value: rowID

假設(shè)TiDB分配的tableID為10，indexID為1。Unique索引indexName實際存儲為：

t10_r1_Bob--->15
t10_r1_Alice--->18
......

重復(fù)輔助索引：

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue_rowID
Value: null

假設(shè)TiDB分配的tableId為10，indexID為2。索引idxGender實際存儲為：

t10_r2_Fmale_15--->null
t10_r2_Male_18--->null
......

3.表結(jié)構(gòu)存儲

每個Database/Table都被分配了一個唯一的ID，這個ID作為唯一標(biāo)識，并且在編碼為Key-Value時，這個ID會編碼到Key中，加上m前綴。這樣可以構(gòu)造出一個Key，Value中存儲的是序列化后的元信息。一對KV pair就可以表示一個表結(jié)構(gòu)信息：

Key: tableMetaPrefix{tableID}
value:[TableName,cloName,cloName,colName,colName]

假設(shè)TiDB分配的tableId為10,實際表結(jié)構(gòu)存儲為：

m10--->[User,ID,Age,Name,Gender]

二 、SQL到kv模型的查詢映射

前面提到，將TiKV看做一個巨大的有序的KV Map，那么為了實現(xiàn)存儲的水平擴展，需要將數(shù)據(jù)分散在多臺機器上。對于一個KV系統(tǒng)，將數(shù)據(jù)分散在多臺機器上有兩種比較典型的方案：一種是按照Key做Hash，根據(jù)Hash值選擇對應(yīng)的存儲節(jié)點；另一種是分Range，某一段連續(xù)的Key都保存在一個存儲節(jié)點上。TiKV選擇了第二種方式，將整個Key-Value空間分成很多段，每一段是一系列連續(xù)的Key，我們將每一段叫做一個Region，并且會盡量保持每個Region中保存的數(shù)據(jù)不超過一定的大小(這個大小可以配置，目前默認(rèn)是64mb)。每一個Region都可以用StartKey到EndKey這樣一個左閉右開區(qū)間來描述。也就是說上面的數(shù)據(jù)在實際存儲中，按Region劃分，是存儲在不同的TiKV的Node中。如下圖所示：

image.png

當(dāng)對這個表執(zhí)行一條SQL語句Select count(*) from User where id > 0 and id < 90時，數(shù)據(jù)不再分布在一臺物理機上，而是分布在3個物理機上。分布式SQL操作如下：

1. 構(gòu)造Key Range區(qū)間（主鍵ID劃分）。區(qū)間：[0,20)，[20,40)，[40,60)…
2. 獲取key Range所在Tikv節(jié)點。
3. 優(yōu)化執(zhí)行計劃。即將where條件與count(*)，一起推到相應(yīng)的Tikv節(jié)點。
4. 每個Tikv節(jié)點過濾數(shù)據(jù)，計算count(*)。
5. TiDB Server將每個Tikv節(jié)點計算count(*)，合并起來計算。
   
   image.png

以上就是一個分布式的SQL計算，很明顯它是不同于MySQL的SQL查詢。不管是NewSQL數(shù)據(jù)庫還是傳統(tǒng)數(shù)據(jù)庫，都會對 optimizer進(jìn)行優(yōu)化。上面對count(*)的優(yōu)化設(shè)計，一方面增加了計算并行度，同時也減少了網(wǎng)絡(luò)交互。TiDB在優(yōu)化方面做了很多工作，比如常量折疊、常量傳播、JOIN選擇等，并且有一個框架去統(tǒng)計下層數(shù)據(jù)信息，在此基礎(chǔ)上繼續(xù)做優(yōu)化。具體優(yōu)化可以參考MPP and SMP in TiDB。

三、TiDB SQL層框架

上面主要介紹了SQL到KV存儲映射以及SQL分布式計算相關(guān)功能，讓我們從SQL的角度去了解數(shù)據(jù)是如何存儲，SQL是如何計算執(zhí)行的。這些都是在SQL層框架中實現(xiàn)的。實際TiDB的SQL層非常復(fù)雜，涉及到很多優(yōu)化器分布原理，分布框架執(zhí)行的細(xì)節(jié)，是TiDB中比較復(fù)雜的模塊。下圖列出了重要的模塊以及調(diào)用關(guān)系（部分來圖來自網(wǎng)絡(luò)）：

image.png

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