在之前的 Kudu 的文章里面，我已經(jīng)提到過(guò)阱冶，行列混存是一個(gè)非常有意思的研究方向刁憋，因?yàn)椴煌拇鎯?chǔ)方式有不同的針對(duì)應(yīng)用場(chǎng)景，但作為技術(shù)人員木蹬，折騰是天性至耻，所以大家都在研究如何融合行存和列存，讓一個(gè)服務(wù)能盡量滿(mǎn)足大部分應(yīng)用需求镊叁，而這也是 TiDB 在努力的方向有梆。

在 Kudu Paper 里面說(shuō)到，Kudu 首先在 mem 里面使用行存意系，但刷到硬盤(pán)之后，則使用的是列存饺汹，這當(dāng)然是一個(gè)可以嘗試的方式蛔添，但我覺(jué)得應(yīng)該還有更多種的解決方式，于是找到了 CMU 的 Peloton 以及相關(guān)的 Paper兜辞，覺(jué)得有必要研究記錄一下迎瞧。

Storage Model

很多時(shí)候，我喜歡用行存和列存逸吵，但看 Paper 的時(shí)候凶硅，發(fā)現(xiàn)都喜歡使用 NSM 和 DSM 來(lái)說(shuō)明，這里就簡(jiǎn)單說(shuō)明一下扫皱。

NSM

NSM 是 N-ary storage model 的簡(jiǎn)稱(chēng)足绅，當(dāng)然就是通常的行存了。NSM 主要針對(duì) OLTP 場(chǎng)景韩脑，因?yàn)樾枰咝阅艿碾S機(jī)寫(xiě)入氢妈，NSM 的存儲(chǔ)方式如下：

NSM 不適用需要讀取大量數(shù)據(jù)，并分析特定 column 的場(chǎng)景段多，因?yàn)?NSM 需要把整個(gè) record 給讀出來(lái)首量，在拿到對(duì)應(yīng)的 column 數(shù)據(jù)分析，數(shù)據(jù)數(shù)據(jù)量很大进苍，整個(gè)開(kāi)銷(xiāo)會(huì)很大加缘。

DSM

DSM 是 decomposition storage model 的簡(jiǎn)稱(chēng)，也就是列存觉啊。DSM 主要針對(duì) OLAP 場(chǎng)景拣宏，因?yàn)樾枰獙?duì)一些特定的 column 進(jìn)行快速掃描分析，DSM 的存儲(chǔ)方式如下：

DSM 當(dāng)然就不適用與需要頻繁隨機(jī)更新的情況杠人，因?yàn)槿魏螌?xiě)入蚀浆，DSM 需要將 record 分開(kāi)寫(xiě)入到不同的地方缀程，寫(xiě)開(kāi)銷(xiāo)會(huì)很大。

FSM

為了解決這個(gè)問(wèn)題市俊，就有了一個(gè) FSM flexible storage model 來(lái)融合 NSM 和 DSM杨凑，在 Peloton 里面，它把這套系統(tǒng)叫做 HTAP (Hybrid Transactional/Analytical Processing)摆昧，

不同于 NSM 按照每行存放撩满，以及 DSM 按照每列存放，F(xiàn)SM 將數(shù)據(jù)分成了多個(gè)區(qū)塊绅你，Peloton 里面叫做 Tile伺帘，上面的圖顯示的是兩個(gè) Tile，一個(gè) Tile 包含了 ID忌锯，Image ID 以及 Name伪嫁，而另一個(gè) Tile 里面則是包含了 Price 和 Data。各個(gè) Tile 里面數(shù)據(jù)是連續(xù)存放的偶垮。就是說(shuō)张咳，我們使用 Tile 來(lái)模擬了 DSM，在 Tile 里面則是 NSM似舵。

Tile-Based Architecture

Peloton 使用 tiles 來(lái)抽象了 storage 這一層脚猾，在上面的 FSM 例子我們可以看到，Tile 可以將一個(gè) table 進(jìn)行垂直和水平切分砚哗。Peloton 使用 physical tile 來(lái)處理實(shí)際的 storage龙助，然后用另一個(gè) logical tile 來(lái)隱藏了 physical tile 的實(shí)現(xiàn)，讓外面更容易使用蛛芥。

Physical Tile

Physical tile 的最小存儲(chǔ)單位是 tile tuple提鸟，一批 tile tuple 形成了一個(gè) physical tile。而一批 physical tile 則組成一個(gè) tile group仅淑。一個(gè) table 則是有多個(gè) tile group 組成沽一。

在上面的例子中，table 被分成了三個(gè) tile group (A, B, C)漓糙，每個(gè) group 都有不同的 physical tiles铣缠。譬如 group A 就是由 tile A-1 和 A-2 組成，tile A-1 包含 table 前面三個(gè) column ID昆禽，IMAGE-ID蝗蛙，和 NAME，而 tile A-2 則包含了 PRICE 和 DATA醉鳖。

