簡(jiǎn)介

《Apache Drill學(xué)習(xí)筆記一：環(huán)境搭建和簡(jiǎn)單試用》提到過Apache Drill是受Google的Dremel系統(tǒng)啟發(fā)而設(shè)計(jì)實(shí)現(xiàn)的，這出于Google公開于2010年的論文“Dremel Interactive Analysis of WebScaleDatasets”。為了弄清楚Apache Drill的運(yùn)行機(jī)制，這篇論文是一定要先仔細(xì)研讀的，否則就只能像我之前那樣僅僅將其作為CSV或者JSON的SQL查詢工具使用了，而不能真正發(fā)揮其強(qiáng)大的性能優(yōu)勢(shì)。

簡(jiǎn)單說Dremel是Google的“交互式”數(shù)據(jù)分析系統(tǒng)，可以組建成規(guī)模上千的集群，處理PB級(jí)別的數(shù)據(jù)。雖然MapReduce也可以處理這樣規(guī)模的數(shù)據(jù)，但它所需要的時(shí)間相對(duì)比較長(zhǎng)，適合數(shù)據(jù)的批處理，而不適合交互式查詢的場(chǎng)景，Dremel正是這樣的一個(gè)有力補(bǔ)充。

Dremel有2個(gè)顯著特點(diǎn)：

• 可以在秒級(jí)別的時(shí)間查詢PB級(jí)別的數(shù)據(jù)。
• 數(shù)據(jù)模型是嵌套(nested)的。

而這正是其他數(shù)據(jù)庫(kù)、查詢引擎的痛點(diǎn)所在，也正是我們需要著重了解的地方。

數(shù)據(jù)模型

Dremel使用的數(shù)據(jù)就是我們熟悉的Protocol Buffer格式，但通常情況我們都是作為序列化方法或者在RPC中傳輸?shù)葓?chǎng)景使用，較少用它來存放大量數(shù)據(jù)。對(duì)于沒有接觸過Protocol Buffer的讀者，可以用JSON類比，二者結(jié)構(gòu)很相似，一個(gè)不同是Protocol Buffer不支持JSON的map（或者說是dict、hashmap）。

一個(gè)Protocol Buffer的Document.proto文件示例：

message Document {
    required int64 DocId;
    optional group Links {
        repeated int64 Backward;
        repeated int64 Forward;
    }

    repeated group Name {
        repeated group Language {
            required string Code;
            optional string Country;
        }
        optional string Url;
    }
}

注意的不是數(shù)據(jù)本身，而是數(shù)據(jù)的類型，或者說是數(shù)據(jù)的schema。但從中已經(jīng)可以看出2個(gè)特點(diǎn)：

• 類型是可以嵌套的。
• 同一種類型的數(shù)據(jù)是可以重復(fù)（repeated）和可選（optional）的。

對(duì)如此復(fù)雜的數(shù)據(jù)做SQL查詢看起來是很讓人頭疼的，我們自然想到先簡(jiǎn)化一下，從最簡(jiǎn)單的情況考慮。

這種數(shù)據(jù)格式用數(shù)學(xué)方法嚴(yán)格表示是這樣的：

t = dom | <A1:t[*|?], ..., An:t[*|?]>

看起來有點(diǎn)復(fù)雜，但理解起來很容易。t（原文是希臘字母τ，但為了書寫方便這里改成英文字母t）是一個(gè)數(shù)據(jù)類型的定義，而.proto文件就是定義一個(gè)或多個(gè)數(shù)據(jù)類型。t有兩種可能（|和c語言一樣是“或”的意思，一種是基本類型dom（如int、string、float等），另一種是使用遞歸方式定義的，即t可以由其他之前定義好的t組成，就像c中的結(jié)構(gòu)體一樣，與結(jié)構(gòu)體不大相同的是，每個(gè)包含的t的值可以有多個(gè)（*，repeated，類似c中的數(shù)組），還可以是可選的（?，optional，之前那個(gè)數(shù)組可以不包含任何元素）。A1-An是這些t的命名（也就是A1是某個(gè)t類型的變量）。其實(shí)從這個(gè)定義中更容易看出之前總結(jié)的2個(gè)特點(diǎn)。

簡(jiǎn)單情況

