BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

Apache Kylin的快速数据立方体算法——概述

| 作者 史少锋 关注 2 他的粉丝 发布于 2015年9月10日. 估计阅读时间: 14 分钟 | GMTC大前端的下一站,PWA、Web框架、Node等最新最热的大前端话题邀你一起共同探讨。

Apache Kylin(麒麟)是由eBay贡献给开源社区的大数据分析引擎,支持在超大数据集上进行秒级别的SQL及OLAP查询,目前是Apache基金会的孵化项目[1]。本文是一系列介绍快速数据立方体计算(Fast Cubing)的第一篇,将从概念上介绍新算法与旧算法的区别以及分析它的优劣。该算法目前正在内部进行测试和改进,将在Apache Kylin 后续版本中发布。源代码已经公开在Kylin的Git代码库中[2],感兴趣的读者可以到相应分支查看。

背景:Kylin使用Hadoop结合数据立方体(Cube)技术实现多维度快速OLAP分析能力的。关于数据立方体概念,请参考[3]。

逐层算法

在介绍快速Cube算法之前,我们先简单回顾一下现有的算法,也称之为“逐层算法”(By Layer Cubing)。

我们知道,一个N维的完全Cube,是由:1个N维子立方体(Cuboid), N个(N-1)维Cuboid, N*(N-1)/2个(N-2)维Cuboid …, N个1维Cuboid, 1个0维Cuboid,总共2^N个子立方体组成的;在“逐层算法”中,按维度数逐渐减少来计算,每个层级的计算(除了第一层,它是从原始数据聚合而来),是基于它上一层级的结果来计算的。

举例子来说,[Group by A, B]的结果,可以基于[Group by A, B, C]的结果,通过去掉C后聚合得来的;这样可以减少重复计算;当 0维度Cuboid计算出来的时候,整个Cube的计算也就完成了。

图1展示了用该算法计算一个四维Cube的流程。

图1 逐层算法

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

快速Cube算法

快速Cube算法(Fast Cubing)是麒麟团队对新算法的一个统称,它还被称作“逐段”(By Segment) 或“逐块”(By Split) 算法。

该算法的主要思想是,对Mapper所分配的数据块,将它计算成一个完整的小Cube 段(包含所有Cuboid);每个Mapper将计算完的Cube段输出给Reducer做合并,生成大Cube,也就是最终结果;图2解释了此流程。

图2逐块Cube算法

Mapper的预聚合

与旧算法相比,快速算法主要有两点不同:

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

我们看一个例子:某个Cube有四个维度:A、B、C、D;每个Mapper分配到的数据块有约一百万条记录;在这一百万条记录中,每个维度的基数(Cardinality)分别是Card(A), Card(B), Card(C), Card(D)。

当从原始数据计算四维Cuboid(ID: 1111)的时候:旧算法的Mapper会简单地对每条记录去除不相关的维度,然后输出到Hadoop,所以输出量依然是一百万条;新算法的Mapper,由于做了聚合,它只输出[count distinct A, B, C, D]条记录到Hadoop,此数目肯定小于原始条数;在很多时候下,它会是原来的1/10甚至1/1000。

当从四维Cuboid 1111计算三维Cuboid如0111的时候,维度A会被聚合掉;假定A维度的值均匀分布,那么聚合后的记录数会是四维Cuboid记录数的1/ Card(A),;而旧算法的Mapper输出数跟四维Cuboid记录数相同。

可以看到,在Cuboid的推算过程中的每一步,新算法都会比旧算法产生更少数据;总的加起来,新算法中的Mapper对Hadoop的输出,会比老算法少一个或几个数量级,具体数字取决于用户数据的特性;越少的数据,意味着越少的I/O和CPU,从而使得性能得以提升。

子立方体生成树的遍历

值得一提的还有一个改动,就是子立方体生成树(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子立方体生成树的遍历

图3是一个四维Cube的完整生成树;按照DFS的次序,在0维Cuboid 输出前的计算次序是 ABCD -> BCD -> CD -> D -> *, ABCD, BCD, CD和D需要被暂存;在*被输出后,D可被输出,内存得到释放;在C被计算并输出后,CD就可以被输出; ABCD最后被输出。

采用DFS,Mapper的输出会是排序的(某些特殊情况除外):Cube行键(row key)是由[Cuboid ID + 维度值]组成;DFS访问的结果,恰好是按照Cuboid ID从小到大输出;而在同一个Cuboid内,维度值也是升序排序;所以总的输出是排序的,请看如下示例。

0000 
0001[D0] 
0001[D1] 
.... 
0010[C0] 
0010[C1] 
.... 
0011[C0][D0] 
0011[C0][D1] 
.... 
.... 
1111[A0][B0][C0][D0] 
....

注: 这里[D0]代表D维度的最小值,[D1]代表次小值,以此类推。

由于每个Mapper的输出都是排序的,Hadoop对这些输出进行归并排序的效率也会更高。

OutOfMemory error

在新算法的开发和测试初期,我们发现Mapper常常会遇到OutOfMemory而异常终止;总结下来,以下情况往往会导致该异常:

a) Hadoop Mapper所分配的堆内存较小;­­­­­­­

