Apache Kylin的快速數據立方體算法 - 概述
Apache Kylin（麒麟）是由eBay貢獻給開源社區的大數據分析引擎，支持在超大數據集上進行秒級別的SQL及OLAP查詢，目前是Apache基金會的孵化 項目[1]。本文是一系列介紹快速數據立方體計算（Fast Cubing）的第一篇，將從概念上介紹新算法與舊算法的區別以及分析它的優劣。該算法目前正在內部進行測試和改進，將在Apache Kylin 后續版本中發布。源代碼已經公開在Kylin的Git代碼庫中[2]，感興趣的讀者可以克隆并切換到0.8分支查看。
背景：Kylin使用Hadoop結合數據立方體（Cube）技術實現多維度快速OLAP分析能力的。關于數據立方體概念，請參考[3]。
逐層算法
在介紹快速Cube算法之前，我們先簡單回顧一下現有的算法，也稱之為“逐層算法”（By Layer Cubing）。
我們知道，一個N維的完全Cube，是由：1個N維子立方體（Cuboid）， N個（N-1）維Cuboid, N*(N-1)/2個(N-2)維Cuboid …, N個1維Cuboid, 1個0維Cuboid，總共2^N個子立方體組成的；在“逐層算法”中，按維度數逐漸減少來計算，每個層級的計算（除了第一層，它是從原始數據聚合而 來），是基于它上一層級的結果來計算的。
舉例子來說，[Group by A, B]的結果，可以基于[Group by A, B, C]的結果，通過去掉C后聚合得來的；這樣可以減少重復計算；當 0維度Cuboid計算出來的時候，整個Cube的計算也就完成了。
圖1展示了用該算法計算一個四維Cube的流程。
圖1 逐層算法
此算法的Mapper和Reducer都比較簡單。Mapper以上一層Cuboid的結果（Key-Value對）作為輸入。由于Key是由各 維度值拼接在一起，從其中找出要聚合的維度，去掉它的值成新的Key，然后把新Key和Value輸出，進而Hadoop MapReduce對所有新Key進行排序、洗牌（shuffle）、再送到Reducer處；Reducer的輸入會是一組有相同Key的Value集 合，對這些Value做聚合計算，再結合Key輸出就完成了一輪計算。
每一輪的計算都是一個MapReduce任務，且串行執行； 一個N維的Cube，至少需要N次MapReduce Job。
算法優點
- 此算法充分利用了MapReduce的能力，處理了中間復雜的排序和洗牌工作，故而算法代碼清晰簡單，易于維護；
- 受益于Hadoop的日趨成熟，此算法對集群要求低，運行穩定；在內部維護Kylin的過程中，很少遇到在這幾步出錯的情況；即便是在Hadoop集群比較繁忙的時候，任務也能完成。
算法缺點
- 當Cube有比較多維度的時候，所需要的MapReduce任務也相應增加；由于Hadoop的任務調度需要耗費額外資源，特別是集群較龐大的時候，反復遞交任務造成的額外開銷會相當可觀；
- 由于Mapper不做預聚合，此算法會對Hadoop MapReduce輸出較多數據; 雖然已經使用了Combiner來減少從Mapper端到Reducer端的數據傳輸，所有數據依然需要通過Hadoop MapReduce來排序和組合才能被聚合，無形之中增加了集群的壓力;
- 對HDFS的讀寫操作較多：由于每一層計算的輸出會用做下一層計算的輸入，這些Key-Value需要寫到HDFS上；當所有計算都完成后，Kylin還需要額外的一輪任務將這些文件轉成HBase的HFile格式，以導入到HBase中去；
- 總體而言，該算法的效率較低，尤其是當Cube維度數較大的時候；時常有用戶問，是否能改進Cube算法，縮短時間。
快速Cube算法
快速Cube算法（Fast Cubing）是麒麟團隊對新算法的一個統稱，它還被稱作“逐段”(By Segment) 或“逐塊”(By Split) 算法。
該算法的主要思想是，對Mapper所分配的數據塊，將它計算成一個完整的小Cube 段（包含所有Cuboid）；每個Mapper將計算完的Cube段輸出給Reducer做合并，生成大Cube，也就是最終結果；圖2解釋了此流程。
圖2逐塊Cube算法
Mapper 的預聚合
與舊算法相比，快速算法主要有兩點不同：
- Mapper會利用內存做預聚合，算出所有組合；Mapper輸出的每個Key都是不同的，這樣會減少輸出到Hadoop MapReduce的數據量，Combiner也不再需要；
- 一輪MapReduce便會完成所有層次的計算，減少Hadoop任務的調配。
我們看一個例子：某個Cube有四個維度：A、B、C、D；每個Mapper分配到的數據塊有約一百萬條記錄；在這一百萬條記錄中，每個維度的基數(Cardinality)分別是Card(A), Card(B), Card(C), Card(D)。
當從原始數據計算四維Cuboid（ID： 1111）的時候：舊算法的Mapper會簡單地對每條記錄去除不相關的維度，然后輸出到Hadoop，所以輸出量依然是一百萬條；新算法的 Mapper，由于做了聚合，它只輸出[count distinct A, B, C, D]條記錄到Hadoop，此數目肯定小于原始條數；在很多時候下，它會是原來的1/10甚至1/1000。
當從四維Cuboid 1111計算三維Cuboid如0111的時候，維度A會被聚合掉；假定A維度的值均勻分布，那么聚合后的記錄數會是四維Cuboid記錄數的1/ Card(A),；而舊算法的Mapper輸出數跟四維Cuboid記錄數相同。
可以看到，在Cuboid的推算過程中的每一步，新算法都會比舊算法產生更少數據；總的加起來，新算法中的Mapper對Hadoop的輸出，會比老算法少一個或幾個數量級，具體數字取決于用戶數據的特性；越少的數據，意味著越少的I/O和CPU，從而使得性能得以提升。
子立方體生成樹的遍歷
值得一提的還有一個改動，就是子立方體生成樹(Cuboid Spanning Tree)的遍歷次序；在舊算法中，Kylin按照層級，也就是廣度優先遍歷(Broad First Search)的次序計算出各個Cuboid；在快速Cube算法中，Mapper會按深度優先遍歷（Depth First Search）來計算各個Cuboid。深度優先遍歷是一個遞歸方法，將父Cuboid壓棧以計算子Cuboid，直到沒有子Cuboid需要計算時才出 棧并輸出給Hadoop；最多需要暫存N個Cuboid，N是Cube維度數。
采用DFS，是為了兼顧CPU和內存：
- 從父Cuboid計算子Cuboid，避免重復計算；
- 只壓棧當前計算的Cuboid的父Cuboid，減少內存占用。
圖3子立方體生成樹的遍歷
圖3是一個四維Cube的完整生成樹；按照DFS的次序，在0維Cuboid 輸出前的計算次序是 ABCD -> BCD -> CD -> D -> *， ABCD, BCD, CD和D需要被暫存；在*被輸出后，D可被輸出，內存得到釋放；在C被計算并輸出后，CD就可以被輸出； ABCD最后被輸出。
采用DFS，Mapper的輸出會是排序的（某些特殊情況除外）：Cube行鍵(row key)是由[Cuboid ID + 維度值]組成；DFS訪問的結果，恰好是按照Cuboid ID從小到大輸出；而在同一個Cuboid內，維度值也是升序排序；所以總的輸出是排序的，請看如下示例。
0000 0001[D0] 0001[D1] .... 0010[C0] 0010[C1] .... 0011[C0][D0] 0011[C0][D1] .... .... 1111[A0][B0][C0][D0] ....
注: 這里[D0]代表D維度的最小值，[D1]代表次小值，以此類推。
由于每個Mapper的輸出都是排序的，Hadoop對這些輸出進行歸并排序的效率也會更高。
OutOfMemory error
在新算法的開發和測試初期，我們發現Mapper常常會遇到OutOfMemory而異常終止；總結下來，以下情況往往會導致該異常:
a) Hadoop Mapper所分配的堆內存較小;-------
b) Cube中使用了"Distinct count" (HyperLogLog會占用較大內存);
c) Cube的維度較多，導致生成樹較深；
d) 分配到Mapper的數據塊過大；
簡單的增大Mapper的JVM heap size可以暫時解決該問題；但是不是每個用戶的Hadoop機器都有大內存；算法需要足夠的健壯性和適應性，否則用戶會很頭疼；我們花了不少努力來優化 該算法，例如主動探測OOM的發生，將堆棧中的Cuboid緩存到本地磁盤等；這一系列優化在eBay內部測試的結果非常好，OOM的發生率大大降低，而 性能沒有明顯的下降。
下面我們對快速Cube算法做一個總結。
算法優點
-
比老算法性能更好；下圖是一個新老算法在兩個案例上的所耗時間對比（分鐘），能減少約30%到50%；
- Mapper內的Cube計算邏輯可以被其它Cube引擎重用，例如流數據(Streaming)和Spark; 實際上Kylin已經在這么做了。
算法缺點
- 新算法略復雜，學習曲線更陡；
- 雖然新算法會在內存不足時會把數據暫存到本地磁盤，要獲取最佳性能，最好給Mapper以足夠內存，用戶要在輸入數據塊大小、Mapper配置、Cube復雜度之間找到平衡，需具備更多知識和經驗。
快速算法的其它改進
本文概述了快速Cube算法的主要思想；其實Kylin在引入此算法的同時，還引入了其它一些改進，例如基于采樣的Region切分，一步直接生 成HFile，基于HBase表的Cube合并等；這些改變都影響了Cube的構建，是Kylin管理員所需要了解的，我們將在后續文章中做詳細闡述，敬 請關注。
如果你對Apache Kylin項目感興趣，歡迎訪問項目主頁：
http://kylin.incubator.apache.org
或訂閱郵件列表：
user@kylin.incubator.apache.org 和 dev@kylin.incubator.apache.org
或訂閱微信公眾號: ApacheKylin
項目地址： http://kylin.io
參考
[1] Apache Kylin 主頁: https://kylin.incubator.apache.org/
[2] Apache Kylin Git鏡像: https://github.com/apache/incubator-kylin
[3] Data Cubes： http://www2.cs.uregina.ca/~dbd/cs831/notes/dcubes/dcubes.html
作者簡介
史少鋒 ，Apache Kylin PMC 成員，核心開發人員之一，eBay高級軟件工程師，2014年加入eBay Kylin 團隊并轉向大數據分析領域，參與了Kylin一系列優化和新功能的開發，并致力為Kylin社區用戶提供支持和幫助。史少峰碩士畢業于上海交通大學計算機 系，在IBM從事多年軟件全球化和云計算等方面的設計和開發。