【Redis从入门到精通】第68篇：HyperLogLog——用极小内存统计超大基数

上一篇【第67篇】Redis Stream——终于有了真正的消息队列
下一篇【第69篇】Redis性能调优实战——从监控到参数调整的全套方案

产品经理：“上个月咱们网站的UV是多少？”
程序员：“我看看……1.2亿。”
产品经理：“怎么算的？”
程序员：“用Redis的Set存的。”
产品经理：“用了多少内存？”
程序员：“大概……”（看了一眼监控）“7.6GB。”
产品经理：“下个月预算要对齐技术成本，内存该缩减了。”
程序员：“没问题，我用HyperLogLog，12KB搞定。”
产品经理：“12KB？！不可能吧！”
程序员：“可以，误差只有0.81%。”
产品经理：“那你在Set上浪费的7.6GB是……”
程序员：“……是历史的教训。”

这就是HyperLogLog（简称HLL）的魔力——用固定的12KB内存，统计任意规模的基数（去重计数），误差控制在0.81%以内。今天我们就来揭开这个神奇数据结构的面纱。

一、基数统计的场景与挑战

1.1 什么是基数统计？

基数（Cardinality）就是一个集合中不重复元素的数量。通俗说就是：来了多少人？而不是来了多少次。

基数 vs 计数： 原始数据：张三、李四、张三、王五、李四、张三、赵六、李四 计数（Count）： 一共来了8次 → COUNT 就能算，O(1)内存，O(1)时间 基数（Cardinality）： 一共来了4个不同的人 → 需要去重，内存开销巨大 张三、李四、王五、赵六 = 4

1.2 常见基数统计场景

1.3 精确去重的内存代价

用Redis Set做精确去重，内存开销有多大？我们来算一算：

Set存储1亿个用户ID的内存开销： 假设用户ID是 "user_123456789"（14字节） Redis Set存储开销约 64字节/元素（包含内部指针和开销） 1亿元素 × 64字节 = 6.4 GB 这还只是一个指标！如果你还要统计： - 今日UV：6.4GB - 本周UV：6.4GB - 本月UV：6.4GB - 每个页面的UV：每个6.4GB × N个页面 → 内存成本爆炸式增长 HLL方案： 每个指标固定12KB - 今日UV：12KB - 本周UV：12KB - 本月UV：12KB - 100个维度的UV：100 × 12KB = 1.2MB → 相差5000倍！

内存对比直观图： Set方案的内存增长： ┌──────────────────────────────────────────────────────────┐ │ 内存 │ │ 6.4GB ┤ ● │ │ │ ● │ │ 4.8GB ┤ ● │ │ │ ● │ │ 3.2GB ┤ ● │ │ │ ● │ │ 1.6GB ┤ ● │ │ │● │ │ 0 ┼─────┬─────┬─────┬─────┬─────┬─────┬─────> 基数 │ │ 2千万 4千万 6千万 8千万 1亿 │ │ │ │ ← 线性增长，基数越大内存越大 → │ └──────────────────────────────────────────────────────────┘ HLL方案的内存增长： ┌──────────────────────────────────────────────────────────┐ │ 内存 │ │ 24KB ┤ │ │ 12KB ┤●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● │ │ 0 ┼─────┬─────┬─────┬─────┬─────┬─────┬─────> 基数 │ │ 2千万 4千万 6千万 8千万 1亿 10亿 100亿 │ │ │ │ ← 固定12KB！基数再大也不变 → │ └──────────────────────────────────────────────────────────┘

二、HyperLogLog基本原理

2.1 抛硬币的启发

理解HLL需要一个思维跳跃。先看一个概率实验：

抛硬币实验： 规则：反复抛硬币，直到出现正面，记录抛的次数 比如：反反正 → 3次 问题：如果你记录到的最长记录是3次，总共大约抛了多少次？ 直觉答案：大约2^3 = 8次 统计学原理：概率为1/(2^k)的事件，期望需要2^k次实验才会发生一次 把"抛硬币"换成"哈希值的二进制"： 哈希值是一个二进制串，比如 00010101001... 连续前缀0的个数就像一个"硬币反面连抛次数" 最长前缀0的长度k → 估计基数 ≈ 2^k

