Dremel: 互動式分析Web資料

Dremel是一個可擴充的、互動式即時查詢系統，用于分析隻讀的嵌套資料。Dremel可以對叢集上的超大資料集進行互動式分析。Pig、Hive利用MapReduce執行查詢，需要在多個MR作業間傳遞資料，相比之下，Dremel是就地執行查詢的（MapReduce的瓶頸很有可能就是在Map和Reduce之間傳遞資料）。Dremel并不是用來取代MapReduce的，它可以和MapReduce互相補充，比如用于分析MapReduce的輸出。

實作Dremel有2個問題：首先是通用的存儲層，比如GFS，一個高性能的存儲層對于就地查詢是非常關鍵的；其次是存儲格式，按列存儲對于扁平的關系資料非常合适，運用到嵌套資料更加困難，必須要保留結構資訊，并且能夠按任意域的子集重構記錄。

本文的主要内容就是如何按列存儲嵌套資料模型。

1.嵌套資料模型

程式設計語言使用的資料結構，分布式系統交換的資訊，結構化文檔，等等，可以很自然地用嵌套結構表示。在Google，嵌套資料模型是大多數結構化資料處理的基礎。Dremel使用的嵌套資料模型可用下面語句表示：

τ是一個原子類型或者一個記錄類型。Dremel使用的原子類型包括整形、浮點數、字元串等；記錄包括一個或多個域，每個域可以是原子類型或其它記錄類型。Ai是記錄的第i個域，每個域可以選擇一個标簽，标簽*（repeated）表示重複域（可出現0或多次），标簽？（optional）表示可選域（0或1次），無标簽（required）則表示必要域（隻出現一次）。

上圖是論文裡給出的例子，定義了一個記錄類型Document表示網頁，以及該記錄的兩個執行個體。域DocId是必要域；Links是可選域，Links内可以包含一系列的Backward和Forward，指向其它網頁的DocId；每個文檔可以有多個Name，表示可以用不同的URL通路該網頁；每個Name可以有多個Language（Code-Country對），以及可選域Url。r1和r2是滿足該格式的兩個例子。域的完整路徑使用’.’連接配接，比如Name.Language.Country。

整個資料模型可以看成是一棵樹，隻有葉子結點才有值。

2.按列存儲

按列存儲有很多好處，比如更好壓縮率，減少查詢讀取的資料量。按列存儲關系資料很簡單，但是按列存儲嵌套資料很複雜，因為必須儲存資料的結構資訊。本小節解決記錄的按列無損存儲，快速編碼，高效記錄聚合等挑戰。

2.1 重複級别和定義級别

資料本身不能告訴我們記錄的結構。以Document的Name.Language.Code為例，按列存儲後，連續兩個Code的值，我們并不知道它們是屬于同一個Name下的兩個Language，還是不同的兩個Name，如下圖三個Code的關系。是以為了儲存記錄的結構資訊，Dremel引入了Repetition Level和Definition Level概念。

仍然以Code為例，它在r1中出現了3次。’en-us’和’en’位于第一個Name，’en-gb’位于第三個Name。換句話說，’en’是在Language發生重複，’en-gb’是在Name發生重複。為了區分這些情況，Dremel為每個值配置設定一個重複級别。重複級别代表值是在哪一級發生重複。Name.Language.Code路徑上有兩個重複域，是以Code的重複級别可以是0、1、2,0表示開始新記錄（或者了解為在記錄一級重複）。根據定義，r1的三個Code的重複級别分别是0、2、1。注意r1的第二個Name裡沒有Code，為了區分’en-gb’是第二個Name還是第三個Name，必須’en’和’en-gb’之間插入NULL。

在Code的例子裡，因為Code是Language的必要域，如果Code讀取了一個NULL，我們就可以确定這個位置實際上是一個沒有Language的Name。但是一般情況下，還需要額外資訊。以Country為例，Country是Language的可選域，如果Country讀出一個NULL，那麼這個位置到底是缺了Language的Name，還是缺了Country的Language呢？

定義級别用于解決這個問題。定義級别表示這個值的完整路徑上有幾個域是可以未定義（可選域或重複域）但卻已定義。對于非空的值，它的定義級别就等于完整路徑上可選域和重複域的數量；對于NULL，得看它出現的位置上實際定義了幾個可選域和重複域。以Country為例，Name.Language.Country的可選域或重複域有三個，是以對于非空值，它的定義域一定是3；而對于NULL，則要看缺席的原因，比如r1的第一個Name的第二個Language沒有Country，定義級别為2，而第二個Name沒有Country，定義級别為1。NULL告訴我們此處本可以有一個值，定義級别告訴我們缺席的原因。

r1和r2所有域的重複級别和定義級别如下圖所示。論文的附錄A提供了快速計算重複級别和定義級别的算法。

2.2 編碼

列的存儲都以block為機關，值經過壓縮後，和對應的重複級别和定義級别一起被編碼到block。好的編碼方式可以盡可能去掉不必要的資料。

性質一：特定的一列裡，非空值的定義級别都是相同的，而空值的定義級别肯定小于非空值的定義級别。

性質二：重複級别總是小于定義級别。

利用性質一，我們可以不存儲非空值的定義級别和NULL值。根據性質二，定義級别為0意味着重複級别也是0，是以DocId的兩個級别都不用存儲。

2.3 記錄的組裝

前面讨論的是如何将記錄按列存儲，這一小節是如何将列重組為記錄，這對面向記錄的處理工具（比如MapReduce）是非常關鍵的。給定域的一個子集，Dremel将隻重組該記錄被標明的域。Dremel的思想是建立一個有限狀态機（FSM），負責讀取每個域的值和級别。FSM的每個狀态對應一個域，狀态的跳轉由重複級别決定：每讀取了一個值，Dremel檢視下一個重複級别決定跳轉到哪個狀态。

上圖顯示了重組完整記錄的有限狀态機。開始的狀态是DocId，每當讀取一個DocId，FSM跳轉到Links.Backward；根據重複級别的定義，1表示下一個Backward值屬于同一個Links，是以重複讀取，遇到0則表示Backward讀完了，跳轉到Links.Forward；Forward和Backward類似；跳轉到Code後，情況更加複雜，因為Country和Code是兄弟，是以不論Code的重複級别為何值，都跳轉到Country；當下一個Country的重複級别是2時，表明目前Language級别發生重複，跳轉到Code；否則Language級别無重複，跳轉到Name.Url；下一個Url的重複級别是1表明Name發生重複，跳轉到Code；否則Name結束，記錄讀取完畢。完整的算法在論文附錄B。

FSM的構造算法在論文附錄C，基本的思路比較簡單。假如現處于狀态f，即讀取域f的值，如果下一個重複級别是l，則回溯到級别為l的祖先結點，并且選擇該祖先結點下的下一個（論文裡說的是first leaf，個人認為有誤）葉子結點n為跳轉狀态。是以我們得到了一個跳轉(f, l)->n。以Name.Language.Country為例，假如讀取的下一個重複級别為1，因為country的祖先中級别為1的是Name，而Name在Language後的下一個葉子結點是Url，是以得到跳轉(Name.Language.Country, 1)->Name.Url（而按照原文first leaf的解釋，跳轉的目标應該是Name.Language.Code，顯然是錯誤的）。

原文： Dremel: Interactive Analysis of Web-Scale Datasets. In VLDB\'2010.