基於 Tile 連接 Row-Store 和 Column-Store

繼 Kudu 文章之後，我司首架唐劉同學又一力作，共享給大家~

在之前的 Kudu 的文章裡面，我已經提到過，行列混存是一個非常有意思的研究方向，因為不同的存儲方式有不同的針對應用場景，但作為技術人員，折騰是天性，所以大家都在研究如何融合行存和列存，讓一個服務能盡量滿足大部分應用需求，而這也是 TiDB 在努力的方向。

在 Kudu Paper 裡面說到，Kudu 首先在 mem 裡面使用行存，但刷到硬碟之後，則使用的是列存，這當然是一個可以嘗試的方式，但我覺得應該還有更多種的解決方式，於是找到了 CMU 的 Peloton 【cmu-db/peloton】以及相關的 Paper，覺得有必要研究記錄一下。

Storage Model

很多時候，我喜歡用行存和列存，但看 Paper 的時候，發現都喜歡使用 NSM 和 DSM 來說明，這裡就簡單說明一下。

NSM

NSM 是 N-ary storage model 的簡稱，當然就是通常的行存了。NSM 主要針對 OLTP 場景，因為需要高性能的隨機寫入，NSM 的存儲方式如下：

NSM 不適用需要讀取大量數據，並分析特定 column 的場景，因為 NSM 需要把整個 record 給讀出來，在拿到對應的 column 數據分析，數據數據量很大，整個開銷會很大。

DSM

DSM 是 decomposition storage model 的簡稱，也就是列存。DSM 主要針對 OLAP 場景，因為需要對一些特定的 column 進行快速掃描分析，DSM 的存儲方式如下：

DSM 當然就不適用與需要頻繁隨機更新的情況，因為任何寫入，DSM 需要將 record 分開寫入到不同的地方，寫開銷會很大。

FSM

為了解決這個問題，就有了一個 FSM flexible storage model 來融合 NSM 和 DSM，在 Peloton 裡面，它把這套系統叫做 HTAP (Hybrid Transactional/Analytical Processing)，

不同於n NSM 按照每行存放，以及 DSM 按照每列存放，FSM 將數據分成了多個區塊，Peloton 裡面叫做 Tile，上面的圖顯示的是兩個 nTile，一個 Tile 包含了 ID，Image ID 以及 Name，而另一個 Tile 裡面則是包含了 Price 和 Data。各個 nTile 裡面數據是連續存放的。就是說，我們使用 Tile 來模擬了 DSM，在 Tile 裡面則是 NSM。

Tile-Based Architecture

Pelotonn 使用 tiles 來抽象了 storage 這一層，在上面的 FSM 例子我們可以看到，Tile 可以將一個 table n進行垂直和水平切分。Peloton 使用 physical tile 來處理實際的 storage，然後用另一個 logical tile n來隱藏了 physical tile 的實現，讓外面更容易使用。

Physical Tile

Physicaln tile 的最小存儲單位是 tile tuple，一批 tile tuple 形成了一個 physical tile。而一批 physicaln tile 則組成一個 tile group。一個 table 則是有多個 tile group 組成。

在上面的例子中，tablen 被分成了三個 tile group (A, B, C)，每個 group 都有不同的 physical tiles。譬如 group A n就是由 tile A-1 和 A-2 組成，tile A-1 包含 table 前面三個 column ID，IMAGE-ID，和 NAME，而n tile A-2 則包含了 PRICE 和 DATA。

使用n tile group，我們可以非常方便的支持 FSM。對於新插入的數據，通常是熱點數據，我們會直接放到一個 OLTP 友好的 group n中，也就是 group 裡面只有一個 tile（NSM）。當數據變冷之後，我們就將當前的 tile group 轉成更 OLAP n優化的布局，也就是 group 裡面可能有幾個 tile 了。當 group 裡面每個 tile 都只有一個 column n的時候，這其實就變成了 DSM 了。

Logical Tile

使用 physical tile 的好處在於我們可以根據不同的情況將數據切分成不同的布局，但是這對於查詢並不友好，因為數據在不同的 tile 裡面。為了解決這個問題，Peloton 引入了 logical tile。

Logicaln tile 隱藏了 physical tile 的具體實現，logical tile 的每個 column 可以指向一個或者多個 nphysical tiles 的 columns，每個 logical tile column 裡面存儲的是 tuple 在 physical ntiles 裡面的偏移位置。

在上面的例子中，logicaln tile X 指向了兩個 physical tiles A-1 和 A-2。 X 的第一個 column 指向了 physical tile nA-1 的 ATTR-1 和 ATTR-2。而第一個 column 裡面存放的 1，2，3 則是對應的 tuple 在 tile A-1 n裡面的偏移。譬如 1 就對應的是 (101, 201)。

一個n logical tile column 也可以映射不同的 physical tile 的 columns。譬如上面 X 的第二個 ncolumn，就是對應的 tile A-1 的 ATTR-3 和 A-2 的 ATTR-1。當然一些 physical tile column n也可能不會有任何映射，譬如上面的 A-2 的 ATTR-2。

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

