手机版
你好,游客 登录 注册
背景:
阅读新闻

Facebook如何在Presto中使用HyperLogLog来加速基数计算

[日期:2018-12-20 23:12:38] 来源:linux公社   作者:linux公社 [字体: ]

昨天,Facebook分享了他们如何在Presto中使用HyperLogLog(HLL)进行计算密集型操作,例如估算大型数据集中的不同值。通过这种实现,他们能够在处理计数不同的问题时实现高达1000倍的速度提升。

什么是HyperLogLog?

HyperLogLog是一种算法,用于估计巨大数据集中唯一值的数量,也称为基数。为了产生基数的估计,它使用m个单位的辅助存储器并对数据执行单次传递。该算法是先前已知的基数估计器LogLog的临时版本。

Facebook在过去一周使用一台机器确定访问Facebook的不同人数的情况下使用HypeLogLog。为了进一步加速这些类型的查询,他们在Presto中实现了HLL,这是一个开源的分布式SQL查询引擎。 Presto旨在针对各种规模的数据源运行交互式分析查询。

使用HLL,可以在12小时内执行相同的计算,内存少于1 MB。 Facebook强调他们已经看到了很大的改进,一些查询在几分钟内运行,包括用于分析数千个A/B测试的查询。

Presto的HLL实施

Presto中HLL数据结构的实现包括两种布局格式:稀疏和密集。为了节省内存,存储以稀疏布局开始,当输入数据结构超出稀疏格式的预定内存限制时,Presto会自动切换到密集布局。稀疏布局用于获得低基数数据集中的精确计数,例如,不同国家/地区的数量。密集布局用于基数高的情况,例如不同用户的数量。

Presto中有一个HYPERLOGLOG数据类型。那些喜欢单一格式以便他们可以在其他平台(如Python)中处理输出结构的用户,还有另一种称为P4HYPERLOGLOG的数据类型,它启动并严格保持密集的HLL。

要详细了解Facebook如何使用HLL,请查看他们的文章。

Linux公社的RSS地址:https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址:https://www.linuxidc.com/Linux/2018-12/155898.htm

linux Mozilla Firefox的近亲 Basilisk,基于XUL的开源浏览器 苹果发布 iOS 12.1.2,eSIM修复

Linux公社的RSS地址http://www.it56.cn/rss.xml

本文永久更新链接地址www.it56.cn/it/6.html

linux