黃峰，Kyligence?公司高級(jí)研發(fā)工程師，目前主要負(fù)責(zé)?Kyligence?企業(yè)級(jí)產(chǎn)品的開發(fā)以及維護(hù)工作。

對(duì)?OLAP?場(chǎng)景的查詢而言，單個(gè)查詢往往需要在存儲(chǔ)端掃描大量數(shù)據(jù)，再在內(nèi)存中進(jìn)行一些統(tǒng)計(jì)分析后，才能輸出所需要的統(tǒng)計(jì)結(jié)果。因此，如果不能像以?Kylin?為代表的?MOLAP?引擎采用預(yù)計(jì)算的方式來避免數(shù)據(jù)的實(shí)時(shí)掃描，對(duì)于基于磁盤存儲(chǔ)的數(shù)倉(cāng)而言，存儲(chǔ)端無疑會(huì)因?yàn)閽呙璐罅繑?shù)據(jù)造成磁盤吞吐的瓶頸。

既然如此，是否存在別的選擇，可以少?gòu)拇鎯?chǔ)端加載數(shù)據(jù)呢？列存數(shù)據(jù)庫正是通過采取合適的數(shù)據(jù)組織結(jié)構(gòu)，來減小查詢加載的數(shù)據(jù)量，最終提高查詢效率。

大數(shù)據(jù)圈的各位對(duì)列式存儲(chǔ)一定不陌生，快速浮現(xiàn)你腦海里的想必是?ORCFile，Parquet?等，但其實(shí)這些只是數(shù)據(jù)格式，并不能直接和列存數(shù)據(jù)庫劃等號(hào)。

列存格式?=?列存數(shù)據(jù)庫

列存數(shù)據(jù)庫?[1]?更像是基于列存格式，設(shè)計(jì)的一套完整的數(shù)據(jù)庫解決方案，而這套解決方案不僅需要考慮數(shù)據(jù)格式，更要考慮以下因素：

由于考慮成本效率的因素，計(jì)算機(jī)中的存儲(chǔ)常被設(shè)計(jì)成多級(jí)存儲(chǔ)的結(jié)構(gòu)，所以數(shù)據(jù)不單在磁盤上有特定的存儲(chǔ)格式，在內(nèi)存中，甚至?L1，L2，L3?緩存中同樣有其獨(dú)特的布局方式。考慮到存儲(chǔ)端復(fù)雜的情況，如何結(jié)合?OLAP?場(chǎng)景的?workload，從而針對(duì)不同的硬件特點(diǎn)設(shè)計(jì)數(shù)據(jù)布局，是列存數(shù)據(jù)庫在存儲(chǔ)端需要考慮的核心問題;

有了在不同存儲(chǔ)層的數(shù)據(jù)存儲(chǔ)布局之后，數(shù)據(jù)如何在不同存儲(chǔ)層之間流動(dòng)，比如，如何從磁盤加載數(shù)據(jù)到內(nèi)存，什么時(shí)候進(jìn)行加載，這些都是存取方法?[2]?(Access?Method)所涉及的內(nèi)容;

數(shù)據(jù)結(jié)構(gòu)配上合適的算法才能橫行江湖，計(jì)算和數(shù)據(jù)組織方式往往緊密耦合，彰顯團(tuán)結(jié)的力量。如何結(jié)合列存的特點(diǎn)設(shè)計(jì)一個(gè)高效的執(zhí)行引擎，為?Join，Sort，Groupby?等關(guān)系算子提供一種更為高效的算法，都是列存數(shù)據(jù)庫需要考慮的問題。

由此可見，為了追求極致的性能，底層存儲(chǔ)的變化往往會(huì)引發(fā)?存取方法、?執(zhí)行引擎、?關(guān)系算子算法實(shí)現(xiàn)等多方面的一系列適配性的變化，真可謂環(huán)環(huán)相扣，好不緊張。下面，我們就依次從這幾個(gè)方面介紹其所涉及內(nèi)容。

01

存儲(chǔ)格式

可曾記得把列存的思想引入大數(shù)據(jù)的先驅(qū)者——?RCFile?[3]?，它的基本思想是將數(shù)據(jù)水平切分成一個(gè)個(gè)行組，在每個(gè)行組內(nèi)除了元數(shù)據(jù)和行組切分標(biāo)識(shí)以外，數(shù)據(jù)部分按列來進(jìn)行連續(xù)存儲(chǔ)。

