HyperLogLog：用 12KB 近似统计海量去重数

HyperLogLog 用极小的固定内存（Redis 实现仅 12KB）估算数据集中不同元素的数量（基数），误差约 0.81%。Redis PFCOUNT 的底层实现。

目录

要解决的问题

统计一个数据流中不同元素的数量（基数），典型场景：

• UV（独立访客数）统计
• Redis PFCOUNT 底层实现
• 数据库 COUNT(DISTINCT col) 近似优化

精确计数需要 O(n) 内存（用 HashSet 存所有元素）；HyperLogLog 只需 O(1) 固定内存（Redis 实现固定 12KB），误差约 0.81%。

核心原理

直觉：最长前导零估算基数

把哈希值看成一串抛硬币结果（0=正面，1=反面）。若观测到一串哈希中，某元素的哈希高位出现了 k 个前导零，这件事发生的概率是 1/2^k。逆向推理：如果见到了前导零数为 k 的哈希，说明大概遇到了 2^k 个不同元素。

算法步骤：

1. 哈希函数将元素映射为 64 位整数
2. 取哈希值高 p 位作为桶编号（共 m = 2^p 个桶）
3. 对剩余 64-p 位，计算前导零数量 + 1，记为 ρ
4. 更新对应桶的最大值：registers[bucket] = max(registers[bucket], ρ)
5. 估算：estimate = α × m² / Σ(2^(−registers[i]))，其中 α 是修正常数

为什么用多个桶：从 0.78 到 1.04/√m

单桶问题：直接用一个桶的最大 ρ 估算，方差极大（标准差 ≈ 0.78，即误差可达 78%）。

多桶解法：将哈希空间均匀切分为 m 个桶，每个桶独立记录其子流中的最大 ρ，最终对 m 个桶取调和平均数：

$$\text{estimate} = \alpha_m \cdot m^2 \cdot \left(\sum_{i=0}^{m-1} 2^{-\text{registers}[i]}\right)^{-1}$$

• 标准差从 0.78 降到 1.04 / √m
• m=16384（p=14）时，标准误差 ≈ 0.81%
• α 是修正偏差的常数（p=4 时 0.673，p≥6 时约 0.7213）

LinearCounting 小范围修正

当元素数量很少（estimate ≤ 2.5m）时，许多桶仍为空，调和平均数偏差较大。此时切换为更精确的 LinearCounting 算法：

$$\text{estimate} = m \cdot \ln!\left(\frac{m}{\text{zeros}}\right)$$

其中 zeros 是值为 0 的桶数量。

误差分析

Redis 的选择：p=14，标准误差 0.81%，每个寄存器 6 bit（最大 ρ 值 ≤ 63），内存 16384 × 6 / 8 = 12,288 字节 ≈ 12KB。

Java 实现

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;

/**
 * HyperLogLog 基数估算器（k1 scale 近似）
 * 标准误差：1.04 / sqrt(m)，p=12 时约 1.6%
 */
public class HyperLogLog {
    private final int p;            // 桶数量的对数，桶数 m = 2^p
    private final int m;            // 桶数量
    private final byte[] registers; // 每个桶记录最大 ρ（前导零数 + 1）

    public HyperLogLog(int p) {
        if (p < 4 || p > 16) throw new IllegalArgumentException("p must be 4..16");
        this.p = p;
        this.m = 1 << p;
        this.registers = new byte[m];
    }

    public void add(String value) {
        long hash = hash64(value);
        // 高 p 位作为桶编号
        int bucket = (int)(hash >>> (64 - p)) & (m - 1);
        // 剩余位：统计前导零数量 + 1 得到 ρ
        long remaining = hash << p;
        byte rho = (byte)(Long.numberOfLeadingZeros(remaining) + 1);
        if (rho > registers[bucket]) registers[bucket] = rho;
    }

    public long estimate() {
        // α 修正常数：消除调和平均数的系统性偏差
        double alpha = (p <= 5) ? new double[]{0,0,0,0,0.673,0.697,0.709}[p] : 0.7213475;
        double sum = 0.0;
        for (byte r : registers) sum += Math.pow(2, -r);
        double est = alpha * m * m / sum;

        // 小范围修正：数据量少时改用 LinearCounting
        if (est <= 2.5 * m) {
            int zeros = 0;
            for (byte r : registers) if (r == 0) zeros++;
            if (zeros > 0) est = m * Math.log((double) m / zeros);
        }
        return Math.round(est);
    }

    private long hash64(String s) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] bytes = md.digest(s.getBytes(StandardCharsets.UTF_8));
            long h = 0;
            for (int i = 0; i < 8; i++) h = (h << 8) | (bytes[i] & 0xFFL);
            return h;
        } catch (Exception e) { throw new RuntimeException(e); }
    }
}

使用示例：

HyperLogLog hll = new HyperLogLog(12); // p=12，约 1.6% 误差
for (String userId : stream) hll.add(userId);
System.out.println("UV 估算：" + hll.estimate());

验证结果（10,000 个不同元素，p=12）：

工程注意事项

分布式合并：逐桶取 max

多台服务器各维护一个 HLL，合并时只需逐桶取最大值，结果等价于将所有原始元素合并后重新计算：

$$\text{merged}[i] = \max(\text{A}[i],\ \text{B}[i])$$

传输成本极低：m=16384 时仅需传输 16384 × 6 bit = 12KB。

Redis 实战

参考资料

• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (Flajolet et al., 2007)
• Redis PFCOUNT 文档