BT

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

Apache Kylin v1.5版本中的快速数据立方算法揭秘

| 作者 史少锋 关注 2 他的粉丝 发布于 2016年8月8日. 估计阅读时间: 9 分钟 | QCon上海2018 关注大数据平台技术选型、搭建、系统迁移和优化的经验。

Apache Kylin是一个开源的分布式分析引擎,提供Hadoop之上的SQL查询接口及多维分析(OLAP)能力以支持超大规模数据。它能在亚秒内查询巨大的Hive表。本文将详细介绍Apache Kylin 1.5中的Fast-Cubing算法。

Fast Cubing,也称快速数据立方算法, 是一个新的Cube算法。我们知道,Cube的思想是用空间换时间, 通过预先的计算,把索引及结果存储起来,以换取查询时候的高性能 。在Kylin v1.5以前,Kylin中的Cube只有一种算法:layered cubing,也称逐层算法:它是逐层由底向上,把所有组合算完的过程。

图1 逐层的Cube计算

图1是一个四维Cube,有维度A、B、C、D;它会需要五轮的Map-Reduce来完成:第一轮MR的输入是源数据, 这一步会对维度列的值进行编码,并计算ABCD组合的结果。接下来的MR以上一轮的输出为输入,向上聚合计算三个维度的组合: ABC, BCD, ABD, 和ACD;依此类推,直到算出所有的维度组合。

这个算法的优势是每一轮MR以上一轮的输出为结果,这样可以减少重复结算;当计算到后半程的时候,随着数据的减小,计算会越来越快 。

逐层Cube算法的主要优点是简单:Cube聚合的过程就是把要聚合掉的维度从key中减掉组成新的key交给Map-Reduce,由Map-Reduce框架对新key做排序和再聚合,计算结果写到HDFS。这个算法很好地利用了Map-Reduce框架。得益于Hadoop/Map-Reduce的成熟,此算法的稳定性已经非常高。

经过不断的实践,开发团队也发现了此算法的局限:我们知道,当数据量大的时候,Hadoop主要利用外存(也就是磁盘)做排序,数据在Mapper和Reducer之间还需要洗牌(shuffle)。在计算Cube的时候,集群的IO使用率往往很高; 在运行一些大的任务时,瓶颈会出现在网络传输和磁盘读写上,而CPU和内存的使用率比较低。

此外, 因为需要递交N+1次Map-Reduce任务;每次递交任务,都需要检查集群是否有可用的节点能否满足资源要求,如果没有还需等待其它任务释放资源;反复的任务递交,给Hadoop集群带来额外的调度开销。特别是当集群比较繁忙的时候,等待的时间常常会非常可观,这些都导致 了Cube构建的时间比较长 。

带着这个问题开发团队做了不断分析和尝试,结合了若干研究者的论文,于是有了开发新算法的设想。新算法的核心思想是清晰简单的,就是最大化利用Mapper端的CPU和内存,对分配的数据块,将需要的组合全都做计算后再输出给Reducer; 由Reducer再做一次合并(merge),从而计算出完整数据的所有组合。如此,经过一轮Map-Reduce就完成了以前需要N轮的Cube计算。图2是此算法的概览。

图2 Fast Cubing

在Mapper内部, 也可以有一些优化,图3是一个典型的四维Cube的生成树;第一步会计算Base Cuboid(所有维度都有的组合),再基于它计算减少一个维度的组合。基于parent节点计算child节点,可以重用之前的计算结果;当计算child节点时,需要parent节点的值尽可能留在内存中; 如果child节点还有child,那么递归向下,所以它是一个深度优先遍历。当有一个节点没有child,或者它的所有child都已经计算完,这时候它就可以被输出,占用的内存就可以释放。

图3 Mapper端的Cube生成树遍历

如果内存够的话,可以多线程并行向下聚合。如此可以最大限度地把计算发生在Mapper这一端,一方面减少shuffle的数据量,另一方面减少Reducer端的计算量。

Fast Cubing的优点

  • 总的IO量比以前大大减少。

  • 此算法可以脱离Map-Reduce而对数据做Cube计算,故可以很容易地在其它场景或框架下执行,例如Streaming 和Spark。

