Apache Kylin是一個開源的分布式分析引擎，提供Hadoop之上的SQL查詢接口及多維分析（OLAP）能力以支持超大規模數據。它能在亞秒內查詢巨大的Hive表。本文將詳細介紹Apache Kylin 1.5中的Fast-Cubing算法。

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

圖1是一個四維Cube，有維度A、B、C、D；它會需要五輪的Map－Reduce來完成：第一輪MR的輸入是源數據， 這一步會對維度列的值進行編碼，并計算ABCD組合的結果。接下來的MR以上一輪的輸出為輸入，向上聚合計算三個維度的組合： ABC, BCD, ABD, 和ACD；依此類推，直到算出所有的維度組合。

這個算法的優勢是每一輪MR以上一輪的輸出為結果，這樣可以減少重復結算；當計算到后半程的時候，隨著數據的減小，計算會越來越快 。

逐層Cube算法的主要優點是簡單：Cube聚合的過程就是把要聚合掉的維度從key中減掉組成新的key交給Map-Reduce，由Map-Reduce框架對新key做排序和再聚合，計算結果寫到HDFS。這個算法很好地利用了Map-Reduce框架。得益于Hadoop/Map－Reduce的成熟，此算法的穩定性已經非常高。

經過不斷的實踐，開發團隊也發現了此算法的局限：我們知道，當數據量大的時候，Hadoop主要利用外存（也就是磁盤）做排序，數據在Mapper和Reducer之間還需要洗牌（shuffle）。在計算Cube的時候，集群的IO使用率往往很高; 在運行一些大的任務時，瓶頸會出現在網絡傳輸和磁盤讀寫上，而CPU和內存的使用率比較低。

此外, 因為需要遞交N+1次Map－Reduce任務；每次遞交任務，都需要檢查集群是否有可用的節點能否滿足資源要求，如果沒有還需等待其它任務釋放資源；反復的任務遞交，給Hadoop集群帶來額外的調度開銷。特別是當集群比較繁忙的時候，等待的時間常常會非常可觀，這些都導致 了Cube構建的時間比較長 。

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

在Mapper內部， 也可以有一些優化，圖3是一個典型的四維Cube的生成樹；第一步會計算Base Cuboid（所有維度都有的組合），再基于它計算減少一個維度的組合。基于parent節點計算child節點，可以重用之前的計算結果；當計算child節點時，需要parent節點的值盡可能留在內存中； 如果child節點還有child，那么遞歸向下，所以它是一個深度優先遍歷。當有一個節點沒有child，或者它的所有child都已經計算完，這時候它就可以被輸出，占用的內存就可以釋放。

如果內存夠的話，可以多線程并行向下聚合。如此可以最大限度地把計算發生在Mapper這一端，一方面減少shuffle的數據量，另一方面減少Reducer端的計算量。

Fast Cubing的優點：

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

此算法可以脫離Map-Reduce而對數據做Cube計算，故可以很容易地在其它場景或框架下執行，例如Streaming 和Spark。

Fast Cubing的缺點：

代碼比以前復雜了很多： 由于要做多層的聚合，并且引入多線程機制，同時還要估算JVM可用內存，當內存不足時需要將數據暫存到磁盤，所有這些都增加復雜度。

對Hadoop資源要求較高，用戶應盡可能在Mapper上多分配內存；如果內存很小，該算法需要頻繁借助磁盤，性能優勢就會較弱。在極端情況下（如數據量很大同時維度很多），任務可能會由于超時等原因失敗；

要讓Fast-Cubing算法獲得更高的效率，用戶需要了解更多一些“內情”。

首先，在v1.5里，Kylin在對Fast-Cubing請求資源時候，默認是為Mapper任務請求3Gb的內存，給JVM2.7Gb。如果Hadoop節點可用內存較多的話，用戶可以讓Kylin獲得更多內存：在conf/kylin_job_conf_inmem.xml文件，由參數“mapreduce.map.memory.mb”和“mapreduce.map.java.opts”設定 。

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

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

舉例說明，如果每個Mapper之間的key交叉重合度較低，fast cubing更適合；因為Mapper端將這塊數據最終要計算的結果都達到了，Reducer只需少量的聚合。另一個極端是，每個Mapper計算出的key跟其它 Mapper算出的key深度重合，這意味著在reducer端仍需將各個Mapper的數據抓取來再次聚合計算；如果key的數量巨大，該過程IO開銷依然顯著。對于這種情況，Layered-Cubing更適合。

用戶該如何選擇算法呢? 無需擔心，Kylin會自動選擇合適的算法。

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

作者介紹

史少鋒，Kyligence技術合伙人兼資深架構師，Apache Kylin核心開發者和項目管理委員會成員（PMC)，專注于大數據分析和云計算技術。曾任eBay全球分析基礎架構部大數據高級工程師，IBM云計算部門軟件架構師；曾是IBM公有云Bluemix DevOps團隊核心成員，負責平臺的規劃、開發和運營。

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