簡介

Dremel 是Google 的“交互式”數(shù)據(jù)分析系統(tǒng)?？梢越M建成規(guī)模上千的集群，處理PB級別的數(shù)據(jù)。MapReduce處理一個數(shù)據(jù)，需要分鐘級的時間。作為MapReduce的發(fā)起人，Google開發(fā)了Dremel將處理時間縮短到秒級，作為MapReduce的有力補充。Dremel作為Google BigQuery的report引擎，獲得了很大的成功。最近Apache計劃推出Dremel的開源實現(xiàn)Drill，將Dremel的技術(shù)又推到了浪尖上。

Google Dremel設(shè)計

根據(jù)Google公開的論文《Dremel: Interactive Analysis of WebScaleDatasets》可以看到Dremel的設(shè)計原理。還有一些測試報告。論文寫于2006年，公開于2010年，Google在處理大數(shù)據(jù)方面，果真有得天獨厚的優(yōu)勢。下面的內(nèi)容，很大部分來自這篇論文。

隨著Hadoop的流行，大規(guī)模的數(shù)據(jù)分析系統(tǒng)已經(jīng)越來越普及。數(shù)據(jù)分析師需要一個能將數(shù)據(jù)“玩轉(zhuǎn)”的交互式系統(tǒng)。如此，就可以非常方便快捷的瀏覽數(shù)據(jù)，建立分析模型。Dremel系統(tǒng)有下面幾個主要的特點：

• Dremel是一個大規(guī)模系統(tǒng)。在一個PB級別的數(shù)據(jù)集上面，將任務(wù)縮短到秒級，無疑需要大量的并發(fā)。磁盤的順序讀速度在100MB/S上下，那么在1S內(nèi)處理1TB數(shù)據(jù)，意味著至少需要有1萬個磁盤的并發(fā)讀! Google一向是用廉價機器辦大事的好手。但是機器越多，出問題概率越大，如此大的集群規(guī)模，需要有足夠的容錯考慮，保證整個分析的速度不被集群中的個別慢(壞)節(jié)點影響。
• Dremel是MR交互式查詢能力不足的補充。和MapReduce一樣，Dremel也需要和數(shù)據(jù)運行在一起，將計算移動到數(shù)據(jù)上面。所以它需要GFS這樣的文件系統(tǒng)作為存儲層。在設(shè)計之初，Dremel并非是MapReduce的替代品，它只是可以執(zhí)行非?？斓姆治?，在使用的時候，常常用它來處理MapReduce的結(jié)果集或者用來建立分析原型。
• Dremel的數(shù)據(jù)模型是嵌套(nested)的。互聯(lián)網(wǎng)數(shù)據(jù)常常是非關(guān)系型的。Dremel還需要有一個靈活的數(shù)據(jù)模型，這個數(shù)據(jù)模型至關(guān)重要。Dremel支持一個嵌套(nested)的數(shù)據(jù)模型，類似于Json。而傳統(tǒng)的關(guān)系模型，由于不可避免的有大量的Join操作，在處理如此大規(guī)模的數(shù)據(jù)的時候，往往是有心無力的。
• Dremel中的數(shù)據(jù)是用列式存儲的。使用列式存儲，分析的時候，可以只掃描需要的那部分?jǐn)?shù)據(jù)的時候，減少CPU和磁盤的訪問量。同時列式存儲是壓縮友好的，使用壓縮，可以綜合CPU和磁盤，發(fā)揮最大的效能。對于關(guān)系型數(shù)據(jù)，如果使用列式存儲，我們都很有經(jīng)驗。但是對于嵌套(nested)的結(jié)構(gòu)，Dremel也可以用列存儲，非常值得我們學(xué)習(xí)。
• Dremel結(jié)合了Web搜索 和并行DBMS的技術(shù)。首先，他借鑒了Web搜索中的“查詢樹”的概念，將一個相對巨大復(fù)雜的查詢，分割成較小較簡單的查詢。大事化小，小事化了，能并發(fā)的在大量節(jié)點上跑。其次，和并行DBMS類似，Dremel可以提供了一個SQL-like的接口，就像Hive和Pig那樣。

