您的位置:首页>综合 >

通讯!大数据Kylin(六):Kylin构建Cube算法

2023-03-13 21:09:20    来源:腾讯云

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)

关键词:

相关阅读