?

?

　　不多說，直接上干貨！

?

?

?

?

1、 Cube的物理模型

Cube物理模型

　　如上圖所示，一個(gè)常用的3維立方體，包含：時(shí)間、地點(diǎn)、產(chǎn)品。假如data cell 中存放的是產(chǎn)量，則我們可以根據(jù)時(shí)間、地點(diǎn)、產(chǎn)品來確定產(chǎn)量，同時(shí)也可以根據(jù)時(shí)間、地點(diǎn)來確定所有產(chǎn)品的總產(chǎn)量等。
　　Apache Kylin就將所有（時(shí)間、地點(diǎn)、產(chǎn)品）的各種組合實(shí)現(xiàn)算出來，data cell 中存放度量，其中每一種組合都稱為cuboid。估n維的數(shù)據(jù)最多有2^n個(gè)cuboid，不過Kylin通過設(shè)定維度的種類，可以減少cuboid的數(shù)目。

2 、Cube構(gòu)建算法介紹

2.1 逐層算法(Layer Cubing)

　　我們知道，一個(gè)N維的Cube，是由1個(gè)N維子立方體、N個(gè)(N-1)維子立方體、N*(N-1)/2個(gè)(N-2)維子立方體、......、N個(gè)1維子立方體和1個(gè)0維子立方體構(gòu)成，總共有2^N個(gè)子立方體組成，在逐層算法中，按維度數(shù)逐層減少來計(jì)算，每個(gè)層級(jí)的計(jì)算（除了第一層，它是從原始數(shù)據(jù)聚合而來），是基于它上一層級(jí)的結(jié)果來計(jì)算的。
比如，[Group by A, B]的結(jié)果，可以基于[Group by A, B, C]的結(jié)果，通過去掉C后聚合得來的；這樣可以減少重復(fù)計(jì)算；當(dāng) 0維度Cuboid計(jì)算出來的時(shí)候，整個(gè)Cube的計(jì)算也就完成了。

　　　　　　　　　　　　 逐層算法

　　如上圖所示，展示了一個(gè)4維的Cube構(gòu)建過程。
　　此算法的Mapper和Reducer都比較簡單。Mapper以上一層Cuboid的結(jié)果（Key-Value對(duì)）作為輸入。由于Key是由各維度值拼接在一起，從其中找出要聚合的維度，去掉它的值成新的Key，并對(duì)Value進(jìn)行操作，然后把新Key和Value輸出，進(jìn)而Hadoop MapReduce對(duì)所有新Key進(jìn)行排序、洗牌（shuffle）、再送到Reducer處；Reducer的輸入會(huì)是一組有相同Key的Value集合，對(duì)這些Value做聚合計(jì)算，再結(jié)合Key輸出就完成了一輪計(jì)算。
　　每一輪的計(jì)算都是一個(gè)MapReduce任務(wù)，且串行執(zhí)行； 一個(gè)N維的Cube，至少需要N次MapReduce Job。

算法優(yōu)點(diǎn)

• 此算法充分利用了MapReduce的能力，處理了中間復(fù)雜的排序和洗牌工作，故而算法代碼清晰簡單，易于維護(hù)；
• 受益于Hadoop的日趨成熟，此算法對(duì)集群要求低，運(yùn)行穩(wěn)定；在內(nèi)部維護(hù)Kylin的過程中，很少遇到在這幾步出錯(cuò)的情況；即便是在Hadoop集群比較繁忙的時(shí)候，任務(wù)也能完成。

?

算法缺點(diǎn)

• 當(dāng)Cube有比較多維度的時(shí)候，所需要的MapReduce任務(wù)也相應(yīng)增加；由于Hadoop的任務(wù)調(diào)度需要耗費(fèi)額外資源，特別是集群較龐大的時(shí)候，反復(fù)遞交任務(wù)造成的額外開銷會(huì)相當(dāng)可觀；
• 由于Mapper不做預(yù)聚合，此算法會(huì)對(duì)Hadoop MapReduce輸出較多數(shù)據(jù); 雖然已經(jīng)使用了Combiner來減少從Mapper端到Reducer端的數(shù)據(jù)傳輸，所有數(shù)據(jù)依然需要通過Hadoop MapReduce來排序和組合才能被聚合，無形之中增加了集群的壓力;
• 對(duì)HDFS的讀寫操作較多：由于每一層計(jì)算的輸出會(huì)用做下一層計(jì)算的輸入，這些Key-Value需要寫到HDFS上；當(dāng)所有計(jì)算都完成后，Kylin還需要額外的一輪任務(wù)將這些文件轉(zhuǎn)成HBase的HFile格式，以導(dǎo)入到HBase中去；
• 總體而言，該算法的效率較低，尤其是當(dāng)Cube維度數(shù)較大的時(shí)候；時(shí)常有用戶問，是否能改進(jìn)Cube算法，縮短時(shí)間。