Google Dremel應(yīng)用場景

設(shè)想一個使用場景。我們的美女?dāng)?shù)據(jù)分析師，她有一個新的想法要驗證。要驗證她的想法，需要在一個上億條數(shù)據(jù)上面，跑一個查詢，看看結(jié)果和她的想法是不是一樣，她可不希望等太長時間，最好幾秒鐘結(jié)果就出來。當(dāng)然她的想法不一定完善，還需要不斷調(diào)整語句。然后她驗證了想法，發(fā)現(xiàn)了數(shù)據(jù)中的價值。最后，她可以將這個語句完善成一個長期運行的任務(wù)。

對于Google,數(shù)據(jù)一開始是放在GFS上的?？梢酝ㄟ^MapReduce將數(shù)據(jù)導(dǎo)入到Dremel中去，在這些MapReduce中還可以做一些處理。然后分析師使用Dremel，輕松愉悅的分析數(shù)據(jù)，建立模型。最后可以編制成一個長期運行的MapReduce任務(wù)。

這種處理方式，讓筆者聯(lián)想到Greenplum的Chorus. Chorus也可以為分析師提供快速的數(shù)據(jù)查詢，不過解決方案是通過預(yù)處理，導(dǎo)入部分?jǐn)?shù)據(jù)，減少數(shù)據(jù)集的大小。用的是三十六計，走為上計，避開的瞬時分析大數(shù)據(jù)的難題。Chorus最近即將開源，可以關(guān)注下。

還有一點特別的就是按列存儲的嵌套數(shù)據(jù)格式。如圖所示，在按記錄存儲的模式中，一個記錄的多列是連續(xù)的寫在一起的。在按列存儲中，可以將數(shù)據(jù)按列分開。也就是說，可以僅僅掃描A.B.C而不去讀A.E或者A.B.C。難點在于，我們?nèi)绾文芡瑫r高效地掃描若干列，并做一些分析。

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

在Google, 用Protocol Buffer常常作為序列化的方案。其數(shù)據(jù)模型可以用數(shù)學(xué)方法嚴(yán)格的表示如下：

其中t可以是一個基本類型或者組合類型。其中基本類型可以是integer,float和string。組合類型可以是若干個基本類型拼湊。星號(*)指的是任何類型都可以重復(fù)，就是數(shù)組一樣。問號(?)指的是任意類型都是可以是可選的。簡單來說，除了沒有Map外，和一個Json幾乎沒有區(qū)別。

下圖是例子，Schema定義了一個組合類型Document.有一個必選列DocId，可選列Links，還有一個數(shù)組列Name?？梢杂肗ame.Language.Code來表示Code列。

這種數(shù)據(jù)格式是語言無關(guān)，平臺無關(guān)的?？梢允褂肑ava來寫MR程序來生成這個格式，然后用C++來讀取。在這種列式存儲中，能夠快速通用處理也是非常的重要的。

上圖，是一個示例數(shù)據(jù)的抽象的模型；下圖是這份數(shù)據(jù)在Dremel實際的存儲的格式。

如果是關(guān)系型數(shù)據(jù)，而不是嵌套的結(jié)構(gòu)。存儲的時候，我們可以將每一列的值直接排列下來，不用引入其他的概念，也不會丟失數(shù)據(jù)。對于嵌套的結(jié)構(gòu)，我們還需要兩個變量R (Repetition Level) ,D (Definition Level) 才能存儲其完整的信息。

Repetition Level是記錄該列的值是在哪一個級別上重復(fù)的。舉個例子說明：對于Name.Language.Code  我們一共有三條非Null的記錄。

1. 第一個是”en-us”，出現(xiàn)在第一個Name的第一個Lanuage的第一個Code里面。在此之前，這三個元素是沒有重復(fù)過的，都是第一個。所以其R為0。
2. 第二個是”en”，出現(xiàn)在下一個Lanuage里面。也就是說Lanague是重復(fù)的元素。Name.Language.Code中Lanague排第二個，所以其R為2.
3. 第三個是”en-gb”，出現(xiàn)在下一個Name中，Name是重復(fù)元素，排第一個，所以其R為1。