現(xiàn)在我們來考慮簡(jiǎn)單的Protocol Buffer數(shù)據(jù)，以及如何查詢。

這是一個(gè)簡(jiǎn)化的Document.proto，可以看到它只有一層結(jié)構(gòu)，而且沒有repeated和optional字段。

message Document {
    required int64 DocId;
    string Url;
    string Country;
    int64 Code;
}

而Document的數(shù)據(jù)就是一張普通的二維表：

可以看出我們用二維的方式組織數(shù)據(jù)，但實(shí)際是數(shù)據(jù)在磁盤的地址是一維的，也就是我們需要按某種方式把它拼接成一維的數(shù)據(jù)。那最基本的方式有兩種：

• 按行存：

• 按列存：

我們先考慮下對(duì)這個(gè)表進(jìn)行select，如select Url, Code from Document;

如果是按行存的話，每讀一個(gè)Url后，都需要跳到下一個(gè)Url的位置，所有要查出的字段都不是連續(xù)存放的。而且因?yàn)橛凶址@樣的非定長(zhǎng)字段（如果使用定長(zhǎng)的預(yù)留空間，又會(huì)造成大量的空間浪費(fèi)），不能通過簡(jiǎn)單計(jì)算就可以得到地址，查起來非常痛苦，效率自然不會(huì)很高。

而按列存的情況就好很多，只需要找到第一個(gè)Url和第一個(gè)Code的首地址，然后順序讀取到結(jié)尾即可。不僅實(shí)現(xiàn)簡(jiǎn)單，而且磁盤順序讀取好比隨機(jī)讀取要快，加上更容易優(yōu)化（比如把臨近地址的數(shù)據(jù)預(yù)讀到內(nèi)存，連續(xù)的同類型數(shù)據(jù)更容易壓縮存放），效率自然不可同日而語。

那是不是所有情況都需要按列來存數(shù)據(jù)呢？顯然不是。雖然按列讀的情況比較多，但寫入一般是按行寫的，無論是追加、刪除、修改，一般都是按行處理的。數(shù)據(jù)按列存的話，追加時(shí)需要把一行數(shù)據(jù)按字段拆開，分別插入到不同的地方，刪除也是一樣，修改更加痛苦。因?yàn)槿绻穷愃谱址牟欢ㄩL(zhǎng)字段，按行存的話可以以行為單位預(yù)留空間，而按列存的話需要以字段為單位預(yù)留空間，或者使用更復(fù)雜的方法。想一想就要麻煩許多。

數(shù)據(jù)庫(kù)往往需要同時(shí)照顧到讀和寫的效率，簡(jiǎn)單的按行存或者按列存都存在明顯的問題（包括下文提到的表join效率等問題），所以往往需要存儲(chǔ)復(fù)雜的meta數(shù)據(jù)、添加各類索引、使用各種樹型甚至圖型結(jié)構(gòu)，來在讀和寫之間謀得一個(gè)平衡點(diǎn)。

而Dremel要輕松一些，因?yàn)樗辉O(shè)計(jì)成一個(gè)查詢引擎，即使也有寫入功能也不會(huì)過多考慮寫入的效率，那么顯然按列存是合適的。這樣即使一張表字段很多，數(shù)據(jù)量很大，只要記錄每個(gè)字段的類型以及對(duì)應(yīng)數(shù)據(jù)的起始地址等少量信息，查起來就游刃有余。所以如果只是用來查一個(gè)巨大的二維表的后，并不是很難。

但我們知道，平時(shí)使用的數(shù)據(jù)很難在一張二維表里表達(dá)清楚，往往需要多張表，互相還有關(guān)聯(lián)，查詢起來就需要各種join。數(shù)據(jù)量小還好，數(shù)據(jù)量一大，join效率直線下降，單表select再快也沒用，這才是真正棘手的問題。

有嵌套數(shù)據(jù)的情況

Dremel的解決方法不是設(shè)法提高join的效率，而是換一種思路，使用嵌套的數(shù)據(jù)解決簡(jiǎn)單二維表表達(dá)能力太弱的缺點(diǎn)。

再拿出之前的Document.proto：

message Document {
    required int64 DocId;
    optional group Links {
        repeated int64 Backward;
        repeated int64 Forward;
    }

    repeated group Name {
        repeated group Language {
            required string Code;
            optional string Country;
        }
        optional string Url;
    }
}

