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)營。

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