写点什么

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:004142

评论

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

NLP专栏简介:数据增强、智能标注、意图识别算法|多分类算法、文本信息抽取、多模态信息抽取、可解释性分析、性能调优、模型压缩算法等

汀丶人工智能

人工智能 自然语言处理 深度学习 关系抽取 命名实体识别

浪潮inBuilder低代码平台分布式微服务架构事务一致性技术解析

inBuilder低代码平台

分布式事务 低代码

Django笔记三之使用model对数据库进行增删改查

Hunter熊

Python django model 增删改查

失真的概念和定义

timerring

信息论 信息论与编码

关于 IDP 的五大认知误解

SEAL安全

IdP 平台工程

​ 如何处理Xcode上传IPA文件后无法在后台架构版本中显示的问题?

雪奈椰子

上传了ipa但在苹果App Store中没有看到构建版本的问题

王者荣耀商城异地多活架构设计

白杨

intellijidea卸载重装无法打开怎么办?IntelliJ IDEA彻底卸载教程

Rose

IntelliJ IDEA 2023下载 IntelliJ IDEA 2023破解 IntelliJ IDEA 2023最新 IntelliJ IDEA卸载

智慧公共厕所,重构城市公共服务的新模式@光明源智慧公厕

光明源智慧厕所

智慧城市

智慧污水处理厂Web3D管理系统 把“污水洗白”

2D3D前端可视化开发

智慧水务 智慧污水厂 智慧污水处理 污水厂三维可视化 数字孪生污水厂

如何清理优化你的Mac?MacCleaner Pro系统综合清理释放磁盘空间!

Rose

磁盘清理 mac系统清理优化软件 MacCleaner Pro下载 如何清理苹果电脑

TypeScript常用代码块

青柚1943

Vue3常用代码块

青柚1943

折叠屏时代的全新故事,由华为领启

脑极体

华为

PreSonus Studio One 6 Pro最新版v6.1.1中文下载 (音乐创作编辑软件)

Rose

Studio One6 Studio One 许可证 Studio One 破解 音乐制作软件

macOS 网站下载和离线浏览工具:SiteSucker Pro中文版

Rose

苹果软件资源站 SiteSucker Pro中文 整站下载工具 SiteSucker Pro Mac版

Web & WebDav Server在Mac上创建Web服务器

Rose

Web 服务器 mac软件下载 Web & WebDav Server破解

“ONE”有引力,4月21日见!

博睿数据

智能运维 博睿数据 发布会 Bonree ONE

Drone CI 部署

流火

OpenTiny 的这些特色组件,很实用,但你应该没见过

Kagol

开源 前端 Vue3 组件库

架构实战营模块 5 作业

白杨

LG电视如何投屏?Mirror for LG TV智能投屏工具轻松解决

Rose

mac软件下载 LG电视 投屏软件 Mirror for LG TV

封仲淹:OceanBase开源技术生态全景解析

OceanBase 数据库

数据库 oceanbase

IBM Semeru Runtime 17.0.6.0 在 Linux 下的安装

HoneyMoose

AI日课@20230407:别为下一代过虑;现在多多体验产品

无人之路

ChatGPT

【论文解读】不和谐区域定位

合合技术团队

人工智能 图像识别 图像处理

在生产环境中运行 grpc 服务所面临的挑战

蓬蒿

golang gRPC

用户需求挖掘与分析,某新零售快消品电商系统成功交付的秘诀

L3C老司机

产品 产品设计 需求分析 产品管理 用户画像

阿里云可观测 2023 年 3 月产品动态

阿里巴巴云原生

阿里云 云原生 可观测

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