關(guān)系模型到 Key-Value 模型的映射
在這我們將關(guān)系模型簡單理解為 Table 和 SQL 語句,那么問題變?yōu)槿绾卧?KV 結(jié)構(gòu)上保存 Table 以及如何在 KV 結(jié)構(gòu)上運(yùn)行 SQL 語句。 假設(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è)好的映射方案必須有利于對數(shù)據(jù)操作的需求。那么我們先看一下對數(shù)據(jù)的操作有哪些需求桶蛔,分別有哪些特點(diǎn)。
對于一個(gè) Table 來說漫谷,需要存儲(chǔ)的數(shù)據(jù)包括三部分:
- 表的元信息
- Table 中的 Row
- 索引數(shù)據(jù)
表的元信息我們暫時(shí)不討論仔雷,會(huì)有專門的章節(jié)來介紹。 對于 Row舔示,可以選擇行存或者列存碟婆,這兩種各有優(yōu)缺點(diǎn)。TiDB 面向的首要目標(biāo)是 OLTP 業(yè)務(wù)惕稻,這類業(yè)務(wù)需要支持快速地讀取竖共、保存、修改俺祠、刪除一行數(shù)據(jù)公给,所以采用行存是比較合適的。
對于 Index蜘渣,TiDB 不止需要支持 Primary Index淌铐,還需要支持 Secondary Index。Index 的作用的輔助查詢蔫缸,提升查詢性能腿准,以及保證某些 Constraint。查詢的時(shí)候有兩種模式拾碌,一種是點(diǎn)查吐葱,比如通過 Primary Key 或者 Unique Key 的等值條件進(jìn)行查詢,如 select name from user where id=1;
校翔,這種需要通過索引快速定位到某一行數(shù)據(jù)唇撬;另一種是 Range 查詢,如 select name from user where age > 30 and age < 35;
展融,這個(gè)時(shí)候需要通過idxAge
索引查詢 age 在 20 和 30 之間的那些數(shù)據(jù)窖认。Index 還分為 Unique Index 和 非 Unique Index豫柬,這兩種都需要支持。
分析完需要存儲(chǔ)的數(shù)據(jù)的特點(diǎn)扑浸,我們再看看對這些數(shù)據(jù)的操作需求烧给,主要考慮 Insert/Update/Delete/Select 這四種語句。
對于 Insert 語句喝噪,需要將 Row 寫入 KV础嫡,并且建立好索引數(shù)據(jù)。
對于 Update 語句酝惧,需要將 Row 更新的同時(shí)榴鼎,更新索引數(shù)據(jù)(如果有必要)。
對于 Delete 語句晚唇,需要在刪除 Row 的同時(shí)巫财,將索引也刪除。
上面三個(gè)語句處理起來都很簡單哩陕。對于 Select 語句平项,情況會(huì)復(fù)雜一些。首先我們需要能夠簡單快速地讀取一行數(shù)據(jù)悍及,所以每個(gè) Row 需要有一個(gè) ID (顯示或隱式的 ID)闽瓢。其次可能會(huì)讀取連續(xù)多行數(shù)據(jù),比如 Select * from user;
心赶。最后還有通過索引讀取數(shù)據(jù)的需求扣讼,對索引的使用可能是點(diǎn)查或者是范圍查詢。
大致的需求已經(jīng)分析完了缨叫,現(xiàn)在讓我們看看手里有什么可以用的:一個(gè)全局有序的分布式 Key-Value 引擎椭符。全局有序這一點(diǎn)重要,可以幫助我們解決不少問題弯汰。比如對于快速獲取一行數(shù)據(jù),假設(shè)我們能夠構(gòu)造出某一個(gè)或者某幾個(gè) Key湖雹,定位到這一行咏闪,我們就能利用 TiKV 提供的 Seek 方法快速定位到這一行數(shù)據(jù)所在位置。再比如對于掃描全表的需求摔吏,如果能夠映射為一個(gè) Key 的 Range鸽嫂,從 StartKey 掃描到 EndKey,那么就可以簡單的通過這種方式獲得全表數(shù)據(jù)征讲。操作 Index 數(shù)據(jù)也是類似的思路据某。接下來讓我們看看 TiDB 是如何做的。
TiDB 對每個(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:
<pre style="box-sizing: border-box; margin: 0px; -webkit-tap-highlight-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13.6px; overflow-wrap: normal; padding: 16px; overflow: auto; line-height: 1.45; background-color: rgb(39, 40, 34); border-radius: 3px; word-break: normal; color: rgb(248, 248, 242); tab-size: 4;"> Key: tablePrefix_rowPrefix_tableID_rowID
Value: [col1, col2, col3, col4]</pre>
其中 Key 的 tablePrefix/rowPrefix 都是特定的字符串常量埂材,用于在 KV 空間內(nèi)區(qū)分其他數(shù)據(jù)塑顺。 對于 Index 數(shù)據(jù),會(huì)按照如下規(guī)則編碼成 Key-Value pair:
<pre style="box-sizing: border-box; margin: 0px; -webkit-tap-highlight-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13.6px; overflow-wrap: normal; padding: 16px; overflow: auto; line-height: 1.45; background-color: rgb(39, 40, 34); border-radius: 3px; word-break: normal; color: rgb(248, 248, 242); tab-size: 4;"> Key: tablePrefix_idxPrefix_tableID_indexID_indexColumnsValue
Value: rowID</pre>
Index 數(shù)據(jù)還需要考慮 Unique Index 和非 Unique Index 兩種情況俏险,對于 Unique Index严拒,可以按照上述編碼規(guī)則。但是對于非 Unique Index竖独,通過這種編碼并不能構(gòu)造出唯一的 Key裤唠,因?yàn)橥粋€(gè) Index 的 tablePrefix_idxPrefix_tableID_indexID_
都一樣,可能有多行數(shù)據(jù)的 ColumnsValue
是一樣的预鬓,所以對于非 Unique Index 的編碼做了一點(diǎn)調(diào)整:
<pre style="box-sizing: border-box; margin: 0px; -webkit-tap-highlight-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13.6px; overflow-wrap: normal; padding: 16px; overflow: auto; line-height: 1.45; background-color: rgb(39, 40, 34); border-radius: 3px; word-break: normal; color: rgb(248, 248, 242); tab-size: 4;"> Key: tablePrefix_idxPrefix_tableID_indexID_ColumnsValue_rowID
Value:null</pre>
這樣能夠?qū)λ饕械拿啃袛?shù)據(jù)構(gòu)造出唯一的 Key巧骚。 注意上述編碼規(guī)則中的 Key 里面的各種 xxPrefix 都是字符串常量,作用都是區(qū)分命名空間格二,以免不同類型的數(shù)據(jù)之間相互沖突劈彪,定義如下:
<pre style="box-sizing: border-box; margin: 0px; -webkit-tap-highlight-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13.6px; overflow-wrap: normal; padding: 16px; overflow: auto; line-height: 1.45; background-color: rgb(39, 40, 34); border-radius: 3px; word-break: normal; color: rgb(248, 248, 242); tab-size: 4;"> var(
tablePrefix = []byte{'t'}
recordPrefixSep = []byte("_r")
indexPrefixSep = []byte("_i")
)</pre>
另外請大家注意,上述方案中顶猜,無論是 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冬骚,對于任何類型的值,兩個(gè)對象編碼前的原始類型比較結(jié)果懂算,和編碼成 byte 數(shù)組后(注意只冻,TiKV 中的 Key 和 Value 都是原始的 byte 數(shù)組)的比較結(jié)果保持一致。具體的編碼方案參見 TiDB 的 codec 包计技。采用這種編碼后喜德,一個(gè)表的所有 Row 數(shù)據(jù)就會(huì)按照 RowID 的順序排列在 TiKV 的 Key 空間中,某一個(gè) Index 的數(shù)據(jù)也會(huì)按照 Index 的 ColumnValue 順序排列在 Key 空間內(nèi)垮媒。
現(xiàn)在我們結(jié)合開始提到的需求以及 TiDB 的映射方案來看一下舍悯,這個(gè)方案是否能滿足需求航棱。首先我們通過這個(gè)映射方案,將 Row 和 Index 數(shù)據(jù)都轉(zhuǎn)換為 Key-Value 數(shù)據(jù)贱呐,且每一行丧诺、每一條索引數(shù)據(jù)都是有唯一的 Key。其次奄薇,這種映射方案對于點(diǎn)查驳阎、范圍查詢都很友好,我們可以很容易地構(gòu)造出某行馁蒂、某條索引所對應(yīng)的 Key呵晚,或者是某一塊相鄰的行、相鄰的索引值所對應(yīng)的 Key 范圍沫屡。最后饵隙,在保證表中的一些 Constraint 的時(shí)候,可以通過構(gòu)造并檢查某個(gè) Key 是否存在來判斷是否能夠滿足相應(yīng)的 Constraint沮脖。
至此我們已經(jīng)聊完了如何將 Table 映射到 KV 上面金矛,這里再舉個(gè)簡單的例子,便于大家理解勺届,還是以上面的表結(jié)構(gòu)為例驶俊。假設(shè)表中有 3 行數(shù)據(jù):
- “TiDB”, “SQL Layer”, 10
- “TiKV”, “KV Engine”, 20
- “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ù)為:
<pre style="box-sizing: border-box; margin: 0px; -webkit-tap-highlight-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13.6px; overflow-wrap: normal; padding: 16px; overflow: auto; line-height: 1.45; background-color: rgb(39, 40, 34); border-radius: 3px; word-break: normal; color: rgb(248, 248, 242); tab-size: 4;"> t_r_10_1 --> ["TiDB", "SQL Layer", 10]
t_r_10_2 --> ["TiKV", "KV Engine", 20]
t_r_10_3 --> ["PD", "Manager", 30]</pre>
除了 Primary Key 之外胚膊,這個(gè)表還有一個(gè) Index故俐,假設(shè)這個(gè) Index 的 ID 為 1,則其數(shù)據(jù)為:
<pre style="box-sizing: border-box; margin: 0px; -webkit-tap-highlight-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13.6px; overflow-wrap: normal; padding: 16px; overflow: auto; line-height: 1.45; background-color: rgb(39, 40, 34); border-radius: 3px; word-break: normal; color: rgb(248, 248, 242); tab-size: 4;"> t_i_10_1_10_1 --> null
t_i_10_1_20_2 --> null
t_i_10_1_30_3 --> null</pre>
大家可以結(jié)合上面的編碼規(guī)則來理解這個(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,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ā)生了變化)。這部分的具體實(shí)現(xiàn)參見 TiDB 的異步 schema 變更實(shí)現(xiàn)一文埠帕。
SQL on KV 架構(gòu)
TiDB 的整體架構(gòu)如下圖所示
TiKV Cluster 主要作用是作為 KV 引擎存儲(chǔ)數(shù)據(jù)垢揩,上篇文章已經(jīng)介紹過了細(xì)節(jié),這里不再敷述敛瓷。本篇文章主要介紹 SQL 層叁巨,也就是 TiDB Servers 這一層,這一層的節(jié)點(diǎn)都是無狀態(tài)的節(jié)點(diǎn)呐籽,本身并不存儲(chǔ)數(shù)據(jù)锋勺,節(jié)點(diǎn)之間完全對等。TiDB Server 這一層最重要的工作是處理用戶請求狡蝶,執(zhí)行 SQL 運(yùn)算邏輯庶橱,接下來我們做一些簡單的介紹。
SQL 運(yùn)算
理解了 SQL 到 KV 的映射方案之后牢酵,我們可以理解關(guān)系數(shù)據(jù)是如何保存的悬包,接下來我們要理解如何使用這些數(shù)據(jù)來滿足用戶的查詢需求,也就是一個(gè)查詢語句是如何操作底層存儲(chǔ)的數(shù)據(jù)馍乙。 能想到的最簡單的方案就是通過上一節(jié)所述的映射方案布近,將 SQL 查詢映射為對 KV 的查詢,再通過 KV 接口獲取對應(yīng)的數(shù)據(jù)丝格,最后執(zhí)行各種計(jì)算撑瞧。 比如 Select count(*) from user where name="TiDB";
這樣一個(gè)語句,我們需要讀取表中所有的數(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)
的左閉右開區(qū)間 - 掃描 Key Range:根據(jù)上面構(gòu)造出的 Key Range骆撇,讀取 TiKV 中的數(shù)據(jù)
- 過濾數(shù)據(jù):對于讀到的每一行數(shù)據(jù)瞒御,計(jì)算
name="TiDB"
這個(gè)表達(dá)式,如果為真神郊,則向上返回這一行肴裙,否則丟棄這一行數(shù)據(jù) - 計(jì)算 Count:對符合要求的每一行趾唱,累計(jì)到 Count 值上面 這個(gè)方案肯定是可以 Work 的,但是并不能 Work 的很好蜻懦,原因是顯而易見的:
- 在掃描數(shù)據(jù)的時(shí)候甜癞,每一行都要通過 KV 操作同 TiKV 中讀取出來,至少有一次 RPC 開銷宛乃,如果需要掃描的數(shù)據(jù)很多悠咱,那么這個(gè)開銷會(huì)非常大
- 并不是所有的行都有用,如果不滿足條件征炼,其實(shí)可以不讀取出來
- 符合要求的行的值并沒有什么意義乔煞,實(shí)際上這里只需要有幾行數(shù)據(jù)這個(gè)信息就行
分布式 SQL 運(yùn)算
如何避免上述缺陷也是顯而易見的,首先我們需要將計(jì)算盡量靠近存儲(chǔ)節(jié)點(diǎn)柒室,以避免大量的 RPC 調(diào)用渡贾。其次,我們需要將 Filter 也下推到存儲(chǔ)節(jié)點(diǎn)進(jìn)行計(jì)算雄右,這樣只需要返回有效的行空骚,避免無意義的網(wǎng)絡(luò)傳輸。最后擂仍,我們可以將聚合函數(shù)囤屹、GroupBy 也下推到存儲(chǔ)節(jié)點(diǎn),進(jìn)行預(yù)聚合逢渔,每個(gè)節(jié)點(diǎn)只需要返回一個(gè) Count 值即可肋坚,再由 tidb-server 將 Count 值 Sum 起來。 這里有一個(gè)數(shù)據(jù)逐層返回的示意圖:
這里有一篇文章詳細(xì)描述了 TiDB 是如何讓 SQL 語句跑的更快肃廓,大家可以參考一下智厌。
SQL 層架構(gòu)
上面幾節(jié)簡要介紹了 SQL 層的一些功能,希望大家對 SQL 語句的處理有一個(gè)基本的了解盲赊。實(shí)際上 TiDB 的 SQL 層要復(fù)雜的多铣鹏,模塊以及層次非常多,下面這個(gè)圖列出了重要的模塊以及調(diào)用關(guān)系:
用戶的 SQL 請求會(huì)直接或者通過 Load Balancer 發(fā)送到 tidb-server哀蘑,tidb-server 會(huì)解析 MySQL Protocol Packet诚卸,獲取請求內(nèi)容,然后做語法解析绘迁、查詢計(jì)劃制定和優(yōu)化合溺、執(zhí)行查詢計(jì)劃獲取和處理數(shù)據(jù)。數(shù)據(jù)全部存儲(chǔ)在 TiKV 集群中缀台,所以在這個(gè)過程中 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 過程中看不到误辑,但是對整體集群又非常重要沧踏。主要會(huì)涉及到集群的管理和調(diào)度。