写点什么

雅虎开源可以提升流操作速度的 DataSketches

  • 2016-01-24
  • 本文字数:1609 字

    阅读完需:约 5 分钟

就像在 Venture Beat 上所宣布的那样,雅虎开源了 DataSketches ,这是一个用 Java 编写的随机流算法库。DataSketches 允许进行通常来说开销很大的操作,像计算变量不同的值在流中出现的次数,而且消耗的时间少,占用的内存小,误差可预测。

正如他们在技术博客上所作的说明,雅虎内部已经使用DataSketches 来提升多个产品的性能,包括 Flurry 。_ Sketch _ 是 DataSketches 的一个基本概念,这是一个流的“汇总(summary)”,其中每次更新都按同样方式处理,而不考虑历史更新。这个概念是 DataSketches 性能的核心,因为传统的流处理需要保存一个随着时间增长的历史。例如,如果要计算每个唯一值出现的次数,就需要保存每个新出现的唯一值,这样,对于后来的唯一值,检查时间将会增加;因此,每次更新都会以一种不同的、开销更大的方式处理。另一方面,sketch 的构造方式使它只能保存固定数量的、需要保存的信息,也就是说,所有的更新都以完全相同的方式执行。

如果仔细研究下 DataSketches 背后的科学原理,那么我们就会发现,它以整合了 KMV 和自适应采样算法的 Theta-Sketch 框架为基础。感兴趣的读者可以读下这篇论文,它提供了该框架的形式化描述和特性说明,但在这里,我们将提供一种简化的、更为直观的描述。

就让我们将这个问题置于实时计算一个网站的独立访客的场景下。计算一个流中不同的变量值出现的次数,主要的问题是需要为每个已知的、不同的变量值存储一个副本。除此之外,变量的每个新实例(例如,每次新访问网站)都需要对照已知的、不同的变量值所组成的列表进行检查,看看这是一个新访客,还是一个已有的访客。这就是说,假如独立访客的数量为 N,则系统需要的内存为 O(N),每次网站访问需要花费长为 O(log N)的时间来检查是否是一个独立访客。

KMV(第 k 个最小值)算法的策略是以存储更少的值(k 个值)为基础,从中可以估计出 N 的大小,而且误差范围固定。要存储的值使用哈希函数计算得出,该函数将要测量的变量(在这个例子中是指对页面的独立访问)映射成 0 到 1 之间的一个值;实际上,这个哈希函数是什么并不重要,只要结果可以均匀地分布在 0 到 1 之间就可以。每次测量变量的一个新实例,我们就计算它的哈希值,并查看我们是否已经存储了该哈希值,如果没有,就存储它。实际上,主要的不同点是,在任何时刻,只有 k 个最小的值会被保存:如果有一个新值加入到组中,那么第 k+1 个值会被移除,保证内存占用一直为 O(k),时间成本一直为 O(log k)。这样,不同值出现的次数就可以估计为(k-1)/KMV,其中,KMV 为第 k 个最小值,或者是组中存储的、幸存下来的、最大的哈希值。

从检查结果表达式很容易推断出,如果我们比较两个流的数据,一个流中出现不同值的次数多于另一个,那么出现更多不同值的流会产生更多的哈希值,因此,存储的第 k 个哈希值将会比另一个流的第 k 个哈希值小。在 k 相同的情况下,第 k 个哈希值越小,上述表达式计算得出的值越大。由此可以得出结论,该表达式至少是与出现不同值的实际数量成正比的。

多篇研究论文已经证明了,上文从形式上阐述的表达式是一个很好的估计,不过,一个简单的试验就可以提供描述性的证据。假设一个数据流出现199 个不同的值,而且我们在算法中让k=20。如果一个哈希函数将结果均衡分布在0 到1 之间,那出现的199 个不同的值大体上将映射为0.005、0.01、0.015 等等,直到0.995。如果我们只保存20 个最小的值,那么第20 个值将是0.1,将这个值带入上述表达式,结果是(20-1)/0.1=190。