這樣的數(shù)據(jù)如果用二維表來存放一般需要多張才能描述清楚，處理重復(fù)字段也比較痛苦，而一個(gè)Protocol Buffer類型就可以描述，但在磁盤的實(shí)際存放還是要?jiǎng)硬簧倌X筋的。

現(xiàn)在就需要搬出論文里的這張圖了：

record-wise-vs-columnar-representation-of-nested-data

雖然嵌套的數(shù)據(jù)比之前的二維表更加復(fù)雜，還是有按行存和按列存兩種基本方法，而且正如我們之前提到的，為了查詢效率，我們采用按列存的方法（圖中的column-oriented）。我們重點(diǎn)關(guān)注A、B、C、D、E這些樹型關(guān)系如何存儲(chǔ)。

我們來準(zhǔn)備一些符合Document.proto的簡(jiǎn)單的數(shù)據(jù)：

DocId: 10
Links
    Forward: 20
    Forward: 40
    Forward: 60
Name
    Language
        Code: 'en-us'
        Country: 'us'
    Language
        Code: 'en'
        Url: 'http://A'
Name
    Url: 'http://B'
Name
    Language
        Code: 'en-gb'
        Country: 'gb'

DocId: 20
Links
    Backward: 10
    Backward: 30
    Forward: 80
Name
    Url: 'http://C'

其中DocId: 10和DocId: 20是兩個(gè)Document。

Dremel是這樣拆解數(shù)據(jù)的：

column-striped-representation-of-the-sample-data

可以看出每個(gè)需要存放實(shí)際數(shù)據(jù)的葉子節(jié)點(diǎn)都變成了一張二維表，但表中除了字段自身的值。如果是repeated字段，則在表中增添行；如果是optional字段，并且數(shù)據(jù)中不填充，則用NULL代替（而不是去掉這一行）。但還出現(xiàn)了r和d，這兩個(gè)又是什么東西，而且為何要記錄NULL呢？

試想如果去掉上圖中r和d兩列，則每個(gè)二維表都變成了一個(gè)一維表（list），那么我們?cè)噲D把數(shù)據(jù)還原回去，DocId沒問題，一定是屬于兩個(gè)Document的。Name.Url就出現(xiàn)了問題，因?yàn)?code>Name是repeated的，我怎么知道這3個(gè)Name.Url是全屬于第一個(gè)Document，還是其他情況呢？丟失的信息太多無法還原了。所有我們需要記錄每個(gè)值是否是重復(fù)的以及在哪一層重復(fù)的（比如是在第一個(gè)Name的第二個(gè)Code，還是第二個(gè)Name的第一個(gè)Code）。有了這個(gè)信息，我們就可以根據(jù)之前的記錄一個(gè)一個(gè)往上拼接來還原原始的數(shù)據(jù)結(jié)構(gòu)。r就是做這個(gè)的。

r是重復(fù)層次（Repetition Level），記錄該列的值是在哪一個(gè)層次上重。

如果r是0，則表示是第一個(gè)（非重復(fù)）的元素，如上圖中的DocId，兩個(gè)DocId都是第一個(gè)元素，比較簡(jiǎn)單。但其他的字段就比較復(fù)雜了，如Name.Language.Code，一共有五行：

• en-us是第一個(gè)Document（不同的Document不算重復(fù)，不影響r和d的取值，只有repeated類型的字段才算）里第一個(gè)Name中的第一個(gè)Language里的，重復(fù)還沒有發(fā)生，所以r是0。
• en是第一個(gè)Document里第一個(gè)Name中第二個(gè)Language里的，Language發(fā)生了重復(fù)，在/Name/Language層次結(jié)構(gòu)中處于第二層，所以r是2。
• en-gb是第一個(gè)Document里第三個(gè)Name中第一個(gè)Language里的，Name發(fā)生了重復(fù)，在/Name/Language層次結(jié)構(gòu)中處于第一層，所以r是1。
• 第一個(gè)NULL是第一個(gè)Document里第二個(gè)Name中的，Name發(fā)生了重復(fù)，在/Name/Language層次結(jié)構(gòu)中處于第一層，所以r是1。
• 第二個(gè)NULL是第二個(gè)Document里第一個(gè)Name中的，沒有發(fā)生重復(fù)，所以r是0。

