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

語言: CN / TW / HK

作者簡介

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

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

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

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

列存格式 = 列存資料庫

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

  1. 由於考慮成本效率的因素,計算機中的儲存常被設計成多級儲存的結構,所以資料不單在磁碟上有特定的儲存格式,在記憶體中,甚至 L1,L2,L3 快取中同樣有其獨特的佈局方式。考慮到儲存端複雜的情況,如何結合 OLAP 場景的 workload,從而針對不同的硬體特點設計資料佈局,是列存資料庫在儲存端需要考慮的核心問題;

  2. 有了在不同儲存層的資料儲存佈局之後,資料如何在不同儲存層之間流動,比如,如何從磁碟載入資料到記憶體,什麼時候進行載入,這些都是存取方法 [2] (Access Method)所涉及的內容;

  3. 資料結構配上合適的演算法才能橫行江湖,計算和資料組織方式往往緊密耦合,彰顯團結的力量。如何結合列存的特點設計一個高效的執行引擎,為 Join,Sort,Groupby 等關係運算元提供一種更為高效的演算法,都是列存資料庫需要考慮的問題。

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

01

儲存格式

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

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

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

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

  1. 對資料型別不感知,從而無法對具體型別做編碼優化,限制了列存的儲存高效性;

  2. 沒有索引輔助過濾資料(如:謂詞下推),造成資料讀取效率低下。

站在前人的肩膀上,後續的 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 也不甘落後,儲存的故事又拉開了一張大幕,世界就是這樣精彩!

02

存取方式

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

  • 資料是怎麼從磁碟讀到記憶體的?(例如 MySQL 載入資料的時候,是通過全表掃描,還是通過索引掃描)

  • 資料在記憶體的佈局是怎樣的?

  • 資料又是怎麼寫回磁碟的?

等一系列過程。

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

  1. 記憶體中的資料表是不是也可以是列式的?

  2. 資料是不是可以懶載入(延遲物化)?

對於問題一,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 )不能大量過濾資料,延遲載入反而低效。對於這種情況,就需要根據一些統計資訊選擇合適的載入演算法,來最大限度的提高效率。

03

執行引擎與關係運算元

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

執行引擎

首先,來了解一下執行引擎的在 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 的方法進行優化。

04

總結

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

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

參考文獻:

[1] The Design and Implementation of Modern Column-oriented Database Systems.

[2] Design Tradeoffs of Data Access Methods.

[3] RCFile: A Fast and Space-efficient Data Placement Structure in MapReduce-based Warehouse Systems.

[4] Major Technical Advancements in Apache Hive.

[5] Materialization Strategies in a Column-oriented DBMS.

[6] Encapsulation of Parallelism in the Volcano Query Processing System.

[7] Vectorization vs. Compilation in Query Execution.

[8] Fast Joins Using Join Indices.

點選閱讀原文,體驗 Kylin 4.0.0-beta