我們可以想象，將所有的沒有值的列，設(shè)值為NULL。如果是數(shù)組列，我們也想象有一個NULL值。有了Repetition Level，我們就可以很好的用列表示嵌套的結(jié)構(gòu)了。但是還有一點不足。就是還需要表示一個數(shù)組是不是我們想象出來的。

Definition Level 是定義的深度，用來記錄該列是否是”想象”出來的。所以對于非NULL的記錄，是沒有意義的，其值必然為相同。同樣舉個例子。例如Name.Language.Country,

• 第一個”us”是在R1里面，其中Name,Language,Country是有定義的。所以D為3。
• 第二個”NULL”也是在R1的里面，其中Name,Language是有定義的,其他是想象的。所以D為2。
• 第三個”NULL”還是在R1的里面，其中Name是有定義的,其他是想象的。所以D為1。
• 第四個”gb”是在R1里面，其中Name,Language,Country是有定義的。所以D為3。

就是這樣，如果路徑中有required，可以將其減去，因為required必然會define，記錄其數(shù)量沒有意義。

理解了如何存儲這種嵌套結(jié)構(gòu)。寫沒有難度。讀的時候，我們只讀其中部分字段，來構(gòu)建部分的數(shù)據(jù)模型。例如，只讀取DocID和Name.Language.Country。我們可以同時掃描兩個字段，先掃描DocID。記錄下第一個，然后發(fā)現(xiàn)下一個DocID的R是0；于是該讀Name.Language.Country，如果下一個R是1或者2就繼續(xù)讀，如果是0就開始讀下一個DocID。

到此為止，我們已經(jīng)知道了Dremel的數(shù)據(jù)結(jié)構(gòu)。就像其他數(shù)據(jù)分析系統(tǒng)一樣，數(shù)據(jù)結(jié)構(gòu)確定下來，功能就決定了一大半。對于Dremel的數(shù)據(jù)查詢，必然是“全表掃描”，但由于其巧妙的列存儲設(shè)計，良好的數(shù)據(jù)模型設(shè)計可以回避掉大部分Join需求和掃描最少的列。

Google Dremel查詢方式

Dremel可以使用一種SQL-like的語法查詢嵌套數(shù)據(jù)。由于Dremel的數(shù)據(jù)是只讀的，并且會密集的發(fā)起多次類似的請求。所以可以保留上次請求的信息，還優(yōu)化下次請求的explain過程。那又是如何explain的呢？

這是一個樹狀架構(gòu)。當(dāng)Client發(fā)其一個請求，根節(jié)點受到請求，根據(jù)metadata，將其分解到枝葉，直到到位于數(shù)據(jù)上面的葉子Server。他們掃描處理數(shù)據(jù)，又不斷匯總到根節(jié)點。

舉個例子：對于請求：

SELECT A, COUNT(B) FROM T GROUP BY A

根節(jié)點收到請求，會根據(jù)數(shù)據(jù)的分區(qū)請求，將請求變成可以拆分的樣子。原來的請求會變?yōu)椤?/p>

SELECT A, SUM(c) FROM (R1 UNION ALL ... Rn) GROUP BY A

R1,…RN是T的分區(qū)計算出的結(jié)果集。越大的表有越多的分區(qū)，越多的分區(qū)可以越好的支持并發(fā)。

然后再將請求切分，發(fā)送到每個分區(qū)的葉子Server上面去,對于每個Server

 Ri = SELECT A, COUNT(B) AS c FROM Ti GROUP BY A

結(jié)構(gòu)集一定會比原始數(shù)據(jù)小很多，處理起來也更快。根服務(wù)器可以很快的將數(shù)據(jù)匯總。具體的聚合方式，可以使用現(xiàn)有的并行數(shù)據(jù)庫技術(shù)。

Dremel是一個多用戶的系統(tǒng)。切割分配任務(wù)的時候，還需要考慮用戶優(yōu)先級和負(fù)載均衡。對于大型系統(tǒng)，還需要考慮容錯，如果一個葉子Server出現(xiàn)故障或變慢，不能讓整個查詢也受到明顯影響。

