關系模型到 Key-Value 模型的映射

在這我們將關系模型簡單理解為 Table 和 SQL 語句，那么問題變為如何在 KV 結構上保存 Table 以及如何在 KV 結構上運行 SQL 語句。 假設我們有這樣一個表的定義：

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

SQL 和 KV 結構之間存在巨大的區別，那么如何能夠方便高效地進行映射，就成為一個很重要的問題。一個好的映射方案必須有利于對數據操作的需求。那么我們先看一下對數據的操作有哪些需求，分別有哪些特點。

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

1. 表的元信息
2. Table 中的 Row
3. 索引數據

表的元信息我們暫時不討論，會有專門的章節來介紹。 對于 Row，可以選擇行存或者列存，這兩種各有優缺點。TiDB 面向的首要目標是 OLTP 業務，這類業務需要支持快速地讀取、保存、修改、刪除一行數據，所以采用行存是比較合適的。

對于 Index，TiDB 不止需要支持 Primary Index，還需要支持 Secondary Index。Index 的作用的輔助查詢，提升查詢性能，以及保證某些 Constraint。查詢的時候有兩種模式，一種是點查，比如通過 Primary Key 或者 Unique Key 的等值條件進行查詢，如 select name from user where id=1; ，這種需要通過索引快速定位到某一行數據；另一種是 Range 查詢，如 select name from user where age > 30 and age < 35;，這個時候需要通過idxAge索引查詢 age 在 20 和 30 之間的那些數據。Index 還分為 Unique Index 和 非 Unique Index，這兩種都需要支持。

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

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

對于 Update 語句，需要將 Row 更新的同時，更新索引數據（如果有必要）。

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

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

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

TiDB 對每個表分配一個 TableID，每一個索引都會分配一個 IndexID，每一行分配一個 RowID（如果表有整數型的 Primary Key，那么會用 Primary Key 的值當做 RowID），其中 TableID 在整個集群內唯一，IndexID/RowID 在表內唯一，這些 ID 都是 int64 類型。 每行數據按照如下規則進行編碼成 Key-Value pair：

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

其中 Key 的 tablePrefix/rowPrefix 都是特定的字符串常量，用于在 KV 空間內區分其他數據。 對于 Index 數據，會按照如下規則編碼成 Key-Value pair：

	Key: tablePrefix_idxPrefix_tableID_indexID_indexColumnsValue
	Value: rowID

Index 數據還需要考慮 Unique Index 和非 Unique Index 兩種情況，對于 Unique Index，可以按照上述編碼規則。但是對于非 Unique Index，通過這種編碼并不能構造出唯一的 Key，因為同一個 Index 的 tablePrefix_idxPrefix_tableID_indexID_  都一樣，可能有多行數據的 ColumnsValue  是一樣的，所以對于非 Unique Index 的編碼做了一點調整：

	Key: tablePrefix_idxPrefix_tableID_indexID_ColumnsValue_rowID
	Value：null

這樣能夠對索引中的每行數據構造出唯一的 Key。 注意上述編碼規則中的 Key 里面的各種 xxPrefix 都是字符串常量，作用都是區分命名空間，以免不同類型的數據之間相互沖突，定義如下：

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

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

現在我們結合開始提到的需求以及 TiDB 的映射方案來看一下，這個方案是否能滿足需求。首先我們通過這個映射方案，將 Row 和 Index 數據都轉換為 Key-Value 數據，且每一行、每一條索引數據都是有唯一的 Key。其次，這種映射方案對于點查、范圍查詢都很友好，我們可以很容易地構造出某行、某條索引所對應的 Key，或者是某一塊相鄰的行、相鄰的索引值所對應的 Key 范圍。最后，在保證表中的一些 Constraint 的時候，可以通過構造并檢查某個 Key 是否存在來判斷是否能夠滿足相應的 Constraint。

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

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

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

	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 之外，這個表還有一個 Index，假設這個 Index 的 ID 為 1，則其數據為：

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

大家可以結合上面的編碼規則來理解這個例子，希望大家能理解我們為什么選擇了這個映射方案，這樣做的目的是什么。

元信息管理