HLL的核心思想： 用户ID "user_123456" │ ▼ 哈希函数（如MurmurHash） 哈希值: 0010101110011010... (64位二进制) ^^ ││ 00 = 前缀2个0 → 记录值=2 用户ID "user_999999" │ ▼ 哈希函数 哈希值: 0000001010110101... (64位二进制) ^^^^^ 00000 = 前缀5个0 → 记录值=5 经过大量用户后： 记录的最大前缀0个数 = 5 估计基数 ≈ 2^5 = 32（实际上可能是30或35，有误差）

2.2 从LogLog到HyperLogLog

光靠一个计数器还不够，误差太大了。HLL的改进分为三步：

进化史： 1. LogLog（Durand & Flajolet, 2003） 把哈希值分成多个"桶"，每个桶独立统计 多个桶的调和平均数 → 减少方差 桶数m=1024，每个桶记录max前导零 内存 = 1024 × 5bit = 640字节 2. HyperLogLog（Flajolet et al., 2007） 上面用的是算术平均，HLL改用调和平均 + 偏差修正（小基数和大基数分别修正） 标准误差 ≈ 1.04/√m m=16384(2^14) → 误差约0.81% 3. Redis HLL（Redis 2.8.9） 注册数≤阈值 → 稀疏存储（省内存） 注册数>阈值 → 密集存储（标准HLL） 自动切换，无需人工干预

2.3 Redis HLL的内存结构

Redis HLL的存储格式： 稀疏模式（少量元素时）： ┌─────────────────────────────────────────┐ │ 使用类似ZIPLIST的结构 │ │ 每个元素用一个操作码+少量字节表示 │ │ 变长编码，极致省空间 │ │ │ │ 适用场景：基数较小的HLL │ └─────────────────────────────────────────┘ 密集模式（元素足够多时）： ┌─────────────────────────────────────────┐ │ 16384个寄存器，每个6bit │ │ = 16384 × 6bit = 98304 bit │ │ = 12288 bytes ≈ 12KB │ │ │ │ 适用场景：基数足够大 │ └─────────────────────────────────────────┘ 自动切换阈值： 当稀疏编码的字节数 > 16384 × 6/8 = 12288字节时 → 自动切换到密集存储

三、PFADD / PFCOUNT / PFMERGE 命令详解

3.1 PFADD：添加元素

# 基本用法127.0.0.1:6379>PFADD uv:20260526 user_001 user_002 user_003(integer)1# 1=基数发生了变化，0=没有变化# 大量添加（同上）127.0.0.1:6379>PFADD uv:20260526 user_001# 重复添加(integer)0# 已经计数过，基数不变# PFADD可以接受多个参数127.0.0.1:6379>PFADD uv:20260526 user_004 user_005 user_006(integer)1

3.2 PFCOUNT：估算基数

# 单个HLL127.0.0.1:6379>PFCOUNT uv:20260526(integer)6# 估计6个不同元素（实际就是6个，小基数时误差更小）# 实际测试：添加100万个元素127.0.0.1:6379>PFADD test:million[100万个元素...]127.0.0.1:6379>PFCOUNT test:million(integer)997837# 估计998K，误差约0.22%（比理论0.81%更好）# 多个HLL的联合基数127.0.0.1:6379>PFCOUNT uv:20260525 uv:20260526 uv:20260527(integer)150234# 三天总UV的去重计数

3.3 PFMERGE：合并多个HLL

# 合并两个HLL127.0.0.1:6379>PFMERGE uv:this_week uv:20260525 uv:20260526 uv:20260527 OK127.0.0.1:6379>PFCOUNT uv:this_week(integer)150234# 与上面的联合查询结果一致# MERGE的威力：可以快速聚合任意时间维度# 日UV → 周UV → 月UV → 年UV 都能合并计算

PFMERGE的典型应用场景： 按天记录UV： ┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐ │ uv:0523 │ │ uv:0524 │ │ uv:0525 │ │ uv:0526 │ │ 12KB │ │ 12KB │ │ 12KB │ │ 12KB │ └─────┬─────┘ └─────┬─────┘ └─────┬─────┘ └─────┬─────┘ │ │ │ │ └──────────────┴──────┬───────┴──────────────┘ │ PFMERGE ↓ ┌─────────────────┐ │ uv:this_week │ │ 12KB │ │ 周UV去重计算 │ └─────────────────┘ 再按需合并： PFMERGE uv:this_month uv:week1 uv:week2 uv:week3 uv:week4 → 月度UV也是12KB

