HyperLogLog

HyperLogLog 是一种概率型数据结构,用于估计集合的基数。

HyperLogLog 是一种概率型数据结构,用于估计集合的基数。作为一种概率型数据结构,HyperLogLog 以牺牲完美的准确性换取高效的空间利用率。

Redis HyperLogLog 实现最多使用 12 KB 内存,提供 0.81% 的标准误差。

统计唯一项通常需要与要统计的项数成比例的内存量,因为你需要记住过去已经看到的元素,以避免重复计数。然而,存在一系列算法,它们以内存换取精度:这些算法返回带有标准误差的估计值,对于 Redis 的 HyperLogLog 实现,标准误差小于 1%。这种算法的奇妙之处在于,你不再需要使用与统计的项数成比例的内存量,而是可以使用恒定的内存量;最坏情况下为 12k 字节,如果你的 HyperLogLog(我们以后简称 HLL)看到的元素很少,则使用的内存会少很多。

Redis 中的 HLL,虽然技术上是一种不同的数据结构,但被编码为 Redis 字符串,因此你可以调用 GET 来序列化 HLL,并调用 SET 将其反序列化回服务器。

从概念上讲,HLL 的 API 类似于使用集合来完成相同的任务。你会将每个观察到的元素 SADD 到一个集合中,并使用 SCARD 来检查集合中的元素数量,这些元素是唯一的,因为 SADD 不会重新添加已存在的元素。

虽然你并没有真正地将项添加到 HLL 中,因为该数据结构只包含一个不包含实际元素的状态,但 API 是相同的

  • 每次看到新元素时,使用 PFADD 将其添加到计数中。
  • 当你想获取使用 PFADD 命令添加的唯一元素的当前近似值时,可以使用 PFCOUNT 命令。如果你需要合并两个不同的 HLL,可以使用 PFMERGE 命令。由于 HLL 提供唯一元素的近似计数,合并的结果将为你提供两个源 HLL 中唯一元素总数的近似值。

这种数据结构的一些用例示例包括统计用户每天在搜索表单中执行的唯一查询数、网页的唯一访问者数以及其他类似情况。

Redis 也能够对 HLL 执行并集操作,更多信息请查阅完整文档

用例

网页的匿名独立访问量(SaaS,分析工具)

此应用可以回答这些问题

  • 此页面今天有多少独立访问量?
  • 有多少独立用户播放过这首歌?
  • 有多少独立用户观看过此视频?
注意
在某些国家/地区,存储 IP 地址或任何其他类型的个人标识符是违法的,这使得无法获取网站的唯一访问者统计信息。

每个页面(视频/歌曲)在每个时间段创建一个 HyperLogLog,每次访问时将每个 IP/标识符添加到其中。

基本命令

  • PFADD 将项添加到 HyperLogLog 中。
  • PFCOUNT 返回集合中项数的估计值。
  • PFMERGE 将两个或多个 HyperLogLog 合并为一个。

查看HyperLogLog 命令完整列表

性能

对 HyperLogLog 的写入 (PFADD) 和读取 (PFCOUNT) 操作在恒定的时间和空间内完成。合并 HLL 的时间复杂度为 O(n),其中 n 是草图(sketches)的数量。

限制

HyperLogLog 可以估计最多包含 18,446,744,073,709,551,616 (2^64) 个成员的集合的基数。

了解更多

评价此页面
返回顶部 ↑