OLAP引擎Kylin——Cube构建算法

  |   0 评论   |   2,792 浏览

Layer Cubing算法

也可称为“逐层算法”,通过启动N+1轮MapReduce计算。第一轮读取原始数据(RawData),去掉不相关的列,只保留相关的。同时对维度列进行压缩编码,第一轮的结果,我们称为Base Cuboid,此后的每一轮MapReuce,输入是上一轮的输出,以重用之前的计算结果,去掉要聚合的维度,计算出新的Cuboid,以此向上,直到最后算出所有的Cuboid。

by-layer-cubing.png

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

此算法的Mapper和Reducer都比较简单。Mapper以上一层Cuboid的结果(Key-Value对)作为输入。由于Key是由各维度值拼接在一起,从其中找出要聚合的维度,去掉它的值成新的Key,并对Value进行操作,然后把新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算法,缩短时间。

Fast(in-mem) Cubing算法

也被称作“逐段”(By Segment) 或“逐块”(By Split) 算法

从1.5.x开始引入该算法,利用Mapper端计算先完成大部分聚合,再将聚合后的结果交给Reducer,从而降低对网络瓶颈的压力。

主要思想

对Mapper所分配的数据块,将它计算成一个完整的小Cube 段(包含所有Cuboid);

每个Mapper将计算完的Cube段输出给Reducer做合并,生成大Cube,也就是最终结果;下图解释了此流程

by-segment-cubing.png

与旧算法的不同之处

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

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

举一个例子

一个cube有4个维度:A,B,C,D;每个Mapper都有100万个源记录要处理;Mapper中的列基数是Car(A),Car(B),Car(C)和Car(D); 

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

当从父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和计算越少,性能就越好。

子立方体生成树(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,减少内存占用。

cube-spanning-tree.png

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

按照DFS的次序,在0维Cuboid 输出前的计算次序是 ABCD -> BCD -> CD -> D -> , 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的预聚合发生在内存中,这样可以避免不必要的磁盘和网络I / O,并且减少了Hadoop的开销;

在开发阶段,我们在mapper中遇到了OutOfMemory错误;这可能发生在:

  • Mapper的JVM堆大小很小;

  • 使用“dictinct count”度量(HyperLogLog占用空间)

  • 生成树太深(维度太多);

  • 给Mapper的数据太大

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

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

优缺点

优点

它比旧的方法更快;从我们的比较测试中可以减少30%到50%的build总时间;

它在Hadoop上产生较少的工作负载,并在HDFS上留下较少的中间文件;

Cubing和Spark等其他立方体引擎可以轻松地重复使用该立方体代码;

缺点

该算法有点复杂;这增加了维护工作;

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

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

By-layer Spark Cubing算法

我们知道,RDD(弹性分布式数据集)是Spark中的一个基本概念。 N维立方体的集合可以很好地描述为RDD,N维立方体将具有N + 1个RDD。这些RDD具有parent/child关系,因为parent RDD可用于生成child RDD。通过将父RDD缓存在内存中,子RDD的生成可以比从磁盘读取更有效。下图描述了这个过程

spark-cubing-layer.png

改进

  • 每一层的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-dag.png

性能测试

image.png

spark-mr-performance.png

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

不同Cubing算法的对比

image.png

读后有收获可以支付宝请作者喝咖啡