首先簡單介紹一下Dremel是什么，能解決什么問題。第二部分著重講Dremel的數(shù)據(jù)模型，即數(shù)據(jù)結(jié)構(gòu)。第三部分將談一下在此數(shù)據(jù)結(jié)構(gòu)上設(shè)計的算法。

1?起源

Dremel的數(shù)據(jù)模型起源于分布式系統(tǒng)的應(yīng)用環(huán)境(Protocol Buffers，一種在Google內(nèi)廣泛使用，現(xiàn)已開源的實現(xiàn))。其數(shù)據(jù)模型是基于強類型的嵌套記錄，抽象語法可以表示成下面公式：

一個例子：

2?嵌套列式存儲

2.1?記錄結(jié)構(gòu)的無損表示

首先來看一下Dremel的數(shù)據(jù)模型是如何在列式存儲下無損的表示出記錄的結(jié)構(gòu)的(lossless representation of record structure in a columnar format)。如果僅僅是數(shù)值(values)的話，數(shù)值本身無法傳遞出記錄(record)的結(jié)構(gòu)信息。我們不知道兩個數(shù)值是屬于兩條不同的記錄還是在一條記錄下，同時我們也不知道一些可選的字段(field)是否顯式定義。因此，我們引入了兩個概念：Repetition Level和Definition Level。

為了說清楚Dremel模型是如何無損地表示數(shù)據(jù)的，我想到了兩種畫法。最終還是決定采用第一種畫法，類似有向圖，感覺與后面的FSM狀態(tài)機能更好的對應(yīng)上。

Repetition Level

Dremel論文中對repetition level的定義聽起來比較抽象：at what repeated field in the field's path the value has repeated。意思就是在路徑上，在哪個repeated字段上重復(fù)了。還是看個例子解釋一下吧，以之前的圖例中的文檔r1中的Code字段為例。

?

上圖清晰地表示出三個Code字段與文檔中字段的對應(yīng)關(guān)系。下面來看一下這三個Code的repetition level(簡寫為r) 0，2，1是如何計算出來的。下圖忽略無關(guān)的字段，將三個Code字段的完整路徑都表示出來。那么就可以簡單易懂地看出，r就是這些字段路徑上，發(fā)生重復(fù)了的字段的level。請參考下圖中的注釋就能很快理解。

?

大家可能還注意到Name.Code表中除了en-us、en和en-gb三行外，還有兩行NULL。第二個NULL是描述文檔r2的，我們就分析一下第一個NULL的含義吧。因為文檔r1的第二個Name字段下沒有Code，而為了說明en-gb是屬于第三個Name字段下的，所以在en和en-gb之間加了一行NULL，其r也等于1(Name重復(fù))。同時，由于Code在定義中是required的字段，所以事實上這一行NULL也暗示了：在第二個Name字段下Language也是不存在的。不然Language存在而下面卻沒有Name，這是不符合文檔定義的。

以此類推，其他字段的r值都是這樣計算出來的。同時注意一點：我們只保存了有值的字段，如DocId、Name.Url、Name.Language.Code等，而像Links、Name.Language等字段是沒必要保存的。

?

Definition Level

definition level(簡寫為d)在論文中的定義還比較清楚：Each value of a field with path p ,?esp. every NULL, has a definition level specifying?how many fields in p that could be undefined?(because they are optional or repeated)?are actually present.?尤其對于NULL來說，路徑p上有多少字段可以是不存在(例如在文檔定義中是optional或repeated，而不是required)，然而實際卻存在的。例如文檔r1的Links下沒有Backward字段，然而Links字段卻存在(因為Links下有Forward)，所以我們在Links.Backward表中保存一條NULL，并且d=1。對于非NULL字段來說，意義不大，因為d的值對于每種字段來說都是相同的，例如Code都是2，Country都是3。

值得注意的幾點是：

???在路徑上計算多少字段本可以不存在時，包含了當(dāng)前字段本身。例如計算Country:us時，Country本身也是optional，也計入總數(shù)，所以d=3。

???每種字段只計算1次。例如最下面的Country:gb，在其路徑上的3個Name都滿足條件，但只計1次，所以d=3，而不是5。(前面提過，也許是我這第一種畫法的緣故，需要這一條規(guī)則來限定)

數(shù)據(jù)壓縮

前面介紹了數(shù)據(jù)的保存方法，實際上真正保存時，數(shù)據(jù)還會被進(jìn)一步壓縮。

