★ FEATURED ARTICLE 1. 从一个“统计去重”需求说起为什么传统方案扛不住做后端时间长了总会碰到一类需求统计某个页面的独立访客数、某个关键词的独立搜索次数、某个活动页的独立点击用户数。说白了就是基数统计——一个集合里到底有多少个不重复的元素。刚入行的做法通常是拿一个Set或者HashSet往内存里塞来一个用户 ID 就add一次最后size()一下完事。数据量小的时候这招确实好用代码三行搞定。但问题在于一旦量级上来这套方案会瞬间崩掉。假设一个活动页一天有 500 万独立用户每个用户 ID 按 16 字节算比如 UUID 或者较长的字符串光存这些 ID 就要 5000000 × 16 字节 ≈ 76 MB。如果统计周期拉长到一个月或者同时维护几十个维度的统计内存直接爆炸。更别提如果用Set还要考虑去重时的哈希冲突、扩容 rehash 带来的性能抖动。那用位图Bitmap行不行如果用户 ID 是连续自增的整数位图确实是个好选择一个用户占一个 bit500 万用户也就 625 KB。但现实里用户 ID 往往不是连续的可能是雪花算法生成的 64 位长整型也可能是带前缀的字符串。这时候位图的空间会随着最大 ID 值线性膨胀一个 64 位 ID 就能把位图撑到 2^64 位完全不现实。所以问题的本质是在元素数量极大、元素本身占空间、且允许一定误差的前提下如何用极小的固定内存完成基数统计这正是 Redis 里 HyperLogLog 要解决的问题。Redis 从 2.8.9 版本开始引入 HyperLogLog把它封装成了PFADD、PFCOUNT、PFMERGE三个命令用 12 KB 的固定内存就能统计接近 2^64 个元素的基数标准误差只有 0.81%。这篇文章我就把 HyperLogLog 的实现原理、Redis 里的具体落地、参数计算、实操踩坑一次性讲透适合已经会用 Redis 但想搞明白底层原理的后端开发也适合准备架构面试的同学。2. HyperLogLog 到底是怎么“猜”出基数的2.1 从抛硬币说起概率估计的直觉要理解 HyperLogLog得先接受一个反直觉的事实它不存元素本身它只存元素的“特征”然后靠概率反推基数。这个思路最早来自 Flajolet-Martin 算法后来经过多次改进才有了 HyperLogLog。我用抛硬币来打个比方。假设你不停地抛一枚公平的硬币记录下“第一次出现正面”时抛了多少次。如果某次你抛了 10 次才出现正面那说明什么说明你运气不太好但更重要的是如果你做了很多组这样的实验出现“连续 10 次反面”这件事本身暗示你大概做了 2^10 1024 组实验。因为连续 k 次反面的概率是 1/2^k要观察到这个事件实验次数得达到 2^k 量级。HyperLogLog 就是把这个逻辑搬到了哈希上。对每个元素做一次哈希得到一个足够长的二进制串比如 64 位。然后看这个二进制串里“第一个 1 出现的位置”或者“末尾连续 0 的个数”。这个位置的数值越大说明这个哈希值越“稀有”也就暗示集合里的元素越多。单个元素的估计误差极大但如果把很多元素的估计值做一次调和平均误差就会被大幅拉平。2.2 分桶把一次估计变成多次估计只用一个哈希值估计基数方差大到没法用。HyperLogLog 的做法是分桶bucket把哈希值的高位拿出来当桶编号低位拿来做上述的“抛硬币”估计。假设用 14 位做桶编号就能分出 2^14 16384 个桶。每个桶独立维护一个“最大连续零个数”的寄存器最后把所有桶的值做调和平均再乘一个修正系数就得到基数估计。这里有个关键点桶的数量决定了精度也决定了内存。Redis 用的就是 16384 个桶每个桶的寄存器用 6 个 bit 存储因为最大连续零个数不会超过 646 bit 能表示 0~63。所以总内存是 16384 × 6 bit 98304 bit 12288 字节 12 KB。这就是那个“固定 12 KB”的由来。标准误差公式是 1.04 / √mm 是桶数代入 16384 得到 1.04 / 128 ≈ 0.008125也就是0.81%。2.3 稀疏与稠密Redis 的两种存储编码如果不管三七二十一一上来就分配 12 KB那对于只统计几十个元素的小场景就太浪费了。Redis 在这里做了一个很聪明的优化稀疏编码sparse和稠密编码dense自动切换。稀疏编码用一系列操作码来表示那些值为 0 或者值很小的寄存器比如连续多个 0 可以用一个字节表示这样在小基数时内存占用可能只有几百字节甚至几十字节。当稀疏编码的体积超过阈值默认hll-sparse-max-bytes是 3000 字节或者某个寄存器的值超过 32无法用稀疏格式表示Redis 就会自动把它转成稠密编码也就是固定的 12 KB。这个切换是自动的不需要你手动干预。但你要知道它的存在因为在做内存评估的时候小基数场景下 HyperLogLog 的实际占用远小于 12 KB而一旦基数涨上去就会稳定在 12 KB 左右。3. Redis 中 HyperLogLog 的核心命令与实操3.1 三个命令搞定所有操作Redis 把 HyperLogLog 封装得非常简单核心就三个命令命令作用时间复杂度PFADD key element [element ...]向指定 key 添加元素O(1) 每个元素PFCOUNT key [key ...]返回基数估计值O(1) 单 keyO(N) 多 key 合并PFMERGE destkey sourcekey [sourcekey ...]合并多个 HyperLogLogO(N)先看一个最基础的例子。假设我要统计某天某页面的独立访客# 添加几个用户 ID PFADD uv:20240501 user_1001 user_1002 user_1003 # 返回 1 表示基数发生了变化 # 重复添加同一个用户 PFADD uv:20240501 user_1001 # 返回 0 表示基数没变 # 查看当前基数估计 PFCOUNT uv:20240501 # 返回 3这里有个细节值得注意PFADD的返回值不是“添加成功”而是“基数是否发生了变化”。如果添加的元素之前已经存在或者哈希后落到了同样的寄存器状态它返回 0。这个特性可以用来做“是否是新用户”的粗判断但要注意它是概率性的不能当作精确的去重判断。3.2 PFCOUNT 的多 key 合并陷阱PFCOUNT支持一次传多个 key比如PFCOUNT uv:20240501 uv:20240502 uv:20240503这个操作会把多个 HyperLogLog 在内部合并后再计算基数得到的是并集的基数而不是各自基数之和。这一点非常容易搞错。很多人以为PFCOUNT k1 k2等于PFCOUNT k1 PFCOUNT k2实际上它算的是去重后的总人数。但这里有个性能坑多 key 的 PFCOUNT 是 O(N) 的而且会临时创建一个合并后的 HyperLogLog。如果你频繁对几十个 key 做 PFCOUNT性能开销不小。正确的做法是先用PFMERGE把结果合并到一个目标 key然后对目标 key 做单 key 的 PFCOUNT这样后续查询就是 O(1)。# 把三天的数据合并到周维度 PFMERGE uv:week uv:20240501 uv:20240502 uv:20240503 # 之后直接查周维度 PFCOUNT uv:week3.3 内存占用的实测观察我在测试环境做过一组实测用MEMORY USAGE命令观察不同基数下的内存占用基数规模编码类型内存占用100sparse约 200 字节1000sparse约 1.5 KB5000dense约 12 KB100000dense约 12 KB1000000dense约 12 KB可以看到一旦转成稠密编码内存就锁死在 12 KB 左右不管基数是 5000 还是 100 万。这就是 HyperLogLog 最迷人的地方——内存与基数解耦。当然代价就是那 0.81% 的误差以及无法判断某个元素是否真的存在。4. 底层实现拆解从哈希到寄存器更新4.1 哈希函数的选择HyperLogLog 的精度高度依赖哈希函数的均匀性。如果哈希函数分布不均匀某些桶会频繁被更新另一些桶永远是 0调和平均就会失真。Redis 用的是MurmurHash64A这是一个非加密哈希速度快、分布均匀非常适合这种场景。具体来说Redis 对每个元素调用MurmurHash64A得到一个 64 位哈希值然后低 14 位用来做桶编号index hash 16383高 50 位用来计算连续零个数实际上 Redis 会把高 50 位左移后再处理确保有足够的位数这里为什么用低 14 位做桶编号而不是高位因为 MurmurHash 的低位分布同样均匀而且位运算更快。这个选择不影响精度只是实现上的便利。4.2 寄存器值的计算拿到高 50 位后Redis 要计算的是“从最低位开始连续 0 的个数 1”。为什么是 1因为如果高 50 位全是 0连续零个数是 50但这种情况概率极低。加 1 是为了保证寄存器值至少为 1避免全零状态和“未初始化”混淆。用代码表示这个逻辑大概是// 伪代码示意 uint64_t hash MurmurHash64A(element, len, seed); uint32_t index hash 16383; // 低 14 位做桶编号 uint64_t bits hash 14; // 高 50 位 uint8_t count 1; while ((bits 1) 0 count 50) { count; bits 1; } // 用 count 去更新第 index 个桶的寄存器 if (count registers[index]) { registers[index] count; }注意这里用的是“取最大值”而不是累加。每个桶只记录它见过的最大连续零个数因为最大值才代表最稀有的那个哈希值才最有信息量。4.3 基数估计的修正最后一步是把 16384 个寄存器的值做调和平均然后乘修正系数。原始公式是E alpha * m^2 / sum(2^(-register[i]))其中 m 16384alpha 是一个常数约等于 0.7213 / (1 1.079/m)。但这个公式在基数很小或者很大的时候会有偏差所以 HyperLogLog 还引入了分段修正小基数修正当估计值小于 2.5m 时用线性计数法修正因为此时很多桶还是 0原始公式会高估。大基数修正当估计值接近 2^64 时用对数修正避免哈希碰撞导致的低估。Redis 的实现里把这些修正都封装好了你不需要手动算。但理解这些修正的存在能帮你明白为什么 HyperLogLog 在基数很小的时候反而不太准——因为那时候它还在用另一套逻辑。5. 误差、边界与常见问题排查5.1 误差到底有多大能不能接受0.81% 是标准误差意思是大约 68% 的情况下误差在这个范围内95% 的情况下误差在 1.62% 以内。实际测试中我用 10 万个真实不重复 ID 做验证PFCOUNT返回的结果通常在 99000 到 101000 之间波动偶尔会到 98500 或 101500。这个精度对于 UV 统计、搜索词统计这类场景完全够用但如果你要做精确的计费或者对账那就不能用它。注意HyperLogLog 的误差是概率性的不是固定偏差。同样的数据在不同时间、不同 key 上可能得到略微不同的结果这是正常现象不是 bug。5.2 为什么 PFADD 返回 0 但基数其实变了前面说过PFADD返回的是“基数是否变化”。但有一种情况新元素的哈希值更新了某个寄存器但那个寄存器的值本来就已经更大所以实际存储状态没变PFADD返回 0但基数其实增加了。反过来如果新元素的哈希值让某个寄存器变大PFADD返回 1但基数估计值可能因为调和平均的平滑效果而没有明显变化。所以不要用 PFADD 的返回值做精确的新增判断它只是一个“可能发生了变化”的信号。5.3 常见问题速查表问题现象可能原因解决思路PFCOUNT 结果比实际大很多小基数下修正未生效或哈希碰撞检查基数是否小于 100小基数建议用 Set内存占用突然从几百字节涨到 12 KB稀疏转稠密正常现象可通过hll-sparse-max-bytes调整阈值PFMERGE 后结果异常源 key 不是 HyperLogLog 类型用TYPE命令确认 key 类型多 key PFCOUNT 很慢每次都在做合并计算改用 PFMERGE 预合并删除元素后基数没变HyperLogLog 不支持删除只能重建 key这是设计限制5.4 几个容易踩的坑第一个坑把 HyperLogLog 当 Set 用。有人看到PFADD和SADD长得像就以为可以混用。实际上 HyperLogLog 不支持判断元素是否存在也不支持删除单个元素。如果你需要这些能力老老实实用 Set 或者布隆过滤器。第二个坑对同一个 key 频繁 PFMERGE。PFMERGE会覆盖目标 key 的内容。如果你把 A 合并到 B再把 C 合并到 BB 里就是 A∪C 的结果。但如果你不小心把 B 合并到了 A那 A 的数据就被覆盖了。合并前一定要确认目标 key 是不是你想要的那个。第三个坑忽略 key 的过期时间。HyperLogLog 的 key 和普通 key 一样可以设置EXPIRE。做日维度统计时记得给每天的 key 设置合理的过期时间否则 Redis 里会堆积大量 12 KB 的 key时间长了内存也会被吃掉。6. 生产环境中的组合玩法与选型建议6.1 UV 统计的标准姿势最常见的用法就是 UV 统计。我的建议是按天建 key按需合并# 用户访问时 PFADD uv:page:1001:20240501 user_id # 查当天 UV PFCOUNT uv:page:1001:20240501 # 查本周 UV先合并再查 PFMERGE uv:page:1001:week uv:page:1001:20240501 uv:page:1001:20240502 ... PFCOUNT uv:page:1001:weekkey 的命名建议带上业务标识、页面 ID、时间维度方便管理和批量清理。过期时间可以设成统计周期的 2 到 3 倍比如日 key 设 7 天过期周 key 设 30 天过期。6.2 和 Bitmap、Set 的选型对比方案内存精度支持删除支持判断存在适用场景Set随基数线性增长精确支持支持小基数、需精确Bitmap随最大 ID 增长精确支持支持ID 连续且范围可控HyperLogLog固定 12 KB0.81% 误差不支持不支持大基数、允许误差选型的核心判断就两条基数大不大能不能接受误差。基数超过 10 万且允许误差闭眼选 HyperLogLog基数小或者要精确用 SetID 是连续整数且范围明确Bitmap 最省。6.3 一个容易忽略的优化合并时机如果你有多个维度的统计需要合并比如“按页面 按地区 按渠道”不要每次查询都实时合并。正确的做法是在数据写入时或者定时任务里预合并把常用的组合维度提前算好。比如每小时把当小时的 HyperLogLog 合并到日维度每天把日维度合并到周维度。这样查询时永远是单 key 的 O(1) 操作响应时间稳定在毫秒级。6.4 监控与容量规划虽然单个 HyperLogLog 只占 12 KB但如果你有 10 万个统计维度那就是 1.2 GB。所以容量规划不能只看单个 key。我的经验是先估算维度数量再乘以 12 KB最后留 30% 的余量。同时监控used_memory和 key 的数量增长趋势设置合理的过期策略避免冷数据长期占用内存。另外PFCOUNT虽然是 O(1)但在高并发场景下如果 QPS 很高也会占用 CPU。可以考虑在应用层做一层短时间的本地缓存比如同一个 key 的 PFCOUNT 结果缓存 1 秒能挡掉大量重复查询。7. 我个人在实际操作中的几点体会HyperLogLog 这个数据结构刚接触的时候觉得它很“玄学”——不存数据还能算基数误差还这么小。但把原理拆开之后会发现它的每一步都是扎实的概率论和工程取舍。Redis 把它封装成三个命令用起来几乎没有门槛但真正用好需要理解它的边界。我踩过最深的坑是在一个小基数场景下用 HyperLogLog 统计结果发现误差比预期大得多。后来才明白基数小于 100 的时候稀疏编码和线性计数修正还没完全生效这时候反而不如直接用 Set。所以我的建议是基数预期超过 1000 再用 HyperLogLog低于这个量级别给自己找麻烦。还有一个体会是关于PFMERGE的。早期我做周维度统计时每次查询都实时合并 7 个日 keyQPS 一高就明显卡顿。后来改成定时任务预合并查询性能直接提升了一个数量级。这个优化不复杂但效果立竿见影值得每个用 HyperLogLog 的人注意。最后分享一个小技巧如果你需要同时统计 UV 和 PVPV 用普通的INCR计数器UV 用 HyperLogLog两者分开存储。不要试图用 HyperLogLog 去算 PV它做不到也不该做。工具用对地方才能发挥最大价值。
阅读完成 · 觉得有帮助？
