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)