Kylin構(gòu)建Cube算法

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

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

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

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

【資料圖】

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

player-1：以source data（源數(shù)據(jù)）為基礎(chǔ)計算出一個n維的cuboid；

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

... ...

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

... ...

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

如下圖：

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

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

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

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

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

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

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

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

性能對比：

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

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

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

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

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

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

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

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

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

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