HyperLogLog（HLL）是 Redis 里用来做基数估计（统计不重复元素个数）的概率数据结构，核心卖点是：无论塞进去多少元素，内存固定只占 12KB（16384 个 6-bit 寄存器），标准误差约 0.81%。它不存原始元素，所以能统计的量级远超内存上限（理论上到 2⁶⁴）。
下面按「直觉 → 算法 → Redis 实现细节 → UV 落地」的顺序展开。
1. 直觉：抛硬币问题
想象你抛一枚均匀硬币，记录第一次出现正面「1」之前连续抛出了几个反面「0」。
- 连续 k 个反面后才出现正面的概率是 2⁻ᵏ
- 所以「连续 10 个反面」这个事件，大概要抛 2¹⁰ = 1024 次才会遇到一次；「连续 20 个反面」大概要抛 2²⁰ ≈ 100 万次
反过来看：如果你看到一个哈希值开头有 k 个连续的 0，那就强烈暗示你手上大概有 2ᵏ 个不同的元素。这就是全部直觉的起点——「最长前置零串长度」可以作为去重数量的估计器。
2. 核心算法
第一步：哈希
每个元素（例如 user:123）经过哈希函数（Redis 用 MurmurHash64A）映射成一个 64 位均匀分布的二进制串。哈希保证：同一个元素永远得到同一个串，不同元素概率上均匀散布。
第二步：分桶（stochastic averaging，随机平均）
只用「全局最长零串」方差太大，所以把哈希值拆成两段：
- 前 14 位 → 桶索引（Redis 有 2¹⁴ = 16384 个寄存器/register）
- 后 50 位 → 统计前置零个数
每个寄存器 M[j] 只保存「掉进桶 j 的元素里，最大的前置零个数」。插入元素时：
idx = hash 前 14 位
zeros = hash 后 50 位的前置零个数
if zeros > M[idx]: M[idx] = zeros # 只更新，只增不减第三步：调和平均估计
最终估计公式（Flajolet et al.）：
E = α_m · m² / Σ( 2^(-M[j]) ) # m = 16384, α_m ≈ 0.7213/(1+1.079/m)用调和平均而不是算术平均或最大值，是因为它对方差更鲁棒，配合修正系数 α_m 后无偏性最好。
第四步：偏差修正
- 小基数修正：当估计值 < 2.5m 且还有空寄存器（V 个）时，改用 linear counting：
E = m · ln(m/V)，消除小数据时的系统性偏差 - 大基数修正：当估计值极大时加
-2⁶⁴·ln(1 - E/2⁶⁴)修正（64 位哈希下实际几乎不会触发）
误差上界：1.04/√m = 1.04/128 ≈ 0.81%，这是概率保证，不随数据量增长而变化。
3. Redis 的具体实现
内存布局
- 16384 个寄存器 × 6 bit = 98304 bit = 12KB，固定不变
- 寄存器最大值是 50（64 位哈希去掉 14 位桶索引后剩 50 位），6 bit 足够存（最大 63）
稀疏编码（sparse）
刚创建时寄存器几乎全空，直接用 12KB 太浪费。所以 Redis 先用压缩的 sparse 表示（把连续的 0 寄存器做游程编码，约 2 bit/寄存器），只有当编码后大小超过 3000 字节（HLL_SPARSE_MAX_BYTES）才转成 dense（12KB 固定数组）。这也是 PFADD 大量数据时偶尔会变慢的原因——触发了编码转换。
三个命令
| 命令 | 行为 |
|---|---|
PFADD key ele... | 哈希并更新寄存器（只增） |
PFCOUNT key | 用公式算基数，结果缓存在 HLL 头部（cardinality cache），源数据变了才重算 |
PFMERGE dest src... | 逐寄存器取 max（即合并），合并后同样写缓存 |
使用示例：
PFADD users:2024-06-01 user:1 user:2 user:3
PFCOUNT users:2024-06-01 # 3
PFADD users:2024-06-02 user:2 user:4
PFMERGE users:uv users:2024-06-01 users:2024-06-02典型场景：UV 统计、IP 去重、爬虫 URL 去重计数。
4. 和其他结构对比
| 结构 | 内存 | 是否精确 | 能否删元素 |
|---|---|---|---|
| Set | 与元素数成正比 | 精确 | 能 |
| Bloom Filter | 固定但较大 | 假阳性（可能误判存在） | 不能 |
| HyperLogLog | 固定 12KB | 有误差（±0.81%） | 不能（只能增） |
局限：
- 只能插入不能删除（寄存器只增不减）
- 近似而非精确
- 结果由哈希而来，无法从 HLL 里查回原始元素值——它根本不存元素
一句话总结：HLL 用 12KB 换来了「海量数据去重计数」的能力，代价是把精确答案换成 0.81% 误差内的近似值，以及不可删除。
想看源码的话，核心在 Redis 的 src/hyperloglog.c（约 1500 行，注释详细，是理解上文所有公式的最佳现场）。
5. 用 HyperLogLog 统计网站 UV
前面讲的是数学内核（哈希 + 分桶 + 调和平均），这一部分聚焦**「UV 问题怎么映射成 HLL 能算的东西」**，以及工程上怎么落地。
5.1 核心映射：一次访问 → 一个「元素」
UV 的定义是去重后的不同访客数。HLL 恰好只认「元素」——它不管元素出现了多少次，只在乎「这个值我见没见过」。
所以第一步是：给每个访客挑一个稳定标识符，作为 PFADD 的元素：
访客 V 访问页面
→ PFADD uv:2024-06-01 V关键语义：同一个访客一天访问 100 次，每次都哈希出同一个值，寄存器内容一模一样，所以只算 1 次。HLL 天然去重，这是它和 PV（计数器，每次都 +1）的本质区别。
标识符怎么选，直接决定统计质量：
| 标识符 | 优点 | 缺点 |
|---|---|---|
user_id（登录用户） | 最准 | 未登录的匿名访问算不进 |
| cookie / device_id | 覆盖全部访问 | 同一人换设备或清 cookie 会被算成多个 |
| IP | 无需埋点 | NAT / 公司出口共享 IP 会严重低估 |
现实做法通常是「cookie + user_id 合并」取较优值，并接受误差。
5.2 时间维度：三种 UV 和它们的做法
网页统计里几乎总需要按时间维度拆分：
① 每日 UV——一个 key 对应一天，当天访问就 PFADD day_{date} 访客。
② 自然增长型累计 UV（比如「产品上线以来总访客」）——同一个 key 一直往里加，永不 reset。
③ 区间 UV（比如「近 7 天去重访客」）——这是 HLL 的杀手锏场景，靠的是它的可合并性：
PFMERGE uv:last7 uv:2024-06-01 uv:2024-06-02 ... uv:2024-06-07
PFCOUNT uv:last7逐寄存器取 max 合并，合并成本与数据量无关、只和寄存器数（16384）有关。而且 Redis 更贴心——PFCOUNT 本来就能直接接多个 key，内部先 merge 再算，一条命令搞定：
PFCOUNT uv:2024-06-01 ... uv:2024-06-07对比一下：不用 HLL 的话，区间去重要么把 7 天明细拉出来塞 Set（内存爆炸），要么用一个带窗口的布隆（删不了旧的）。HLL 用「每天一个 12KB 的 key + 一次合并」优雅解决，而且天然满足跨天去重：同一个人周一看过、周三又看过，合并后只算一次。
5.3 一个完整的埋点流水
[Nginx/CDN 日志] ——(异步消费)--> [ClickHouse/队列]
|
解析出 { 访客ID V, 日期 D }
|
对每个 (日期, 访客) 去重后:
PFADD uv:{D} V
报表层:
今日UV = PFCOUNT uv:2024-06-01
7日UV = PFCOUNT uv:06-01 ... uv:06-07
近30日UV = PFCOUNT 30 个 key（或先 PFMERGE 再 count，结果缓存更快）5.4 工程上的三个实战注意点
-
合理分桶粒度：key 不要只按天分，很多团队按
(天, 站点/频道)分，这样能自由组合出任意区间的去重，合并是 O(16384) 量级，组合再多也不怕。 -
不要在高频热路径里重复
PFCOUNT：PFCOUNT结果缓存在 HLL 头部，同一 key 短期内重复计数几乎零成本；但跨 30 个 key 的区间计数每次都要 merge，量大的话建议计一次、缓存到报表层（比如每分钟刷新一次即可，UV 对延迟不敏感）。 -
误差心里要有数：±0.81% 是概率保证，对 UV 报表（几十万量级，差几百人）完全可接受，但计费、KPI 对赌、法律要求的精确数不要用 HLL——那种场景用精确去重（bitmap 或明细表），数据量不够大时成本也不高。
5.5 方案对比小结
| 方案 | 内存 | 精确度 | 区间去重 | 明细 | 适合 |
|---|---|---|---|---|---|
| 明细表 COUNT DISTINCT | 最大 | 精确 | 最灵活 | 有 | 量小 / 要精确 |
| Set | 大 | 精确 | 可 | 有 | 单日几十万内 |
| HLL | 每 key 12KB 固定 | ±0.81% | 合并 O(16384) | 无 | 海量 UV、跨天去重 |
| Bitmap | 依赖用户 id 上限 | 精确（若 id 连续） | 可 | 无 | id 可压缩成位的场景 |
一句话总结：HLL 做 UV 的本质，是把「第 n 次见到这个访客」压缩成对 16384 个寄存器里某个计数器的单调上升更新；UV 去重的正确性来自「同一标识符哈希恒等、寄存器只增不减」，区间 UV 的效率来自「合并 = 逐寄存器取 max」。12KB 换一个 0.81% 误差内的答案，正是 UV 这种「量很大、不要求精确到最后一个人」的场景该付出的代价。
顺带一算：如果按天建 key，一年就是 365 个 key × 12KB ≈ 4.4MB，整年 UV 数据躺在内存里都没压力——这也是它在实时看板里几乎成为默认选项的原因。