通常情況下，每個計算節(jié)點，執(zhí)行多個任務(wù)。例如，技巧中有3000個葉子Server，每個Server使用8個線程，有可以有24000個計算單元。如果一張表可以劃分為100000個區(qū)，就意味著大約每個計算單元需要計算5個區(qū)。這執(zhí)行的過程中，如果某一個計算單元太忙，就會另外啟一個來計算。這個過程是動態(tài)分配的。

對于GFS這樣的存儲，一份數(shù)據(jù)一般有3份拷貝，計算單元很容易就能分配到數(shù)據(jù)所在的節(jié)點上，典型的情況可以到達95%的命中率。

Dremel還有一個配置，就是在執(zhí)行查詢的時候，可以指定掃描部分分區(qū)，比如可以掃描30%的分區(qū)，在使用的時候，相當(dāng)于隨機抽樣，加快查詢。

Google Dremel測試實驗

實驗的數(shù)據(jù)源如下表示。大部分?jǐn)?shù)據(jù)復(fù)制了3次，也有一個兩次。每個表會有若干分區(qū)，每個分區(qū)的大小在100K到800K之間。如果壓縮率是25%，并且計入復(fù)制3份的事實的話。T1的大小已經(jīng)達到PB級別。這幺小且巨量的分區(qū)，對于GFS的要求很高，現(xiàn)在的Hdfs穩(wěn)定版恐怕受不了。接下來的測試會逐步揭示其是如何超過MR，并對性能作出分析。

列存測試

首先，我們測試看看列存的效果。對于T1表，1GB的數(shù)據(jù)大約有300K行，使用列存的話壓縮后大約在375MB。這臺機器磁盤的吞吐在70MB/s左右。這1GB的數(shù)據(jù)，就是我們的現(xiàn)在的測試數(shù)據(jù)源，測試環(huán)境是單機。

見上圖。

• 曲線A，是用列存讀取數(shù)據(jù)并解壓的耗時。
• 曲線B是一條一條記錄挨個讀的時間。
• 曲線C是在B的基礎(chǔ)上，加上了反序列化的時間。
• 曲線d，是按行存讀并解壓的耗時。
• 曲線e加上了反序列化的時間。因為列很多，反序列化耗時超過了讀并解壓的50%。

從圖上可以看出。如果需要讀的列很少的話，列存的優(yōu)勢就會特別的明顯。對于列的增加，產(chǎn)生的耗時也幾乎是線性的。而一條一條該個讀和反序列化的開銷是很大的，幾乎都在原來基礎(chǔ)上增加了一倍。而按行讀，列數(shù)的增加沒有影響，因為一次性讀了全部列。

Dremel和MapReduce的對比測試

MR和Dremel最大的區(qū)別在于行存和列存。如果不能擊敗MapReduce，Remel就沒有意義了。使用最常見的WordCount測試，計算這個數(shù)據(jù)中Word的個數(shù)。

Q1: SELECT SUM(CountWords(txtField)) / COUNT(*) FROM T1

上圖是測試的結(jié)果。使用了兩個MR任務(wù)。這兩個任務(wù)和Dremel一樣都運行在3000個節(jié)點上面。如果使用列存，Dremel的按列讀的MR只需要讀0.5TB的數(shù)據(jù)，而按行存需要讀87TB。 MR提供了一個方便有效的途經(jīng)來講按行數(shù)據(jù)轉(zhuǎn)換成按列的數(shù)據(jù)。Dremel可以方便的導(dǎo)入MapReduce的處理結(jié)果。

樹狀計算Server測試

接下來我們要對比在T2表示使用兩個不同的Group BY查詢。T2表有24 billion 行的記錄。每個記錄有一個 item列表，每一item有一個amount 字段?？偣灿?0 billion個item.amount。這兩個Query分別是。

Q2: SELECT country, SUM(item.amount) FROM T2 GROUP BY country

