AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

雅虎开源可以提升流操作速度的 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:004551
用户头像

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

关注

评论

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

云+AI时代下,Alibaba Cloud Linux 如何进一步演进?

OpenAnolis小助手

开源 AI 操作系统 Alibaba Cloud Linux 阿里云服务器操作系统

除了deadline,我们还能用什么驱动开发?

思码逸研发效能

程序员 DevOps 软件开发 编码 IT 运维

《Programming from the Ground Up》阅读笔记:p217-p238

codists

汇编 编程人

阿里云服务器操作系统 Alibaba Cloud Linux 全新升级,核心场景性能提升超 20%

OpenAnolis小助手

开源 龙蜥社区 Alibaba Cloud Linux

CAS存在的问题及在Java中的解决方式

不在线第一只蜗牛

Java Python

AI时代,2024火山引擎飞连新品发布会盛大开启

新消费日报

联手豆包大模型,容联七陌打造更懂客户的智能客服

新消费日报

2024年第3届海南跨博会及低空经济产业博览会

秋硕展览

浅谈kafka

京东科技开发者

SIGGRAPH Asia 2024 | 网易伏羲研究成果入选,3D面部动画技术再获新突破

网易伏羲

论文 网易伏羲

高性能网络SIG月度动态:推动 SMC 用户态工具支持细粒度透明替换和共享内存占用监控

OpenAnolis小助手

操作系统 smc 龙蜥社区SIG 龙蜥SIG月报 龙蜥高性能网络SIG

大模型在商业领域的应用:如何提升决策效率与用户体验

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

测试

智能合约与大语言模型的结合:未来的应用场景探索

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

测试

【论文速读】|用于安全代码评估的大语言模型:一项多语言实证研究

云起无垠

OASA 年中研讨会成功举办,新增 8 家厂商加入联盟,推进 3 个合作方向

OpenAnolis小助手

安全 操作系统 龙蜥社区 龙蜥社区安全联盟 OASA

深度学习在视觉识别中的突破:从理论到实践

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

测试

知识图谱融入向量数据库,带来RAG效果飞升

Zilliz

知识图谱 向量数据库 LLMs rag

制造已然走出国门,数据如何走向全球?

奇点云

人工智能 AI 互联网 软件 制造业

安全基础设施如何形成统一生态标准?OASA 硬件安全合作计划启动 | 2024 龙蜥大会

OpenAnolis小助手

安全 操作系统 龙蜥社区 龙蜥操作系统大会 龙蜥社区安全联盟

全局视角看技术-Java多线程演进史

京东科技开发者

谈JVM xmx, xms等内存相关参数合理性设置

京东科技开发者

Rust 与生成式 AI:从语言选择到开发工具的演进

亚马逊云科技 (Amazon Web Services)

机器学习 深度学习 rust 生成式人工智能

高性能存储 SIG 月度动态:优化 fuse 提升 AI 存储接入能力,erofs 工具发布新版本

OpenAnolis小助手

开源 操作系统 龙蜥社区 龙蜥社区SIG

实现MySQL异地多活场景

NineData

数据一致性 数据同步 异地多活 NineData 单元节点

SD-WAN帮助跨国企业实现网络加速

Ogcloud

网络加速 SD-WAN SD-WAN组网 SDWAN SD-WAN国际专线

如何在实际开发中深入使用 yalantinglibs 编译期反射库

OpenAnolis小助手

c++ 编译期 yaLanTingLibs

【免费可视化仪表盘】轻松实现静态/动态数据可视化图表—积木仪表盘

JEECG低代码

数据分析 数据可视化 BI 报表 数据仪表盘

TikTok养号推荐:海外独享原生IP

Ogcloud

TikTok tiktok运营 海外原生IP TikTok养号 tiktok矩阵

2025包装展-2025年广州国际包装供应链博览会

秋硕展览

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