首先簡單介紹一下Dremel是什么,能解決什么問題。第二部分著重講Dremel的數據模型,即數據結構。第三部分將談一下在此數據結構上設計的算法。
### 1?起源
Dremel的數據模型起源于分布式系統的應用環境(Protocol Buffers,一種在Google內廣泛使用,現已開源的實現)。其數據模型是基于強類型的嵌套記錄,抽象語法可以表示成下面公式:

一個例子:

### 2?嵌套列式存儲
### 2.1?記錄結構的無損表示
首先來看一下Dremel的數據模型是如何在列式存儲下無損的表示出記錄的結構的(lossless representation of record structure in a columnar format)。如果僅僅是數值(values)的話,數值本身無法傳遞出記錄(record)的結構信息。我們不知道兩個數值是屬于兩條不同的記錄還是在一條記錄下,同時我們也不知道一些可選的字段(field)是否顯式定義。因此,我們引入了兩個概念:**Repetition Level**和**Definition Level**。
為了說清楚Dremel模型是如何無損地表示數據的,我想到了兩種畫法。最終還是決定采用第一種畫法,類似有向圖,感覺與后面的FSM狀態機能更好的對應上。

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

上圖清晰地表示出三個Code字段與文檔中字段的對應關系。下面來看一下這三個Code的repetition level(簡寫為r) 0,2,1是如何計算出來的。下圖忽略無關的字段,將三個Code字段的完整路徑都表示出來。那么就可以簡單易懂地看出,r就是這些字段路徑上,發生重復了的字段的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重復)。同時,由于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。

值得注意的幾點是:
???在路徑上計算多少字段本可以不存在時,包含了當前字段本身。例如計算Country:us時,Country本身也是optional,也計入總數,所以d=3。
???每種字段只計算1次。例如最下面的Country:gb,在其路徑上的3個Name都滿足條件,但只計1次,所以d=3,而不是5。(前面提過,也許是我這第一種畫法的緣故,需要這一條規則來限定)
### 數據壓縮
前面介紹了數據的保存方法,實際上真正保存時,數據還會被進一步壓縮。
???不顯式保存NULL,因為它可以通過d來確定:d <?路徑上repeated和optional字段總數,就說明是NULL。可以通過前面的例子印證一下。
???總是會被定義的字段的d不會被保存。
???r也是僅在必要時才會保存。例如d=0暗示r=0,所以r可以省略不存。
???像DocId這種所有level都是0的,實際上不會保存任何level信息。
???盡可能使用位圖。例如假如d最大是3,那么我們只使用2個bit來保存。
### 2.2?快速編碼成列式存儲
略,詳見論文附錄部分的偽代碼。
### 2.3?高效地組裝記錄
高效地從列式存儲數據中組裝出記錄,對像MapReduce這種面向記錄的數據處理工具來說非常重要。我們的目標是:給定字段的子集,我們能重新構建出僅包含選中字段的原始記錄,而過濾掉其他字段。**核心思想是:使用有限狀態機(finite state machine, FSM)**讀取每個字段的值和level,順序地追加到輸出流中。FSM為每種字段都關聯一個field reader。狀態轉變通過repetition level來標記。一旦reader抓取到值,我們繼續看下一repetition level來決定使用哪個reader。FSM就這樣從開始狀態到結束狀態遍歷完每條記錄。
下面還是用前面的例子,通過DocId和Name.Language.Country這兩個字段的重建,來詳細解析一下FSM的工作過程。關鍵步驟用紅色加粗標記。

1.??????FSM委托Reader1讀取DocId第一行,通過r=0重建記錄。
2.??????檢查DocId第二行,發現r=0,則**Reader1停在當前“游標”位置**。FSM將狀態變化到Name.Language.Country。
3.??????FSM委托Reader2讀取Name.Language.Country第一行,通過r=0重建記錄。
4.??????FSM委托Reader2讀取Name.Language.Country第二行。**通過r=2(說明Language字段重復,即Language有多個)重建記錄。**
5.??????FSM委托Reader2讀取Name.Language.Country第三行。**通過r=1和d=1(說明只有Name字段不是NULL)重建記錄。**
6.??????略過第四行。
7.??????檢查到第五行,發現r=0,Reader2停在當前位置。FSM再次發生狀態變化,繼續重建文檔2的記錄。
8.??????FSM委托**Reader1繼續讀取DocId第二行(之前Reader1就停在這里了)**。
9.??????到這里應該已經很清楚了,最后過程就略說了:DocId中沒有數據了,FSM狀態變化,Reader2繼續讀取Country的最后一行數據,重建出記錄。
*注:論文原圖中少了第二個Name字段,我覺得應該加上吧。在第五步被重新構建出來。為什么在原圖中沒有呢?*
前面例子的完整FSM就是這樣的:
