Kylin的两种核心算法与cube构建优化

kylin是即席查询很典型的工具，通过预计算构建cube，可以达到毫秒级查询体验，十分快！同时支持REST接口，通过该接口进行应用访问查询。kylin的元数据以及缓存都存储在hbase中。

一、核心算法

1. 逐层构建算法（layer）
   
   该算法构建cube的思想就是逐层，从高维度到低维度，按维度数逐层减少来计算，每个层级的计算（除了第一层，它是从原始数据聚合而来），是基于它上一层级的结果来计算的。比如，[Group by A, B]的结果，可以基于[Group by A, B, C]的结果，通过去掉 C 后聚合得来的；这样可以减少重复计算；当0 维度 Cuboid 计算出来的时候，整个 Cube 的计算也就完成了。
   每一轮的计算都是一个 MapReduce 任务，且串行执行；一个 N 维的 Cube，至少需要N+1 次MapReduce Job。

该算法的效率较低，尤其是当 Cube 维度数较大的时候

2. 快速构建算法（inmem）
   利用Mapper 端计算先完成大部分聚合，再将聚合后的结果交给 Reducer，从而降低对网络瓶颈的压力。该算法的主要思想是，对 Mapper 所分配的数据块，将它计算成一个完整的小 Cube 段（包含所有 Cuboid，即所有维度）；每个 Mapper 将计算完的 Cube 段输出给 Reducer 做合并，生成大 Cube，也就是最终结果
   

Mapper 会利用内存做预聚合，一轮 MapReduce 便会完成所有层次的计算，减少 Hadoop 任务的调配

二、cube构建优化

假设用户有 20 个维度，那么 Cube中总共会存在 2 20 =1048576 个 Cuboid。虽然每个 Cuboid 的大小存在很大的差异，但是 Cuboid 的数量对构建引擎、存储引擎来说压力巨大。因此，在构建维度数量较多的 Cube 时，尤其要注意 Cube 的剪枝优化（即减少 Cuboid的生成）

膨胀率（Expansion Rate）：当前 Cube 的大小除以源数据大小的比例，一般来说，Cube 的膨胀率应该在 0%~1000%之间，Cube 中的维度数量较多，Cube 中存在较高基数的维度都会引起高膨胀率。

1. 强制维度
如果一个维度被定义为强制维度，那么这个分组产生的所有 Cuboid 中每一个 Cuboid 都会包含该维度。每个分组中都可以有 0 个、1 个或多个强制维度。如果根据这个分组的业务逻辑，则相关的查询一定会在过滤条件或分组条件中，因此可以在该分组中把该维度设置为强制维度，这样可以过滤掉不含强制维度的cubeid。

2. 层级维度
每个层级包含两个或更多个维度。假设一个层级中包含 D1，D2…Dn 这 n 个维度，那么在该分组产生的任何 Cuboid 中， 这 n 个维度只会以（），（D1），（D1，D2）…（D1，D2…Dn）这 n+1 种形式中的一种出现。每个分组中可以有 0 个、1 个或多个层级，不同的层级之间不应当有共享的维度。如果根据这个分组的业务逻辑，则多个维度直接存在层级关系，因此可以在该分组中把这些维度设置为层级维度.比如年-月-日，年月日分别为三个维度，其为层级维度，月和日不可能单独出现，一定是年或者年月或者年月日，这样过滤掉月和日单独出现的cubeid，减少cubeid数量。

3. 联合维度
每个联合中包含两个或更多个维度，如果某些列形成一个联合，那么在该分组产生的任何 Cuboid 中，这些联合维度要么一起出现，要么都不出现。每个分组中可以有 0 个或多个联合，但是不同的联合之间不应当有共享的维度（否则它们可以合并成一个联合）。如果根据这个分组的业务逻辑，多个维度在查询中总是同时出现，则可以在该分组中把这些维度设置为联合维度。

4. 并发粒度优化

某一个 Cuboid 的大小超出一定的阈值时，系统会将该 Cuboid 的数据分片到多个分区中，以实现 Cuboid 数据读取的并行化，从而优化 Cube 的查询速度。

kylin.hbase.region.cut 的默认值是 5.0，单位是 GB，也就是说对于一个大小估计是 50GB 的 Segment，构建引擎会给它分配 10 个分区。