2 .2 快速Cube算法(Fast Cubing)

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

　　該算法的主要思想是，對(duì)Mapper所分配的數(shù)據(jù)塊，將它計(jì)算成一個(gè)完整的小Cube 段（包含所有Cuboid）；每個(gè)Mapper將計(jì)算完的Cube段輸出給Reducer做合并，生成大Cube，也就是最終結(jié)果；圖2解釋了此流程。

　　　　　　　　　　　　 快速Cube算法

?

?

與舊算法相比，快速算法主要有兩點(diǎn)不同

• Mapper會(huì)利用內(nèi)存做預(yù)聚合，算出所有組合；Mapper輸出的每個(gè)Key都是不同的，這樣會(huì)減少輸出到Hadoop MapReduce的數(shù)據(jù)量，Combiner也不再需要；
• 一輪MapReduce便會(huì)完成所有層次的計(jì)算，減少Hadoop任務(wù)的調(diào)配。

?

?

?

子立方體生成樹的遍歷
　　值得一提的還有一個(gè)改動(dòng)，就是子立方體生成樹(Cuboid Spanning Tree)的遍歷次序；在舊算法中，Kylin按照層級(jí)，也就是廣度優(yōu)先遍歷(Broad First Search)的次序計(jì)算出各個(gè)Cuboid；在快速Cube算法中，Mapper會(huì)按深度優(yōu)先遍歷（Depth First Search）來計(jì)算各個(gè)Cuboid。深度優(yōu)先遍歷是一個(gè)遞歸方法，將父Cuboid壓棧以計(jì)算子Cuboid，直到?jīng)]有子Cuboid需要計(jì)算時(shí)才出棧并輸出給Hadoop；最多需要暫存N個(gè)Cuboid，N是Cube維度數(shù)。
采用DFS，是為了兼顧C(jī)PU和內(nèi)存：

• 從父Cuboid計(jì)算子Cuboid，避免重復(fù)計(jì)算；
• 只壓棧當(dāng)前計(jì)算的Cuboid的父Cuboid，減少內(nèi)存占用。

　　　　　　　　　　　　　　　　

• • • • • • • • 立方體生成數(shù)的遍歷過程

　　上圖是一個(gè)四維Cube的完整生成樹；按照DFS的次序，在0維Cuboid 輸出前的計(jì)算次序是 ABCD -> BCD -> CD -> D -> ， ABCD, BCD, CD和D需要被暫存；在被輸出后，D可被輸出，內(nèi)存得到釋放；在C被計(jì)算并輸出后，CD就可以被輸出； ABCD最后被輸出。

4.3 、Cube構(gòu)建流程

Cube構(gòu)建流程圖

主要步驟如下：

構(gòu)建一個(gè)中間平表(Hive Table)：將Model中的fact表和look up表構(gòu)建成一個(gè)大的Flat Hive Table。

重新分配Flat Hive Tables。

從事實(shí)表中抽取維度的Distinct值。

對(duì)所有維度表進(jìn)行壓縮編碼，生成維度字典。

計(jì)算和統(tǒng)計(jì)所有的維度組合，并保存，其中，每一種維度組合，稱為一個(gè)Cuboid。

創(chuàng)建HTable。

構(gòu)建最基礎(chǔ)的Cuboid數(shù)據(jù)。

利用算法構(gòu)建N維到0維的Cuboid數(shù)據(jù)。

構(gòu)建Cube。

將Cuboid數(shù)據(jù)轉(zhuǎn)換成HFile。

將HFile直接加載到HBase Table中。

更新Cube信息。

清理Hive。

總結(jié)

以上是生活随笔為你收集整理的Apache Kylin Cube 的构建过程的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。