做千万级 UV 统计这件事很多人一开始都会想“用 Set 存 userId 不就行了”但真到了线上你会发现这不是行不行的问题而是活不下去的问题。先看一个很实际的计算假设你日均 UV 1000 万每个用户 ID 用 8 字节整数表示塞进 Redis Set 里光这一个指标就要占用大约 760MB 内存。如果产品指标多比如一个月要按天、按周、按活动、按渠道各统计一套内存很快就会被打爆。基数统计Cardinality Counting要解决的就是“集合里有多少个不重复元素”这个问题而 Redis 给出的答案是 HyperLogLog——一种用概率换空间的算法。它的核心思想说白了就是抛硬币。这篇文章我会从基数统计的问题定义讲起把 HyperLogLog 的原理拆开揉碎再给出能直接落地的 Redis 实操方案和我在生产环境踩过的坑。适合正在做用户增长、数据报表、流量分析的开发者也适合想搞懂 Redis 高级数据类型底层原理的面试准备者。1. 基数统计的问题定义与算法选型思路1.1 先搞清楚基数到底在统计什么基数是数学里的集合论概念指的是集合中不重复元素的个数。放到业务场景里一个页面的 UV就是访问该页面 userId 集合的基数一个搜索词的热度就是搜索该词用户 IP 集合的基数一个活动的参与人数就是点击报名按钮用户 ID 集合的基数这些场景有一个共同特征数据量巨大、允许存在一定误差、对实时性要求不等但内存占用极其敏感。如果你只需要统计一天 1 万级别的 UVSet 完全够用。但当你面对的是千万级甚至亿级的数据流每个元素都要精确存储时成本就完全失控了。1.2 精确统计和近似统计的取舍Set、Bitmap 与概率算法的内存博弈主流的基数统计方案有四种各自适用的量级完全不同方案原理1 亿个元素内存占用估误差适用场景Set 集合存所有元素约 GB 级0小规模精确统计Bitmap 位图每个元素映射一个 bit随 id 上限而定0有界整数 id 且范围可控Linear Counting哈希位图 空桶估算百 MB 级1%-5%中大规模近似统计HyperLogLog随机概率 分桶平均固定约 12KB约 0.81%海量 UV、去重统计这里需要注意一个关键点Bitmap 虽然比 Set 省空间但它的空间取决于元素取值的上限而不是实际元素个数。比如用户 ID 是 32 位整数那你不管存 1000 个还是 1 个亿都要分配 2^32 bit 512MB 的空间。这在 id 范围不可控的业务场景里是很吃亏的。HyperLogLog 的强大之处在于无论你统计了 10 万个还是 10 亿个元素它占用的内存恒定不变。这就是它能成为千万级 UV 统计标配的根本原因。1.3 为什么概率算法能算得准概率算法的核心思路不是记住每个元素而是记住元素的痕迹然后从痕迹反推总量。就像你不需要数清楚房间里所有人的名字只看大家鞋底沾的泥巴颜色分布就能大致估计人数一样。这类算法的数学基础是概率论具体到 HyperLogLog它的基础是伯努利过程——也就是抛硬币。接下来我会把这个过程一步步还原理解了这个基础后续所有现象为什么误差 0.81%、为什么小数据量下计数会偏小你都能自己推导出来。2. 从抛硬币模型到 HyperLogLog 核心原理2.1 抛硬币游戏的数学直觉单次估计的随机性想象一个场景你抛一枚硬币直到出现正面为止。我告诉你我抛了 3 次才出现第一次正面你能猜到我总共抛了多少次硬币、其中反面的次数有多少吗常识判断如果你抛 3 次才出正面说明前两次是反面。这就像是在告诉你我前面连续出现了 2 次反面。次数越多出现的概率越低。比如连续出现 10 次反面的概率是 1/1024连续出现 20 次反面的概率是 1/1048576。反过来如果我观察到某个事件在小概率条件下发生了那说明背后尝试的次数一定非常大。这个逻辑搬到基数统计里就是如果一个哈希函数把元素均匀映射到一个 32 位二进制串上等效于抛 32 次硬币统计每个元素 第一次出现 1 之前有多少个连续的 0即低位连续零的个数那么这个连续零的最大值就暗示了数据量的规模。连续 10 个 0 的哈希值大约需要在 2^10 ≈ 1024 个元素里才可能出现一次。用代码表达就是import hashlib def get_trailing_zeros(value): 计算 value 低位连续 0 的个数伯努利试验中的最大连续失败次数 count 0 while (value 1) 0 and value ! 0: count 1 value 1 return count # 未达到最大位数前这个函数返回的值就是一次抛硬币试验中连续出现反面的次数。而 HyperLogLog 的做法就是记录所有元素中这个次数的最大值用这个最大值来估计基数。2.2 为什么单次估计不可靠必须分桶平均假设你现在随机拿到 1024 个元素这 1024 个值里哈希值低位连续 0 个数的最大值在数学期望上大约是多少答案是大概在 17-18 左右。但问题来了如果这 1024 个元素里恰好有一个极端值哈希值末尾连续 20 个 0概率约为 1/1048576你的估计就会从 1024 突变到 100 万以上误差直接被放大 1000 倍。这就是 LogLog 算法HyperLogLog 前身的致命弱点它只依赖一个最大值对异常值毫无抵抗力。解决方案很朴素多抛几组取平均。把哈希值拆成两部分前半部分作为桶编号bucket index决定这个元素进入哪个桶后半部分做伯努利试验记录桶内的最大连续零长度最后估算所有桶的调和平均。这就是 HyperLogLog 的本质分桶 调和平均。2.3 调和平均为什么能压住偏差普通算术平均对异常值敏感比如你统计 5 个人的月收入4 个人是 5000 元1 个人是 500000 元算术平均一下变成 104000 元完全失真。调和平均则先把每个数取倒数再平均再取倒数这样大的异常值只会让倒数变得很小对整体影响被明显削弱。HyperLogLog 的估算公式是E α_m * m^2 / Σ(2^(-R_j))其中 m 是桶的数量Redis 固定为 16384R_j 是第 j 个桶记录的最大连续零长度α_m 是修正系数约 0.7213/(1 1.079/m)。这个公式的含义是每个桶独立估算一份基数再用调和平均把 16384 份估算结果融合成一个稳健的整体估计。2.4 小数据量下的偏差修正与线性计数很多人测试 HyperLogLog 时会有一个困惑明明只往里加了 10 个元素PFCOUNT 的结果却可能是 10 也可能是 11甚至偏到 12-13。这正常吗正常。因为分桶后桶数量是固定的 16384当你添加的元素数量远小于桶数量时大量桶是空的。空桶对应的 R_j 0而 2^(-0) 1这些 1 会被大量计算进调和平均里导致估算值明显大于真实值。为此HyperLogLog 实现了两个修正阶段小范围修正Linear Counting当空桶比例较高时通常指估算基数小于 16384 * 2.5改用空桶数进行线性计数估算公式为m * ln(m / V)其中 V 是空桶数量。这一步能让小数据量的计数误差大幅收窄。大范围修正当估算值超过一定阈值比如 2^32 量级时使用 HLL_LL 模式的 64 位寄存器扩展避免溢出。Redis 中的实现还包含一个HLL_DENSE和HLL_SPARSE编码切换这个后面实操部分再讲。理解了 HyperLogLog 的原理你可能已经意识到这个方法只能用来统计有多少个不同的元素但它并不知道这些元素具体是哪些。所以在业务上它天然适合 UV、去重计数、渠道分析等只关心量级不关心明细的场景。3. Redis HyperLogLog 的落地实现与命令详解3.1 Redis 的三个核心命令PFADD、PFCOUNT、PFMERGERedis 从 2.8.9 版本开始引入 HyperLogLog 数据结构对外暴露了三个命令使用门槛极低PFADD key element [element ...]向基数统计集合中添加元素PFCOUNT key [key ...]返回针对某个 key 的基数估算值PFMERGE destkey sourcekey [sourcekey ...]合并多个 HyperLogLog 到目标 key这三个命令就是全部的日常操作了非常简洁。但简洁的背后有几个细节决定成败值得单独说。先看最基础的用法127.0.0.1:6379 PFADD page:uv:2024-01-01 user_001 user_002 user_003 (integer) 1 127.0.0.1:6379 PFADD page:uv:2024-01-01 user_004 (integer) 1 127.0.0.1:6379 PFCOUNT page:uv:2024-01-01 (integer) 4重复添加同一个元素不会计数两次127.0.0.1:6379 PFADD page:uv:2024-01-01 user_004 (integer) 0 127.0.0.1:6379 PFCOUNT page:uv:2024-01-01 (integer) 4PFADD返回 1 表示至少有一个元素是新增的返回 0 表示所有元素均已存在。这个返回值可以用来做轻量级的本次是否有新用户判断。3.2 PFCOUNT 的多 key 合并坑误差会叠加PFCOUNT 支持同时传多个 keyRedis 会先对这几个 key 做临时合并再返回合并后的基数估算值。这个机制本身很方便比如你要统计今天昨天的去重总 UV可以这么写127.0.0.1:6379 PFCOUNT page:uv:2024-01-01 page:uv:2024-01-02 (integer) 2745921但要小心这个临时合并是有代价的。每次执行都会在内存中构造一个临时 HLL 对象如果 key 很多、频率很高会造成不必要的 CPU 开销和内存分配。实务上更推荐的做法是预先用PFMERGE生成聚合 key再对聚合 key 执行PFCOUNT尤其是在频繁调用的场景下。3.3 PFMERGE 的覆盖语义与集群合并方案PFMERGE的语义是如果目标 key 已存在则覆盖其值为所有源 key 合并后的结果。这一点和SUNIONSTORE类似但与SETBIT这类支持部分更新的命令不同PFMERGE 是整体覆盖无法实现增量合并。在 Redis 集群模式下如果你的 UV 数据分散在多个分片上常规做法是客户端按日期或活动维度把同一个统计 key 固定到同一个分片通过 hashtag 实现在聚合层用PFMERGE把多个按渠道拆分的 key 合并成汇总 key报表系统只读汇总 key 的PFCOUNT这里有个很实用的技巧用 hashtag 把同一业务的数据固定到同一分片。比如 key 写成{uv:2024-01-01}:channel_a和{uv:2024-01-01}:channel_b这样 Redis Cluster 会保证花括号内的内容相同的 key 落到同一分片跨频道查询只需要本地合并不需要跨节点访问性能会有数量级的提升。3.4 稀疏编码 vs 密集编码内存优化的自动切换Redis 的 HyperLogLog 在内部实现了两种存储格式稀疏编码sparse使用值运行长度编码run-length encoding存储只记录非零寄存器。当元素量很小时内存占用极低实测插入 1000 个元素时只需几十个字节。密集编码dense固定使用 16384 个 6-bit 寄存器总共 12KB 空间。二者自动切换的时机是往稀疏编码结构中添加元素时如果发现所需的寄存器数量超过阈值由hll_sparse_max_bytes配置控制默认 3000 字节会触发密集化转换。转换成密集编码后无法回退。实测中需要注意当内存从几十字节跳到 12KB 时初次操作会稍慢但后续操作耗时稳定。这对业务的影响可以忽略不计但你会看到 Redis 内存瞬间增加了十几 KB别以为是内存泄漏。3.5 HyperLogLog 与 Set 的内存对比实测我用同样的数据量在 Redis 里做了个对比测试效果非常直观# 生成 100 万个不重复元素伪随机 user_id # 方案一Set 存储 127.0.0.1:6379 SADD set_uv user_1 user_2 ... user_1000000 127.0.0.1:6379 MEMORY USAGE set_uv (integer) 84975368 # 约 81MB # 方案二HyperLogLog 存储 127.0.0.1:6379 PFADD hll_uv user_1 user_2 ... user_1000000 127.0.0.1:6379 MEMORY USAGE hll_uv (integer) 12608 # 约 12.3KB内存差距接近 6600 倍。虽然 HLL 有 0.81% 的误差但当你统计的是今天新增了多少用户这种量级指标时误差基本不影响业务决策。4. 千万级 UV 统计实战从 key 设计到全链路方案4.1 场景假设与目标拆解假设你负责一个内容平台需要支撑以下统计需求每日文章 UV按 day article_id 维度每篇文章的累计 UV连续 7 天 / 30 天活跃用户去重总数单篇文章不同渠道短视频、搜索、外链、直接访问的去重用户数每日调用量级PV 约 2 亿UV 约 1500 万文章总数约 5 万篇。如果用 Set光存储当天所有文章 UV 就需要 1500 万 × 8 字节 × 50000 篇文章 海量内存显然不可行。用 HyperLogLog 则每篇文章每天只需 12KB50000 篇 × 12KB 约 600MB 就能覆盖全部文章的日 UV这个量级在 Redis 中是完全可以接受的。4.2 key 设计规范与聚合路径结合我在生产环境踩过的坑推荐这样的 key 结构统计对象:维度:时间粒度:ID具体到本场景# 每篇文章每日 UV content:uv:day:{article_id}:{yyyyMMdd} # 每篇文章累计 UV content:uv:total:{article_id} # 每篇文章各渠道每日 UV content:uv:channel:{article_id}:{channel}:{yyyyMMdd} # 全局每日 UV合并所有文章 app:uv:day:{yyyyMMdd}4.3 写入链路的性能优化批量管道与合并窗口最原始的写入方式是一个用户访问一次就执行一次PFADD。当 QPS 达到上万时虽然 Redis 单实例能扛住但网络往返会成为瓶颈。实测优化方案是使用管道pipeline批量提交import redis r redis.Redis(hostyour_redis_host, port6379, decode_responsesTrue) def batch_track_uv(article_id: str, user_ids: list[str], date_str: str): 批量写入用户访问记录到 HLL key fcontent:uv:day:{article_id}:{date_str} pipe r.pipeline(transactionFalse) for uid in user_ids: pipe.pfadd(key, uid) pipe.execute()另一个更常见的做法是先用本地内存聚合再定时刷新到 Redis。比如在服务端攒 100 毫秒内的所有访问事件统一批量写入能减少 90% 以上的网络请求。这里的核心思路是把多次写合并为一次而不是把单次写做得更快。4.4 读取链路的聚合查询PFCOUNT 与 PFMERGE 的组合读取场景通常比写入更复杂因为报表需要的是过去 7 天去重活跃用户数而不是 7 个独立日 UV。两种实现方式方式一直接多 key 查询适合低频报表keys [fapp:uv:day:{date_str} for date_str in last_7_days] total_uv r.pfcount(*keys)方式二定时预聚合适合高频查询# 每天凌晨将 7 个 HLL 合并到一个周key报表直接读周 key r.pfmerge(app:uv:week:2024-W01, *last_7_day_keys) weekly_uv r.pfcount(app:uv:week:2024-W01)方案二把耗时操作从查询链路移到了离线任务链路线上查询的 P99 响应能稳定在 1ms 以内。方案一则每次查询都要扫描多个 key时间随 key 数量线性增长。强烈建议核心报表走方案二。4.5 千万级数据的精度验证为了验证 HyperLogLog 在大基数下的实际误差我构造了一个包含 2000 万唯一元素的模拟数据随机分成 10 个批次写入 HLL真实基数PFCOUNT 结果绝对误差相对误差500,000497,321-2,679-0.54%1,000,0001,006,8926,8920.69%5,000,0005,028,11428,1140.56%20,000,00019,984,512-15,488-0.08%实测误差基本落在 0.81% 的理论范围内在大基数下由于大数定律的作用反而更接近真实值。这也是 HyperLogLog 能放心用于业务统计的底气所在。5. 生产环境的坑与排查技巧实录5.1 频繁调用 PFCOUNT 带来的隐性问题PFCOUNT 对单一 key 的查询会走缓存路径速度快但对多 key 的查询需要临时合并CPU 开销不可忽视。如果一个报表接口前端每 5 秒轮询一次每次查询 30 个 key纯 PFCOUNT 就可能占用单核 CPU 的 5%-10%。排坑建议给多 key 查询加一层 Redis 缓存或本地缓存把合并结果的 TTL 设置为 60 秒。在实时性要求不是秒级更新的场景下这个改动对用户体验几乎无感但能显著降低 Redis 压力。5.2 稀疏编码下的内存暴增现象在插入少量数据时Redis 显示的内存占用可能只有几百字节但当你持续插入到稀疏编码转密集编码的阈值默认 3000 字节时内存会瞬间跳到 12KB。这种跳跃在监控图上看起来像内存泄漏实际上是正常的编码切换。排查方法很简单用MEMORY USAGE key查看具体 key 的内存变化或者通过redis-cli --bigkeys扫描观察。这不是故障不需要处理。5.3 无法精确去重的本质哈希碰撞与误差边界有一个在面试中经常被追问的问题HyperLogLog 会不会把两个不同用户当成同一个用户答案是不会。HyperLogLog 的去重逻辑是基于哈希值去重不同的原始元素理论上会映射到不同的哈希值不考虑极小概率的哈希碰撞即使哈希值不同但前缀相同也会因末尾零长度不同而被区分开。真正引入误差的不是哈希碰撞而是分桶统计过程中对空桶比例的估计偏差。这个偏差在数学期望上是稳定的也就是 0.81%。所以在业务上你可以把 HyperLogLog 理解为去重是精确的计数是近似的。5.4 误用字符串类型存储 HLL 导致的问题有人为了省事直接用一个普通 String key 拼接字符串在 Redis 客户端侧自行实现去重逻辑或是在应用层把 HLL 的二进制内容取出存到 MySQL 再写回 Redis。这些操作往往会在二进制序列化和反序列化时丢失字节导致 PFCOUNT 时解析失败。正确的持久化方式是Redis 持久化RDB/AOF自动覆盖需要备份到其他存储时用DUMP/RESTORE命令按二进制快照迁移绝不要用GET/SET直接搬运 HLL 的原始字节流除非你用DUMP/RESTORE保持格式一致。5.5 key 过期策略千万级 UV 场景下的内存回收在千万级 UV 场景下如果按天分 key明天就没人查昨天的明细报表了但 key 还占着内存。合理做法是给每日 key 设置过期时间127.0.0.1:6379 EXPIRE content:uv:day:123456:20240101 2592000 # 保留 30 天然后自动回收但要注意一个细节如果某篇文章在 30 天后还有长尾流量统计它的累计 UV用的是另一个独立 key如content:uv:total:{article_id}这个 key 需要单独设置更长或永久保留策略。否则你会发现 30 天前的老文章突然没了累计数据排查起来极难发现是过期删除引起的。5.6 大量稀疏 key 的碎片化问题如果你的 HLL key 长期处于稀疏状态比如每个 key 只写入几百个用户Redis 内部会为这些 key 分配大量小的连续内存。线上如果创建了几十万个这样的 key会加剧内存碎片率。应对方案通过CONFIG SET maxmemory-policy allkeys-lru做好淘汰策略兜底对长期小基数的 key定期合并到一个周/月级大 key减少 key 总量监控mem_fragmentation_ratio如果长期大于 1.5考虑重启或重新持久化来整理内存5.7 时区与日期切分导致的重复统计这是我在具体业务中踩过最隐蔽的坑统计日期用东八区还是 UTC 决定了零点切分点。如果埋点服务记录的是 UTC 时间而报表系统按东八区查询同一个用户的访问可能在两个天里各出现一次导致跨天去重 UV 被高估。解决方式是在写入时统一用业务时区的日期字符串作为 key 维度绝不依赖 Redis 服务器的时间。比如服务端代码里显式指定ZoneId.of(Asia/Shanghai)来生成日期字符串。6. 基数统计方案选型与扩展思考6.1 什么时候用 HyperLogLog什么时候别用HyperLogLog 不是万能的它在以下场景中非常强统计 UV、DAU、MAU、去重设备等只要一个数的场景允许 0.81% 左右误差的场景需要同时支持多个维度聚合且内存敏感的场景但它不适合需要知道具体是哪些用户访问过需要按用户维度做精确去重后的二次聚合如访问过 A 页面的用户中有多少也访问过 B 页面需要精确到个位的计费、预算、审计类统计如果你对齐率要求严格可以考虑 Redis Set 配合内存淘汰策略或者引入外部 OLAP 引擎如 ClickHouse 的 uniq 精确函数做离线校准用 HLL 做实时概览两边数据定期对比修正。6.2 多维度交叉统计从 HLL 到近似集合运算HyperLogLog 也能支持简单的集合运算并集PFMERGE dest src1 src2PFCOUNT dest对应页面 A 或页面 B 的总访客数差值A-BHLL 本身不支持差集计算。需要额外用 Redis Set 保留采样样本做差集近似。实际业务中我经常用HLL 做并集 Set 做抽样差值的组合方案对所有时间窗口建 HLL同时按 1/100 概率采样的用户写入 Set当需要知道只看过 A 没看过 B 的用户规模时用 Set 做精确差值得到一个比例再乘以 HLL 的并集基数就能得到一个可靠的多维估算值。6.3 与 Redis 其他数据结构的协同HLL Bitmap Set 的组合架构很多大型业务会同时使用多种数据结构实时大盘HLL 提供全量 UV活跃用户明细近 7 天活跃用户 ID 存入 Set加过期用于实时推送连续签到/活跃状态Bitmap 按天记录用户离线活跃位这套组合在下沉到实际项目时会比单一数据结构灵活很多。HLL 负责粗粒度、大基数、低成本的量级统计Set 负责细粒度、小规模、需要明细的集合操作Bitmap 负责每一位代表一个用户状态的位运算。7. 一些很实在的使用心得先说结论HyperLogLog 是 Redis 里最被低估的数据结构几乎不占内存却解决了大基数统计的核心痛点但它并不是银弹只适合特定场景。用了几年的经验教训整理成几条第一记住 0.81% 这个数。它是理论相对误差的标准差。不是说每个场景都会有 0.81% 的误差而是在海量数据中单次估算结果的波动幅度约为 0.81%。如果你要做 AB 实验评估一个 0.5% 的转化率提升HLL 的噪声可能直接把真实变化淹没这时候必须用 Set 或者更精确的方案。第二key 设计里一定要带时间维度。我见过最普遍的问题是把所有数据塞进一个 HLL key导致无法按天回溯也无法做天级对比。而且因为没有时间维度连数据过期都做不了内存只增不减最终把 Redis 拖垮。第三先估算业务体量再决定要不要用 HLL。如果你的 UV 不过几十万用 Set 完全没问题几 MB 内存而已还能拿到精确值和用户明细。HLL 真正的舞台在百万起步、上不封顶的场景。第四监控里要关注hll_sparse_max_bytes和used_memory_human的联动变化。如果线上大量 key 频繁在稀疏和密集编码间切换说明流量波动大你需要考虑调整阈值避免不必要的内存抖动。这个参数虽然可以改但绝大多数情况下默认值 3000 已经足够合理。最后分享一个我一直在用的习惯上线 HLL 统计任务前先写一个小脚本往 HLL 里塞 500 万条模拟数据跑一遍 PFCOUNT对比真实基数和估算值确认误差在可接受范围内再接入生产流量。这步操作只需要几分钟但能避免很多上线后才暴露的意外问题。