1.4 核心算法

简单介绍下 Cube 构建引擎在构建 Cube 时用到的算法.

预计算过程是 Kylin 从 Hive 中读取原始数据，按照我们选定的维度进行计算，并将结果集保存到 Hbase 中，默认的计算引擎为 MapReduce，可以选择 Spark 作为计算引擎。

一次 build 的结果，我们称为一个 Segment。构建过程中会涉及多个 Cuboid 的创建，具体创建过程算法由kylin.cube.algorithm参数决定，参数值可选 auto，layer 和 inmem， 默认值为 auto，即 Kylin 会通过采集数据动态地选择一个算法 (layer or inmem)，如果用户很了解 Kylin 和自身的数据、集群，可以直接设置喜欢的算法。

1. 逐层构建算法（layer）

我们知道，一个 N 维的 Cube，是由 1 个 N 维子立方体、N 个 (N-1) 维子立方体、N*(N-1)/2个(N-2)维子立方体、......、N个1维子立方体和1个0维子立方体构成，总共有2^N个子立方体组成，

在逐层算法中，按维度数逐层减少来计算，每个层级的计算（除了第一层，它是从原始数据聚合而来），是基于它上一层级的结果来计算的。比如，[Group by A, B]的结果，可以基于[Group by A, B, C]的结果，通过去掉C后聚合得来的；这样可以减少重复计算；当 0 维度Cuboid计算出来的时候，整个Cube的计算也就完成了。

每一轮的计算都是一个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 中去；

2. 快速构建算法（inmem）

也被称作“逐段”(By Segment) 或“逐块”(By Split) 算法，从1.5.x开始引入该算法

利用Mapper端计算先完成大部分聚合，再将聚合后的结果交给Reducer，从而降低对网络瓶颈的压力。

该算法的主要思想是，对Mapper所分配的数据块，将它计算成一个完整的小Cube 段（包含所有 Cuboid ）；每个 Mapper将 计算完的 Cube 段输出给 Reducer 做合并，生成大 Cube，也就是最终结果；如图所示解释了此流程。

与旧算法相比，快速算法主要有两点不同：

• Mapper 会利用内存做预聚合，算出所有组合；Mapper 输出的每个 Key 都是不同的，这样会减少输出到 Hadoop MapReduce 的数据量，Combiner 也不再需要；

• 一轮 MapReduce 便会完成所有层次的计算，减少 Hadoop 任务的调配。