HyperLogLog
提示
来自deepseek解释
原文链接：https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/
HyperLogLog 命令摘要
本组共 5 条命令：
| 命令 | 摘要 | 复杂度 | 起始版本 |
|---|---|---|---|
| PFADD | 向 HyperLogLog 键添加元素。如果键不存在则创建。 | 每个元素添加为 O(1)。 | 2.8.9 |
| PFCOUNT | 返回 HyperLogLog 键观察到的集合的近似基数。 | O(1)，平均常数时间很小... | 2.8.9 |
| PFDEBUG | 用于调试 HyperLogLog 值的内部命令。 | 不适用 | 2.8.9 |
| PFMERGE | 将一个或多个 HyperLogLog 值合并到单个键中。 | 合并 N 个 HyperLogLog 为 O(N)，但常数开销较高... | 2.8.9 |
| PFSELFTEST | 用于测试 HyperLogLog 值的内部命令。 | 不适用 | 2.8.9 |
HyperLogLog 是一种概率数据结构，用于估计集合的基数，以精确性换取高效的空间利用。Redis 实现最多使用 12 KB 内存，并提供 0.81% 的标准误差率。
计数唯一项通常需要与要计数的项数成比例的内存量，因为您需要记住已经见过的元素以避免重复计数。然而，存在一类算法，用内存换取精度：它们返回带有标准误差的估计度量，在 Redis 的 HyperLogLog 实现中，误差小于 1%。该算法的神奇之处在于，您不再需要与计数的项数成比例的内存量，而是可以使用恒定的内存量；最坏情况下为 12 KB，如果您的 HyperLogLog（此后简称 HLL）只见过很少的元素，则使用量会更少。
Redis 中的 HLL 虽然在技术上是不同的数据结构，但被编码为 Redis 字符串，因此您可以调用 GET 序列化 HLL，使用 SET 将其反序列化回服务器。
从概念上讲，HLL 的 API 类似于使用集合（Set）执行相同任务。您会 SADD 每个观察到的元素到集合中，并使用 SCARD 检查集合中的元素数量，由于 SADD 不会重新添加已存在的元素，因此这些元素是唯一的。
虽然您实际上不是将元素 添加 到 HLL 中（因为数据结构只包含不包含实际元素的状态），但 API 是相同的：
- 每次看到新元素时，使用
PFADD将其添加到计数中。 - 当您想要检索使用
PFADD添加的唯一元素的当前近似值时，可以使用PFCOUNT命令。如果需要合并两个不同的 HLL，可以使用PFMERGE命令。由于 HLL 提供唯一元素的近似计数，合并结果将给出两个源 HLL 中唯一元素数量的近似值。
HyperLogLog 操作：使用 PFADD 向 HyperLogLog 添加元素，PFCOUNT 估计基数，PFMERGE 合并多个 HyperLogLog，用于需要节省空间的基数估计
难度： 中级
命令： PFADD, PFCOUNT, PFMERGE
复杂度：
- PFADD: O(1)
- PFCOUNT: O(1)
- PFMERGE: O(N)
Java 示例（同步 - Jedis）：
long res1 = jedis.pfadd("bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar");
System.out.println(res1); // >>> 1
long res2 = jedis.pfcount("bikes");
System.out.println(res2); // >>> 4
long res3 = jedis.pfadd("commuter_bikes", "Salacia", "Mimas", "Quaoar");
System.out.println(res3); // >>> 1
String res4 = jedis.pfmerge("all_bikes", "bikes", "commuter_bikes");
System.out.println(res4); // >>> OK
long res5 = jedis.pfcount("all_bikes");
System.out.println(res5); // >>> 6此数据结构的一些使用场景包括：统计用户每天在搜索表单中执行的唯一查询次数、网页的唯一访问者数量等类似场景。
Redis 还能够执行 HLL 的并集操作，更多信息请查看完整文档。
使用场景
网页匿名唯一访问量（SaaS、分析工具）
此应用回答以下问题：
- 此页面当天有多少唯一访问量？
- 有多少唯一用户播放了这首歌曲？
- 有多少唯一用户观看了此视频？
在某些国家，存储 IP 地址或任何其他个人标识符违反法律，这使得无法获取网站的唯一访客统计数据。
为每个页面（视频/歌曲）按周期创建一个 HyperLogLog，每次访问时将 IP/标识符添加到其中。
性能
对 HyperLogLog 进行写入（PFADD）和读取（PFCOUNT）操作在常数时间和空间内完成。合并 HLL 为 O(n)，其中 n 是草图的数量。
限制
HyperLogLog 可以估计最多 18,446,744,073,709,551,616（2^64）个成员的集合基数。
了解更多
- Redis new data structure: the HyperLogLog 包含了有关该数据结构及其在 Redis 中实现的许多细节。
- Redis HyperLogLog Explained 展示了如何使用 Redis HyperLogLog 数据结构构建流量热图。