這里例子中沒有出現(xiàn)多個(gè)字段都發(fā)生重復(fù)的情況，如第二個(gè)Name中的第二個(gè)Language的Code。如果是這種情況，那么r取最大的，也就是最近發(fā)生重復(fù)的字段，這里例子中就是Language的2。（待驗(yàn)證）

之前還有個(gè)問題沒有回答，為何要記錄NULL呢？

如果把圖中所有的NULL都去掉，看會(huì)發(fā)生什么。 拿Links.Backward舉例，去掉第一行的NULL后，我們讀到第一個(gè)Links.Backward，必然認(rèn)為它是屬于第一個(gè)Document的，但實(shí)際數(shù)據(jù)中第一個(gè)Document里沒有Links.Backward，完全搞錯(cuò)了。所以即使是NULL也必須記錄，為了后續(xù)的數(shù)據(jù)知道自己在哪。

那么有了r后，是否信息就完善了呢？

我們還是假設(shè)去掉d的一列，試圖還原數(shù)據(jù)。DocId依然沒問題，Name.Url也沒問題了，直接看Name.Language.Country吧：

讀完第一行我們得到了：

Document
    Name
        Language
            Country : 'us'

第二行是個(gè)NULL，是在第二層也就是Language重復(fù)的：

Document
    Name
        Language
            Country : 'us'
        Language
            Country : NULL

第三行又是個(gè)NULL，是在第一層也就是Name重復(fù)的：

Document
    Name
        Language
            Country : 'us'
        Language
            Country : NULL
    Name
        Language
            Country : NULL

第四行是在第一層也就是Name重復(fù)的：

Document
    Name
        Language
            Country : 'us'
        Language
            Country : NULL
    Name
        Language
            Country : NULL
    Name
        Language
            Country : 'gb'

看起來似乎沒問題，不過對(duì)比原始數(shù)據(jù)發(fā)現(xiàn)第二個(gè)Name不只沒有Country，連上層的Language也沒有。也就是單看Name.Language.Country這個(gè)表，還是把數(shù)據(jù)還原錯(cuò)了。雖然把所有的表都還原出來，然后去掉所有的NULL以及NULL上邊多余的部分，還是可以準(zhǔn)確還原，但如果只是去查詢某個(gè)字段，難道需要把其他所有字段全部分析一遍嗎？另外沒有發(fā)生重復(fù)的字段，具體是required、repeated、還是optional的信息也丟了。（此處似乎還有其他問題）

為了解決這個(gè)問題，d被引入了。

d是定義層次（Definition Level），記錄這個(gè)值是在哪一層被定義的。需要注意的是如果這個(gè)值是required的，則層數(shù)不包括自身，否則如果是repeated或optional的，則包括自身。目的主要是區(qū)分是否是required字段（但如何區(qū)分只有一行的repeated和optional呢？）。

舉例：

• Document.Links.Backward的d是2（Document是0）
• Document.Name.Language.Code也是2（因?yàn)?code>Code是required的，所以不包括它自己）

對(duì)于一般的數(shù)據(jù)，這個(gè)值看起來沒什么意義（除了可以區(qū)分是否是required字段），因?yàn)橐呀?jīng)有值了，從根到它自身整條路徑必然是存在的，但對(duì)于NULL則不同，d可以說明這個(gè)NULL是在哪一層定義的，也就是解決我們之前還原Name.Language.Country數(shù)據(jù)遇到的問題。

r和d這兩個(gè)值還是需要好好理解一下，而且還有一些沒弄清楚的細(xì)節(jié)，以及具體查詢的復(fù)雜邏輯，只能后續(xù)繼續(xù)學(xué)習(xí)了。

因?yàn)榉N種原因，這一系列學(xué)習(xí)筆記最近可能不會(huì)更新了。

參考

• Google Dremel 原理 - 如何能3秒分析1PB
• Dremel Interactive Analysis of WebScaleDatasets.pdf

付費(fèi)解決 Windows、Linux、Shell、C、C++、AHK、Python、JavaScript、Lua 等領(lǐng)域相關(guān)問題，靈活定價(jià)，歡迎咨詢，微信 ly50247。