b) Cube中使用了"Distinct count" (HyperLogLog会占用较大内存);

c) Cube的维度较多,导致生成树较深;

d) 分配到Mapper的数据块过大;

简单的增大Mapper的JVM heap size可以暂时解决该问题;但是不是每个用户的Hadoop机器都有大内存;算法需要足够的健壮性和适应性,否则用户会很头疼;我们花了不少努力来优化该算法,例如主动探测OOM的发生,将堆栈中的Cuboid缓存到本地磁盘等;这一系列优化在eBay内部测试的结果非常好,OOM的发生率大大降低,而性能没有明显的下降。

下面我们对快速Cube算法做一个总结。

算法优点

  • 比老算法性能更好;下图是一个新老算法在两个案例上的所耗时间对比(分钟),能减少约30%到50%;

  • Mapper内的Cube计算逻辑可以被其它Cube引擎重用,例如流数据(Streaming)和Spark; 实际上Kylin已经在这么做了。

算法缺点

  • 新算法略复杂,学习曲线更陡;
  • 虽然新算法会在内存不足时会把数据暂存到本地磁盘,要获取最佳性能,最好给Mapper以足够内存,用户要在输入数据块大小、Mapper配置、Cube复杂度之间找到平衡,需具备更多知识和经验。

快速算法的其它改进

本文概述了快速Cube算法的主要思想;其实Kylin在引入此算法的同时,还引入了其它一些改进,例如基于采样的Region切分,一步直接生成HFile,基于HBase表的Cube合并等;这些改变都影响了Cube的构建,是Kylin管理员所需要了解的,我们将在后续文章中做详细阐述,敬请关注。

如果你对Apache Kylin项目感兴趣,欢迎访问项目主页:

http://kylin.incubator.apache.org

或订阅邮件列表:

user@kylin.incubator.apache.orgdev@kylin.incubator.apache.org

或订阅微信公众号:ApacheKylin

项目地址:http://kylin.io

参考

[1] Apache Kylin 主页: https://kylin.incubator.apache.org/

[2] Apache Kylin Git镜像: https://github.com/apache/incubator-kylin

[3] Data Cubes: http://www2.cs.uregina.ca/~dbd/cs831/notes/dcubes/dcubes.html

作者简介

史少锋,Apache Kylin PMC 成员,核心开发人员之一,eBay高级软件工程师,2014年加入eBay Kylin 团队并转向大数据分析领域,参与了Kylin一系列优化和新功能的开发,并致力为Kylin社区用户提供支持和帮助。史少峰硕士毕业于上海交通大学计算机系,在IBM从事多年软件全球化和云计算等方面的设计和开发。

 

感谢郭蕾对本文的策划,丁晓昀对本文的审校。

给InfoQ中文站投稿或者参与内容翻译工作,请邮件至editors@cn.infoq.com。也欢迎大家通过新浪微博(@InfoQ@丁晓昀),微信(微信号:InfoQChina)关注我们,并与我们的编辑和其他读者朋友交流(欢迎加入InfoQ读者交流群InfoQ好读者)。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

不错 by yu xiaodong

持续关注中

写的很好,不过,有几个问题想请教一下: by 陶 fr

1.老算法(逐层)中一个N维的Cube,至少需要N次MapReduce Job? 不应该是2的N次方次吗?
2.新算法(逐块)如何做到在MAPPER阶段预聚合?“新算法的Mapper,由于做了聚合,它只输出[count distinct A, B, C, D]条记录到Hadoop”,是仅[count distinct A, B, C, D]条
还是[count distinct A, B, C, D]+[count distinct A, B, C]+[count distinct A, B, D]+[count distinct A, C, D]+。。。条?MAPPER阶段是输出每个MAPPER数据块对应各个Cuboid的数据还是每个Cuboid都对应一个MAPPER(或者说建CUBE的过程是一趟MR还是2的N次方趟MR)?

Re: 写的很好,不过,有几个问题想请教一下: by 徐 海滨

同问

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

3 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT