Redis 在 2.8.9 版本添加了 HyperLogLog （HLL）。
HyperLogLog 是一种高效的基数估算工具，通过概率算法和哈希化技术，在常数空间内提供了基数的估算。

eg.

  • 统计一个网站的独立用户数。
  • 统计一个日志中的独立 IP 数量。
  • 计算一个流中的独立事件数。

传统的做法是将所有元素存储在集合中，然后进行去重、计数。但当集合的元素数量非常大时，这种方法会占用大量内存，甚至无法存储所有数据。
HyperLogLog 有一定误差，但对于海量数据来说，它的内存开销极低且精度足够高，非常适合用于大数据处理、流量统计、去重计数等场景。

Redis 中的 HyperLogLog 支持以下操作：

  • PFADD：将元素添加到 HyperLogLog 中，Redis 会对元素进行哈希处理，并更新相应的桶。
  • PFCOUNT：返回一个或多个 HyperLogLog 键的基数估算。
  • PFMERGE：合并多个 HyperLogLog 键的基数估算。

核心思想

HyperLogLog 使用概率算法，通过哈希化数据并记录哈希值的前导零数量来估算基数。

1. 哈希函数与二进制表示

为了将集合中的元素映射为哈希值，HyperLogLog 使用了 哈希函数。假设我们使用一个 m-bit 的哈希函数，它会把输入数据映射到一个包含 m 位二进制数字的哈希值。

例如：

  • 假设我们将一个元素哈希成 10111001101100010101010101101010 这样的 32 位二进制数字。
  • 这个哈希值的前导零数量就是我们关心的指标。对于这个例子，假设前导零的数量为 3。
2. 关键点：记录前导零的数量

HyperLogLog 并不直接存储每个哈希值，而是计算每个哈希值的前导零的数量，把这个值保存在一个桶（通过哈希值的某些位进行映射）中。

3. 桶与桶编号

为了优化空间，HyperLogLog 使用多个桶来存储不同的哈希值。每个桶的索引是由哈希值的某些位生成的。假设我们有一个桶数量为 b 的 HyperLogLog。我们将哈希值的前 log2(b) 位作为桶的索引，其余的位用于计算前导零数量。

  • 例如，如果我们有 16 个桶（b = 16），则桶的索引由哈希值的前 4 位决定（因为 log2(16) = 4）。如果哈希值的前 4 位为 1100，那么该哈希值将被映射到第 12 号桶（因为 1100 二进制对应 12）。
4. 计算基数估算

HyperLogLog 会计算所有桶中记录的前导零最大值的平均值。然后根据这个平均值来估算整个数据集的基数。
其数学公式如下：

[ \text{Estimate} = \alpha \times m^2 \times 2^{\bar{R}} ]

其中：

  • ( \alpha ) 是一个常数，通常为 0.7213 / (1 + 1.079 / m)，用来调整估算的误差。
  • ( m ) 是桶的数量。
  • ( \bar{R} ) 是所有桶中的前导零数量的平均值。
5. 桶的数量和误差

桶的数量 ( m ) 直接影响 HyperLogLog 的估算精度。通常，桶的数量越多精度越高，但内存消耗也会相应增加。Redis 默认使用 14 个字节来存储 HyperLogLog，这大约可以提供 0.81% 的误差。

详细讲解：Redis中的HyperLogLog以及HyperLogLog原理。