列存資料庫，不只是列式儲存

語言: CN / TW / HK

時間 2021-04-07 18:07:08 apachekylin

作者簡介

黃峰，Kyligence 公司高階研發工程師，目前主要負責 Kyligence 企業級產品的開發以及維護工作。

對 OLAP 場景的查詢而言，單個查詢往往需要在儲存端掃描大量資料，再在記憶體中進行一些統計分析後，才能輸出所需要的統計結果。因此，如果不能像以 Kylin 為代表的 MOLAP 引擎採用預計算的方式來避免資料的實時掃描，對於基於磁碟儲存的數倉而言，儲存端無疑會因為掃描大量資料造成磁碟吞吐的瓶頸。

既然如此，是否存在別的選擇，可以少從儲存端載入資料呢？列存資料庫正是通過採取合適的資料組織結構，來減小查詢載入的資料量，最終提高查詢效率。

大資料圈的各位對列式儲存一定不陌生，快速浮現你腦海裡的想必是 ORCFile，Parquet 等，但其實這些只是資料格式，並不能直接和列存資料庫劃等號。

列存格式 = 列存資料庫

列存資料庫 ^[1] 更像是基於列存格式，設計的一套完整的資料庫解決方案，而這套解決方案不僅需要考慮資料格式，更要考慮以下因素：

由於考慮成本效率的因素，計算機中的儲存常被設計成多級儲存的結構，所以資料不單在磁碟上有特定的儲存格式，在記憶體中，甚至 L1，L2，L3 快取中同樣有其獨特的佈局方式。考慮到儲存端複雜的情況，如何結合 OLAP 場景的 workload，從而針對不同的硬體特點設計資料佈局，是列存資料庫在儲存端需要考慮的核心問題；
有了在不同儲存層的資料儲存佈局之後，資料如何在不同儲存層之間流動，比如，如何從磁碟載入資料到記憶體，什麼時候進行載入，這些都是存取方法 ^[2] （Access Method）所涉及的內容；
資料結構配上合適的演算法才能橫行江湖，計算和資料組織方式往往緊密耦合，彰顯團結的力量。如何結合列存的特點設計一個高效的執行引擎，為 Join，Sort，Groupby 等關係運算元提供一種更為高效的演算法，都是列存資料庫需要考慮的問題。

由此可見，為了追求極致的效能，底層儲存的變化往往會引發 存取方法 、 執行引擎 、 關係運算元演算法實現 等多方面的一系列適配性的變化，真可謂環環相扣，好不緊張。下面，我們就依次從這幾個方面介紹其所涉及內容。

儲存格式

可曾記得把列存的思想引入大資料的先驅者—— RCFile ^[3] ，它的基本思想是將資料水平切分成一個個行組，在每個行組內除了元資料和行組切分標識以外，資料部分按列來進行連續儲存。

這樣操作的原因在於 OLAP 的查詢雖然一般都會掃描大量行，但只會涉及少量列，通過這樣的列存佈局方式，能夠有效避免無關列的載入，從而達到減小磁碟吞吐的目的。

但似乎先驅者的下場往往不那麼盡如人意，RCFile 也沒有擺脫這個魔咒。相較傳統數倉中的列存而言，RCFile 還是太過粗糙，要學就學全套呀！

Hive 的開發者們總結了 RCFile 的經驗教訓，指出其核心問題 ^[4] 在於：

對資料型別不感知，從而無法對具體型別做編碼優化，限制了列存的儲存高效性；
沒有索引輔助過濾資料（如：謂詞下推），造成資料讀取效率低下。

站在前人的肩膀上，後續的 ORCFile，Parquet 都開啟了進化之旅，一方面加入一些 Min、Max、Count 等 輕量級統計索引 來加速查詢；另一方面，針對不同場景，採用 RLE，Bitcode，Dictionary Code 等編碼方式進行儲存優化，比如 RLE，針對的就是取值範圍不大，重複度高的資料，假設有一列資料是 AAABBBB，RLE 就會直接採用 A3B4 來表達（其中“3”和“4”代表前一個值出現的次數）。

自此以後，列存格式的風吹遍了整個大資料生態圈，CarbonData 採用多維排序的方式優化資料的列式佈局；Druid 在列存之上，通過對維度列進行 Dictionary 編碼加 Bitmap 索引的方式加速了資料的篩選和聚合......

當然，儲存格式並不是只需關心儲存查詢的效率問題，將其應用到實際中所需要考慮的問題同樣重要。比如，2019 年 4 月，Databricks 公司重磅開源 Delta Lake，給資料添加了 ACID 特性，支援資料的併發讀寫，Hudi 和 Iceberg 也不甘落後，儲存的故事又拉開了一張大幕，世界就是這樣精彩！

存取方式

資料存在磁碟上的資料佈局叫做儲存格式，而存取方式則包括：

資料是怎麼從磁碟讀到記憶體的？（例如 MySQL 載入資料的時候，是通過全表掃描，還是通過索引掃描）
資料在記憶體的佈局是怎樣的？
資料又是怎麼寫回磁碟的？

等一系列過程。

這裡我們以資料從磁碟載入到記憶體的過程為例，來探討列式儲存能夠給存取過程帶來哪些優勢。由於資料最終輸出時是以行為單位，所以在將列存資料讀入記憶體時，直接定位到要掃描的列，然後按順序重構一行行資料並交由執行引擎處理，就顯得尤為自然，但我們不如想的更深入一步：

記憶體中的資料表是不是也可以是列式的？
資料是不是可以懶載入（延遲物化）？

對於問題一，Presto、ClickHouse 等實踐者通過在記憶體中使用列存佈局，不僅優化了儲存效率，也使得向量化計算加速分析查詢變為可能；

