大話 Druid 存儲(chǔ)結(jié)構(gòu)
點(diǎn)擊上方藍(lán)色字體，選擇“設(shè)為星標(biāo)”
回復(fù)”資源“獲取更多驚喜
Apache Druid是一款優(yōu)秀的OLAP引擎，眾所周知數(shù)據(jù)存儲(chǔ)格式對(duì)一款存儲(chǔ)系統(tǒng)來說是最核心的組件，Druid的數(shù)據(jù)格式是自定義的，以此保證了在海量數(shù)據(jù)下的亞秒級(jí)查詢。本文深入分析Druid V1版本數(shù)據(jù)存儲(chǔ)格式，包括索引結(jié)構(gòu)和數(shù)據(jù)在磁盤中的存儲(chǔ)方式。在閱讀本文之前希望您對(duì)Druid和數(shù)據(jù)存儲(chǔ)有簡(jiǎn)單了解。
Druid的存儲(chǔ)方式是列式的，每個(gè)列為一個(gè)邏輯文件，列與列之間的數(shù)據(jù)格式是相對(duì)獨(dú)立的。與傳統(tǒng)OLAP系統(tǒng)一樣，Druid的列分為維度與度量?jī)煞N，其中維度列因?yàn)樾枰粰z檢索，所以設(shè)計(jì)了索引，維度列的數(shù)據(jù)格式也是Druid數(shù)據(jù)結(jié)構(gòu)的核心；相對(duì)的度量列只需要存儲(chǔ)行值就可以。為了方便闡述數(shù)據(jù)格式，本文以一個(gè)廣告效果分析作為例子進(jìn)行分析，圖1中是樣例數(shù)據(jù)，請(qǐng)一定注意它是聚合后的數(shù)據(jù)，而不是原始數(shù)據(jù)。
維度數(shù)據(jù)結(jié)構(gòu)
上文提到維度是Druid存儲(chǔ)結(jié)構(gòu)的核心，并且各個(gè)維度是相對(duì)獨(dú)立存儲(chǔ)的，所以我們可以通過分析單個(gè)維度的數(shù)據(jù)結(jié)構(gòu)，來窺探Druid的存儲(chǔ)結(jié)構(gòu)。圖2展示了“city”維度和兩個(gè)度量的邏輯存儲(chǔ)結(jié)構(gòu)，整體上Druid維度的索引包含三部分：字典、編碼后的維度值、倒排索引，接下來詳細(xì)分析這三部分。
字典
字典是將列的所有值去重，然后按照字典順序排序的值組成的數(shù)組，雖然字典中只存儲(chǔ)了排序后的維度值，但是它還隱含了另一個(gè)信息，那就是每個(gè)維度值的編碼值，編碼值就等于數(shù)組的下標(biāo)。字典的設(shè)計(jì)目的有兩個(gè)：一是維度值可以使用編碼后的整數(shù)表示，而不是實(shí)際的值，編碼值一般可以節(jié)約存儲(chǔ)空間；二是編碼后的整數(shù)是定長(zhǎng)的，磁盤中定長(zhǎng)存儲(chǔ)可以省去定位單個(gè)值的offset length等索引信息的開銷，最終還是能節(jié)省存儲(chǔ)空間。
圖3展示了Druid字典的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，Druid字典采用了線性的數(shù)組結(jié)構(gòu)。因?yàn)樽值渲械闹凳遣欢ㄩL(zhǎng)的，所以物理結(jié)構(gòu)中有一段index部分，其中記錄了每個(gè)值的offset；data部分每個(gè)值的頭部記錄了該值的長(zhǎng)度。這樣的設(shè)計(jì)才能定位到任意一個(gè)行的值。
編碼后的維度值
Druid是一個(gè)預(yù)聚合的方案，但是其聚合不是按照一個(gè)維度的group-by聚合，而是按照所有維度的group-by聚合，對(duì)于圖1中的數(shù)據(jù)已經(jīng)是按照聚合過了。可以看出對(duì)于單一維度而言，編碼過后的維度值依然可能重復(fù)，所以每個(gè)維度的行信息不能用字典代替，而需要額外存儲(chǔ)。
編碼后的維度值都是一個(gè)個(gè)的整數(shù)。為了保證單一值在磁盤中能快速定位，在整個(gè)維度范圍內(nèi)這些整數(shù)需要是定長(zhǎng)的，因?yàn)槎ㄩL(zhǎng)元素組成的數(shù)組可以通過計(jì)算直接定位到某一個(gè)元素。同時(shí)為了節(jié)約存儲(chǔ)空間這些整數(shù)不一定需要用4個(gè)字節(jié)表示，它的長(zhǎng)度取決于該維度在單一數(shù)據(jù)文件內(nèi)的唯一值的數(shù)量，Druid采用了采用了變長(zhǎng)整數(shù)編碼的方式，具體如下：
1 – 2^8-1 => 1 byte
2^8 - 2^16-1 => 2 bytes
2^16 - 2^24-1 => 3 bytes
2^24 - 2^32-1 => 4 bytes
2^32 - 2^40-1 => 5 bytes
...
以圖1中“city”維度為例，它包含唯一值3個(gè)，所以每個(gè)值用1個(gè)字節(jié)表示。
圖4展示了編碼后維度值的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，在邏輯上整個(gè)維度是一個(gè)線性的結(jié)構(gòu)，但是在物理存儲(chǔ)上數(shù)據(jù)結(jié)構(gòu)中包含了offset索引和元素length部分，這很明顯是存儲(chǔ)非定長(zhǎng)數(shù)據(jù)的。原來Druid將整個(gè)線性結(jié)構(gòu)首先劃分成了一個(gè)個(gè)分組，每個(gè)分組大小不超過64KB，而分組又進(jìn)行了壓縮，壓縮后的分組已經(jīng)是非定長(zhǎng)的了，所以站在整個(gè)數(shù)據(jù)結(jié)構(gòu)的角度，需要按照非定長(zhǎng)數(shù)據(jù)的格式進(jìn)行存儲(chǔ)。
將整個(gè)整數(shù)數(shù)組進(jìn)行分組壓縮的設(shè)計(jì)思路，其背后的考量點(diǎn)主要是：一是對(duì)于磁盤存儲(chǔ)壓縮是有必要的，因?yàn)槟軠p小空間占用和傳輸消耗；二是分組也是有必要的，因?yàn)榻^大多數(shù)讀取數(shù)據(jù)的場(chǎng)景不會(huì)涉及到所有的分組，而是部分分組，分組后一次查詢只涉及到了少數(shù)分組，對(duì)于查詢速度的提升有極大幫助。
倒排索引
最后是倒排索引部分，對(duì)于字典中的每個(gè)元素，Druid都會(huì)生成一個(gè)Bitmap，其中1表示該bit下標(biāo)對(duì)應(yīng)的行的值是對(duì)應(yīng)字典元素的值，反之不是。
Bitmap數(shù)據(jù)是基于聚合后的數(shù)據(jù)的，所以它的長(zhǎng)度和原始數(shù)據(jù)的行數(shù)是沒有關(guān)系的。從圖5中“Beijing”對(duì)應(yīng)的Bitmap可以看出，它基于圖1中的聚合后的數(shù)據(jù)，而不是原始數(shù)據(jù)，所以Bitmap的長(zhǎng)度是4。
Druid的反向索引采用的是Bitmap的方案，因?yàn)樽值渲忻總€(gè)元素對(duì)應(yīng)的Bitmap的長(zhǎng)度都是一樣的，所以物理存儲(chǔ)上可以采用定長(zhǎng)的方式？其實(shí)不是的，出于節(jié)省存儲(chǔ)空間的考慮，Druid將每個(gè)Bitmap進(jìn)行了壓縮，一般Bitmap數(shù)據(jù)結(jié)構(gòu)的壓縮比例是比較大的，所以壓縮的是有必要的。因?yàn)閴嚎s后數(shù)據(jù)長(zhǎng)度不相同了，所以存儲(chǔ)上需要按照非定長(zhǎng)數(shù)據(jù)進(jìn)行存儲(chǔ)。
數(shù)組
Druid是支持?jǐn)?shù)組數(shù)據(jù)類型維度的，對(duì)于數(shù)組數(shù)據(jù)類型Druid如何存儲(chǔ)呢？整體上數(shù)組的存儲(chǔ)方式還是字典、編碼后的維度值、倒排索引三個(gè)部分。其中字典和倒排索引部分是跟單值類型的維度的存儲(chǔ)方式?jīng)]有任何區(qū)別。
但是在編碼后的維度值部分是有區(qū)別的，對(duì)于單值維度這部分的邏輯結(jié)構(gòu)是一個(gè)線性列表（這里暫時(shí)不考慮分組），但是對(duì)于數(shù)組類型的維度，它其實(shí)是一個(gè)二層的層次結(jié)構(gòu)，外層是一個(gè)非定長(zhǎng)的線性列表，線性列表的每個(gè)元素也就是內(nèi)層，是一個(gè)定長(zhǎng)的線性列表。對(duì)于整個(gè)數(shù)據(jù)結(jié)構(gòu)來說，在物理結(jié)構(gòu)上依然可以進(jìn)行分組和壓縮。
存儲(chǔ)結(jié)構(gòu)小結(jié)
對(duì)于物理結(jié)構(gòu)來說其元素是否定長(zhǎng)，對(duì)其存儲(chǔ)方式起到?jīng)Q定作用，圖6總結(jié)了定長(zhǎng)和非定長(zhǎng)的存儲(chǔ)模式，請(qǐng)注意這里沒有考慮分組和壓縮。
Druid對(duì)線性非定長(zhǎng)存儲(chǔ)結(jié)構(gòu)有這大量的應(yīng)用，它遵循圖6的總結(jié)，只是在元數(shù)據(jù)部分稍有不同，現(xiàn)總結(jié)如下：
version：占用 1byte
allowReverseLookup：1byte ，是否允許反向查找，指根據(jù)Value反查index, 用于Dictionary字典查找
numBytesUsed ：4bytes ，所占字節(jié)數(shù)
numElements：4bytes，元素的總數(shù)量
如何使用
最后簡(jiǎn)單分析下Druid在查詢中如何使用到以上數(shù)據(jù)結(jié)構(gòu)，為了聚焦問題，假設(shè)查詢只命中了一個(gè)數(shù)據(jù)文件，這樣可以忽略多個(gè)數(shù)據(jù)文件的結(jié)果合并等問題。我們以下面簡(jiǎn)單查詢?yōu)槔?/span>
select city, sum(click_cnt) from table_t where category=0 or category=1 group by city
圖8展示了查詢流程，其中第1.6步用到了字典結(jié)構(gòu)，第3步用到了倒排索引數(shù)據(jù)結(jié)構(gòu)，第4部用到了編碼后的維度值數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)湖VS數(shù)據(jù)倉(cāng)庫(kù)？湖倉(cāng)一體了解一下
Kylin、Druid、ClickHouse核心技術(shù)對(duì)比
萬字長(zhǎng)文，超全Spark性能優(yōu)化總結(jié)
代達(dá)羅斯之殤-大數(shù)據(jù)領(lǐng)域小文件問題解決攻略
大數(shù)據(jù)可視化從未如此簡(jiǎn)單 - Apache Zepplien全面介紹
Kylin 大數(shù)據(jù)下的OLAP解決方案和行業(yè)典型應(yīng)用
版權(quán)聲明：
編輯|?《大數(shù)據(jù)技術(shù)與架構(gòu)》
文章鏈接|?http://www.jackywoo.cn/data-structure-in-druid/
文章不錯(cuò)？點(diǎn)個(gè)【在看】吧！??