总目录

Kylin系列（一）—— 入门
Kylin系列（二）—— Cube 构造算法

[TOC]

Kylin cube 构造算法

逐层算法（layer Cubing）

我们知道，一个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的计算也就完成了。

此处输入图片的描述

如上图所示，展示了一个4维的Cube构建过程。

此算法的Mapper和Reducer都比较简单。Mapper以上一层Cuboid的结果（key-value对）作为输入。由于Key是由各维度值拼接在一起，从其中找出要聚合的维度，去掉它的值成新的key，并对value进行操作，然后把新的key和value输出，进而Hadoop MapReduce对所有新的key进行排序、洗牌（shuffle）、再送到Reducer处；Reducer的输入会是一组具有相同key的value集合，对这些value做聚合运算，再结合key输出就完成了一轮计算。

举个例子：
假设一共四个维度A/B/C/D，他们的成员分别是（A1、A2、A3），（B1、B2）、(C1)、（D1），有一个measure（对于这列V，计算sum（V）），这里忽略dictionary编码。原始表如下：

此处输入图片的描述

那么base cuboid最终的输出如下
（A1、B1、C1、D1、2）
（A1、B2、C1、D1， 3）
（A2、B1、C1、D1， 5）
（A3、B1、C1、D1， 6）
（A3、B2、C1、D1， 8）
那么它作为下面一个cuboid的输入，对于第一行输入
（A1、B1、C1、D1，2），mapper执行完成之后会输出
（A1、B1、C1， 2）、
（A1、B1、D1， 2）、
（A1、C1、D1， 2）、
（B1、C1、D1，2）这四项，同样对于其他的内一行也会输出四行，最终他们经过reducer的聚合运算，得到如下的结果：
（A1、B1、C1， 2）
（A1、B1、D1， 2）
（A1、C1、D1， 2 + 3）
（B1、C1、D1，2 + 5 +６）

这个例子其实在cube的构建过程中可以看到。

一定要注意，这里的每一轮计算都是MapReducer任务，且串行执行；一个N维的Cube，至少需要N次MapReduce Job。

算法的优点

• 此算法充分利用了MR的能力，处理了中间复杂的排序和洗牌工作，故而算法代码清晰简单，易于维护。
• 受益于Hadoop的日趋成熟，此算法对集群要求低，运行稳定。

算法的缺点

• 当Cube有比较多维度的时候，所需要的MR任务也相应增加；由于Hadoop的任务调度需要耗费额外资源，特别是集群较庞大的时候，反复递交任务造成的额外开销会很可观
• 由于Mapper不做预聚合，此算法会对Hadoop MR输出较多数据；虽然已经使用了Combiner来减少从Mapper端到Reducer端的数据传输，所有数据依然需要通过MR来排序和组合才能被聚合，无形之中增加了集群的压力。
• 对HDFS的读写操作较多：由于每一层计算的输出会用作下一层计算的输入，这些Key-value需要写到HDFS上；当所有计算都完成后，Kylin还需要额外一轮任务将这些文件转成Hbase的HFile格式，以导入到HBase中去。
• 总体而言，该算法的效率较低，尤其当Cube维度数较大的时候。

这里其实在困惑到底什么是0维，后来想明白了。举个例子，现在有一个度量叫成交量。有几个维度从大到小：业务类型、渠道、门店。3维的例子就是[业务类型、渠道、门店],二维的例子是[业务类型、渠道],一维[业务类型],0维其实就是没有维度，也就是全部聚合，举个例子就是

select sum(price) from table1

其实在我看来，逐层算法就是先算维度数最高的，一层算完后，再算维度数减少的一层，以此类推。至于为什么从层级高向层级低计算，而不是反过来，在于如果是反过来，那你每次的计算量都是初始数据，数据量非常大，没必要。

快速Cube算法（Fast Cubing）

快速Cube算法，它还被称作“逐段”（By Segment）或“逐块”（By Split）算法。

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

快速cube

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

• Mapper会利用内存做预聚合，算出所有组合；Mapper输出的每个Key都是不同的，这样会减少输出到Hadoop MapReduce的数据量，Combiner也不再需要；
• 一轮MapReduce便会完成所有层次的计算，减少Hadoop任务的调配。

来说个比较。逐层算法的每一层的计算都有一个MapReduce任务，因为是从高维到低维的MR任务，任务之间传递的数据量是非常大的。比如上面的例子，生成4维的数据，需要在mapper中对全数据进行的整理，再传递给reducer聚合，如果数据量非常大，那么网络IO是很大的。而快速算法，它会对某个分片数据进行构造完整的cube（所有cuboid）。再将mapper中的数据送入reducer进行大聚合生成Cube。这其实是在map阶段就已经完成了聚合，IO是很小的。

举个例子

这里不理解没关系，看完后面的构建过程再翻回来看例子就能懂

一个Cube有4个维度：A,B,C,D；每个Mapper都有100万个源记录要处理;Mapper中的列基数是Car(A),Car(B),Car(C)和Car(D)。（cardinal 基数）