對於延遲物化 ^[5] 的問題，核心就在於 資料是否能等到真正需要它們的時候再載入 ，例如對於以下查詢：

select b from R where a = X and d = Y

是直接如上圖左側所示，將查詢涉及到的 a、b、d 列全部載入到記憶體裡構成一行一行資料，然後進行過濾（Filter）和對映（Project）；

還是如上圖右側所示，選擇儘量延遲載入，先分別對 a、d 列進行單獨載入過濾，決定要輸出的行（圖中的 01 向量），再把對應行的 b 列載入輸出，最後再構建成行資料輸出？

這兩者的 Tradeoff 在於，雖然延遲載入能夠減少資料的載入量，但需要維護原始資料的位置，這樣才能找到對應行的其他列的值，然而如果篩選條件（R.a = X and R.d = Y ）不能大量過濾資料，延遲載入反而低效。對於這種情況，就需要根據一些統計資訊選擇合適的載入演算法，來最大限度的提高效率。

執行引擎與關係運算元

說完了儲存端的故事，讓我們轉戰計算端，嘮一嘮執行引擎和關係運算元與列存之間又有怎樣的故事。

執行引擎

首先，來了解一下執行引擎的在 SQL 查詢過程中發揮了什麼樣的作用。

熟悉 SQL 查詢引擎的同學應該都清楚，一條 SQL 會經過詞法語法解析、語義校驗、邏輯執行計劃生成優化等一系列步驟，生成最後的物理執行計劃，例如，對於如下 SQL：

select * from R where a = 1

其物理執行計劃如下圖所示：

執行引擎所做的事情就包括，定義 TableScan，Filter 等一系列關係運算元（Operator）的實現框架，從而可以組合使用多個關係運算元，構建它們之間的資料依賴關係（也就是執行計劃），最終實現不同 SQL 的功能。

最經典的執行引擎實現非 Volcano ^[6] 莫屬了。它把每一個運算元抽象成資料的迭代器（Iterator），分別由 Open，Next，Close 構成。其中 Open 做一些初始化的工作，比如 TableScan 如何實現開啟對應的表文件；Next 按照特定運算元的功能邏輯處理資料，增量式得到輸出；Close 清理資源。如下的虛擬碼就是 TableScan 的一個實現：

public class TableScan implement Iterator{
    void open(){
        tableFile.open();
    }
    Row next(){
        if ( (row = tableFile.nextRow()) != EOF){
            return row;
        }
        return EOF;
    }
    
    void close(){
        tableFile.close();
    }
}

Volcano 的優點在於處理邏輯清晰，每個運算元只需關心自己的處理邏輯即可，耦合性低。不過它的缺點也很明顯，過多虛擬函式的呼叫，導致大量 CPU cache miss，從而影響 CPU 執行效率。

在資料庫誕生之初，資料庫先賢們奮戰在彌補磁碟和 CPU 速度巨大的鴻溝上，CPU 的浪費顯得微不足道。然而，在資料庫新時代，摩爾定律的失效使得單核效能提升日漸趨緩，OLAP 的發展導致將大量資料載入到記憶體進行計算，瓶頸慢慢從儲存端向 CPU 端傾斜，榨乾 CPU 每一滴效能的企圖就變得越發強烈，於是 CodeGen，向量化執行 ^[7] 等方法應運而生，它們從不同的方向入手來優化 CPU 的利用率，能夠極大的提高執行效率。向量化執行正是利用列式儲存的優勢，可以一次性對整列資料進行批量處理，減少 CPU 的消耗。

關係運算元

有了執行引擎奠定的框架，關係運算元只需要一個蘿蔔一個坑，逐一實現即可，然而演算法的世界是層出不窮，千變萬化的，比如對於 Join 大家最熟悉的演算法就有 BroadcastJoin，LookupJoin，SortJoin 等等，而列存又會給 Join 演算法帶來什麼樣的優化空間呢？

對於 Join 而言，運算的核心在於兩表中 Joinkey 的匹配上，而對於其他列資料匹配上了就複製，匹配不上就丟棄。那麼結合延遲物化的思想，是否可以等到匹配完成後再載入其他列資料，從而減小不必要的資料載入。

舉個例子，對於如下 SQL：

SELECT emp.age, dept.name FROM emp, dept
WHERE emp.dept_id = dept.id

我們先抽出 emp 表的 dept_id 和 dept 表的 id 列資料，進行匹配，並輸出匹配結果對應原表的位置資訊，如下圖所示：

其中等於號的左邊為 dept_id 和 id 列的資料，等於號的右邊為匹配結果對應原表的位置資訊，比如第一行 1，2 代表 dept_id 列的第一個值 42 和 id 列的第 2 個值 42，Join 的結果。

然後根據輸出的位置資訊，就可以從原始資料中抽取 age，name 列的資料得到 Join 最後的結果。當然該演算法能夠產生明顯優化效果的前提是 Join 的結果相較於原始資料比較小，這樣才能夠有效避免載入過多資料。另外由於上圖輸出結果的第二列是無序的，如果回表查必然造成大量隨機 IO，為了解決這個問題，Jive Join ^[8] 採用了對其進行排序之後再查詢，即將隨機 IO 轉化為順序 IO 的方法進行優化。

總結

綜上，我們從大資料儲存格式的變遷；存取方式中 Early Materialization 和 Late Materialization 的權衡取捨；執行框架向優化 CPU 的方向邁進；關係運算元結合儲存進行優化等幾個方面對列存資料庫進行了講解。

實際上，列存資料庫不只是儲存格式的問題，底層儲存的變化往往牽一髮而動全身，如何適應性的修改計算引擎、存取方式等來達到更高更快的效能，並適應不同的 workload 或者硬體發展的趨勢，都是列存資料庫要關心的問題。