這樣操作的原因在于?OLAP?的查詢雖然一般都會(huì)掃描大量行，但只會(huì)涉及少量列，通過這樣的列存布局方式，能夠有效避免無關(guān)列的加載，從而達(dá)到減小磁盤吞吐的目的。

但似乎先驅(qū)者的下場(chǎng)往往不那么盡如人意，RCFile?也沒有擺脫這個(gè)魔咒。相較傳統(tǒng)數(shù)倉(cāng)中的列存而言，RCFile?還是太過粗糙，要學(xué)就學(xué)全套呀!

Hive?的開發(fā)者們總結(jié)了?RCFile?的經(jīng)驗(yàn)教訓(xùn)，指出其核心問題?[4]?在于：

對(duì)數(shù)據(jù)類型不感知，從而無法對(duì)具體類型做編碼優(yōu)化，限制了列存的存儲(chǔ)高效性;

沒有索引輔助過濾數(shù)據(jù)(如：謂詞下推)，造成數(shù)據(jù)讀取效率低下。

站在前人的肩膀上，后續(xù)的?ORCFile，Parquet?都開啟了進(jìn)化之旅，一方面加入一些?Min、Max、Count?等?輕量級(jí)統(tǒng)計(jì)索引來加速查詢;另一方面，針對(duì)不同場(chǎng)景，采用?RLE，Bitcode，Dictionary?Code?等編碼方式進(jìn)行存儲(chǔ)優(yōu)化，比如?RLE，針對(duì)的就是取值范圍不大，重復(fù)度高的數(shù)據(jù)，假設(shè)有一列數(shù)據(jù)是?AAABBBB，RLE?就會(huì)直接采用?A3B4?來表達(dá)(其中“3”和“4”代表前一個(gè)值出現(xiàn)的次數(shù))。

自此以后，列存格式的風(fēng)吹遍了整個(gè)大數(shù)據(jù)生態(tài)圈，CarbonData?采用多維排序的方式優(yōu)化數(shù)據(jù)的列式布局;Druid?在列存之上，通過對(duì)維度列進(jìn)行?Dictionary?編碼加?Bitmap?索引的方式加速了數(shù)據(jù)的篩選和聚合......

當(dāng)然，存儲(chǔ)格式并不是只需關(guān)心存儲(chǔ)查詢的效率問題，將其應(yīng)用到實(shí)際中所需要考慮的問題同樣重要。比如，2019?年?4?月，Databricks?公司重磅開源?Delta?Lake，給數(shù)據(jù)添加了?ACID?特性，支持?jǐn)?shù)據(jù)的并發(fā)讀寫，Hudi?和?Iceberg?也不甘落后，存儲(chǔ)的故事又拉開了一張大幕，世界就是這樣精彩!

02

存取方式

數(shù)據(jù)存在磁盤上的數(shù)據(jù)布局叫做存儲(chǔ)格式，而存取方式則包括：

數(shù)據(jù)是怎么從磁盤讀到內(nèi)存的？(例如?MySQL?加載數(shù)據(jù)的時(shí)候，是通過全表掃描，還是通過索引掃描)

數(shù)據(jù)在內(nèi)存的布局是怎樣的？

數(shù)據(jù)又是怎么寫回磁盤的？

等一系列過程。

這里我們以數(shù)據(jù)從磁盤加載到內(nèi)存的過程為例，來探討列式存儲(chǔ)能夠給存取過程帶來哪些優(yōu)勢(shì)。由于數(shù)據(jù)最終輸出時(shí)是以行為單位，所以在將列存數(shù)據(jù)讀入內(nèi)存時(shí)，直接定位到要掃描的列，然后按順序重構(gòu)一行行數(shù)據(jù)并交由執(zhí)行引擎處理，就顯得尤為自然，但我們不如想的更深入一步：

內(nèi)存中的數(shù)據(jù)表是不是也可以是列式的？

數(shù)據(jù)是不是可以懶加載(延遲物化)？

對(duì)于問題一，Presto、ClickHouse?等實(shí)踐者通過在內(nèi)存中使用列存布局，不僅優(yōu)化了存儲(chǔ)效率，也使得向量化計(jì)算加速分析查詢變?yōu)榭赡?

對(duì)于延遲物化?[5]?的問題，核心就在于?數(shù)據(jù)是否能等到真正需要它們的時(shí)候再加載，例如對(duì)于以下查詢：

selectb?fromR?wherea?=X?andd?=Y

是直接如上圖左側(cè)所示，將查詢涉及到的?a、b、d?列全部加載到內(nèi)存里構(gòu)成一行一行數(shù)據(jù)，然后進(jìn)行過濾(Filter)和映射(Project);

還是如上圖右側(cè)所示，選擇盡量延遲加載，先分別對(duì)?a、d?列進(jìn)行單獨(dú)加載過濾，決定要輸出的行(圖中的?01?向量)，再把對(duì)應(yīng)行的?b?列加載輸出，最后再構(gòu)建成行數(shù)據(jù)輸出？

這兩者的?Tradeoff?在于，雖然延遲加載能夠減少數(shù)據(jù)的加載量，但需要維護(hù)原始數(shù)據(jù)的位置，這樣才能找到對(duì)應(yīng)行的其他列的值，然而如果篩選條件(R.a?=?X?and?R.d?=?Y?)不能大量過濾數(shù)據(jù)，延遲加載反而低效。對(duì)于這種情況，就需要根據(jù)一些統(tǒng)計(jì)信息選擇合適的加載算法，來最大限度的提高效率。

03

執(zhí)行引擎與關(guān)系算子

說完了存儲(chǔ)端的故事，讓我們轉(zhuǎn)戰(zhàn)計(jì)算端，嘮一嘮執(zhí)行引擎和關(guān)系算子與列存之間又有怎樣的故事。

執(zhí)行引擎

首先，來了解一下執(zhí)行引擎的在?SQL?查詢過程中發(fā)揮了什么樣的作用。

熟悉?SQL?查詢引擎的同學(xué)應(yīng)該都清楚，一條?SQL?會(huì)經(jīng)過詞法語法解析、語義校驗(yàn)、邏輯執(zhí)行計(jì)劃生成優(yōu)化等一系列步驟，生成最后的物理執(zhí)行計(jì)劃，例如，對(duì)于如下?SQL：

select*fromR?wherea?=1

其物理執(zhí)行計(jì)劃如下圖所示：

執(zhí)行引擎所做的事情就包括，定義?TableScan，F(xiàn)ilter?等一系列關(guān)系算子(Operator)的實(shí)現(xiàn)框架，從而可以組合使用多個(gè)關(guān)系算子，構(gòu)建它們之間的數(shù)據(jù)依賴關(guān)系(也就是執(zhí)行計(jì)劃)，最終實(shí)現(xiàn)不同?SQL?的功能。

最經(jīng)典的執(zhí)行引擎實(shí)現(xiàn)非?Volcano?[6]?莫屬了。它把每一個(gè)算子抽象成數(shù)據(jù)的迭代器(Iterator)，分別由?Open，Next，Close?構(gòu)成。其中?Open?做一些初始化的工作，比如?TableScan?如何實(shí)現(xiàn)打開對(duì)應(yīng)的表文件;Next?按照特定算子的功能邏輯處理數(shù)據(jù)，增量式得到輸出;Close?清理資源。如下的偽代碼就是?TableScan?的一個(gè)實(shí)現(xiàn)：

publicclassTableScanimplementIterator{?voidopen{?tableFile.open;?}?Row?next{?if(?(row?=?tableFile.nextRow)?!=?EOF){?returnrow;?}?returnEOF;?}?voidclose{?tableFile.close;?}?}

Volcano?的優(yōu)點(diǎn)在于處理邏輯清晰，每個(gè)算子只需關(guān)心自己的處理邏輯即可，耦合性低。不過它的缺點(diǎn)也很明顯，過多虛函數(shù)的調(diào)用，導(dǎo)致大量?CPU?cache?miss，從而影響?CPU?執(zhí)行效率。