使用 tile group捡硅，我們可以非常方便的支持 FSM。對(duì)于新插入的數(shù)據(jù)盗棵，通常是熱點(diǎn)數(shù)據(jù)壮韭，我們會(huì)直接放到一個(gè) OLTP 友好的 group 中北发，也就是 group 里面只有一個(gè) tile（NSM）。當(dāng)數(shù)據(jù)變冷之后喷屋，我們就將當(dāng)前的 tile group 轉(zhuǎn)成更 OLAP 優(yōu)化的布局琳拨，也就是 group 里面可能有幾個(gè) tile 了。當(dāng) group 里面每個(gè) tile 都只有一個(gè) column 的時(shí)候屯曹，這其實(shí)就變成了 DSM 了狱庇。

Logical Tile

使用 physical tile 的好處在于我們可以根據(jù)不同的情況將數(shù)據(jù)切分成不同的布局，但是這對(duì)于查詢(xún)并不友好恶耽，因?yàn)閿?shù)據(jù)在不同的 tile 里面密任。為了解決這個(gè)問(wèn)題，Peloton 引入了 logical tile偷俭。

Logical tile 隱藏了 physical tile 的具體實(shí)現(xiàn)浪讳，logical tile 的每個(gè) column 可以指向一個(gè)或者多個(gè) physical tiles 的 columns，每個(gè) logical tile column 里面存儲(chǔ)的是 tuple 在 physical tiles 里面的偏移位置涌萤。

在上面的例子中淹遵，logical tile X 指向了兩個(gè) physical tiles A-1 和 A-2。 X 的第一個(gè) column 指向了 physical tile A-1 的 ATTR-1 和 ATTR-2形葬。而第一個(gè) column 里面存放的 1，2暮的，3 則是對(duì)應(yīng)的 tuple 在 tile A-1 里面的偏移笙以。譬如 1 就對(duì)應(yīng)的是 (101, 201)。

一個(gè) logical tile column 也可以映射不同的 physical tile 的 columns冻辩。譬如上面 X 的第二個(gè) column猖腕，就是對(duì)應(yīng)的 tile A-1 的 ATTR-3 和 A-2 的 ATTR-1。當(dāng)然一些 physical tile column 也可能不會(huì)有任何映射恨闪，譬如上面的 A-2 的 ATTR-2倘感。

使用 logical tile 的好處是很明顯的，主要包括：

• Layout Transparency：logical tile 隱藏底層底層實(shí)際的存儲(chǔ)實(shí)現(xiàn)咙咽，所以我們可以用不同的 engine 來(lái)滿(mǎn)足不同的場(chǎng)景老玛。
• Vectorized Processing：使用 logical tile，我們可以一次進(jìn)行一批向量處理钧敞，在一些場(chǎng)景下能極大的提升 CPU 性能蜡豹。
• Flexible Materialization：我們可以提前或者推遲的物化。在執(zhí)行 query plan tree 的時(shí)候溉苛，甚至都能夠動(dòng)態(tài)去選擇一個(gè)物化策略镜廉。
• Caching Behavior：我們可以根據(jù)不同的維度去創(chuàng)建不同的 tile group，放到 cache 了愚战，用來(lái)處理后續(xù)的查詢(xún)娇唯。

Logical Tile Algebra

Peloton 提供 algebra operators 來(lái)讓外面更方便的使用齐遵。Operators 主要包括：

• Bridge：Bridge operators 連接的 logical tile 和 physical tile。譬如我們可以使用 sequential scan 和 index scan operators 去訪問(wèn)實(shí)際的數(shù)據(jù)塔插，然后生成對(duì)應(yīng)的 logical tile梗摇。而 materialize operator 則是將實(shí)際的 logical tile 轉(zhuǎn)成實(shí)際的 physical tile。

• Metadata：Logical tile 的 metadata 存放的一些關(guān)于底層 physical tile 的信息佑淀，以及一些 bitmap 來(lái)表明哪些 rows 在執(zhí)行的時(shí)候必須被檢查留美。Metadata 的 operators 只會(huì)改變 logical tile 的 metadata，并不會(huì)改變底層的 physical tile 的數(shù)據(jù)伸刃。譬如 projection operator 如果發(fā)現(xiàn)上層的 query plan 并不需要一些 attributes 了谎砾，就可以在 logical tile 里面移除。

• Mutators ：Mutator operators 會(huì)改變 table 的實(shí)際存儲(chǔ)數(shù)據(jù)捧颅。譬如 insert operator 首先會(huì)重新構(gòu)建 logical tile 的 tuple景图，然后在插入到對(duì)應(yīng)的 table 里面，而 delete operator 則是刪除 table 里面的數(shù)據(jù)碉哑，update operator 則是先在 logical tile 里面刪除挚币，在通過(guò)之前的 tuple 重新構(gòu)建一個(gè)新版本的 tuple，在插入到 table扣典。Mutators 同時(shí)也會(huì)控制 tuple 在 transaction 里面的可見(jiàn)性妆毕。

