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的記錄。
- 第一個是”en-us”,出現在第一個Name的第一個Lanuage的第一個Code里面。在此之前,這三個元素是沒有重復過的,都是第一個。所以其R為0。
- 第二個是”en”,出現在下一個Lanuage里面。也就是說Lanague是重復的元素。Name.Language.Code中Lanague排第二個,所以其R為2.
- 第三個是”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/
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
