簡介

Dremel 是Google 的“交互式”數據分析系統。可以組建成規模上千的集群，處理PB級別的數據。MapReduce處理一個數據，需要分鐘級的時間。作為MapReduce 的發起人，Google開發了Dremel將處理時間縮短到秒級，作為MapReduce的有力補充。Dremel作為Google BigQuery的report引擎，獲得了很大的成功。最近Apache計劃推出Dremel的開源實現Drill，將Dremel的技術又推到了浪尖 上。

Google Dremel設計

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

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

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

Google Dremel應用場景

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

對于Google,數據一開始是放在GFS上的。可以通過MapReduce將數據導入到Dremel中去，在這些MapReduce中還可以做一些處理。然后分析師使用Dremel，輕松愉悅的分析數據，建立模型。最后可以編制成一個長期運行的MapReduce任務。

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

還有一點特別的就是按列存儲的嵌套數據格式。如圖所示，在按記錄存儲的模式中，一個記錄的多列是連續的寫在一起的。在按列存儲中，可以將數據按列分 開。也就是說，可以僅僅掃描A.B.C而不去讀A.E或者A.B.C。難點在于，我們如何能同時高效地掃描若干列，并做一些分析。

Google Dremel數據模型

在Google, 用Protocol Buffer常常作為序列化的方案。其數據模型可以用數學方法嚴格的表示如下：

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

下圖是例子，Schema定義了一個組合類型Document.有一個必選列DocId，可選列Links，還有一個數組列Name。可以用Name.Language.Code來表示Code列。

這種數據格式是語言無關，平臺無關的。可以使用Java來寫MR程序來生成這個格式，然后用C++來讀取。在這種列式存儲中，能夠快速通用處理也是非常的重要的。

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

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

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

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

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

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，記錄其數量沒有意義。

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

下圖展示了一個更為復雜的讀取的狀態機示例。在讀取過程中使用了Definition Level來快速Jump,提升性能。

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

Google Dremel查詢方式

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

這是一個樹狀架構。當Client發其一個請求，根節點受到請求，根據metadata，將其分解到枝葉，直到到位于數據上面的葉子Server。他們掃描處理數據，又不斷匯總到根節點。

舉個例子：對于請求：

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

根節點收到請求，會根據數據的分區請求，將請求變成可以拆分的樣子。原來的請求會變為。

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

R1,…RN是T的分區計算出的結果集。越大的表有越多的分區，越多的分區可以越好的支持并發。

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

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

結構集一定會比原始數據小很多，處理起來也更快。根服務器可以很快的將數據匯總。具體的聚合方式，可以使用現有的并行數據庫技術。

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

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

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

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

Google Dremel測試實驗

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

表名	記錄數	大小(已壓縮)	列數	數據中心	復制數量
T1	85 billion	87 TB	270	A	3×
T2	24 billion	13 TB	530	A	3×
T3	4 billion	70 TB	1200	A	3×
T4	1+ trillion	105 TB	50	B	2×
T5	1+ trillion	20 TB	30	B	3×

列存測試

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

見上圖。

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

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

Dremel和MapReduce的對比測試

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

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

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

樹狀計算Server測試

接下來我們要對比在T2表示使用兩個不同的Group BY查詢。T2表有24 billion 行的記錄。每個記錄有一個 item列表，每一item有一個amount 字段。總共有40 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的壓縮數據，Q3需要掃描180GB，同時還要過濾一個條件。

上圖是這兩個Query在不同的server拓撲下的性能。每個測試都是有2900個葉子Server。在2級拓撲中，根server直接和葉子 Server通信。在3級拓撲中，各個級別的比例是1:100:2900，增加了100個中間Server。在4級拓撲中，比例為 1:10:100:2900.

Q2可以在3級拓撲下3秒內執行完畢，但是為他提供更高的拓撲級別，對性能提升沒有裨益。相比之下，為Q3提供更高的拓撲級別，性能可以有效提升。這個測試體現了樹狀拓撲對性能提升的作用。

每個分區的執行情況

對于剛剛的兩個查詢，具體的每個分區的執行情況是這樣的。

可以看到99%的分區都在1s內完成了。Dremel會自動調度，使用新的Server計算拖后腿的任務。

記錄內聚合

由于Demel支持List的數據類型，有的時候，我們需要計算每個記錄里面的各個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)，執行這條語句實際只需要掃描13GB的數據，耗時15s，而整張表有70TB。如果沒有這樣的嵌套數據結構，這樣的查詢會很復雜。

擴展性測試

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

對于查詢：

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

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

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

容錯測試

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

    Q6: SELECT COUNT(DISTINCT a) FROM T5
  

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

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

Google Dremel 的影響

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

Dremel與Hadoop

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

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

Dremel的開源實現

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

OpenDremel/Dazo

OpenDremel是一個開源項目，最近改名為Dazo。可以在GoogleCode上找到 http://code.google.com/p/dremel/ 。目前還沒有發布。作者聲稱他已經完成了一個通用執行引擎和OpenStack Swift的集成。筆者感覺其越走越歪，離Dremel越來越遠了。

Apache Drill

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

現在Drill的目標是完成初始的需求，架構。完成一個初始的實現。這個實現包括一個執行引擎和DrQL。DrQL是一個基于列的格式，類似于Dremel。目前，Drill已經完成的需求和架構設計。總共分為了四個組件

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

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

最后的話

本文介紹了Google Dremel的使用場景，設計實現，測試實驗，和對開源世界的影響。相信不久的將來，Dremel的技術會得到廣泛的應用。

原文出處： http://www.yankay.com/google-dremel-rationale/

Google Dremel 原理 - 如何能 3 秒分析 1PB