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

在這我們將關(guān)系模型簡單理解為 Table 和 SQL 語句，那么問題變?yōu)槿绾卧?KV 結(jié)構(gòu)上保存 Table 以及如何在 KV 結(jié)構(gòu)上運行 SQL 語句。 假設(shè)我們有這樣一個表的定義：

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ū)別，那么如何能夠方便高效地進行映射，就成為一個很重要的問題。一個好的映射方案必須有利于對數(shù)據(jù)操作的需求。那么我們先看一下對數(shù)據(jù)的操作有哪些需求，分別有哪些特點。

對于一個 Table 來說，需要存儲的數(shù)據(jù)包括三部分：

   · 表的元信息

   · Table 中的 Row

   · 索引數(shù)據(jù)

表的元信息我們暫時不討論，后面介紹。

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

對于 Index，TiDB 不止需要支持 Primary Index，還需要支持 Secondary Index。Index 的作用的輔助查詢，提升查詢性能，以及保證某些 Constraint。

查詢的時候有兩種模式，一種是點查，比如通過 Primary Key 或者 Unique Key 的等值條件進行查詢，如 select name from user where id=1; ，這種需要通過索引快速定位到某一行數(shù)據(jù);另一種是 Range 查詢，如 select name from user where age > 30 and age < 35;，這個時候需要通過idxAge索引查詢 age 在 30 和 35 之間的那些數(shù)據(jù)。Index 還分為 Unique Index 和 非 Unique Index，這兩種都需要支持。

分析完需要存儲的數(shù)據(jù)的特點，我們再看看對這些數(shù)據(jù)的操作需求，主要考慮 Insert/Update/Delete/Select 這四種語句。

對于 Insert 語句，需要將 Row 寫入 KV，并且建立好索引數(shù)據(jù)。

對于 Update 語句，需要將 Row 更新的同時，更新索引數(shù)據(jù)(如果有必要)。

對于 Delete 語句，需要在刪除 Row 的同時，將索引也刪除。

上面三個語句處理起來都很簡單。對于 Select 語句，情況會復(fù)雜一些。首先我們需要能夠簡單快速地讀取一行數(shù)據(jù)，所以每個 Row 需要有一個 ID (顯示或隱式的 ID)。其次可能會讀取連續(xù)多行數(shù)據(jù)，比如 Select * from user;。最后還有通過索引讀取數(shù)據(jù)的需求，對索引的使用可能是點查或者是范圍查詢。

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

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

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

Key: tablePrefix{tableID}_recordPrefixSep{rowID}

Value: [col1, col2, col3, col4]

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

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

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue

Value: rowID

Index 數(shù)據(jù)還需要考慮 Unique Index 和非 Unique Index 兩種情況，對于 Unique Index，可以按照上述編碼規(guī)則。但是對于非 Unique Index，通過這種編碼并不能構(gòu)造出唯一的 Key，因為同一個 Index 的 tablePrefix{tableID}_indexPrefixSep{indexID} 都一樣，可能有多行數(shù)據(jù)的 ColumnsValue 是一樣的，所以對于非 Unique Index 的編碼做了一點調(diào)整：

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue_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")
)

另外請大家注意，上述方案中，無論是 Row 還是 Index 的 Key 編碼方案，一個 Table 內(nèi)部所有的 Row 都有相同的前綴，一個 Index 的數(shù)據(jù)也都有相同的前綴。這樣具體相同的前綴的數(shù)據(jù)，在 TiKV 的 Key 空間內(nèi)，是排列在一起。

同時只要我們小心地設(shè)計后綴部分的編碼方案，保證編碼前和編碼后的比較關(guān)系不變，那么就可以將 Row 或者 Index 數(shù)據(jù)有序地保存在 TiKV 中。這種保證編碼前和編碼后的比較關(guān)系不變 的方案我們稱為 Memcomparable，對于任何類型的值，兩個對象

編碼前的原始類型比較結(jié)果，和編碼成 byte 數(shù)組后(注意，TiKV 中的 Key 和 Value 都是原始的 byte 數(shù)組)的比較結(jié)果保持一致。采用這種編碼后，一個表的所有 Row 數(shù)據(jù)就會按照 RowID 的順序排列在 TiKV 的 Key 空間中，某一個 Index 的數(shù)據(jù)也會按照 Index 的 ColumnValue 順序排列在 Key 空間內(nèi)。

現(xiàn)在我們結(jié)合開始提到的需求以及 TiDB 的映射方案來看一下，這個方案是否能滿足需求。

首先我們通過這個映射方案，將 Row 和 Index 數(shù)據(jù)都轉(zhuǎn)換為 Key-Value 數(shù)據(jù)，且每一行、每一條索引數(shù)據(jù)都是有唯一的 Key。

其次，這種映射方案對于點查、范圍查詢都很友好，我們可以很容易地構(gòu)造出某行、某條索引所對應(yīng)的 Key，或者是某一塊相鄰的行、相鄰的索引值所對應(yīng)的 Key 范圍。

最后，在保證表中的一些 Constraint 的時候，可以通過構(gòu)造并檢查某個 Key 是否存在來判斷是否能夠滿足相應(yīng)的 Constraint。

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

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

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

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

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

t10_i1_10_1 --> null
t10_i1_20_2 --> null
t10_i1_30_3 --> null