赞
踩
切块(Dice):选择维中特定区间的数据或者某批特定值进行分析,比如选择2010年第一季度到2010年第二季度的销售数据,或者是电子产品和日用品的销售数据。
旋转(Pivot):即维的位置的互换,就像是二维表的行列转换,如图中通过旋转实现产品维和地域维的互换。
Kylin的Cube算法
以下内容为全文引用,有兴趣的同学可以去参考连接查看原文。
Layer Cubing算法
==============
也可称为“逐层算法”,通过启动N+1轮MapReduce计算。第一轮读取原始数据(RawData),去掉不相关的列,只保留相关的。同时对维度列进行压缩编码,第一轮的结果,我们称为Base Cuboid,此后的每一轮MapReuce,输入是上一轮的输出,以重用之前的计算结果,去掉要聚合的维度,计算出新的Cuboid,以此向上,直到最后算出所有的Cuboid。
如上图所示,展示了一个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,也就是最终结果;下图解释了此流程
与旧算法的不同之处
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。