轉載請注明出處。作者：archimekai
核心參考文獻： Dremel: Interactive Analysis of Web-Scale Datasets
文章目錄
- 引言
- 復雜嵌套數據結構的無損表征問題
- Dremel論文中提出的表征方法
- parquet
- 備注
引言
Dremel是Google的交互式分析系統。Google大量采用protobuf格式，因此Dremel必須支持protobuf這種復雜嵌套格式的分析。眾多工作已經論證了列式存儲格式對分析系統（AP, analytical processing）的重要性，因此Dremel需要把復雜嵌套格式存儲為列存。本文接下來重點分析Dremel是如何把復雜嵌套格式轉換為每一列單獨存儲的。
我們的目標是：沒有蛀牙（劃掉）把相同字段的所有值連續存儲。因此需要設計一種能夠適用于任意protobuf/json格式的，無損的數據表征方式。
復雜嵌套數據結構的無損表征問題
不同的數據，其表征難度是不同的。最簡單的是完全沒有嵌套，平鋪直敘的數據。這種數據只要將每一個字段的名稱取出，放在數據庫中作為一列即可。
數據樣例如下：
{"Code": "en-us", "Country": "us"}
一種表征方式如下：
| Code | Country |
|---|---|
| en-us | us |
如果數據中有嵌套，但是沒有列表，也比較簡單。只需要用某個分隔符（例如 . ）把嵌套的字段名稱連接起來即可。以下面的數據為例：
{"DocId": 10, "Links": {"Forward": 20}}
其一種表征方式如下：
| DocId | Links.Forward |
|---|---|
| 10 | 20 |
如果數據中存在列表，就比較復雜了。這里的難點在于，列表的長度無法提前預知，所以一般不能把列表中的每一個元素都作為一列存儲。例如
{"Links": {"Backward": [10,30], "Forward": [80]}}
不能表征為
| Links.Backward[0] | Links.Backward[1] | Links.Forward[0] |
|---|---|---|
| 10 | 30 | 80 |
如果將來Backward中有10000個元素就很難處理。
這個問題其實有一個簡單場景，即列表中的元素都是相同的基本數據類型。這里的基本數據類型可以簡單理解為數據庫有原生數組類型支持的數據類型，例如 int ( int[] )，float ( float[] )等，因此，上述數據可以表征為下表。Hologres就是采用了這樣的方案。
| Links.Backward | Links.Forward |
|---|---|
| [10.30] | [80] |
通過上面的方案，筆者認為已經可以搞定80%以上的場景了。但是如果列表中的元素不是基本數據類型，上面的的方案就又搞不定了。考慮下面的數據：
{"Name": [{"url": "http://C", "long_data": "data"}]}
在這個例子中，數組里面的元素是{"url": "http://C"}，并不是一種基本數據類型，如何存儲才能支撐對Name.url的高效查詢呢？。除了上面的例子，還有更為復雜的數組套數組的例子：
{"Name": [{"Language":[{"Code": "en-us", "Country": "us"}, {"Code": "en"}]}]}
那么，有沒有一種方法可以一勞永逸地搞定所有protobuf/強類型json（強類型json指每個字段的類型是確定的）能夠表達的所有數據呢？還真有，這就是Google的天才工程師們在Dremel論文中提出的方案。下面筆者重點介紹這個方案。
Dremel論文中提出的表征方法
還是看上面數組套數組的例子，主要的困難點是，讀取數據時如何確定內層元素（例如{"Code": "en"}）的位置？這需要準確表達內層元素在當前數組（也即Language）和父數組（也即Name）中的位置，才能在讀取時把數據結構還原回來。這提示我們，至少需要增加兩個位置信息才行。
Google的工程師們也是這么想的，他們定義了兩個變量來表示上述信息，這兩個變量也是理解Dremel數據表征算法的關鍵：
- 第一個變量是repetition level，簡稱r，其表示對于給定的字段，其當前在哪一個級別重復。這個概念比較抽象，請結合下面的例子仔細閱讀備注進行理解。
- 第二個變量是definition level，簡稱d，其表示對于給定的字段，其前面有多少個字段是存在的。例如，r3中的DocId，d=0，也即DocId更上層沒有字段了，r3中的Links.Forward字段，d=1，也即Links這個字段是存在的。
可以看到，r和d并非直接表示當前數組和父數組的位置，而是以一種類似增量（在當前級別重復還是在哪個級別重復）的方式進行編碼。
一個加料版的例子（r3，基于論文中的r1修改而來）。數據schema如下
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; }}
數據如下（簡稱r3）
{"DocId": 10, "Links": {"Forward": [20,40,60]}, "Name": [{"Language": [{"Code": "en-us", "Country": "us"},{"Code": "en"},{"Code": "zh-cn", "Country": "cn"}]"Url": "http://A"},{"Url": "http://B"},{"Language": [{"Code": "en-us", "Country": "gb"}]}]
}
數據r3中的Name.Language.Country字段編碼后如下。
| value | r | d | 備注 |
|---|---|---|---|
| us | 0 | 2 | r=0表示r3這篇文檔的第一個Country字段，d=2表示Name, Language兩個字段都是存在的 |
| null | 2 | 2 | r=2表示Language字段在第二級，也即Language數組這一級重復，null表示Country字段實際上未在Language這個數組的第二個元素{"Code": "en"}中出現。注意null在dremel的編碼方式中是必須的 |
| cn | 2 | 2 | r=2表示Language字段在第二級，也即Language數組這一級重復，出現在Language這個數組的第三個元素 |
| null | 1 | 1 | r=1表示Language字段在第一級，也即Name數組這一級重復，null表示Country字段實際上為在Name這個數組的第二個元素{"Url": "http://B"}中出現。結合d=1可知，Name.Language.Country中只有頭一個字段，也即Name存在，Language字段不存在。 |
| gb | 1 | 2 | r=1表示Language字段在第一級，也即Name數組這一級重復，出現在Name數組的第三個元素 |
到了這里，相信讀者已基本理解了r和d的含義。筆者將Dremel論文中的原圖貼在這里，大家應該可以看懂了。
parquet
parquet中對于嵌套數據的數據和Google Dremel基本一致。本篇文章不詳細展開
備注
- 為了方便理解，上述描述中省略了一些不重要的細節，感興趣的讀者可自行閱讀論文原文。
- 本篇文章只介紹了最核心的數據結構表征方式，Dremel論文中還有關于如何將各個字段拆分為列，如何使用有限狀態自動機真正生成r和d值的描述，以后有機會再介紹。
)
)
