集市里的神秘算账人：HyperLogLog 基数估计的智慧

可视化演示

通过哈希前导零计数、分桶调和平均估计、误差与内存分析三模式动画，展示HyperLogLog概率基数估计的核心原理。

伯努利试验与基数估计

神秘的算账人蹲在美食街口，从口袋里掏出一枚硬币。他对你说：“我抛这枚硬币，正面代表翻过这条街的顾客留下了标记，反面代表没留下。我记录下最长连续出现反面的次数。”你听得一头雾水，可他说出了一个惊人的规律：假如他连续抛出了最长的 5 次反面，那这条街大概来过 2 的 5 次方，也就是 32 位客人。

这听起来像是在变戏法，却藏着概率论的朴素智慧。抛硬币是一个伯努利试验——每次只有正反两种结果，且各占一半概率。连续抛硬币时，出现“连续 k 次反面”的概率是 2 的负 k 次方。反过来想：如果某种“罕见事件”真的发生了，那么在此之前，很可能已经尝试过大约 2 的 k 次方次。于是，观察“最长连续反面次数 k”，就能倒推出硬币被抛过多少次。

$ \displaystyle \hat{n} = 2^{k} $

其中，$\hat{n}$ 是估算的抛硬币总次数，$k$ 是记录到的最长连续反面的次数。这个公式是 HyperLogLog 的种子思想。

1. 确定观察量：我们要找的，是这组实验里“最极端”的那次结果——最长的连续反面。它对应着最罕见的概率事件。

$$\displaystyle k = \max(\text{连续反面长度})$$

2. 计算罕见概率：连续出现 $k$ 个反面的概率是每次 1/2 的概率连乘 $k$ 次。

$$\displaystyle P = \left(\frac{1}{2}\right)^{k} = 2^{-k}$$

3. 反推尝试次数：概率事件“出现 $k$ 个连续反面”大约需要 $1/P = 2^k$ 次尝试才能遇到一次，于是总次数估算为 $2^k$。

$$\displaystyle \hat{n} = \frac{1}{P} = 2^{k}$$

但这位算账人还有一个烦恼：抛硬币太“看脸”了。运气好时，可能只抛了 10 次就遇到了 4 个连续反面，估算出 16；运气差时，抛了 1000 次也可能只出现 3 个连续反面，估算成 8。单次实验的波动极大，就像只看一位顾客很难判断整条街的客流。于是，算账人开始琢磨：能不能多做几组实验，互相纠正误差呢？这就引出了哈希函数和分桶的思想。

哈希函数的作用

算账人发现自己没法真的让每位顾客都来抛硬币。于是他换了个思路：给每位顾客一个“号码牌”，号码牌是随机生成的。他发现，号码牌上“从左边数起有几个 0”这件事，和抛硬币的结果一模一样——都是随机的，都是二选一。

这个“号码牌生成器”在计算机里叫哈希函数。它能把任意输入（比如用户 ID、IP 地址）映射成一个固定长度的二进制数。哈希函数有个神奇的性质：哪怕输入只改变一个字符，输出也会像换了一个人似的完全不同，而且输出中每一位为 0 或 1 的概率都是 1/2。所以“哈希值二进制表示中前导 0 的个数”，就和“连续抛反面次数”等价了。

$ \displaystyle k = \rho(hash(x)) $

其中 $\rho$ 表示“数二进制前导零个数”的操作，$hash(x)$ 是元素 $x$ 的哈希值。比如哈希值是 0010...，前导零个数就是 2。

1. 哈希映射：计算元素 $x$ 的哈希值，得到一个二进制串。

$$\displaystyle h = hash(x)$$

2. 数前导零：从最左边开始数，看有多少个连续为 0 的位，记为 $k$。

$$\displaystyle k = \rho(h)$$

3. 概率解释：哈希值每一位独立随机，所以 $k$ 越大，说明这种哈希值越罕见，对应的元素规模越大。

$$\displaystyle P(\rho(h) \geq k) = 2^{-k}$$

算账人小心翼翼地写下每位顾客号码牌的前导零个数，只保留历史最大值。但他很快发现，单靠一个人的“运气记录”太不稳定。也许把号码牌分成几组，每组分别记录，再综合起来看，会更靠谱。这正是 HyperLogLog 从“简单估算”走向“精确估算”的转折点。

分桶与调和平均数

算账人把美食街上的顾客按照号码牌的“首几位数字”分成了 16 个小组，每个小组有一张专用的记录纸。每来一位顾客，先看他属于哪个小组，再数他号码牌上剩下的位数中有几个前导零。如果这个数比纸上记的大，就擦掉旧的写上新的。

这就是 HyperLogLog 里的分桶（也称寄存器）。通过哈希值的前 $p$ 位确定桶编号（共 $m = 2^p$ 个桶），其余位用来数前导零。每个桶只保存一个整数——目前看到的最大前导零数量。这样，16 组独立的“抛硬币实验”同时进行，然后用调和平均数（而非算术平均数）把各组结果结合起来，从而对抗个别桶的极端值。

$ \displaystyle \hat{n} = \alpha_m \, m^2 \left( \sum_{j=1}^{m} 2^{-M_j} \right)^{-1} $

其中 $m$ 是桶数，$M_j$ 是第 $j$ 个桶记录的最大前导零数，$\alpha_m$ 是修正系数（$m$ 越大越接近 0.7213）。

1. 分桶索引：取哈希值的前 $p$ 位作为桶号，元素归入对应桶。

$$\displaystyle j = h_1h_2\dots h_p$$

2. 桶内记录：对剩余位统计前导零数量，更新该桶的最大值 $M_j$。

$$\displaystyle M_j = \max(M_j,\ \rho(h_{剩余}))$$

3. 调和平均汇总：将所有桶的 $2^{-M_j}$ 求和取倒数，再乘修正系数和桶数平方，得到最终估算。

$$\displaystyle \hat{n} = \alpha_m \, m^2 \left( \sum_{j=1}^{m} 2^{-M_j} \right)^{-1}$$

算账人用 16 组硬币实验互相“打配合”，结果比单组实验稳定多了。但这还不够——他需要知道自己这个估算到底有多可靠。就像天气预报会说“降水概率 80%”，他也想告诉美食街老板：我估算的客流大概在什么范围内、有多大的把握。于是，标准误差和置信区间登场了。

标准误差与置信区间

算账人反复做了很多次实验，发现每次估算的结果虽然都接近真实值，但各有不同，像射箭一样散布在靶心周围。他总结出：当使用 $m$ 个桶时，估算值的标准误差约为 $1.04 / \sqrt{m}$。桶越多，箭簇越密集，估算越精准。

在概率统计中，标准误差衡量的是“估算值偏离真实值”的典型幅度。HyperLogLog 的误差分布近似正态分布，这就意味着约 68% 的估算值会落在真实值的一个标准误差范围内，约 95% 的估算值会落在两个标准误差范围内。这里的“约”体现了概率保证，而不是绝对保证。

$ \displaystyle \text{相对标准误差} \approx \frac{1.04}{\sqrt{m}} $

其中 $m$ 是桶的数量。精度每提高一倍（$m$ 变为原来的 4 倍），误差就减半。

1. 误差定义：定义相对标准误差为估算值与真实值之差的典型相对幅度。

$$\displaystyle \text{RSE} = \frac{\sqrt{\text{Var}(\hat{n})}}{n}$$

2. 代入 HyperLogLog 方差：该算法的方差近似为常数乘以 $1/m$。

$$\displaystyle \text{Var}(\hat{n}) \approx \frac{n^2}{m} \cdot \beta$$

3. 推导标准误差：开方后得到相对标准误差约 $1.04/\sqrt{m}$。

$$\displaystyle \text{RSE} \approx \frac{1.04}{\sqrt{m}}$$

算账人现在对自己的估算既有信心也有分寸。但也遇到了新难题：刚开门营业时，整条街几乎没什么顾客，如果立刻用 16 张记录纸——每张都要占一个内存格子——太浪费了。能不能人少时只带一张纸，人多时再把纸分出来？这引出了存储模式的艺术。

稀疏与密集存储

聪明算账人发现了一个规律：当顾客很少时，大多数记录纸都是空白的，只有极少数纸上有数字。如果为每张空白纸都预留空间，相当于为根本不存在的顾客准备了座位。更好的做法是只记录“有数字的那几张纸的编号和数字”，其余不看——这就是稀疏存储。