???不顯式保存NULL，因為它可以通過d來確定：d

???總是會被定義的字段的d不會被保存。

???r也是僅在必要時才會保存。例如d=0暗示r=0，所以r可以省略不存。

???像DocId這種所有l(wèi)evel都是0的，實際上不會保存任何level信息。

???盡可能使用位圖。例如假如d最大是3，那么我們只使用2個bit來保存。

2.2?快速編碼成列式存儲

略，詳見論文附錄部分的偽代碼。

2.3?高效地組裝記錄

高效地從列式存儲數(shù)據(jù)中組裝出記錄，對像MapReduce這種面向記錄的數(shù)據(jù)處理工具來說非常重要。我們的目標(biāo)是：給定字段的子集，我們能重新構(gòu)建出僅包含選中字段的原始記錄，而過濾掉其他字段。核心思想是：使用有限狀態(tài)機(finite state machine, FSM)讀取每個字段的值和level，順序地追加到輸出流中。FSM為每種字段都關(guān)聯(lián)一個field reader。狀態(tài)轉(zhuǎn)變通過repetition level來標(biāo)記。一旦reader抓取到值，我們繼續(xù)看下一repetition level來決定使用哪個reader。FSM就這樣從開始狀態(tài)到結(jié)束狀態(tài)遍歷完每條記錄。

下面還是用前面的例子，通過DocId和Name.Language.Country這兩個字段的重建，來詳細(xì)解析一下FSM的工作過程。關(guān)鍵步驟用紅色加粗標(biāo)記。

?

1.??????FSM委托Reader1讀取DocId第一行，通過r=0重建記錄。

2.??????檢查DocId第二行，發(fā)現(xiàn)r=0，則Reader1停在當(dāng)前“游標(biāo)”位置。FSM將狀態(tài)變化到Name.Language.Country。

3.??????FSM委托Reader2讀取Name.Language.Country第一行，通過r=0重建記錄。

4.??????FSM委托Reader2讀取Name.Language.Country第二行。通過r=2(說明Language字段重復(fù)，即Language有多個)重建記錄。

5.??????FSM委托Reader2讀取Name.Language.Country第三行。通過r=1和d=1(說明只有Name字段不是NULL)重建記錄。

6.??????略過第四行。

7.??????檢查到第五行，發(fā)現(xiàn)r=0，Reader2停在當(dāng)前位置。FSM再次發(fā)生狀態(tài)變化，繼續(xù)重建文檔2的記錄。

8.??????FSM委托Reader1繼續(xù)讀取DocId第二行(之前Reader1就停在這里了)。

9.??????到這里應(yīng)該已經(jīng)很清楚了，最后過程就略說了：DocId中沒有數(shù)據(jù)了，F(xiàn)SM狀態(tài)變化，Reader2繼續(xù)讀取Country的最后一行數(shù)據(jù)，重建出記錄。

注：論文原圖中少了第二個Name字段，我覺得應(yīng)該加上吧。在第五步被重新構(gòu)建出來。為什么在原圖中沒有呢？

前面例子的完整FSM就是這樣的：

?

?“神秘”的r和d

單從數(shù)據(jù)結(jié)構(gòu)來看的話，我們可以這樣解釋r和d的含義。r代表著當(dāng)前字段與前一字段的關(guān)系，是在哪一層合并的，即公共的父結(jié)點在哪？舉例來說，假如我們重建到了Code='en'，通過r=2可以知道是在Language那一層發(fā)生了重復(fù)。

?

為了保持原紀(jì)錄的結(jié)構(gòu)，我們會保存一些NULL數(shù)據(jù)，而d就是用于重建NULL字段。通過d的值，就能知道NULL的結(jié)構(gòu)。例如下圖，通過r=1知道應(yīng)該合并到Name那一層。而通過d=1則知道路徑上只有一個字段，即不僅僅是Code字段不存在，Language也不存在。這樣就把NULL正確地重建出來了，那么接下來的Code='en-gb'的層級也就不會亂了。

?

然而這只是從靜態(tài)的數(shù)據(jù)結(jié)構(gòu)來解釋，而r和d的深層次含義還是要看FSM是如何執(zhí)行的。真正的因果關(guān)系是FSM的執(zhí)行方式?jīng)Q定了數(shù)據(jù)結(jié)構(gòu)的設(shè)計。