• Pipeline Breakers：當(dāng)我們給一個(gè) query plan 生成對(duì)應(yīng)的 query plan tree 之后，在 tree 上層的 operators 需要等待 children 的操作完成返回了贮尖，才能繼續(xù)進(jìn)行笛粘。譬如 join operator 需要處理多個(gè) logical tiles，并且在這些 tiles 上面執(zhí)行 predicate湿硝。首先薪前，join operator 會(huì)構(gòu)建一個(gè) output logical tile，它的 schema 是根據(jù)輸入的 logical tile 來(lái)構(gòu)建的关斜。然后 join operator 會(huì)遍歷 input logical tile示括，如果發(fā)現(xiàn)滿(mǎn)足 predicate，就將結(jié)果放到 output logical tile痢畜，下面是 join 的一個(gè)例子：

  

Layout reorganization

雖然基于 Tile-Based Architecture 看起來(lái)很美好垛膝，但如果對(duì)于不同的 query，如果沒(méi)有好的 tile 與其對(duì)應(yīng)丁稀，那么其實(shí)根本就沒(méi)啥用繁涂。 Peloton 采用的方法是定期對(duì)每個(gè) table 計(jì)算出最優(yōu)化的 storage layout，然后在根據(jù)這個(gè) layout 重新組織 table二驰。

Peloton 使用一個(gè)輕量級(jí)的 monitor 來(lái)記錄每個(gè) query 訪問(wèn)的 attributes扔罪，用來(lái)確定哪一些 attributes 應(yīng)該在新的 physical tile 里面放在一起。通常 Peloton 會(huì)收集 query 里面的 SELECT 和 WHERE 上面的 attributes桶雀。

為了減少監(jiān)控帶來(lái)的開(kāi)銷(xiāo)矿酵，monitor 會(huì)隨機(jī)的對(duì) query 進(jìn)行采樣統(tǒng)計(jì)唬复，并且 monitor 還需要保證不能只關(guān)注頻繁的 transactional query，還需要關(guān)注一些不頻繁的 analytical query全肮，所以 Peloton 會(huì)也會(huì)記錄 query 的 plan cost敞咧，并通過(guò)這些來(lái)給 analytical query 生成特定的 storage layout。

Peloton 使用增量的方式進(jìn)行 data layout 的 reorganization辜腺。對(duì)于一個(gè)給定的 tile group休建，Peloton 首先會(huì)將 data 拷貝到一個(gè)新的 layout 上面，同時(shí)會(huì)原子地用一個(gè)新的 tile group 來(lái)替換评疗。任何并發(fā)的 delete 或者 update 操作都只會(huì)更新metadata 信息测砂。新的 tile group 會(huì)有舊的 tile group metadata 的引用。如果一個(gè) physical tile 沒(méi)有被任何 logical tile 引用百匆，那么 Peloton 就會(huì)將其回收砌些。

對(duì)于一個(gè)熱點(diǎn) tile group 來(lái)說(shuō)，因?yàn)楹芸赡芤恢痹诒?OLTP 的事務(wù)持續(xù)訪問(wèn)加匈，所以 Peloton 并不會(huì)對(duì)這種 tile group 做 reorganization存璃，只會(huì)等到數(shù)據(jù)變冷之后才會(huì)進(jìn)行。因?yàn)?Peloton 使用的是通用的 MVCC 模式雕拼，所以一段時(shí)間之后纵东，老版本的數(shù)據(jù)一定會(huì)變成冷數(shù)據(jù)，那么就可以開(kāi)始 reorganization 了啥寇。Reorganization 通常就是將 layout 從 OLTP 友好的偎球，逐漸變成 OLAP 友好的。

小結(jié)

上面僅僅是介紹 Peloton 的一些實(shí)現(xiàn) FSM 的機(jī)制示姿，這里并沒(méi)有介紹 MVCC甜橱，transaction 這些逊笆，因?yàn)檫@些對(duì)于數(shù)據(jù)庫(kù)產(chǎn)品來(lái)說(shuō)都幾乎是標(biāo)配的東西栈戳，原理上面差不多。這里僅僅是關(guān)注的是 Peloton 是如何做到行列混存的难裆。

簡(jiǎn)單來(lái)說(shuō)子檀，Peloton 使用 physical tile 將數(shù)據(jù)切分成了不同的單元，同時(shí)用 logical tile 來(lái)隱藏了相關(guān)的實(shí)現(xiàn)乃戈，并提供 algebra 讓上層更方便的操作褂痰。在后臺(tái)，統(tǒng)計(jì) query 等信息症虑，并定期增量的對(duì) layout 進(jìn)行 reorganization缩歪。不得不說(shuō)，整個(gè)設(shè)計(jì)思路還是很巧妙的谍憔。TiKV 后面也會(huì)考慮行列混存匪蝙，我們一直想同時(shí)搞定 OLTP + OLAP主籍，但究竟采用哪些方案，還需要我們慢慢研究和思考逛球，也歡迎對(duì)這塊感興趣的同學(xué)加入千元。