四、UV统计实战

4.1 日UV统计

@ServicepublicclassUVStatisticsService{@AutowiredprivateStringRedisTemplateredisTemplate;/** * 记录一次访问 * @param userId 用户ID */publicvoidrecordVisit(LonguserId){Stringtoday=LocalDate.now().format(DateTimeFormatter.BASIC_ISO_DATE);Stringkey="uv:day:"+today;redisTemplate.opsForHyperLogLog().add(key,userId.toString());}/** * 查询今日UV */publiclonggetTodayUV(){Stringtoday=LocalDate.now().format(DateTimeFormatter.BASIC_ISO_DATE);returnredisTemplate.opsForHyperLogLog().size("uv:day:"+today);}/** * 查询过去N天总UV（去重） */publiclonggetLastNDaysUV(intdays){String[]keys=newString[days];LocalDatetoday=LocalDate.now();for(inti=0;i<days;i++){keys[i]="uv:day:"+today.minusDays(i).format(DateTimeFormatter.BASIC_ISO_DATE);}returnredisTemplate.opsForHyperLogLog().size(keys);}}

4.2 多维度UV统计

/** * 多维度UV统计：页面UV + 渠道UV + 端UV */@ServicepublicclassMultiDimUVService{@AutowiredprivateStringRedisTemplateredisTemplate;publicvoidrecordVisit(LonguserId,StringpageId,Stringchannel,Stringdevice){Stringtoday=LocalDate.now().format(DateTimeFormatter.BASIC_ISO_DATE);// 多个HLL key，每个12KB，互不影响redisTemplate.opsForHyperLogLog().add("uv:day:"+today,userId.toString());redisTemplate.opsForHyperLogLog().add("uv:page:"+today+":"+pageId,userId.toString());redisTemplate.opsForHyperLogLog().add("uv:channel:"+today+":"+channel,userId.toString());redisTemplate.opsForHyperLogLog().add("uv:device:"+today+":"+device,userId.toString());}// 合并多天数据计算周/月活publiclonggetWeeklyUV(){List<String>keys=getLast7DayKeys();StringmergeKey="uv:week:"+getCurrentWeekKey();// 先合并到一个临时keyredisTemplate.opsForHyperLogLog().union(mergeKey,keys.toArray(newString[0]));redisTemplate.expire(mergeKey,7,TimeUnit.DAYS);// 一周后自动清理returnredisTemplate.opsForHyperLogLog().size(mergeKey);}}

4.3 存储七天的历史数据

@ComponentpublicclassUVHistoryStorage{@AutowiredprivateStringRedisTemplateredisTemplate;// 每天凌晨自动汇总前一天的HLL@Scheduled(cron="0 5 0 * * ?")publicvoidarchiveYesterdayUV(){Stringyesterday=LocalDate.now().minusDays(1).format(DateTimeFormatter.BASIC_ISO_DATE);StringyesterdayKey="uv:day:"+yesterday;// 合并到周活StringweekKey="uv:week:"+WeekFields.ISO.weekOfYear();redisTemplate.opsForHyperLogLog().union("uv:week:"+weekKey,yesterdayKey);redisTemplate.expire("uv:week:"+weekKey,30,TimeUnit.DAYS);// 合并到月活StringmonthKey="uv:month:"+YearMonth.now().format(DateTimeFormatter.ofPattern("yyyyMM"));redisTemplate.opsForHyperLogLog().union("uv:month:"+monthKey,yesterdayKey);redisTemplate.expire("uv:month:"+monthKey,90,TimeUnit.DAYS);// 日HLL保留7天redisTemplate.expire(yesterdayKey,7,TimeUnit.DAYS);}}

⚠️ 注意：PFMERGE/PFCOUNT支持多个key联合查询，但这与预先MERGE到目标key有本质区别。联合查询是实时计算的，频繁执行有性能开销；预先MERGE是一次性操作，后续查询PFCOUNT目标key即可。对于固定需要的历史聚合（如周活/月活），建议提前MERGE。

五、HyperLogLog vs Set vs BitMap 选型对比

5.1 三种方案总览

用户ID范围：1 ~ 1亿，统计活跃用户数 方案A：Set ┌──────────────────────────────────────┐ │ SADD active:today user_001 │ │ SCARD active:today → 精确结果 │ │ │ │ 内存：6.4GB（1亿活跃） │ │ 精确度：100% │ │ 能枚举：✓ │ └──────────────────────────────────────┘ 方案B：BitMap ┌──────────────────────────────────────┐ │ SETBIT active:today user_id 1 │ │ BITCOUNT active:today → 精确结果 │ │ │ │ 内存：1亿bit = 12.5MB（压缩后约1MB） │ │ 精确度：100% │ │ 能枚举：✓（遍历bit） │ │ 前提：用户ID必须是连续整数 │ └──────────────────────────────────────┘ 方案C：HyperLogLog ┌──────────────────────────────────────┐ │ PFADD active:today user_001 │ │ PFCOUNT active:today → 近似结果 │ │ │ │ 内存：12KB（固定） │ │ 精确度：≈99.19%（误差0.81%） │ │ 能枚举：✗ │ │ 前提：无（ID可以是任意字符串） │ └──────────────────────────────────────┘

5.2 详细对比表格

5.3 选型决策树

你的需求是什么？ │ ├─ 需要精确计数？ │ ├─ YES → 用户ID是连续整数？ │ │ ├─ YES → 用户量上亿？→ BitMap │ │ └─ NO → 数据量百万级？→ Set │ │ │ │ └─ NO → 可以接受0.81%误差？ │ │ ├─ YES → 数据可能上亿？ │ │ │ ├─ YES → HLL │ │ │ └─ NO → HLL也行，Set更简单 │ │ │ └─ NO → 回到"需要精确"分支 │ ├─ 需要列举有哪些用户？→ Set或BitMap，HLL不行 │ └─ 需要判断某个用户是否在集合中？→ Set或BitMap，HLL不行

六、HLL的局限与注意事项

6.1 三大局限

局限1：不能枚举元素 ┌─────────────────────────────────────────┐ │ PFCOUNT告诉你"大约有100万人" │ │ 但你没法知道这100万人具体是谁 │ │ │ │ 如果你需要给所有活跃用户推送通知 │ │ → HLL不行，用Set吧 │ └─────────────────────────────────────────┘ 局限2：有误差（0.81%） ┌─────────────────────────────────────────┐ │ 真实基数100万时，PFCOUNT可能返回 │ │ 991,900 ~ 1,008,100 │ │ │ │ 对于运营"大概一百万"的报告没问题 │ │ 但用来做计费结算或精确对账不行 │ │ 切记：HLL是"估算"不是"统计" │ └─────────────────────────────────────────┘ 局限3：不能删除元素 ┌─────────────────────────────────────────┐ │ HLL只记录"最大值"，无法回退 │ │ 删了用户后，HLL不会变小 │ │ │ │ 适合统计"来过的人"，不适合"当前在线" │ │ 后者应该用Set，在线时SADD，离线时SREM │ └─────────────────────────────────────────┘

6.2 使用建议

⚠️ 注意：Redis的HLL命令以"PF"开头，这是为了纪念HLL的发明者Philippe Flajolet（1948-2011）。这位法国数学家在概率计数算法领域的贡献，让今天的我们能在12KB内存里做1亿用户的去重统计。

七、总结

HyperLogLog是典型的"用精确度换空间"的算法。它不完美，但在它的适用场景里，它是完美的。

核心记住三点：

1. 12KB内存，无论多少数据，固定不变
2. 0.81%标准误差，够用但不精确
3. 只能加不能删，适合"来过多少人"不适合"现在有多少人"

如果你在做UV统计、DAU统计、搜索词去重，HLL是最优解。如果需要精确计数或元素枚举，回去用Set或BitMap吧。

上一篇【第67篇】Redis Stream——终于有了真正的消息队列
下一篇【第69篇】Redis性能调优实战——从监控到参数调整的全套方案