Fast Cubing的缺点

  • 代码比以前复杂了很多: 由于要做多层的聚合,并且引入多线程机制,同时还要估算JVM可用内存,当内存不足时需要将数据暂存到磁盘,所有这些都增加复杂度。

  • 对Hadoop资源要求较高,用户应尽可能在Mapper上多分配内存;如果内存很小,该算法需要频繁借助磁盘,性能优势就会较弱。在极端情况下(如数据量很大同时维度很多),任务可能会由于超时等原因失败;

要让Fast-Cubing算法获得更高的效率,用户需要了解更多一些“内情”。

首先,在v1.5里,Kylin在对Fast-Cubing请求资源时候,默认是为Mapper任务请求3Gb的内存,给JVM2.7Gb。如果Hadoop节点可用内存较多的话,用户可以让Kylin获得更多内存:在conf/kylin_job_conf_inmem.xml文件,由参数“mapreduce.map.memory.mb”和“mapreduce.map.java.opts”设定 。

其次,需要在并发性和Mapper端聚合之间找到一个平衡。在v1.5.2里,Kylin默认是给每个Mapper分配32兆的数据;这样可以获得较高的并发性。但如果Hadoop集群规模较小,或可用资源较少,过多的Mapper会造成任务排队。这时,将数据块切得更大,如 64兆,效果会更好。数据块是由Kylin创建Hive平表时生成的, 在kylin_hive_conf.xml由参数dfs.block.size决定的。从v1.5.3开始,分配策略又有改进,给每个mapper会分配一样的行数,从而避免数据块不均匀时的木桶效应:由conf/kylin.properteis里的“kylin.job.mapreduce.mapper.input.rows”配置,默认是100万,用户可以示自己集群的规模设置更小值获得更高并发,或更大值减少请求的Mapper数。

通常推荐Fast-Cubing 算法,但不是所有情况下都如此。

举例说明,如果每个Mapper之间的key交叉重合度较低,fast cubing更适合;因为Mapper端将这块数据最终要计算的结果都达到了,Reducer只需少量的聚合。另一个极端是,每个Mapper计算出的key跟其它 Mapper算出的key深度重合,这意味着在reducer端仍需将各个Mapper的数据抓取来再次聚合计算;如果key的数量巨大,该过程IO开销依然显著。对于这种情况,Layered-Cubing更适合。

用户该如何选择算法呢? 无需担心,Kylin会自动选择合适的算法。

Kylin在计算Cube之前对数据进行采样,在“fact distinct”步,利用HyperLogLog模拟去重,估算每种组合有多少不同的key,从而计算出每个Mapper输出的数据大小,以及所有Mapper之间数据的重合率,据此来决定采用哪种算法更优。在对上百个Cube任务的时间做统计分析后,Kylin选择了8做为默认的算法选择阀值(参数kylin.cube.algorithm.auto.threshold):如果各个Mapper的小Cube的行数之和,大于reduce后的Cube行数的8倍,采用Layered Cubing, 反之采用Fast Cubing。如果用户在使用过程中,更倾向于使用Fast Cubing,可以适当调大此参数值,反之调小。

作者介绍

史少锋,Kyligence技术合伙人兼资深架构师,Apache Kylin核心开发者和项目管理委员会成员(PMC),专注于大数据分析和云计算技术。曾任eBay全球分析基础架构部大数据高级工程师,IBM云计算部门软件架构师;曾是IBM公有云Bluemix DevOps团队核心成员,负责平台的规划、开发和运营。


感谢杜小芳对本文的审校。

给InfoQ中文站投稿或者参与内容翻译工作,请邮件至editors@cn.infoq.com。也欢迎大家通过新浪微博(@InfoQ@丁晓昀),微信(微信号:InfoQChina)关注我们。

评价本文

专业度
风格

您好,朋友!

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

获得来自InfoQ的更多体验。

告诉我们您的想法

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

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

图片无法显示 by tang xi

貌似图片都无法显示了。

允许的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通知我

1 讨论

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


找回密码....

Follow

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

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

Like

内容自由定制

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

Notifications

获取更新

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

BT