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誤差率由很多因素決定的：

未來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團隊核心成員，負責平臺的規劃、開發和運營。