Apache Kylin的Top-N近似预计算

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

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

图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）数据的分布：数据分布越陡，误差越小。

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团队核心成员，负责平台的规划、开发和运营。