写点什么

Apache Kylin 的 Top-N 近似预计算

  • 2016-08-07
  • 本文字数:1887 字

    阅读完需:约 6 分钟

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 )关注我们。

2016-08-07 19:004157

评论

发布
暂无评论
发现更多内容

程序人生 | 编程的上帝视角应该怎么去找

小明Java问道之路

程序人生 编程思维 如何学习 9月月更 计算机思维

《游戏机图鉴》:发展、继承、崩溃、复兴,游戏机的前世今生

图灵社区

科普 游戏机

中小企业集成AI人工智能的窘境

felix

人工智能 中小企业 开放应用模型

SpringCloud 配置中心(Nacos)的简单使用

nacos SpringCloud 配置中心 9月月更

设计模式的艺术 第十二章装饰设计模式练习(开发一个数据加密模块,可以对字符串进行加密。最简单的加密算法通过对字母移位来实现,同时提供了稍复杂的逆向输出加密和更高级的求模加密。用户先用最简单的算法加密,如果觉得不够,可以使用其他算法进行二次加密和三次加密)

代廉洁

设计模式的艺术

费时3个月啃烂了这份Redis技术笔记,我成功上岸进了字节

收到请回复

redis 架构 语言 & 开发 Java core redis 底层原理

一名中年码农转型成远程工作及远程全栈教学创业者的故事

pincman

node.js typescript react.js 远程工作 nestjs

Java进阶(三)Java安全通信:HTTPS与SSL应用配置

No Silver Bullet

https SSL证书 9月月更

阿里顶配版 Spring 全家桶高级笔记+300道硬核面试题,跪着啃完了

钟奕礼

Java 编程 程序员 架构 java面试

数据治理的内核:元数据管理

小鲸数据

数据治理 数字化 元数据 元数据管理 元数据管理平台

分布式技术难学?谷歌大神首发纯手撸ZK+Dubbo笔记,网友看完直呼NB

收到请回复

Java zookeeper 架构 分布式 语言 & 开发

发布仅1小时Github破万赞!这份LeetCode算法刷题手册真是离谱

了不起的程序猿

Java 程序员 LeetCode 数据结构算法

设计模式的艺术 第十一章组合设计模式练习(开发一个界面控件库。界面控件分为两大类:一类是单元控件,例如按钮、文本框等;另一类是容器控件,例如窗体、中间面板等。试用组合模式设计该界面控件库)

代廉洁

设计模式的艺术

秋招国内大厂最牛的Java面试八股文合集(全彩版),不接受反驳

退休的汤姆

Java 程序员 面经 Java工程师 秋招

线上问题如何复盘

老张

线上故障 问题复盘

重学网络系列之(我的名字叫IP)

自然

网络 9月月更

腾讯T4整合Spring+Spring MVC+MyBatis+Redis实现

退休的汤姆

Java 程序员 面经 Java工程师 秋招

DPDK技术学习路线总结,虚拟化专家之路

C++后台开发

后台开发 DPDK VPP OvS DPDK开发

首次发布!Java面试八股文让569人成功进入大厂,堪称2022最强面试八股文核心知识版!

退休的汤姆

Java 程序员 面经 秋招 Java八股文

数据存储与物联网

CnosDB

IoT 时序数据库 开源社区 CnosDB infra

分享一套自己制作的Nestjs实战教程

pincman

node.js typescript nestjs

远程TS全栈学习+远程全职工作+远程高质量外包=3R教室

pincman

node.js typescript react.js 远程工作 nestjs

什么是 SAP Business Function

汪子熙

SAP abap Netweaver 业务流程驱动 9月月更

Java工程师丨面试必会进程线程问答

陈橘又青

Java 面试 9月月更

软件复杂性的来源与应对

源字节1号

软件开发 前端开发 后端开发 小程序开发

C++后台开发学习路线(已多人拿下腾讯后台开发)

C++后台开发

后台开发 后端开发 C++后台开发 C++开发 腾讯后台开发

设计模式的艺术 第十三章外观设计模式练习(为新开发的智能手机控制与管理软件提供一键备份功能。通过该功能可以将原本存储在手机中的通讯录、短信、照片、歌曲等资料一次性地全部复制到移动存储介质(如MMC卡或SD卡)中。实现过程中需要与多个已有的类进行交互)

代廉洁

设计模式的艺术

易观千帆 | 2022年7月宁波市手机银行应用活跃人数榜单

易观分析

手机银行 宁波

[教你做小游戏] 只用几行原生JS,写一个函数,播放音效、播放BGM、切换BGM

HullQin

CSS JavaScript html 前端 9月月更

上车上车,快速搞懂Redis 过期策略和内存淘汰策略

知识浅谈

redis 过期策略 9月月更

云原生(三十四) | Kubernetes篇之平台存储系统实战

Lansonli

云原生 9月月更

Apache Kylin的Top-N近似预计算_开源_史少锋_InfoQ精选文章