上節介紹了表中的數據和索引是如何映射為 KV，本節介紹一下元信息的存儲。Database/Table 都有元信息，也就是其定義以及各項屬性，這些信息也需要持久化，我們也將這些信息存儲在 TiKV 中。每個 Database/Table 都被分配了一個唯一的 ID，這個 ID 作為唯一標識，并且在編碼為 Key-Value 時，這個 ID 都會編碼到 Key 中，再加上 m_ 前綴。這樣可以構造出一個 Key，Value 中存儲的是序列化后的元信息。 除此之外，還有一個專門的 Key-Value 存儲當前 Schema 信息的版本。TiDB 使用 Google F1 的 Online Schema 變更算法，有一個后臺線程在不斷的檢查 TiKV 上面存儲的 Schema 版本是否發生變化，并且保證在一定時間內一定能夠獲取版本的變化（如果確實發生了變化）。這部分的具體實現參見 TiDB 的異步 schema 變更實現一文。

SQL on KV 架構

TiDB 的整體架構如下圖所示

TiKV Cluster 主要作用是作為 KV 引擎存儲數據，上篇文章已經介紹過了細節，這里不再敷述。本篇文章主要介紹 SQL 層，也就是 TiDB Servers 這一層，這一層的節點都是無狀態的節點，本身并不存儲數據，節點之間完全對等。TiDB Server 這一層最重要的工作是處理用戶請求，執行 SQL 運算邏輯，接下來我們做一些簡單的介紹。

SQL 運算

理解了 SQL 到 KV 的映射方案之后，我們可以理解關系數據是如何保存的，接下來我們要理解如何使用這些數據來滿足用戶的查詢需求，也就是一個查詢語句是如何操作底層存儲的數據。 能想到的最簡單的方案就是通過上一節所述的映射方案，將 SQL 查詢映射為對 KV 的查詢，再通過 KV 接口獲取對應的數據，最后執行各種計算。 比如 Select count(*) from user where name="TiDB"; 這樣一個語句，我們需要讀取表中所有的數據，然后檢查 Name 字段是否是 TiDB，如果是的話，則返回這一行。這樣一個操作流程轉換為 KV 操作流程：

• 構造出 Key Range：一個表中所有的 RowID 都在 [0, MaxInt64) 這個范圍內，那么我們用 0 和 MaxInt64 根據 Row 的 Key 編碼規則，就能構造出一個 [StartKey, EndKey) 的左閉右開區間
• 掃描 Key Range：根據上面構造出的 Key Range，讀取 TiKV 中的數據
• 過濾數據：對于讀到的每一行數據，計算 name="TiDB" 這個表達式，如果為真，則向上返回這一行，否則丟棄這一行數據
• 計算 Count：對符合要求的每一行，累計到 Count 值上面 這個方案肯定是可以 Work 的，但是并不能 Work 的很好，原因是顯而易見的：

1. 在掃描數據的時候，每一行都要通過 KV 操作同 TiKV 中讀取出來，至少有一次 RPC 開銷，如果需要掃描的數據很多，那么這個開銷會非常大
2. 并不是所有的行都有用，如果不滿足條件，其實可以不讀取出來
3. 符合要求的行的值并沒有什么意義，實際上這里只需要有幾行數據這個信息就行

分布式 SQL 運算

如何避免上述缺陷也是顯而易見的，首先我們需要將計算盡量靠近存儲節點，以避免大量的 RPC 調用。其次，我們需要將 Filter 也下推到存儲節點進行計算，這樣只需要返回有效的行，避免無意義的網絡傳輸。最后，我們可以將聚合函數、GroupBy 也下推到存儲節點，進行預聚合，每個節點只需要返回一個 Count 值即可，再由 tidb-server 將 Count 值 Sum 起來。 這里有一個數據逐層返回的示意圖：

這里有一篇文章詳細描述了 TiDB 是如何讓 SQL 語句跑的更快，大家可以參考一下。

SQL 層架構

上面幾節簡要介紹了 SQL 層的一些功能，希望大家對 SQL 語句的處理有一個基本的了解。實際上 TiDB 的 SQL 層要復雜的多，模塊以及層次非常多，下面這個圖列出了重要的模塊以及調用關系：

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

小結

到這里，我們已經從 SQL 的角度了解了數據是如何存儲，如何用于計算。SQL 層更詳細的介紹會在今后的文章中給出，比如優化器的工作原理，分布式執行框架的細節。 下一篇文章我們將會介紹一些關于 PD 的信息，這部分會比較有意思，里面的很多東西是在使用 TiDB 過程中看不到，但是對整體集群又非常重要。主要會涉及到集群的管理和調度。

-----------------------------------End[Tony.Tang]2018.3.8------------------------------------------------------------