Q3: SELECT domain, SUM(item.amount) FROM T2 WHERE domain CONTAINS ’.net’ GROUP BY domain

Q2需要掃描60GB的壓縮數(shù)據(jù)，Q3需要掃描180GB，同時還要過濾一個條件。

上圖是這兩個Query在不同的server拓?fù)湎碌男阅堋Ｃ總€測試都是有2900個葉子Server。在2級拓?fù)渲校鵶erver直接和葉子Server通信。在3級拓?fù)渲?，各個級別的比例是1:100:2900，增加了100個中間Server。在4級拓?fù)渲?，比例?:10:100:2900.

Q2可以在3級拓?fù)湎?秒內(nèi)執(zhí)行完畢，但是為他提供更高的拓?fù)浼墑e，對性能提升沒有裨益。相比之下，為Q3提供更高的拓?fù)浼墑e，性能可以有效提升。這個測試體現(xiàn)了樹狀拓?fù)鋵π阅芴嵘淖饔谩?/p>

每個分區(qū)的執(zhí)行情況

對于剛剛的兩個查詢，具體的每個分區(qū)的執(zhí)行情況是這樣的。

可以看到99%的分區(qū)都在1s內(nèi)完成了。Dremel會自動調(diào)度，使用新的Server計算拖后腿的任務(wù)。

記錄內(nèi)聚合

由于Demel支持List的數(shù)據(jù)類型，有的時候，我們需要計算每個記錄里面的各個List的聚合。如

Q4 : SELECT COUNT(c1 > c2) FROM

(SELECT SUM(a.b.c.d) WITHIN RECORD AS c1,

SUM(a.b.p.q.r) WITHIN RECORD AS c2

FROM T3)

我們需要count所有sum(a.b.c.d)比sum(a.b.p.q.r)，執(zhí)行這條語句實際只需要掃描13GB的數(shù)據(jù)，耗時15s，而整張表有70TB。如果沒有這樣的嵌套數(shù)據(jù)結(jié)構(gòu)，這樣的查詢會很復(fù)雜。

擴展性測試

Dremel有良好的擴展性，可以通過增加機器來縮短查詢的時間。并且可以處理數(shù)以萬億計的記錄。

對于查詢：

Q5: SELECT TOP(aid, 20), COUNT(*) FROM T4 WHERE bid = fvalue1g AND cid = fvalue2g

使用不同的葉子Server數(shù)目來進行測試。

可以發(fā)現(xiàn)CPU的耗時總數(shù)是基本不變的，在30萬秒左右。但是隨著節(jié)點數(shù)的增加，執(zhí)行時間也會相應(yīng)縮短。幾乎呈線性遞減。如果我們使用通過CPU時間計費的“云計算”機器，每個租戶的查詢都可以很快，成本也會非常低廉。

容錯測試

一個大團隊里面，總有幾個拖油瓶。對于有萬億條記錄的T5，我們執(zhí)行下面的語句。

Q6: SELECT COUNT(DISTINCT a) FROM T5

值得注意的是T5的數(shù)據(jù)只有兩份拷貝，所以有更高的概率出現(xiàn)壞節(jié)點和拖油瓶。這個查詢需要掃描大約1TB的壓縮數(shù)據(jù)，使用2500個節(jié)點。

可以看到99%的分區(qū)都在5S內(nèi)完成的。不幸的是，有一些分區(qū)需要較長的時間來處理。盡管通過動態(tài)調(diào)度可以加快一些，但在如此大規(guī)模的計算上面，很難完全不出問題。如果不在意太精確的結(jié)果，完全可以小小減少覆蓋的比例，大大提升相應(yīng)速度。

Google Dremel 的影響

Google Dremel的能在如此短的時間內(nèi)處理這么大的數(shù)據(jù)，的確是十分驚艷的。有個伯克利分校的教授Armando Fox說過一句話“如果你曾事先告訴我Dremel聲稱其將可做些什么，那么我不會相信你能開發(fā)出這種工具”。這么給力的技術(shù)，必然對業(yè)界造成巨大的影響。第一個被波及到的必然是Hadoop。

Dremel與Hadoop

