Apache Kylin的Top-N近似预计算

在大数据处理场景,由于数据量巨大,某些功能严格准确实现可能会耗费可观的资源,甚至无法计算。这种情况需要牺牲一定的准确性来换取的灵活性和性能。在最近项目中需要定时计算Top N,并提供数天内的Top N,经过考虑后,计划每次计算出Top N * M,然后合并出Top N,当然M越大,最终的结果越准确。但是还是希望找到业界处理类似问题的方案,最终找到了下面这篇文章。

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

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

二八定律&facebook上统计的NBA各球队受赞次数排名,也基本符合Zipf分布

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

长尾

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

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

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

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

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

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

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

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.

Ref