首先簡單介紹一下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就是這樣的：