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

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

[日期:2018-12-18] 来源: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
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款