Google Dremel數(shù)據(jù)模型講解

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

1?起源

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

一個例子：

2?嵌套列式存儲

2.1?記錄結構的無損表示

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

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

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就是這些字段路徑上，發(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重復)。同時，由于Code在定義中是required的字段，所以事實上這一行NULL也暗示了：在第二個Name字段下Language也是不存在的。不然Language存在而下面卻沒有Name，這是不符合文檔定義的。