HyperLogLog基数统计的原理与在大数据中的应用
请解释HyperLogLog(HLL)算法如何用极少量内存统计海量数据的基数(UV/独立访客数)？包括分桶(Bucket)方法、调和平均(Harmonic Mean)修正、以及Redis和Flink中HyperLogLog的具体实现和误差控制。
回答
孤独的心
HyperLogLog原理：
-
核心思想：利用哈希后二进制串中末尾连续0的个数来估计不重复元素数
- 哈希值后出现k个连续0的概率为1/2^k
- 记录每个元素哈希后的最大前导零数ρ_max
- 基数估计 ≈ 2^ρ_max
-
分桶(Bucket)优化：
- 取哈希值前m位作为桶编号（m=14，则2^14=16384个桶）
- 每个桶独立记录该桶内的最大前导零数
- 各桶估计值做调和平均（而非算术平均）减少异常值影响
-
计算公式：
E = α_m * m² * (Σ 2^(-M[j]))⁻¹其中α_m为偏差修正系数，M[j]是第j个桶中的最大前导零数
-
误差：标准误差 ≈ 1.04/√m
- m=16384时，误差≈0.81%
- 内存占用：每个桶6bit → 16384×6bit ≈ 12KB
-
大数据应用：
| 组件 | 实现 | 场景 |
|---|---|---|
| Redis | PFADD/PFCOUNT | 实时UV统计 |
| Flink | HyperLogLogFunction | 实时去重计数 |
| Presto | approx_distinct() | SQL近似去重 |
| ClickHouse | uniqCombined() | 近似基数统计 |
| Druid | HyperLogLog Aggregator | 近似去重 |
- 局限性：
- 无法准确统计极小基数（<1000）
- 无法删除元素（不支持减操作）