Apache Kylin v1.5版本中的快速數(shù)據(jù)立方算法揭秘

責(zé)任編輯:editor004

作者:史少鋒

2016-08-08 12:26:10

摘自:INFOQ

Apache Kylin是一個(gè)開源的分布式分析引擎,提供Hadoop之上的SQL查詢接口及多維分析(OLAP)能力以支持超大規(guī)模數(shù)據(jù)。此算法可以脫離Map-Reduce而對數(shù)據(jù)做Cube計(jì)算,故可以很容易地在其它場景或框架下執(zhí)行,例如Streaming 和Spark。

Apache Kylin是一個(gè)開源的分布式分析引擎,提供Hadoop之上的SQL查詢接口及多維分析(OLAP)能力以支持超大規(guī)模數(shù)據(jù)。它能在亞秒內(nèi)查詢巨大的Hive表。本文將詳細(xì)介紹Apache Kylin 1.5中的Fast-Cubing算法。

Fast Cubing,也稱快速數(shù)據(jù)立方算法, 是一個(gè)新的Cube算法。我們知道,Cube的思想是用空間換時(shí)間, 通過預(yù)先的計(jì)算,把索引及結(jié)果存儲(chǔ)起來,以換取查詢時(shí)候的高性能 。在Kylin v1.5以前,Kylin中的Cube只有一種算法:layered cubing,也稱逐層算法:它是逐層由底向上,把所有組合算完的過程。

圖1是一個(gè)四維Cube,有維度A、B、C、D;它會(huì)需要五輪的Map-Reduce來完成:第一輪MR的輸入是源數(shù)據(jù), 這一步會(huì)對維度列的值進(jìn)行編碼,并計(jì)算ABCD組合的結(jié)果。接下來的MR以上一輪的輸出為輸入,向上聚合計(jì)算三個(gè)維度的組合: ABC, BCD, ABD, 和ACD;依此類推,直到算出所有的維度組合。

這個(gè)算法的優(yōu)勢是每一輪MR以上一輪的輸出為結(jié)果,這樣可以減少重復(fù)結(jié)算;當(dāng)計(jì)算到后半程的時(shí)候,隨著數(shù)據(jù)的減小,計(jì)算會(huì)越來越快 。

逐層Cube算法的主要優(yōu)點(diǎn)是簡單:Cube聚合的過程就是把要聚合掉的維度從key中減掉組成新的key交給Map-Reduce,由Map-Reduce框架對新key做排序和再聚合,計(jì)算結(jié)果寫到HDFS。這個(gè)算法很好地利用了Map-Reduce框架。得益于Hadoop/Map-Reduce的成熟,此算法的穩(wěn)定性已經(jīng)非常高。

經(jīng)過不斷的實(shí)踐,開發(fā)團(tuán)隊(duì)也發(fā)現(xiàn)了此算法的局限:我們知道,當(dāng)數(shù)據(jù)量大的時(shí)候,Hadoop主要利用外存(也就是磁盤)做排序,數(shù)據(jù)在Mapper和Reducer之間還需要洗牌(shuffle)。在計(jì)算Cube的時(shí)候,集群的IO使用率往往很高; 在運(yùn)行一些大的任務(wù)時(shí),瓶頸會(huì)出現(xiàn)在網(wǎng)絡(luò)傳輸和磁盤讀寫上,而CPU和內(nèi)存的使用率比較低。

此外, 因?yàn)樾枰f交N+1次Map-Reduce任務(wù);每次遞交任務(wù),都需要檢查集群是否有可用的節(jié)點(diǎn)能否滿足資源要求,如果沒有還需等待其它任務(wù)釋放資源;反復(fù)的任務(wù)遞交,給Hadoop集群帶來額外的調(diào)度開銷。特別是當(dāng)集群比較繁忙的時(shí)候,等待的時(shí)間常常會(huì)非??捎^,這些都導(dǎo)致 了Cube構(gòu)建的時(shí)間比較長 。

帶著這個(gè)問題開發(fā)團(tuán)隊(duì)做了不斷分析和嘗試,結(jié)合了若干研究者的論文,于是有了開發(fā)新算法的設(shè)想。新算法的核心思想是清晰簡單的,就是最大化利用Mapper端的CPU和內(nèi)存,對分配的數(shù)據(jù)塊,將需要的組合全都做計(jì)算后再輸出給Reducer; 由Reducer再做一次合并(merge),從而計(jì)算出完整數(shù)據(jù)的所有組合。如此,經(jīng)過一輪Map-Reduce就完成了以前需要N輪的Cube計(jì)算。圖2是此算法的概覽。

在Mapper內(nèi)部, 也可以有一些優(yōu)化,圖3是一個(gè)典型的四維Cube的生成樹;第一步會(huì)計(jì)算Base Cuboid(所有維度都有的組合),再基于它計(jì)算減少一個(gè)維度的組合?;趐arent節(jié)點(diǎn)計(jì)算child節(jié)點(diǎn),可以重用之前的計(jì)算結(jié)果;當(dāng)計(jì)算child節(jié)點(diǎn)時(shí),需要parent節(jié)點(diǎn)的值盡可能留在內(nèi)存中; 如果child節(jié)點(diǎn)還有child,那么遞歸向下,所以它是一個(gè)深度優(yōu)先遍歷。當(dāng)有一個(gè)節(jié)點(diǎn)沒有child,或者它的所有child都已經(jīng)計(jì)算完,這時(shí)候它就可以被輸出,占用的內(nèi)存就可以釋放。

如果內(nèi)存夠的話,可以多線程并行向下聚合。如此可以最大限度地把計(jì)算發(fā)生在Mapper這一端,一方面減少shuffle的數(shù)據(jù)量,另一方面減少Reducer端的計(jì)算量。

Fast Cubing的優(yōu)點(diǎn)

總的IO量比以前大大減少。

此算法可以脫離Map-Reduce而對數(shù)據(jù)做Cube計(jì)算,故可以很容易地在其它場景或框架下執(zhí)行,例如Streaming 和Spark。

Fast Cubing的缺點(diǎn)

代碼比以前復(fù)雜了很多: 由于要做多層的聚合,并且引入多線程機(jī)制,同時(shí)還要估算JVM可用內(nèi)存,當(dāng)內(nèi)存不足時(shí)需要將數(shù)據(jù)暫存到磁盤,所有這些都增加復(fù)雜度。

對Hadoop資源要求較高,用戶應(yīng)盡可能在Mapper上多分配內(nèi)存;如果內(nèi)存很小,該算法需要頻繁借助磁盤,性能優(yōu)勢就會(huì)較弱。在極端情況下(如數(shù)據(jù)量很大同時(shí)維度很多),任務(wù)可能會(huì)由于超時(shí)等原因失??;

要讓Fast-Cubing算法獲得更高的效率,用戶需要了解更多一些“內(nèi)情”。

首先,在v1.5里,Kylin在對Fast-Cubing請求資源時(shí)候,默認(rèn)是為Mapper任務(wù)請求3Gb的內(nèi)存,給JVM2.7Gb。如果Hadoop節(jié)點(diǎn)可用內(nèi)存較多的話,用戶可以讓Kylin獲得更多內(nèi)存:在conf/kylin_job_conf_inmem.xml文件,由參數(shù)“mapreduce.map.memory.mb”和“mapreduce.map.java.opts”設(shè)定 。

其次,需要在并發(fā)性和Mapper端聚合之間找到一個(gè)平衡。在v1.5.2里,Kylin默認(rèn)是給每個(gè)Mapper分配32兆的數(shù)據(jù);這樣可以獲得較高的并發(fā)性。但如果Hadoop集群規(guī)模較小,或可用資源較少,過多的Mapper會(huì)造成任務(wù)排隊(duì)。這時(shí),將數(shù)據(jù)塊切得更大,如 64兆,效果會(huì)更好。數(shù)據(jù)塊是由Kylin創(chuàng)建Hive平表時(shí)生成的, 在kylin_hive_conf.xml由參數(shù)dfs.block.size決定的。從v1.5.3開始,分配策略又有改進(jìn),給每個(gè)mapper會(huì)分配一樣的行數(shù),從而避免數(shù)據(jù)塊不均勻時(shí)的木桶效應(yīng):由conf/kylin.properteis里的“kylin.job.mapreduce.mapper.input.rows”配置,默認(rèn)是100萬,用戶可以示自己集群的規(guī)模設(shè)置更小值獲得更高并發(fā),或更大值減少請求的Mapper數(shù)。

通常推薦Fast-Cubing 算法,但不是所有情況下都如此。

舉例說明,如果每個(gè)Mapper之間的key交叉重合度較低,fast cubing更適合;因?yàn)镸apper端將這塊數(shù)據(jù)最終要計(jì)算的結(jié)果都達(dá)到了,Reducer只需少量的聚合。另一個(gè)極端是,每個(gè)Mapper計(jì)算出的key跟其它 Mapper算出的key深度重合,這意味著在reducer端仍需將各個(gè)Mapper的數(shù)據(jù)抓取來再次聚合計(jì)算;如果key的數(shù)量巨大,該過程IO開銷依然顯著。對于這種情況,Layered-Cubing更適合。

用戶該如何選擇算法呢? 無需擔(dān)心,Kylin會(huì)自動(dòng)選擇合適的算法。

Kylin在計(jì)算Cube之前對數(shù)據(jù)進(jìn)行采樣,在“fact distinct”步,利用HyperLogLog模擬去重,估算每種組合有多少不同的key,從而計(jì)算出每個(gè)Mapper輸出的數(shù)據(jù)大小,以及所有Mapper之間數(shù)據(jù)的重合率,據(jù)此來決定采用哪種算法更優(yōu)。在對上百個(gè)Cube任務(wù)的時(shí)間做統(tǒng)計(jì)分析后,Kylin選擇了8做為默認(rèn)的算法選擇閥值(參數(shù)kylin.cube.algorithm.auto.threshold):如果各個(gè)Mapper的小Cube的行數(shù)之和,大于reduce后的Cube行數(shù)的8倍,采用Layered Cubing, 反之采用Fast Cubing。如果用戶在使用過程中,更傾向于使用Fast Cubing,可以適當(dāng)調(diào)大此參數(shù)值,反之調(diào)小。

作者介紹

史少鋒,Kyligence技術(shù)合伙人兼資深架構(gòu)師,Apache Kylin核心開發(fā)者和項(xiàng)目管理委員會(huì)成員(PMC),專注于大數(shù)據(jù)分析和云計(jì)算技術(shù)。曾任eBay全球分析基礎(chǔ)架構(gòu)部大數(shù)據(jù)高級工程師,IBM云計(jì)算部門軟件架構(gòu)師;曾是IBM公有云Bluemix DevOps團(tuán)隊(duì)核心成員,負(fù)責(zé)平臺(tái)的規(guī)劃、開發(fā)和運(yùn)營。

感謝杜小芳對本文的審校。

鏈接已復(fù)制,快去分享吧

企業(yè)網(wǎng)版權(quán)所有?2010-2024 京ICP備09108050號-6京公網(wǎng)安備 11010502049343號