HyperLogLog如何在亿级UV统计中把内存从7GB降到12KB？-北京尧图网络

1. UV统计到底难在哪先算一笔存储的账很多人一提UV统计下意识就是“用Set去重不就行了”。我早期也是这么干的当时日活还只是百万级一个Set装下所有用户IDRedis里跑得还算欢快。直到有一次业务做活动预热预估峰值UV要到一亿我按现网的数据结构粗算了一下内存当场就放弃了Set方案。这笔账值得仔细算给大家看。1.1 为什么UV统计不能靠计数器UV和PV最大的区别在于PV是加法服务端每收到一次请求就1这个太简单了UV要求同一个用户只能算一次。如果直接拿访问日志去数日志里同一个用户一天可能访问几十次你怎么知道哪些是同一个人所以UV统计的本质是一个基数去重问题英文叫Cardinality Counting。要去重就得“记住”已经来过的用户。怎么记这就引出了下面两种思路精确去重和概率估算。精确去重就是HashSet、Redis Set、Bitmap、数据库唯一索引这一派概率估算就是以HyperLogLog为代表的一派。两者本质上是内存换精度的取舍。那为什么不能总是用精确去重因为当基数大到一定程度精确去重的内存开销是指数级增长的而你为了这个“精确到个位数”的UV指标可能要付出几个G的内存成本。现实是几乎没有任何业务需求要求UV必须精确到“1000000”和“1000001”这两个数之间做区分。1.2 一亿用户的HashSet和Bitmap方案到底要多少内存为了说服团队我当时真的做了两组内存估算。方案ARedis Set / HashSet直接存用户ID假设用户ID是UUID或者一串36字节的字符串。Set底层是哈希表除了存原始字符串本身还要存dictEntry结构包含指针、哈希值等信息。粗略算下来单个元素的整体开销在60到80字节之间我一般按70字节左右做估算。如果UV是1亿那就需要100,000,000 × 70 ≈ 7,000,000,000 字节 ≈ 7GB这只是纯内存已经不小了。问题是UV是会涨的翻个倍就是14GB一次大促活动就要扩容运维和成本都很难受。方案BBitmap / 位图Bitmap的好处是每个用户只占1个bit位内存公式是(用户总量/8) 字节如果是1亿用户Bitmap只需要约12MB看起来非常完美。但这里有个前提用户ID必须能映射到一个连续且足够紧凑的整数空间。比如数据库自增ID并且你的用户ID是从1排到一亿的很连续那Bitmap很合适。但如果用户ID是36字节的UUID或者是手机号、设备号这种本身不规则的标识你要怎么确定它对应哪一位你只能把可能出现的所有位都分配好。假设哈希成64bit的整数那就需要2^64个bit位换算一下是2EB级别的内存直接把集群吃穿都不够。所以结论很清晰当标识符是不规则的海量字符串时精确去重方案要么内存爆炸要么位空间不可控。这正是HyperLogLog登场的时机。1.3 概率估算为什么可以“蒙”出结果HyperLogLog的核心逻辑是我不记“谁来过”我只记“来的人里面有没有出现过某种特征”。这种特征在数学上能反过来估算出整体的规模。它给出的结果不是精确值而是一个置信度极高的近似值误差在0.81%左右。听上去很玄乎但后面我会用原理和实测数据解释为什么这个误差率在工程上是完全可以接受的。很多架构师一听到“近似”就摇头觉得不严谨。但在UV统计这个场景里0.81%的误差换来的是从7GB降到12KB的内存这个账怎么算都划算。接下来我们就从原理层面拆一拆这台“概率估算机器”内部到底是怎么工作的。2. HyperLogLog核心原理抛硬币实验和分桶平均先说个反直觉的事实在超大规模基数统计上精确往往不是第一需求可控的误差率才是。HyperLogLog之所以能以极小的内存估算出任意规模去重后的数据量靠的是两个核心思想一个叫“概率抽样中的极值推断”另一个叫“分桶平均消除噪声”。2.1 抛硬币实验最长零串的长度暗示了总数假设你在抛硬币正面记为1反面记为0。你抛了很多轮每轮结束后记录“这一轮最多连续出现了多少个反面”。如果某一轮出现了连续5个反面你可以粗略猜测这一轮硬币至少抛了2^532次。为什么因为连续出现5个反面的概率约是1/32如果总数远远小于32出现这种连续5个反面的概率就很低。这就是LogLog算法的核心原型用“最长一串特征”推断总量级。应用到UV场景我们要给每个用户取指纹一般做法是对UserId做一次哈希得到一个足够均匀的bit串。哈希后的bit串可以看成“随机抛硬币的结果”。具体操作是取哈希值的一部分做桶号分桶其余部分的“低位连续零个数”作为特征值记录下所有桶里出现过的最大零串长度。零串越长说明样本量越大的概率越高。哲学上讲就是“群体中出现过的极端个体间接暴露了群体的规模”。2.2 分桶和调和平均从“可能偏差”到“稳定估算”只用一个桶、依赖最大零串长度方差太大可能采样不巧某次很快就出现了一个很长的零串导致估算值直接翻倍。正是因为这个原因直接照搬LogLog算法的人会发现结果忽高忽低非常不稳定。HyperLogLog的改进点在于“多桶平均”。假设把哈希值的前14位作为桶号能分出16384个桶每个桶独立计算最大的零串长度汇总时使用调和平均而不是算术平均。调和平均对异常大值不敏感比算术平均更能反映整体水平。估算公式类似估算值常数 × 桶数^2 / Σ(2^(-每个桶的记录值))我记忆这个公式的一个技巧是把它想成“倒过来算平均数”先算每个桶“代表”的量级再倒推总量最后乘一个经验校准系数。这样即使某几个桶出现极端值它们对最终结果的影响也只是局部的不会让整体估算爆炸。2.3 为什么误差率固定跟基数大小无关HyperLogLog的误差来源是“采样噪声”而采样噪声受桶数影响。桶数越多统计越稳。Redis取的是16384个桶每个桶记一个6bit的数字总内存就是16384 × 6 bit 98304 bit ≈ 12KB理论上它的标准误差是1.04/sqrt(桶数)带入163841.04 / sqrt(16384) ≈ 1.04 / 128 0.81%这意味着无论你的UV是1万还是1亿统计结果大概都会落在真实值左右0.81%这个标准差范围内。绝大多数场景下没有人能感知这个级别的误差波动而12KB的内存是恒定的不会因为用户量增长而变化。这是它最迷人的地方。我也遇到过朋友问“那为什么实际测下来误差有时候超过1%”这里要注意0.81%是标准差不是绝对上限。个例落在±2%甚至±3%区间是有可能的尤其当基数特别小时误差比例感知上会更明显。3. Redis里的HyperLogLog从命令到底层机制的完整实践理论归理论落地还是要看工具。Redis在高版本里原生支持HyperLogLog总共就三个命令PFADD、PFCOUNT、PFMERGE。API设计极其简洁但坑也藏在“简洁”背后。如果不了解底层存储结构你可能会在几个看似不大的选择上吃亏。3.1 三个命令的基本用法先看最基本的写入和查询# 添加元素返回1表示HyperLogLog内部存储发生了变化 127.0.0.1:6379 PFADD uv:2024-06-01 user_1001 user_1002 user_1003 (integer) 1 # 统计该key的基数近似值 127.0.0.1:6379 PFCOUNT uv:2024-06-01 (integer) 3 # 继续添加已存在元素内部存储无变化则返回0 127.0.0.1:6379 PFADD uv:2024-06-01 user_1001 (integer) 0 # 合并多个key结果写入目标key 127.0.0.1:6379 PFMERGE uv:week1 uv:2024-06-01 uv:2024-06-02 uv:2024-06-03 OK 127.0.0.1:6379 PFCOUNT uv:week1 (integer) 6PFADD支持一次性传入多个元素内部会对每个元素做哈希并更新对应的桶PFCOUNT传入单个key时走的是HyperLogLog内部缓存计数速度很快传入多个key时相当于临时把这些key合并成一个虚拟的HyperLogLog再统计开销会明显上升。这个差异在监控报表场景里很容易踩雷。我见过有人写了一个定时任务每分钟对三十个天级key执行一次PFCOUNT key1 key2 ... key30目的是看月活趋势。结果Redis CPU飙升。问题就出在传入多key的PFCOUNT并不会帮你保存合并结果它每次都在请求里临时做一次合并计算。正确做法是先PFMERGE一次再对合并结果PFCOUNT或者干脆把合并结果缓存到一个固定key里。3.2 底层存储稀疏存储和密集存储的切换Redis的HyperLogLog底层不是一上来就用12KB的密集数组。它有两种存储形态密集存储固定分配16384个寄存器每个寄存器6bit总大小约12KB。无论基数多大内存恒定。稀疏存储当数据量还很小的时候直接分配12KB太浪费。Redis会用一种类似“跳过了大量0值寄存器”的编码只记录非零寄存器。每个非零寄存器需要2字节如果只有100个用户可能只占几百字节。什么时候从稀疏切换成密集根据源码中的逻辑大概在非零寄存器个数超过3000个或者稀疏编码的总大小超过阈值约3KB时Redis会在下一次PFADD时自动升级为密集存储。这个机制看起来聪明但有一个工程隐患首次灌入大量历史数据时可能触发从稀疏到密集的突然转换这个转换是一次性完成的会在瞬间产生少量CPU损耗。如果是大促后补录一个大key而该key很长一段时间都是稀疏状态忽然进来百万级数据触发的密集化会让这次请求的耗时明显增长。应对方式很简单对于确定会变大的统计key可以在初始化阶段故意添加一些padding数据或者接受首次写入的轻微延迟后续查询几乎无感。3.3 PFMERGE的合并规则和重复计数PFMERGE的语义是“并集”。合并两个key时每个寄存器取两个key中数值较大的那个。这样设计其实很巧妙因为每个寄存器记录的是“见过的最大零串长度”并集里只要任一边见过这个特征合并后就应该保留最大值。不过要注意PFMERGE的合并结果仍然是一个HyperLogLog它本身也有0.81%的误差。多个误差源叠加后最终误差可能略放大但不会线性叠加到很夸张的程度。实测中几十个key合并后的误差一般在1%到2%之间仍然在可接受范围。4. 工程落地日活、周活、月活统计标准姿势原理和命令都讲通了接下来直接给一套可以照抄的工程方案。这套方案我在多个项目里验证过覆盖了从单日UV到跨周跨月去重的常见需求。4.1 天级UV统计的Key设计最朴素的方案是按天建keyuv:2024-06-01 uv:2024-06-02 uv:2024-06-03每次请求进来把用户ID作为PFADD的参数追加到当天key。key的TTL可以设置为37到40天这样既能满足“最近30天趋势”查询又能让旧数据自动过期防止key无限堆积。如果是多业务线或者多端App、小程序、H5建议在key里带上业务维度uv:appid_a:2024-06-01 uv:appid_b:2024-06-01Redis官方文档里提到一个HyperLogLog key的常规大小约12KB即便你一天有100个业务线维度也就是1.2MB的存储量非常轻松。这里不需要对key做额外的压缩优化注意别重复创建同名key即可。4.2 月活统计PFMERGE多天key还是按月单独建key先说不推荐的做法每天直接往一个“月活key”里PFADD。这样做的问题是一旦Redis里的数据误删或需要回溯更新前几天的数据你没有办法对“某一天”单独修正只能整月重算。正确姿势是保留天级key月底通过PFMERGE合并成月级keyPFMERGE uv:2024-06 uv:2024-06-01 uv:2024-06-02 ... uv:2024-06-30合并完成之后天级key就可以按TTL自然淘汰了。周活类似合并最近7天即可。这里可以顺便算一笔账如果按月合并30个天key临时合并开销只发生一次平时查询月活直接PFCOUNT uv:2024-06走的是单key缓存非常快。如果业务经常需要动态查询任意时间段的UV例如“从6月10日到6月20日”可以写一个脚本动态PFMERGE这11个天key到临时key再统计后删除临时key。临时key的生命周期只有几秒注意清理即可。4.3 我踩过的坑误差、缓存和大key坑一PFCOUNT的单key结果可能被缓存改数据不影响计数PFCOUNT对单key的统计结果会被缓存到key的头部后续PFADD导致数据变化时缓存失效。这是Redis内部做的性能优化。但如果你在某个时刻PFCOUNT后缓存了结果然后对该key执行PFMERGE合并其他key的数据接着再PFCOUNT结果会正确刷新因为PFMERGE会清掉旧的缓存并更新。这里真正要注意的是不要把PFCOUNT结果暴露成“精确UV”给业务方否则哪天超过1%的偏差被用户抓到解释起来很麻烦。坑二大key合并耗时虽然单个key最多12KB但如果你用一个大key承载了超高频写入比如每秒几万次PFADD持续一整天的活动这个key可能长期处于密集存储状态每次写入需要随机写入16384个寄存器中的一个虽然分摊下来成本不高但Redis单线程模型下过高的写入频率会挤占CPU。实测中单key写入量超过每秒5万次时建议把key按小时维度拆开例如uv:2024-06-01:10表示当天10点到11点的UV后续再合并成天级。这样既能分散写压力又不影响最终统计口径。坑三不要拿HyperLogLog统计低于1000的量级当真实基数小于几百时HyperLogLog的误差会显得比例很大可能出现“真实UV是500统计出900”的情况绝对误差400比例达到80%。如果你的业务里存在大量小流量key比如长尾页面的访问量最好用一个简单的阈值判断低于某个量级时直接用Set或Redis Set统计精确值超过阈值后再迁移到HyperLogLog。用Set统计1000个用户的内存开销完全可忽略没必要为小数据量引入误差。我个人的习惯是在业务代码里做双层策略当天key的PFCOUNT结果如果长期低于1000就改用Set达到阈值后再切换成HyperLogLog。伪代码如下if (estimatedUv 1000) { sadd(uv:exact: date, userId); if (scard(uv:exact: date) 1000) { // 将Set中的元素一次性灌入HyperLogLog String[] ids smembers(uv:exact: date); pfadd(uv: date, ids); del(uv:exact: date); } } else { pfadd(uv: date, userId); }这套方案兼顾了精确度和资源开销实测效果很好。5. 技术选型的边界什么场景必须放弃HyperLogLogHyperLogLog虽好但绝不是什么统计场景都能套。我见过有人试图用它做订单去重、支付幂等校验这完全用错了方向。技术选型前一定要先问自己一个问题“业务上这个数字差1%会不会出大事”5.1 必须精确的场景如果统计结果直接影响资金、对账、发放权益、库存扣减那么任何概率估算都不能用必须走精确去重。下单去重同一用户同一订单只能下一次。这种判断错了会引发重复扣款必须用数据库唯一索引或分布式锁来保证。消息幂等消费同一个事件不能重复处理这种判断错了会造成业务数据错乱必须用Redis Set做精确INCR或者落库做唯一键。对账系统财务账单的笔数和金额必须分毫不差预算口径的偏差是不能靠“大约”来糊弄的。这些场景下内存成本再高也得扛或者用分片、压缩等手段优化但绝不能用牺牲准确性的方案。如果你的业务场景允许“量级正确、趋势可信、误差有界”那HyperLogLog可以放心用。UV统计就是一个典型日常决策看的是增长趋势和活动效果而不是那几千个用户的差值。5.2 一个可落地的组合方案明细近似双层架构现在的很多数据平台实际上不是只依赖HyperLogLog。我见过比较稳的做法是“明细落库实时聚合兜底”。实时链路用HyperLogLog出大屏和趋势曲线离线链路用明细表跑了精确的日活/月活。大屏上的数字允许随时变化几万离线报表的最终数据则是精确的。两者可以做一个每日校准把HyperLogLog的偏差控制在一个已知范围内。这样做的好处是实时指标响应快、成本低离线指标精确、可追溯。如果你的系统并发高又必须给运营出一个“差不多可信”的数字这套组合目前看是最稳的。5.3 进阶本地HyperLogLog 定期同步Redis还有一个进阶玩法适合游戏、推送类业务客户端或业务实例在本地维护一个HyperLogLog例如Java的stream-lib库提供了现成的HyperLogLog实现批量收集后每个一段时间合并到Redis。这样做能避免每一次用户访问都穿透到Redis减少网络IO。本地HLL占用的内存也极小单个实例攒10万元素也就是12KB级别。合并到Redis时调用PFMERGE把本地HLL的header和register数据填写到Redis整体成本很低。这个方案的注意点是本地HLL的桶数要和Redis一致否则合并会出错。Redis用的是16384个桶你在本地定义桶数时一定要对齐。6. 个人实操复盘从上线到调优的完整路径最后复盘一下我在一个真实项目里从选型到上线的过程希望能给你一些具体的参照。一开始需求很简单老板要看到一个页面“今日访客数”要求数据实时刷新。原始方案是每个访客ID写Redis Set日请求量大概三千万光这个key就占了几GB而且Set的元素规模一直在涨扩容风险很高。我当时的替换方案是这样的第一步把每天拆成一个天级HyperLogLog key线上流量平均分配写入。第二步凌晨离线跑一个任务把天级key按周、月分别PFMERGE成聚合key。第三步大屏和报表都读聚合key的PFCOUNT结果。第四步当天key保留40天TTL让监控大屏能看最近一个多月趋势。上线后再看监控几个明显变化Redis内存从7GB降到不到500MB周月活查询从几次“合并数十个key”变成单key统计耗时从几十毫秒降到几毫秒。误差方面我特意拿了离线精确表和HLL对比过一周日均误差在0.3%到0.8%之间老板完全感知不到差异。唯一一次“翻车”是活动期间的极端流量导致单个天级key在几分钟内涌入大量写入Redis出现瞬时CPU升高。后来我把天级key按小时拆成24个key写入分散之后监控曲线恢复平稳。这个教训说明HyperLogLog虽然内存极小但高频写入对单key的压力依然存在热点Key的设计思路不能丢。如果你要在一个新的业务里引入HyperLogLog我建议你先在低峰期做一个仿真压测拿一批真实离线数据做对比确认误差在自己可接受的范围内再上生产。不要只在文档里看到“0.81%误差”就觉得万事大吉误差分布的具体表现和你的数据特征相关。多测几天把置信区间摸清楚后面上线才会踏实。

HyperLogLog如何在亿级UV统计中把内存从7GB降到12KB？

相关推荐

光伏行业走向精度生存：电站资产管理如何从粗放转向精细化运营

Java高校师生问答平台源码运行与答辩指南

3个免费工具搞定html模板图片加载慢与变形

更多资讯

中专财务突破薪资瓶颈：从Excel到SQL的数据分析进阶路线

模型优化器实战：从800ms到170ms的推理加速与精度平衡

ESP32开发怎么选？Arduino、ESP-IDF、MicroPython对比与选型指南

CLI-Anything：声明式 CLI 运行时基础设施

CLI-Anything：面向智能体的可插拔CLI能力中枢

高维空间百年直觉被推翻：超立方体密铺反例的计算机搜索之路

今日更新

济南做网站多少钱：3个案例拆解，防黑源码下载全攻略

婚恋网站实战案例：避开3个高价坑，省钱50%还能跑赢流量

制作网页比较方便的软件怎么选?一文搞懂避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？