BT

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

Apache Kylin的Top-N近似预计算

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

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

大家都听过二八定律,这是在很多领域存在的规律,例如世界上20%的人占有了超过80%的财富;20%最受欢迎的商品,贡献超过了80%的销售额等等。 二八定律背后的规律是Zipf分布法则,它是美国学者G.K.齐普夫在统计英文单词出现频率时发现的规律。简单说就是如果把频率出现最高的单词的频率看作是1的话,第二个出现的频率是二分之一,第三个是三分之一,依此类推,出现的频率是它排名的某次幂分之一。

图1 二八原则和Zipf分布

图1的右图是facebook上统计的NBA各球队受赞次数排名,它也基本符合Zipf分布。

在互联网时代,还有一个知名的理论-长尾效应,举例来说就是某个网站的用户或者商品的数量非常的多,但是大部分都是访问频率(或价值)极低的,这条尾巴可以很长。长尾的存在对大数据分析带来挑战,因为它的基数(cardinality)特别高,如何从中快速找到高价值的商品或者用户,是一个迫切而难度很高的任务。

图2 长尾

现在来看一个典型的Top-N查询示例。该查询是选择在 2015年10月1日,地址在北京,销售商品按价格之和排序(倒序),找前100个。

在Kylin v1.5之前,SQL中的group by列,需声明成维度,所以这个Cube的维度中要有日期,地点和商品名,度量是SUM(PRICE) 。图3展示了一个这样设计Cube。因为商品的基数很大,计算的cuboid的行数会很多;而度量值SUM(PRICE)是非排序的,因此需要将这些纪录都从存储器读到Kylin查询引擎中(内存), 然后再排序找出最高的纪录;这样的解决办法总开销较大

图3 用普通度量处理Top N查询

针对上面的情形,Kylin开发团队决定另辟蹊径来处理这种查询,研究了多种Top-N的解决方法;由于在大数据的背景下,算法要求一定是可并发执行的,计算结果是需要可再次合并的,而计算结果的少量误差是可以接受的; 最终Kylin选择了Space-Saving算法[1],以及它的一个衍生版Parallel Space-Saving[2],并在此之上做了特定的优化。这种算法的优势是使用较少的空间,同时保证较高的精确度。

有了Top-N之后,Cube的设计会比以前简单很多,因为像刚才的商品名会被挪到Measure中去,在Measure里按Sum值做倒序,只保留最大的若干值。

图4 使用Top N度量的Cube

值得一提的是需要用多少空间运算Top-N。简单来说存储空间越多准确率越高。我们通过使用生成一些样本数据然后用Space-Saving计算,并且跟真实结果做比较,发现50倍空间对于普通的数据分布是够用的。也即,用户需要Top 100的结果,Kylin对于每种组合条件值,保留Top 5000的纪录, 并供以后再次合并。这样即使多次合并, Top100依然是比较接近真实结果 。

图5 Top N度量的合并

Top-N的优点:因为它只保留Top的记录,会让Cube空间大幅度减少,而查询性能大大提升。在一个典型的例子里,改用Top-N后,Cube的大小减少了90%,而查询时间则只有以前的10%不到。

缺点是它可能是近似的结果(当50倍空间也无法容纳所有基数的时候)。如果业务场景需要绝对精确的话,它可能不适合。

Top-N误差率由很多因素决定的

  1. 数据的分布:数据分布越陡,误差越小。
  2. 算法使用的空间:如果对精度要求高的话,可以选择用更多的空间换取更精准的准确率 。在实际使用中,可以做一些比较以了解误差情况。

未来Top N的功能将有了进一步提升,例如可以将多个维度放入到Top N度量中,使用非字典编码等,敬请期待。

[1] Ahmed Metwally, et al. “Efficient computation of frequent and top-k elements in data streams”. Proceeding ICDT'05 Proceedings of the 10th international conference on Database Theory, 2005.

[2]Massimo Cafaro, et al. “A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution”. Proceeding arXiv: 1401.0702v12 [cs.DS] 19 Setp 2015.

作者介绍

史少锋,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通知我
社区评论

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

讨论

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


找回密码....

Follow

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

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

Like

内容自由定制

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

Notifications

获取更新

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

BT