文档：HyperLogLog

HyperLogLog 是一种概率数据结构，用于估计集合的基数。作为一种概率数据结构，HyperLogLog 以牺牲完美精度为代价，换取高效的空间利用率。

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

统计唯一项通常需要与您想要统计的项数成比例的内存量，因为您需要记住过去已经见过的元素，以避免多次计数。然而，存在一组算法以牺牲内存为代价换取精度：它们返回一个带有标准误差的估计值，在 Valkey 的 HyperLogLog 实现中，这个误差小于 1%。这种算法的奇妙之处在于，您不再需要使用与计数项数成比例的内存量，而是可以使用恒定内存量；在最坏情况下为 12k 字节，如果您的 HyperLogLog（从现在起我们称之为 HLL）只见过很少的元素，则会少得多。

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

从概念上讲，HLL API 类似于使用集合（Sets）来完成相同的任务。您会使用 SADD 将每个观察到的元素添加到集合中，并使用 SCARD 检查集合中的元素数量，这些元素是唯一的，因为 SADD 不会重复添加现有元素。

尽管您实际上并没有向 HLL 中“添加项”，因为该数据结构只包含一个不包括实际元素的状态，但 API 是相同的。

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

127.0.0.1:6379> PFADD bikes Hyperion Deimos Phoebe Quaoar
(integer) 1
127.0.0.1:6379> PFCOUNT bikes
(integer) 4
127.0.0.1:6379> PFADD commuter_bikes Salacia Mimas Quaoar
(integer) 1
127.0.0.1:6379> PFMERGE all_bikes bikes commuter_bikes
OK
127.0.0.1:6379> PFCOUNT all_bikes
(integer) 6

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

Valkey 还能够执行 HLL 的合并操作，请查看完整文档以获取更多信息。

用例

网页的匿名独立访问（SaaS，分析工具）

此应用程序回答以下问题：

• 此页面当天有多少次独立访问？
• 有多少独立用户播放过这首歌？
• 有多少独立用户观看过这个视频？

注意： 在某些国家/地区，存储 IP 地址或任何其他类型的个人标识符是违法的，这使得无法获取您网站的独立访客统计信息。

每个页面（视频/歌曲）在每个时期都会创建一个 HyperLogLog，并且每次访问时都会将每个 IP/标识符添加到其中。

基本命令

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

查看HyperLogLog 命令的完整列表。

性能

对 HyperLogLog 进行写入 (PFADD) 和读取 (PFCOUNT) 操作的时间和空间复杂度都是常数。合并 HLL 是 O(n)，其中 n 是 sketch 的数量。

限制

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

了解更多

• 这篇关于HyperLogLog 数据结构的博客文章详细介绍了该数据结构及其在 Valkey 中的实现。