Kylin構建Cube算法

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

一、??????????????layered cubing

1、??????????????基于MR

這個算法的對cube的計算就像它的名字一樣是按layer進行的。

【資料圖】

以一個n維cube（即事實表有n個維度）為例：

player-1：以source data（源數據）為基礎計算出一個n維的cuboid；

player-2：以上一層的n維cuboid維基礎，計算出n個n-1維的cuboid；

... ...

player-k+1：以上一層的n-k+1維cuboid為基礎，計算出n!/[(n-k)!k!]=個n-k維的cuboid；

... ...

player-n+1：以上一層的1維cuboid為基礎，計算出1個0維的cuboid。

如下圖：

用官網上一個4維cube的例子來說明一下具體過程。

在player-1，根據源數據得到1個4-D的cuboid；然后cong中任意取出三個維度得到4個3-D cuboids；接著從3-D cuboids出發，任意取出其中兩個維度得到6個2-D cuboids；再以2-D cuboids為基礎，任意取出其中一個維度得到4個1-D cuboids；最后根據1-D cuboids 計算出一個0-D cuboid。

此算法的Mapper和Reducer都比較簡單。Mapper以上一層Cuboid的結果（Key-Value對）作為輸入。由于Key是由各維度值拼接在一起，從其中找出要聚合的維度，去掉它的值成新的Key，并對Value進行操作，然后把新Key和Value輸出，進而Hadoop MapReduce對所有新Key進行排序、洗牌（shuffle）、再送到Reducer處；Reducer的輸入會是一組有相同Key的Value集合，對這些Value做聚合計算，再結合Key輸出就完成了一輪計算。

優點：這個算法的原理很清晰，主要就是利用了MR，sorting、grouping、shuffing全部由MR完成，開發人員只需要關注cubing的邏輯，由于hadoop的成熟，該算法的運行很穩定。

缺點：cube的維度越高，需要的MR任務越多（n-D cube 至少需要n 個MR）太多的shuffing操作（mapper端不做聚合，所有在下一層中具有相同維度的值有combiner 和reducer聚合）,對hdfs讀寫比較多（每一層MR的結果會寫到hdfs然后下一層MR從hdfs 讀取數據）。

2、??????????????基于Spark

“by-layer” Cubing把一個大任務劃分為許多步驟，每一步驟的計算依賴于上一個步驟的輸出結果，所以當某一個步驟的計算出現問題時，可以再次讀取上一步驟的結果重新計算，而不用從頭開始。使得“by-layer” Cubing算法穩定可靠，當換到spark上時，便保留了這個算法。因此在spark上這個算法也被稱為“By layer Spark Cubing”。

如上圖所示，與在MR上相比，每一層的計算結果不再輸出到hdfs，而是放在RDD中。由于RDD存儲在內存中，從而有效避免了MR上過多的讀寫操作。

性能對比：

二、??????????????Fast cubing

快速Cube算法（Fast Cubing）是麒麟團隊對新算法的一個統稱，它還被稱作“逐段”(By Segment) 或“逐塊”(By Split) 算法。

該算法的主要思想是，對Mapper所分配的數據塊，將它計算成一個完整的小Cube 段（包含所有Cuboid）；每個Mapper將計算完的Cube段輸出給Reducer做合并，生成大Cube，也就是最終結果；下圖解釋了此流程。新算法的核心思想是清晰簡單的，就是最大化利用Mapper端的CPU和內存，對分配的數據塊，將需要的組合全都做計算后再輸出給Reducer；由Reducer再做一次合并（merge），從而計算出完整數據的所有組合。如此，經過一輪Map-Reduce就完成了以前需要N輪的Cube計算。

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

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

優點：總的IO量比以前大大減少。此算法可以脫離Map-Reduce而對數據做Cube計算，故可以很容易地在其它場景或框架下執行，例如Streaming 和Spark。

缺點：代碼比以前復雜了很多，由于要做多層的聚合，并且引入多線程機制，同時還要估算JVM可用內存，當內存不足時需要將數據暫存到磁盤，所有這些都增加復雜度。對Hadoop資源要求較高，用戶應盡可能在Mapper上多分配內存；如果內存很小，該算法需要頻繁借助磁盤，性能優勢就會較弱。在極端情況下（如數據量很大同時維度很多），任務可能會由于超時等原因失敗。

三、??????????????算法選擇

用戶無需擔心使用什么算法構建cube，Kylin會自動選擇合適的算法。Kylin在計算Cube之前對數據進行采樣，在“fact distinct”步，利用HyperLogLog模擬去重，估算每種組合有多少不同的key，從而計算出每個Mapper輸出的數據大小，以及所有Mapper之間數據的重合度，據此來決定采用哪種算法更優。

如果每個Mapper之間的key交叉重合度較低，fast cubing更適合；因為Mapper端將這塊數據最終要計算的結果都達到了，Reducer只需少量的聚合。另一個極端是，每個Mapper計算出的key跟其它 Mapper算出的key深度重合，這意味著在reducer端仍需將各個Mapper的數據抓取來再次聚合計算；如果key的數量巨大，該過程IO開銷依然顯著。對于這種情況，Layered-Cubing更適合。在對上百個Cube任務的時間做統計分析后，Kylin選擇了7做為默認的算法選擇閥值(參數kylin.cube.algorithm.auto.threshold)：如果各個Mapper的小Cube的行數之和，大于reduce后的Cube行數的8倍(各個Mapper的小Cube的行數之和 /reduce后的Cube行數 > 7)，采用Layered Cubing, 反之采用Fast Cubing(本質就是各個Mapper之間的key重復度越小，就用Fast Cubing，重復度越大，就用Layered Cubing)