除了性能外,DataSketches 还有其他特性,例如,它能够组合已经分别计算好的sketch,并得到一个综合结果,而不需要要检查底层数据。这使用户可以计算单个组的数据或者数据分区,然后根据需要组合它们。 Maven Central 中提供了 DataSketches 库,以及用于 Hadoop Pig、Hadoop Hive 和 Druid 的适配器。

查看英文原文: Yahoo Open-Sources DataSketches for Faster Operations Over Streams

2016-01-24 18:004168
用户头像

发布了 1008 篇内容, 共 389.5 次阅读, 收获喜欢 344 次。

关注

评论

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

Mac虚拟机VMware Fusion Pro 13永久密钥 VM虚拟机 mac版下载安装教程

Rose

VMware Fusion Pro 13 Mac虚拟机 VM虚拟机密钥

中英人寿呈现“ACE 中英事业家”优增品牌,谱写事业与生活共益共生绚丽华章

新消费日报

Supersonic 推出游戏创意生成器,AI 助力激发开发者创作灵感

Geek_2d6073

Perfectly Clear Workbench(图片编辑软件) v4.6.1.2678永久激活版

Rose

如何手搓一个自定义的RPC(远程过程调用框架)

京东科技开发者

设备指纹市场分析及未来展望

芯盾时代

终端安全 移动安全 风控系统

人工智能与聊天机器人:革新互动体验的新纪元

天津汇柏科技有限公司

聊天机器人 人工智能】

洞察消费者需求,实时监控商品信息是关键 —— 淘宝API的力量

技术冰糖葫芦

API Explorer API 编排 api 货币化 API 文档

能源公司 Turcomp 通过 NocoBase 实现敏捷、安全开发

NocoBase

开源 低代码 无代码开发 低代码开发

记一次大库大表的治理过程

京东科技开发者

鞋服品牌飞跃新纪元 智能商品管理软件五大颠覆性优势

第七在线

一文了解大模型会话QA增强

神州数码

性能测试概念

测吧(北京)科技有限公司

测试

4K Video Downloader Plus Pro for Mac(4K视频下载器)v1.8.0激活版

理理

MATLAB R2023a中文版安装教程 MATLAB许可证密钥分享 Mac/win

Rose

数学软件 MATLAB R2023b破解版 MATLAB 密钥 MATLAB 安装教程

【最新LR2023安装包】lightroom classic 2023-一键安装-永久使用-中文简体

Rose

Glyphs 3 for Mac字体设计编辑工具下载安装

Rose

Mac 软件 字体设计 Glyphs 3 mac

Serato DJ Pro mac(专业DJ软件) v3.0.3中文激活版

Rose

减少停机时间的最简单方法 — 避免单点故障

通明湖

瑞能半导体携多元成果打造全新“品牌基石” 驭领可持续篇章 为功率器件注入强劲动力

新消费日报

性能测试概念

测试人

软件测试

生而非凡:皮阿诺哈曼系列不锈钢橱柜打造致净厨房空间

新消费日报

性能测试概念

霍格沃兹测试开发学社

文献解读-液体活检-第二十期|《连续循环肿瘤DNA检测可预测肝癌患者早期复发:一项前瞻性研究》

INSVAST

基因数据分析 生信服务 液体活检

《软件设计哲学》:新“代码整洁之道”

京东科技开发者

DataBuilder2.3.2重磅发布,核心功能全面升级,引领数据治理新高度!

数造万象

数据治理 数据资产 数据开发 DataOps 版本升级

macOS 14 Sonoma系统下载安装 苹果最新14系统离线安装包

Rose

竖版H5摸鱼挂机游戏来啦!新版雷霆传奇详细图文架设教程

echeverra

雷霆传奇

户外LED显示屏具备哪些性能?

Dylan

广告 LED显示屏 全彩LED显示屏 户外LED显示屏 led显示屏厂家

项目管理新利器!Project Office Pro助您精准规划,高效执行,项目成功不是梦

Rose

mesa LLVMpipe ORCJIT 上游化:一场历时两年的后端合并马拉松,幕后英雄竟是TA!

nn-30

Linux 开源 操作系统 risc-v 桌面

雅虎开源可以提升流操作速度的DataSketches_Java_Abraham Marín Pérez_InfoQ精选文章