3?記錄查詢3.1?從FSM角度看r和d

先看一下前面例子的完整FSM的樣子。如果把Protocol Buffer中對數(shù)據(jù)格式定義的schema看作是編譯原理中的語法定義的話，那么一般可以使用工具如antlr,?yacc自動生成自動機，手寫的話是相當(dāng)恐怖的吧。

?

?

?

對列數(shù)據(jù)的完整遍歷就是這個樣子的：

?

在討論查詢?nèi)绾螆?zhí)行之前，先繼續(xù)剛才未完成的題目，r和d的本質(zhì)，這次通過動態(tài)的FSM的角度來分析，而不是靜態(tài)的數(shù)據(jù)結(jié)構(gòu)了：

???FSM狀態(tài)機只是定義了狀態(tài)的變更，即處理流程應(yīng)當(dāng)如何在各個列的存儲表之間跳轉(zhuǎn)，而實際數(shù)據(jù)還是在表中保存。有點像數(shù)據(jù)庫索引，遍歷時是根據(jù)FSM進(jìn)行跳轉(zhuǎn)，然后對某一列的表進(jìn)行table scan。但索引是靠字段值的順序組織，因為數(shù)據(jù)庫表之間沒什么嵌套關(guān)系，而Dremel的FSM則是靠字段之間的嵌套關(guān)系來組織。

?

???狀態(tài)機中線條上的數(shù)字表示什么？回憶一下，數(shù)字表示的是：字段的數(shù)據(jù)表中當(dāng)前行的下一行的r值。通過檢測下一個r值來決定跳轉(zhuǎn)。因為r=0，則說明下一行與當(dāng)前行所表示的字段一定不在同一路徑，否則必然會在某一Level上有共同的字段(路徑的部分重疊)。注意這是由于Protocol Buffer的schema不是樹，沒有共同的根所導(dǎo)致，否則所有字段必然都會在根重復(fù)，上面對r的解釋也就沒意義了。以repeated的Forward為例，檢查到下一行r=1說明40、60都是接在20字段下面的。Code字段也是同樣道理。

?

???Name.Language.Code到Name.Language.Country之間的線上為什么是0，1，2？因為Name.Language.Code是required不是repeated，讀取后不管下一行的r值是多少都要去讀Name.Language.Country。同理Name.Language.Country也是讀完不管怎樣都跳到下一字段。

???最復(fù)雜的要屬Name.Url了，因為它是schema里定義的最后一個字段。在Name.Url這要決定到底是繼續(xù)下一文檔如r2的處理，還是跳回到本文檔的其他字段繼續(xù)處理。具體分析一下：r=0說明當(dāng)前文檔中沒有Name字段了。為什么這么說？因為如果文檔后面真有Name字段，假如下面有Url，則當(dāng)前表中的下一條應(yīng)該是r=1；假如下面沒有Url，則當(dāng)前表的下一條應(yīng)該是r=0的NULL。這里NULL又發(fā)揮用處了！所以中間部分的NULL能保持結(jié)構(gòu)無損，而后面部分的NULL能提示文檔是否結(jié)束。

3.2?查詢引擎

至此，我們已經(jīng)徹底摸清Dremel數(shù)據(jù)模型以及FSM的基本運行方式了。現(xiàn)在終于可以分析Dremel是如何解析和執(zhí)行類SQL查詢的了。查詢語言類似SQL，輸出也是個嵌套式的記錄，以及schema定義。

那么查詢引擎如何執(zhí)行呢？首先為查詢語句中涉及到的每個字段都打開一個Reader來讀取數(shù)據(jù)，然后就是根據(jù)WHERE中的條件過濾以及根據(jù)SELECT中的條件投影并聚合了。難點在于：重建出層次關(guān)系，再進(jìn)行過濾和聚合。例如，過濾掉DocId=20很容易，但其實文檔r2的所有記錄都應(yīng)被過濾。因為WHERE中兩個條件是AND關(guān)系，同時DocId又是最底層的字段，所以相當(dāng)于r2這一整棵樹都被裁剪掉了。Code=en-gb也是由于所在的Name字段下沒有滿足http開頭的Url字段，而被間接的過濾掉了。

聚合也是同樣道理，有了層次關(guān)系，才能正確的聚合。例如Code=en-us，en和Url=http://A是同一個Name下的，COUNT和字符串拼接時會一起處理。而Url=http://B則是另一個Name下的，要分開處理。