Redis HyperLogLog是什么？

发表于 作者 IT之美

Redis HyperLogLog 是一种近似计数算法，用于估计集合中唯一元素的数量，而不必实际存储所有元素。HyperLogLog 数据结构占用空间极小，且误差率有限，适合用于大数据量的基数统计场景。

基本原理：
HyperLogLog 是基于概率论和统计学原理设计的。它依赖于观察随机变量的特征，特别是观察“最长连续0”的个数（max register value）来估计唯一元素的数量。

  1. Hashing: 首先，HyperLogLog 对输入元素使用一个强哈希函数（如 MurmurHash）将其映射到一个固定长度的二进制序列。
  2. Bitmap Registers: Redis HyperLogLog 结构内部维护了一组固定数量（例如 16384）的小型计数器，这些计数器被称为“Bitmap registers”。对于每个输入元素的哈希值，保留最左侧连续的 1 的个数（LSB，Least Significant Bits）作为计数器的值。
  3. Estimation: 统计所有计数器中的最大值（max register value），这个最大值越小，意味着观测到的连续1越多，这表明输入元素的分布更为均匀，据此推算出唯一元素的数量。使用公式 -1.077 * ln(p) 来估计基数，其中 p 是 max register value 所对应的概率（例如，若 max register value 是 6，则 p = 1/64）。

误差分析：
Redis HyperLogLog 设计的目标是在标准误差不超过 0.81% 的情况下，能够统计大约 2^64 个不同的元素。误差来源主要是统计学上的自然偏差，但由于基数估计算法本身的性质，即使在很大的基数范围内，其误差也是有限的。

优化：
Redis 还在其 HyperLogLog 实现中引入了一些优化措施，例如：

  • Merge Operation: 不同的 HyperLogLog 结构可以合并在一起，而不会增加误差，这对于分布式环境中的数据汇聚非常有用。
  • Sparse Representation: 当实际唯一元素数量很少时，HyperLogLog 使用稀疏表示来节省空间，仅存储非零计数器。

通过这种方式，Redis HyperLogLog 结构能够在有限的内存空间内高效地估算出非常大量的唯一元素数量，特别适用于流量统计、网站独立访客统计等场景。