更新時(shí)間:2023-05-17 來(lái)源:黑馬程序員 瀏覽量:
在這我們將關(guān)系模型簡(jiǎn)單理解為 Table 和 SQL 語(yǔ)句,那么問題變?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è)很重要的問題。一個(gè)好的映射方案必須有利于對(duì)數(shù)據(jù)操作的需求。那么我們先看一下對(duì)數(shù)據(jù)的操作有哪些需求,分別有哪些特點(diǎn)。
對(duì)于一個(gè) Table 來(lái)說(shuō),需要存儲(chǔ)的數(shù)據(jù)包括三部分:
· 表的元信息
· Table 中的 Row
· 索引數(shù)據(jù)
表的元信息我們暫時(shí)不討論,后面介紹。
對(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)行查詢,如 select name from user where id=1; ,這種需要通過(guò)索引快速定位到某一行數(shù)據(jù);另一種是 Range 查詢,如 select name from user where age > 30 and age < 35;,這個(gè)時(shí)候需要通過(guò)idxAge索引查詢 age 在 30 和 35 之間的那些數(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ù),比如 Select * from user;。最后還有通過(guò)索引讀取數(shù)據(jù)的需求,對(duì)索引的使用可能是點(diǎn)查或者是范圍查詢。
大致的需求已經(jīng)分析完了,現(xiàn)在讓我們看看手里有什么可以用的:一個(gè)全局有序的分布式 Key-Value 引擎。全局有序這一點(diǎ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{tableID}_recordPrefixSep{rowID}
Value: [col1, col2, col3, col4]
其中 Key 的 tablePrefix/recordPrefixSep 都是特定的字符串常量,用于在 KV 空間內(nèi)區(qū)分其他數(shù)據(jù)。
對(duì)于 Index 數(shù)據(jù),會(huì)按照如下規(guī)則編碼成 Key-Value pair:
Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
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{tableID}_indexPrefixSep{indexID} 都一樣,可能有多行數(shù)據(jù)的 ColumnsValue 是一樣的,所以對(duì)于非 Unique Index 的編碼做了一點(diǎn)調(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") )
另外請(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é)果保持一致。采用這種編碼后,一個(gè)表的所有 Row 數(shù)據(jù)就會(huì)按照 RowID 的順序排列在 TiKV 的 Key 空間中,某一個(gè) Index 的數(shù)據(jù)也會(huì)按照 Index 的 ColumnValue 順序排列在 Key 空間內(nèi)。
現(xiàn)在我們結(jié)合開始提到的需求以及 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ù)為:
t10_r1 --> ["TiDB", "SQL Layer", 10] t10_r2 --> ["TiKV", "KV Engine", 20] t10_r3 --> ["PD", "Manager", 30]
除了 Primary Key 之外,這個(gè)表還有一個(gè) Index,假設(shè)這個(gè) Index 的 ID 為 1,則其數(shù)據(jù)為:
t10_i1_10_1 --> null t10_i1_20_2 --> null t10_i1_30_3 --> null