在數(shù)據(jù)庫誕生之初，數(shù)據(jù)庫先賢們奮戰(zhàn)在彌補(bǔ)磁盤和?CPU?速度巨大的鴻溝上，CPU?的浪費(fèi)顯得微不足道。然而，在數(shù)據(jù)庫新時(shí)代，摩爾定律的失效使得單核性能提升日漸趨緩，OLAP?的發(fā)展導(dǎo)致將大量數(shù)據(jù)加載到內(nèi)存進(jìn)行計(jì)算，瓶頸慢慢從存儲(chǔ)端向?CPU?端傾斜，榨干?CPU?每一滴性能的企圖就變得越發(fā)強(qiáng)烈，于是?CodeGen，向量化執(zhí)行?[7]?等方法應(yīng)運(yùn)而生，它們從不同的方向入手來優(yōu)化?CPU?的利用率，能夠極大的提高執(zhí)行效率。?向量化執(zhí)行正是利用列式存儲(chǔ)的優(yōu)勢(shì)，可以一次性對(duì)整列數(shù)據(jù)進(jìn)行批量處理，減少?CPU?的消耗。

關(guān)系算子

有了執(zhí)行引擎奠定的框架，關(guān)系算子只需要一個(gè)蘿卜一個(gè)坑，逐一實(shí)現(xiàn)即可，然而算法的世界是層出不窮，千變?nèi)f化的，比如對(duì)于?Join?大家最熟悉的算法就有?BroadcastJoin，LookupJoin，SortJoin?等等，?而列存又會(huì)給?Join?算法帶來什么樣的優(yōu)化空間呢？

對(duì)于?Join?而言，運(yùn)算的核心在于兩表中?Joinkey?的匹配上，而對(duì)于其他列數(shù)據(jù)匹配上了就復(fù)制，匹配不上就丟棄。那么結(jié)合延遲物化的思想，是否可以等到匹配完成后再加載其他列數(shù)據(jù)，從而減小不必要的數(shù)據(jù)加載。

舉個(gè)例子，對(duì)于如下?SQL：

SELECTemp.age,?dept.name?FROMemp,?dept?WHEREemp.dept_id?=dept.id

我們先抽出?emp?表的?dept_id?和?dept?表的?id?列數(shù)據(jù)，進(jìn)行匹配，并輸出匹配結(jié)果對(duì)應(yīng)原表的位置信息，如下圖所示：

其中等于號(hào)的左邊為?dept_id?和?id?列的數(shù)據(jù)，等于號(hào)的右邊為匹配結(jié)果對(duì)應(yīng)原表的位置信息，比如第一行?1，2?代表?dept_id?列的第一個(gè)值?42?和?id?列的第?2?個(gè)值?42，Join?的結(jié)果。

然后根據(jù)輸出的位置信息，就可以從原始數(shù)據(jù)中抽取?age，name?列的數(shù)據(jù)得到?Join?最后的結(jié)果。當(dāng)然該算法能夠產(chǎn)生明顯優(yōu)化效果的前提是?Join?的結(jié)果相較于原始數(shù)據(jù)比較小，這樣才能夠有效避免加載過多數(shù)據(jù)。另外由于上圖輸出結(jié)果的第二列是無序的，如果回表查必然造成大量隨機(jī)?IO，為了解決這個(gè)問題，Jive?Join?[8]?采用了對(duì)其進(jìn)行排序之后再查詢，即將隨機(jī)?IO?轉(zhuǎn)化為順序?IO?的方法進(jìn)行優(yōu)化。

04

總結(jié)

綜上，我們從大數(shù)據(jù)存儲(chǔ)格式的變遷;存取方式中?Early?Materialization?和?Late?Materialization?的權(quán)衡取舍;執(zhí)行框架向優(yōu)化?CPU?的方向邁進(jìn);關(guān)系算子結(jié)合存儲(chǔ)進(jìn)行優(yōu)化等幾個(gè)方面對(duì)列存數(shù)據(jù)庫進(jìn)行了講解。

實(shí)際上，列存數(shù)據(jù)庫不只是存儲(chǔ)格式的問題，底層存儲(chǔ)的變化往往牽一發(fā)而動(dòng)全身，如何適應(yīng)性的修改計(jì)算引擎、存取方式等來達(dá)到更高更快的性能，并適應(yīng)不同的?workload?或者硬件發(fā)展的趨勢(shì)，都是列存數(shù)據(jù)庫要關(guān)心的問題。

參考文獻(xiàn)：

[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.

最后，小編給您推薦，如果您不想讓您的文檔被其他人查看，您可以使用金山毒霸“文件夾加密”，讓文檔更加安全。