Dremel的公開論文里面已經(jīng)說的很明白，Dremel不是用來替代MapReduce，而是和其更好的結(jié)合。Hadoop的Hive，Pig無法提供及時的查詢，而Dremel的快速查詢技術(shù)可以給Hadoop提供有力的補充。同時Dremel可以用來分析MapReduce的結(jié)果集，只需要將MapReduce的OutputFormat修改為Dremel的格式，就可以幾乎不引入額外開銷，將數(shù)據(jù)導(dǎo)入Dremel。使用Dremel來開發(fā)數(shù)據(jù)分析模型，MapReduce來執(zhí)行數(shù)據(jù)分析模型。

Hadoop的Hive,Pig現(xiàn)在也有了列存的模式，架構(gòu)上和Dremel也接近。但是無論存儲結(jié)構(gòu)還是計算方式都沒有Dremel精致。對Hadoop實時性的改進也一直是個熱點話題。要想在Hadoop中山寨一個Dremel，并且相對現(xiàn)有解決方案有突破，筆者覺得Hadoop自身需要一些改進。一個是HDFS需要對并發(fā)細(xì)碎的數(shù)據(jù)讀性能有大的改進，HDFS需要更加的低延遲。再者是Hadoop需要不僅僅支持MapReduce這一種計算框架。其他部分,Hadoop都有對應(yīng)的開源組件，萬事俱備只欠東風(fēng)。

Dremel的開源實現(xiàn)

Dremel現(xiàn)在還沒有一個可以運行的開源實現(xiàn)，不過我們看到很多努力。一個是Apache的Drill，一個是OpenDremel/Dazo。

OpenDremel/Dazo

OpenDremel是一個開源項目，最近改名為Dazo?？梢栽贕oogleCode上找到http://code.google.com/p/dremel/。目前還沒有發(fā)布。作者聲稱他已經(jīng)完成了一個通用執(zhí)行引擎和OpenStack Swift的集成。筆者感覺其越走越歪，離Dremel越來越遠(yuǎn)了。

Apache Drill

Drill 是Hadoop的贊助商之一MapR發(fā)起的。Drill作為一個Dremel的山寨項目，有和Dremel相似的架構(gòu)和能力。他們希望Drill最終會想Hive,Pig一樣成為Hadoop上的重要組成部分。為Hadoop提供快速查詢的能力。和Dremel有一點不同，在數(shù)據(jù)模型上，開源的項目需要支持更標(biāo)準(zhǔn)的數(shù)據(jù)結(jié)構(gòu)。比如CSV和JSON。同時Drill還有更大的靈活性，支持多重查詢語言，多種接口。

現(xiàn)在Drill的目標(biāo)是完成初始的需求，架構(gòu)。完成一個初始的實現(xiàn)。這個實現(xiàn)包括一個執(zhí)行引擎和DrQL。DrQL是一個基于列的格式，類似于Dremel。目前，Drill已經(jīng)完成的需求和架構(gòu)設(shè)計?？偣卜譃榱怂膫€組件

• Query language:類似Google BigQuery的查詢語言，支持嵌套模型，名為DrQL.
• Low-lantency distribute execution engine:執(zhí)行引擎，可以支持大規(guī)模擴展和容錯。可以運行在上萬臺機器上計算數(shù)以PB的數(shù)據(jù)。
• Nested data format:嵌套數(shù)據(jù)模型，和Dremel類似。也支持CSV,JSON,YAML類似的模型。這樣執(zhí)行引擎就可以支持更多的數(shù)據(jù)類型。
• Scalable data source: 支持多種數(shù)據(jù)源，現(xiàn)階段以Hadoop為數(shù)據(jù)源。

目前這四個組件在分別積極的推進，Drill也非常希望有社區(qū)其他公司來加入。Drill希望加入到Hadoop生態(tài)系統(tǒng)中去。

最后的話

本文介紹了Google Dremel的使用場景，設(shè)計實現(xiàn)，測試實驗，和對開源世界的影響。相信不久的將來，Dremel的技術(shù)會得到廣泛的應(yīng)用。