当顾客多了起来，几乎每张纸都有数字时，记录编号反而成了负担。这时把所有纸按固定顺序摆开，每张里存一个数字，直接按位置索引——这就是密集存储。HyperLogLog 在 Redis 中正是这样实现的：数据量小时用稀疏模式节省空间，超过阈值自动升级为密集模式。

| 模式 | 存储方式 | 适用场景 | 内存开销 |

|------|----------|----------|----------|

| 稀疏 | 仅记录非零桶的 （位置，值） 对 | 基数较小（如 < 2^p × 阈值） | 极小 |

| 密集 | 每桶固定字节存储 | 基数较大 | $m$ 字节 |

模式自动转换的关键在于稀疏存储存不下了或者查询变慢。降级时机通常基于非零桶数量或稀疏表示的字节数对比密集表示的大小。当稀疏表示的字节数超过密集表示时，就变为密集模式，这个切换对调用方完全透明。

算账人在街头小本子上精简记录、在集市喧闹时展开大账本，总能找到最省纸的方式。正是这种“看菜下饭”的存储智慧，让 HyperLogLog 在真实系统中既省内存又保持好性能。接下来看看这些智慧如何落地到实际的大数据组件里。

Redis与ClickHouse实现

算账人的方法传到了两家大公司：一家叫“Redis 客栈”，一家叫“ClickHouse 粮仓”。Redis 客栈直接在门口柜台提供了一条命令 PFADD，店主只需说“这几个客人来过了”，Redis 就会自动完成哈希、分桶、记录的全部流程。查人数时用 PFCOUNT，几个店合并客流用 PFMERGE。

ClickHouse 粮仓则把 HyperLogLog 包装成了 SQL 聚合函数，分析师们可以像写 count(DISTINCT user_id) 一样自然地调用，底层自动走 HLL 逻辑。两家都采用了“稀疏+密集”的存储模式，Redis 默认配置 $2^{14}$ 个桶，误差约 0.81%。

Redis 的经典用法是统计 UV：

在大数据领域，ClickHouse 预聚合表引擎也内置支持，例如：

其中 13 是精度参数，对应桶数 $2^{13}$。这些工程化实现的背后，都遵循同一个逻辑：用可控的超小误差，换取百倍千倍的内存节省。而实际能省多少，取决于精度怎么配置。

精度参数与内存是工程落地最关键也最容易被忽视的一环。精度参数 $p$ 直接决定桶数 $m = 2^p$，也就决定了内存开销和误差水平。Redis 默认 $p=14$ 对应 $m=16384$ 个桶，使用 6 位存储每个桶的寄存器值，总内存约 12KB，相对标准误差约 0.81%。如果调低 $p=10$（1024 个桶），内存降到约 1KB，但误差上升到 3.25%；如果调高 $p=16$（65536 个桶），内存约 48KB，误差降到 0.4%。

$ \displaystyle \text{内存} = m \times 6 \text{ bit} = 2^{p} \times 6 \text{ bit} $

1. 确定桶数：精度参数 $p$ 决定桶的数量 $m$。

$$\displaystyle m = 2^{p}$$

2. 计算总位数：每个桶用 6 位存储（可表示最大 63 的前导零），总位数是桶数乘 6。

$$\displaystyle \text{总位数} = 2^{p} \times 6$$

3. 换算为字节：除以 8 得到字节数。$p=14$ 时约为 12KB。

$$\displaystyle \text{内存} = \frac{2^{14} \times 6}{8} = 12288 \text{ 字节}$$

当你在真实系统中选择 $p$ 时，实际上是在误差与成本之间做买卖。比如 Redis 的默认值正是经过社区打磨后的平衡点——对大多数 UV 统计场景，0.81% 的误差远远够用，而 12KB 的内存几乎可以忽略不计。这就像算账人用几张小纸片替代了一屋子名册，纸片越多越精准，但对生意来说，纸片再多不如刚才够用的那一叠。

127.0.0.1:6379> PFADD unique:users:20241105 user1 user2 user3(integer) 1127.0.0.1:6379> PFCOUNT unique:users:20241105(integer) 3

SELECT uniqCombined(13)(user_id) AS uv FROM events WHERE dt = '2024-11-05'

大规模UV统计实践