当讲源记录聚集到base cuboid(1111)时，使用旧的“逐层”算法，每个Mapper将向Hadoop输出1百万条记录；使用快速立方算法，在预聚合之后，它预聚合之后，它只向Hadoop输出[distinct A,B,C,D]记录的数量，这样肯定比源数据小；在正常情况下，他可以源记录大小的1/10到1/100.

当从父cuboid聚合到子cuboid时，从base cuboid(1111) 到3维cuboid 0111,将会聚合维度A；我们假设维度A与其他维度独立的，聚合后，cuboid 0111的维度base cuboid的1/Card(A);所以在这一步的输出将减少到原来的1/Card(A);

总的来说，假设维度的平均基数是Card(N),从Mapper到Reducer的写入记录可以减少到原始维度的1/Card(N);Hadoop的输出越少，I/O和计算越少，性能就越好。

这里要提一句，其实很多都是类似的，比如在hive中处理大表， 各种的调优都和IO、计算有关系，因为他们都是基于MR任务。

子立方体生成树（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维到2维的MR任务中计算CD，BFS会压入ABC ABD ACD BCD，mapper进行切分，reducer进行聚合；而在DFS中，只会压入ABCD,BCD，内存大大减少。

子立方体生成树

上图是一个四维Cube的完整生成树：

按照DFS的次序，在0维Cuboid输出前的计算次序是ABCD-》BCD-》CD-》D-》0维，ABCD,BCD,CD和D需要被暂存；在被输出后，D可被输出，内存得到释放；在C被计算并输出后，CD就可以被输出，ABCD最后被输出。

使用DFS访问顺序，Mapper的输出已完全排序，因为Cuboid ID位于行键的开始位置，而内部的Cuboid的行已排序。

0000 0001[D0] 0001[D1] .... 0010[C0] 0010[C1] .... 0011[C0][D0] 0011[C0][D1] .... .... 1111[A0][B0][C0][D0] .... 这里的写法可以看构造过程。

由于mapper的输出已经排序，Hadoop的排序效率会更高。

此外，mapper的预聚合发生在内存中，这样可以避免不必要的磁盘和网络IO，并减少了hadoop的开销。

在开发阶段，我们在mapper中遇到了OOM错误；这可能发生在：

• Mapper的JVM堆大小很小
• 使用 distinct count度量
• 使用树太深（维度太多）
• 给Mapper的数据太大

我们意识到Kylin不能认为mapper总是有足够的内存；Cubing算法需要自适应各种情况；

当主动检测到OOM错误，会优化内存使用并将数据spilling到磁盘上；结果是有希望的，OOM错误现在很少发生。

优点

• 它比旧的方法更快；从我们的比较测试中可以减少30%到50%的build总时间：快在排序，快在IO。
• 他在Hadoop上产生较少的工作负载，并在HDFS上留下较少的中间文件。
• Cubing和Spark等其他立方体引起可以轻松地重复使用该立方体代码。

缺点

• 该算法有点复杂，这增加了维护工作；

• 虽然该算法可以自动将数据spill到磁盘，但他仍希望Mapper有足够的内存来获得最佳性能。

• 用户需要更多知识来调整立方体。

By-layer Spark Cubing算法

我们知道，RDD（Resilient Distributed DataSet）是Spark中的一个基本概念。N维立方体的组合可以很好地描述为RDD，N维立方体将具有N+1个RDD。这些RDD具有parent/child关系，因为这些parent RDD 可用于生成child RDD。通过将父RDD缓存在内存中，子RDD的生成可以比磁盘读取更有效。

此处输入图片的描述

改进

• 每一层的cuboid视为一个RDD
• 父RDD被尽可能cache到内存
• RDD 被导出为sequence file
• 通过将“map”替换为“flatMap”，以及把“reduce”替换为“reduceByKey”，可以复用大部分代码

Spark中Cubing的过程

下图DAG(有向无环图),它详细说明了这个过程：

在Stage 5中，Kylin使用HiveContext读取中间Hive表，然后执行一个一对一映射的"map"操作将原始值编码为KV字节。完成后Kylin得到一个中间编码的RDD。

在Stage 6中，中间RDD用一个“ReduceByKey”操作聚合以获得RDD-1，这是base cuboid。接下来，在RDD-1做了一个flatMap（一对多map）,因为base cuboid有N个cuboid。以此类推，各级RDD得到计算。在完成时，这些RDD将完整地保存在分布式文件系统，但可以缓存在内存中用于下一级计算。当生成子cuboid时，他将从缓存中删除。

此处输入图片的描述

其实我们和旧的逐层算法去比较会发现，他们之间的构建没有什么大的差别，只不过Spark的是在内存中进行的，无需从磁盘读取和网络IO。并且后面的stage的第一步是reduce。

性能测试

此处输入图片的描述

此处输入图片的描述

在所有这三种情况下，Spark都比MR快，总体而言它可以减少约一半的时间。

Kylin的构建算法以及和spark的改进
http://cxy7.com/articles/2018/06/09/1528549073259.html
https://www.cnblogs.com/zlslch/p/7404465.html