• Layout Transparency：logical tile 隱藏底層底層實際的存儲實現，所以我們可以用不同的 engine 來滿足不同的場景。

• Vectorized Processing：使用 logical tile，我們可以一次進行一批向量處理，在一些場景下能極大的提升 CPU 性能。

• Flexible Materialization：我們可以提前或者推遲的物化。在執行 query plan tree 的時候，甚至都能夠動態去選擇一個物化策略。

• Caching Behavior：我們可以根據不同的維度去創建不同的 tile group，放到 cache 了，用來處理後續的查詢。

Logical Tile Algebra

Peloton 提供 algebra operators 來讓外面更方便的使用。Operators 主要包括：

• Bridge：Bridgen operators 連接的 logical tile 和 physical tile。譬如我們可以使用 sequential scan 和 nindex scan operators 去訪問實際的數據，然後生成對應的 logical tile。而 materialize noperator 則是將實際的 logical tile 轉成實際的 physical tile。

• Metadata：Logicaln tile 的 metadata 存放的一些關於底層 physical tile 的信息，以及一些 bitmap 來表明哪些 rows n在執行的時候必須被檢查。Metadata 的 operators 只會改變 logical tile 的 metadata，並不會改變底層的 nphysical tile 的數據。譬如 projection operator 如果發現上層的 query plan 並不需要一些 nattributes 了，就可以在 logical tile 裡面移除。

• Mutatorsn ：Mutator operators 會改變 table 的實際存儲數據。譬如 insert operator 首先會重新構建 logicaln tile 的 tuple，然後在插入到對應的 table 裡面，而 delete operator 則是刪除 table n裡面的數據，update operator 則是先在 logical tile 裡面刪除，在通過之前的 tuple 重新構建一個新版本的 ntuple，在插入到 table。Mutators 同時也會控制 tuple 在 transaction 裡面的可見性。

• Pipelinen Breakers：當我們給一個 query plan 生成對應的 query plan tree 之後，在 tree 上層的 noperators 需要等待 children 的操作完成返回了，才能繼續進行。譬如 join operator 需要處理多個 logical ntiles，並且在這些 tiles 上面執行 predicate。首先，join operator 會構建一個 output logical ntile，它的 schema 是根據輸入的 logical tile 來構建的。然後 join operator 會遍歷 input nlogical tile，如果發現滿足 predicate，就將結果放到 output logical tile，下面是 join 的一個例子：

  

Layout reorganization

雖然基於n Tile-Based Architecture 看起來很美好，但如果對於不同的 query，如果沒有好的 tile n與其對應，那麼其實根本就沒啥用。 Peloton 採用的方法是定期對每個 table 計算出最優化的 storage nlayout，然後在根據這個 layout 重新組織 table。

Pelotonn 使用一個輕量級的 monitor 來記錄每個 query 訪問的 attributes，用來確定哪一些 attributes 應該在新的 nphysical tile 裡面放在一起。通常 Peloton 會收集 query 裡面的 SELECT 和 WHERE 上面的 nattributes。

為了減少監控帶來的開銷，monitorn 會隨機的對 query 進行採樣統計，並且 monitor 還需要保證不能只關注頻繁的 transactional nquery，還需要關注一些不頻繁的 analytical query，所以 Peloton 會也會記錄 query 的 plan ncost，並通過這些來給 analytical query 生成特定的 storage layout。

Pelotonn 使用增量的方式進行 data layout 的 reorganization。對於一個給定的 tile group，Peloton 首先會將 ndata 拷貝到一個新的 layout 上面，同時會原子地用一個新的 tile group 來替換。任何並發的 delete 或者 updaten 操作都只會更新metadata 信息。新的 tile group 會有舊的 tile group metadata 的引用。如果一個 nphysical tile 沒有被任何 logical tile 引用，那麼 Peloton 就會將其回收。

對於一個熱點n tile group 來說，因為很可能一直在被 OLTP 的事務持續訪問，所以 Peloton 並不會對這種 tile group 做 nreorganization，只會等到數據變冷之後才會進行。因為 Peloton 使用的是通用的 MVCC n模式，所以一段時間之後，老版本的數據一定會變成冷數據，那麼就可以開始 reorganization 了。Reorganization 通常就是將n layout 從 OLTP 友好的，逐漸變成 OLAP 友好的。

小結

上面僅僅是介紹 Peloton 的一些實現 FSM 的機制，這裡並沒有介紹 MVCC，transaction 這些，因為這些對於資料庫產品來說都幾乎是標配的東西，原理上面差不多。這裡僅僅是關注的是 Peloton 是如何做到行列混存的。

簡單來說，Pelotonn 使用 physical tile 將數據切分成了不同的單元，同時用 logical tile 來隱藏了相關的實現，並提供 algebra n讓上層更方便的操作。在後台，統計 query 等信息，並定期增量的對 layout 進行 nreorganization。不得不說，整個設計思路還是很巧妙的。TiKV 後面也會考慮行列混存，我們一直想同時搞定 OLTP + nOLAP，但究竟採用哪些方案，還需要我們慢慢研究和思考，也歡迎對這塊感興趣的同學加入。（文／唐劉）

延展閱讀