现在，让我们回到开头的真实场景：你运营的 App 每天有数千万次访问，产品经理要实时看到“今日 UV”（独立的访客人数）。如果用传统的精确 Set 存储，每个用户 ID 占 16 字节，一千万 UV 就要 160MB 内存；而用 HyperLogLog，只需 12KB 就能覆盖所有精度，内存降了整整一万多倍。

在某大型电商平台的实践中，将 UV 统计从 Redis Set 迁移到 HyperLogLog 后，单日报表的内存占用从 2.1GB 降到 48KB，误差始终控制在 1% 以内。这对实时大屏、运营日报来说完全可以接受。

统计系统通常这样组合使用：

1. 实时层：Redis HyperLogLog 接收实时埋点数据，PFADD 原子更新，毫秒级 PFCOUNT 输出。

2. 离线层：ClickHouse 定期对明细数据跑 uniqCombined，与实时值互相校验。

3. 趋势分析：利用 PFMERGE 合并多天的 HLL 结构，快速计算周活跃、月活跃等复合指标。

误差取舍的哲学同样适用：哪些场景必须精确，哪些场景概率足够。在财务对账中，几十元的误差是事故；但在“今天来了多少人看首页”中，0.8% 的误差甚至小于抽样统计本身的人为波动。算账人的智慧不是“算得准”，而是“算得够用又便宜”。

AI 应用场景

Python 演示

import mathimport mmh3  class HyperLogLog:    def __init__(self, p=14):        self.p = p        self.m = 1 << p        self.registers = [0] * self.m        self.alpha = self._get_alpha()     def _get_alpha(self):        if self.m == 16:            return 0.673        if self.m == 32:            return 0.697        if self.m == 64:            return 0.709        return 0.7213 / (1 + 1.079 / self.m)     def _hash_to_bucket_and_zeros(self, item):        h = mmh3.hash(str(item), seed=42)        # 桶索引 = 哈希值的前 p 位        bucket = h >> (32 - self.p)        # 剩余位中数前导零个数 + 1（避免 log(0)）        rest = h & ((1 << (32 - self.p)) - 1)        if rest == 0:            zeros = 33 - self.p        else:            zeros = 1 + (rest.bit_length() - 1)        return bucket, zeros     def add(self, item):        bucket, zeros = self._hash_to_bucket_and_zeros(item)        self.registers[bucket] = max(self.registers[bucket], zeros)     def count(self):        # 调和平均汇总各个桶的 2^-M_j        sum_inv = 0.0        zero_count = 0        for r in self.registers:            sum_inv += 2.0 ** (-r)            if r == 0:                zero_count += 1        estimate = self.alpha * self.m * self.m / max(sum_inv, 1e-9)        # 小基数修正：如果估算值 < 2.5 * m 且存在空桶        if estimate <= 2.5 * self.m and zero_count > 0:            estimate = self.m * math.log(self.m / zero_count)        return int(estimate)  def main():    import random     hll = HyperLogLog(p=14)    true_set = set()     for i in range(100000):        user_id = "user_" + str(random.randint(1, 50000))        hll.add(user_id)        true_set.add(user_id)     estimated = hll.count()    real = len(true_set)    error = abs(estimated - real) / real * 100     print(f"真实基数: {real}")    print(f"HLL估算: {estimated}")    print(f"误差率: {error:.2f}%")    print(f"内存占用: {hll.m * 6 / 8 / 1024:.2f} KB")  if __name__ == "__main__":    main()

1. self.registers = [0] * self.m初始化 $m$ 个桶，每桶记录最大前导零数
2. bucket = h >> (32 - self.p)取哈希值前 $p$ 位作为桶编号
3. zeros = 1 + (rest.bit_length() - 1)计算剩余位的前导零个数，加 1 防止对数为 0
4. self.registers[bucket] = max(self.registers[bucket], zeros)更新桶内最大值，这是合并重复元素的去重关键
5. sum_inv += 2.0 ** (-r)计算调和平均的核心累加：每个桶贡献 $2^{-M_j}$
6. estimate = self.alpha * self.m * self.m / max(sum_inv, 1e-9)用修正系数和桶数平方放大调和均值，得到最终估算
7. if estimate <= 2.5 * self.m and zero_count > 0触发小基数修正，用空桶数量做更准确的估计

常见误区

面试题