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 CLI

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

Java

package io.redis.examples;

import org.junit.Assert;
import org.junit.Test;
import redis.clients.jedis.UnifiedJedis;

public class HyperLogLogExample {

    public void run() {
        UnifiedJedis jedis = new UnifiedJedis("redis://localhost:6379");


        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
    }
}

Python

import redis

r = redis.Redis(decode_responses=True)


res1 = r.pfadd("bikes", "Hyperion", "Deimos", "Phoebe", "Quaoar")
print(res1)  # >>> 1

res2 = r.pfcount("bikes")
print(res2)  # >>> 4

res3 = r.pfadd("commuter_bikes", "Salacia", "Mimas", "Quaoar")
print(res3)  # >>> 1

res4 = r.pfmerge("all_bikes", "bikes", "commuter_bikes")
print(res4)  # >>> True

res5 = r.pfcount("all_bikes")
print(res5)  # >>> 6

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

Redis 还可以执行 HLL 的并集，请查看完整文档以获取更多信息。

用例

网页的匿名唯一访问（SaaS、分析工具）

此应用程序回答以下问题

此页面在这一天有多少唯一访问？
有多少独立用户播放了这首歌？
有多少独立用户观看了此视频？

注意

在某些国家，存储 IP 地址或任何其他类型的个人标识符都是违法的，这使得无法在您的网站上获取唯一访客统计信息。

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

基本命令

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

请参阅HyperLogLog 命令的完整列表。

性能

向 HyperLogLog 写入（PFADD）和从中读取（PFCOUNT）以恒定的时间和空间完成。合并 HLL 为 O(n)，其中n 是草图的数量。

限制

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

了解更多

Redis 新数据结构：HyperLogLog 详细介绍了数据结构及其在 Redis 中的实现。
Redis HyperLogLog 解释向您展示如何使用 Redis HyperLogLog 数据结构构建流量热图。

HyperLogLog

用例

基本命令

性能

限制

了解更多

本页内容