摘自：http://www.yankay.com/google-dremel-rationale/

簡介

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

Google Dremel設計

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

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

·????????Dremel是一個大規(guī)模系統(tǒng)。在一個PB級別的數(shù)據(jù)集上面，將任務縮短到秒級，無疑需要大量的并發(fā)。磁盤的順序讀速度在100MB/S上下，那么在1S內處理1TB數(shù)據(jù)，意味著至少需要有1萬個磁盤的并發(fā)讀! Google一向是用廉價機器辦大事的好手。但是機器越多，出問題概率越大，如此大的集群規(guī)模，需要有足夠的容錯考慮，保證整個分析的速度不被集群中的個別慢(壞)節(jié)點影響。

·????????Dremel是MR交互式查詢能力不足的補充。和MapReduce一樣，Dremel也需要和數(shù)據(jù)運行在一起，將計算移動到數(shù)據(jù)上面。所以它需要GFS這樣的文件系統(tǒng)作為存儲層。在設計之初，Dremel并非是MapReduce的替代品，它只是可以執(zhí)行非常快的分析，在使用的時候，常常用它來處理MapReduce的結果集或者用來建立分析原型。

·????????Dremel的數(shù)據(jù)模型是嵌套(nested)的。互聯(lián)網數(shù)據(jù)常常是非關系型的。Dremel還需要有一個靈活的數(shù)據(jù)模型，這個數(shù)據(jù)模型至關重要。Dremel支持一個嵌套(nested)的數(shù)據(jù)模型，類似于Json。而傳統(tǒng)的關系模型，由于不可避免的有大量的Join操作，在處理如此大規(guī)模的數(shù)據(jù)的時候，往往是有心無力的。

·????????Dremel中的數(shù)據(jù)是用列式存儲的。使用列式存儲，分析的時候，可以只掃描需要的那部分數(shù)據(jù)的時候，減少CPU和磁盤的訪問量。同時列式存儲是壓縮友好的，使用壓縮，可以綜合CPU和磁盤，發(fā)揮最大的效能。對于關系型數(shù)據(jù)，如果使用列式存儲，我們都很有經驗。但是對于嵌套(nested)的結構，Dremel也可以用列存儲，非常值得我們學習。

·????????Dremel結合了Web搜索?和并行DBMS的技術。首先，他借鑒了Web搜索中的“查詢樹”的概念，將一個相對巨大復雜的查詢，分割成較小較簡單的查詢。大事化小，小事化了，能并發(fā)的在大量節(jié)點上跑。其次，和并行DBMS類似，Dremel可以提供了一個SQL-like的接口，就像Hive和Pig那樣。

Google Dremel應用場景

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

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

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

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

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

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

t=dom|<A1:t[?|?],...,An:t[?|?]>

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

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

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

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

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

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

1.??? 第一個是”en-us”，出現(xiàn)在第一個Name的第一個Lanuage的第一個Code里面。在此之前，這三個元素是沒有重復過的，都是第一個。所以其R為0。

2.??? 第二個是”en”，出現(xiàn)在下一個Lanuage里面。也就是說Lanague是重復的元素。Name.Language.Code中Lanague排第二個，所以其R為2.

3.??? 第三個是”en-gb”，出現(xiàn)在下一個Name中，Name是重復元素，排第一個，所以其R為1。

我們可以想象，將所有的沒有值的列，設值為NULL。如果是數(shù)組列，我們也想象有一個NULL值。有了Repetition Level，我們就可以很好的用列表示嵌套的結構了。但是還有一點不足。就是還需要表示一個數(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ù)量沒有意義。

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

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

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

Google Dremel查詢方式

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

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

舉個例子：對于請求：

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

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

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

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

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

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

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

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

通常情況下，每個計算節(jié)點，執(zhí)行多個任務。例如，技巧中有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ū)，在使用的時候，相當于隨機抽樣，加快查詢。

Google Dremel測試實驗

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

表名	記錄數(shù)	大小(已壓縮)	列數(shù)	數(shù)據(jù)中心	復制數(shù)量
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的數(shù)據(jù)大約有300K行，使用列存的話壓縮后大約在375MB。這臺機器磁盤的吞吐在70MB/s左右。這1GB的數(shù)據(jù)，就是我們的現(xiàn)在的測試數(shù)據(jù)源，測試環(huán)境是單機。

見上圖。

·????????曲線A，是用列存讀取數(shù)據(jù)并解壓的耗時。

·????????曲線B是一條一條記錄挨個讀的時間。

·????????曲線C是在B的基礎上，加上了反序列化的時間。

·????????曲線d，是按行存讀并解壓的耗時。

·????????曲線e加上了反序列化的時間。因為列很多，反序列化耗時超過了讀并解壓的50%。

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

Dremel和MapReduce的對比測試

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

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

?

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

樹狀計算Server測試

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

1 2 3

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拓撲下的性能。每個測試都是有2900個葉子Server。在2級拓撲中，根server直接和葉子Server通信。在3級拓撲中，各個級別的比例是1:100:2900，增加了100個中間Server。在4級拓撲中，比例為1:10:100:2900.

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

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

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

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

記錄內聚合

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

1 2 3 4 5 6 7

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ù)結構，這樣的查詢會很復雜。

擴展性測試

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

對于查詢：

1	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í)行時間也會相應縮短。幾乎呈線性遞減。如果我們使用通過CPU時間計費的“云計算”機器，每個租戶的查詢都可以很快，成本也會非常低廉。

容錯測試

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

1	Q6: SELECT COUNT(DISTINCT a) FROM T5

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

?

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

Google Dremel 的影響

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

Dremel與Hadoop

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

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

Dremel的開源實現(xiàn)

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

OpenDremel/Dazo

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

Apache Drill

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

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

·????????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的使用場景，設計實現(xiàn)，測試實驗，和對開源世界的影響。相信不久的將來，Dremel的技術會得到廣泛的應用。

?

轉載于:https://www.cnblogs.com/cl1024cl/p/6205424.html

總結

以上是生活随笔為你收集整理的Google Dremel 原理 - 如何能3秒分析1PB的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。