网易首页 > 网易号 > 正文 申请入驻

12 KB 数清一亿人,它连名字都不存

0
分享至

先把两道题分开抛硬币能数出人数一个极端值就能毁掉全部12 KB 这笔账0.81% 不是上限,是一个标准差它只回答「多少个」日活、周活、月活怎么拼什么时候别用它最后算一笔总账

老板在群里丢过来一句话:昨天首页到底来了多少人?

你说十万出头。他追问:到底是多少,差一万会影响这周的投放预算。

你打开 Redis,里面躺着两百多万个用户 ID,占掉一个多 G 的内存——就为了回答这么一句「一共多少个人」。

今天要讲的这个东西,12 KB 就把这件事答了,误差不到 1%。它叫HyperLogLog。原理朴实得有点可笑:它连你是谁都不记,只记每个人「抛硬币的运气」。

「张三昨天来过没有」和「昨天一共来了多少人」,是两道完全不同的题。

前一道要名单,你就得把人一个个记下来。后一道只要一个数字——数人头的时候,没人会去核对身份证号。

但我们写代码时的习惯动作,一律是第一种解法:来一个人,加一个 ID 进集合。十万用户还行,一亿用户就是几个 G 的内存,外加每次写入都要查一遍重。

HyperLogLog 的出发点很干脆:既然只要数字,那就别存人。

那存什么?存每个人的「运气」。

想象有人在桌上抛硬币,规则是抛到正面就停。

他抛 3 次就出了正面,你什么也看不出来。但如果他连着 12 次都是反面,第 13 次才出正面,你心里会立刻有个判断:这人八成抛了不少次。

为什么?因为「连着 12 个反面」这件事,在 4096 次抛掷里平均会出现一次。所以看到一次 12 连反面,最合理的猜测是总共抛了 2¹² ≈ 4096 次。

这就是全部的核心:你不需要记录每一次正反,只需要记录最长的那一串反面有多长。

HyperLogLog 干的就是这件事。把每个用户 ID 丢进哈希函数,得到一个均匀随机的比特串,然后从低位开始数「连续 0 的个数」,再 +1,记作 rho。

rho 等于 20,说明这个用户很「稀有」,像连抛 20 个反面。2²⁰ 大约 100 万——所以当某个桶里出现 rho 等于 20,可以猜这一桶大概被喂过百万量级的人。

如果全站只有一个计数器,只记全局最大的 rho,会怎样?

我写了个小模拟:1 万个用户,重复 60 次,每次的全局最大 rho 落在12 到 23 之间。换算成人数,就是从 4096 到 838 万——同一个 1 万人的集合,估算值能差 2000 倍。

这不是算法,这是抽奖。问题出在「最大值」这个统计量太脆弱,一个人的运气就能绑架全部结论。

解法是分桶:开 16384 个桶,每个用户按哈希的低 14 位分到其中一个桶,每桶只记自己见过的最大 rho。这样一次好运气只污染 16384 分之一个估计。

最后怎么合成一个数?把所有桶的 2 的负 rho 次方加起来,求调和平均。

为什么是调和平均而不是算术平均?因为桶里还很空的时候,rho 等于 0,这一项就是 1,贡献很大;某个桶运气爆棚、rho 等于 23,那一项约等于千万分之一,几乎不影响结果。调和平均天生对极端值不敏感——这正是我们需要的。

公式就一行:

E ≈ α × m² / Σ 2^(-M[j])

m 是桶数 16384,α 是个常数(约 0.7213),M[j] 是第 j 个桶记下的最大 rho。一个最小实现大概长这样:



注意最后那段特判。基数很小的时候,上面那个主公式会明显偏高,所以要用另一条路:数一数还有多少个桶是空的,空桶比例能直接推出大概填了多少——这叫线性计数。

桶数定成 16384,每个桶只需要存 0 到 51 的数,6 个比特够用。

16384 乘 6 除以 8,等于 12288 字节。再加 16 字节头部(4 字节魔数、1 字节编码标志、3 字节保留、8 字节的基数缓存)。合计12304 字节,12.02 KB。

这个数跟你有多少用户完全无关。100 万、1 亿、10 亿,都是 12 KB。

代价是精度。标准误差等于 1.04 除以 16384 的平方根,也就是0.81%。

这两个数字出自同一个常量:你要么接受「12 KB 配 0.81%」,要么改源码把桶数换成 2 的 16 次方(约 48 KB 换 0.41%)。Redis 里这个参数写死在编译期,配置文件改不了。

和另外两条路放在一起看,取舍就很清楚了:



Bitmap 那一行的前提是「稠密、非负、有上界的整数」。用户 ID 一旦是 UUID 或者雪花 ID,这条路直接断掉——这也是 HyperLogLog 的真正优势:它对输入长什么样完全不挑。

这是最容易被误用的地方。

0.81% 不是「最多差 0.81%」,而是标准差。约 68% 的结果落在正负 0.81% 之内,95% 落在正负 1.62% 之内,99.7% 落在正负 2.43% 之内。换句话说,大约三分之一的情况下,你会看到超过 0.81% 的偏差,这是正常的,不是 bug。

我跑了一组实测,每个基数做 12 次随机实验:



看到 1.34% 和 1.54% 了吗?超出 1 个标准差,但完全在预期之内。平均值都很接近 0,说明这个估计器没有系统性偏移,只是有随机抖动。

还有两个限定要记住。

一是相对误差,不是绝对误差。1 亿人,正负 0.81% 就是正负 81 万人。看板上差个几十万,不用急着去查代码。

二是小基数另说。几百到几千的时候走的是线性计数那条分支,绝对偏差常常只有几个人,别拿 0.81% 去反推区间。而且同一个固定集合,估出来的值每次都是同一个——「多查几次取平均会更准」在这里不成立。

所以工程上该问的不是「误差大不大」,而是「这个误差会不会让某个动作跨过阈值」。看板差几十万,无所谓;熔断阈值设 500,真实 498 读成 502,就直接误熔断了。这种地方不能用它。

HyperLogLog 不保存元素。由此直接推出四个「不能」:

  • • 不能列出里面有谁(根本没有名单)
  • • 不能判断某个人在不在(可以猜,但会误判)
  • • 不能删除单个元素(寄存器只增不减)
  • • 不能精确算交集(能估,但误差会放大)

最容易踩的坑不在算法,在返回值。

很多人以为,写入命令返回 1 就是「新用户」,返回 0 就是「老用户」,然后拿它发新手券。这是错的。

返回 1 的真实含义是「至少有一个寄存器被改写了」。一个新用户落进某个桶,如果他的 rho 不大于桶里已有的最大值,寄存器一动不动,返回 0。

我实测过:连续插入 2000 个全新的用户 ID,其中86 个返回了 0。差不多每 23 个人里,就有一个「新人被当成旧人」。

要判新,用 SETNX、独立集合、布隆过滤器或者数据库唯一约束。这个返回值只能当「估计值可能变了」的信号看。

UV 报表从来不是一天的数。日、周、月要拼起来,靠合并命令。三条必须记准:

一、目标 key 如果已经存在,它会被当成一个额外的源参与合并,不是覆盖。想干净重建,先删除,或者写临时 key 再改名。

二、合并出来的 key 不继承任何源 key 的过期时间。忘了设,就是永久 key,慢慢把内存吃掉。

三、集群下,目标 key 和所有源 key 必须落在同一个 slot。靠 hash tag(花括号)绑在一起。



最容易出的事故是过期时间设错:日 key 只给一天,凌晨的周合并还没跑完,最早那几天已经过期了,周 UV 直接偏小。日 key 至少留 35 天。

还有一种:滚动窗口,比如「最近 7 天」。窗口每天在动,而 HyperLogLog 不能删元素、合并只能加,所以不能「把昨天的减掉、把今天的加上」,只能每次整窗重建。重建要走「临时 key 加改名」,不要「先删再合并」——中间那段空窗期,看板会白屏。

一句话:它只值得用在「海量、可容忍约 1% 误差的去重总数」这一种需求上。

其他情况,按这张表走:



交集这一项要单独说。两个集合各带 0.81% 误差,如果交集远小于并集,误差一减,算出来的交集可能比它本身还大。想要交集就老老实实算,别用「甲加乙减并集」这种容斥公式凑。

说到底,这是一种很典型的工程交易:用一个可接受的误差,换掉一个数量级的内存。它不是万能的,但在「海量去重计数」这一件事上,几乎没有对手。

你项目里那堆 UV 是怎么算的?还是老老实实存了一整个集合吗?评论区聊聊你踩过的坑。

声明:内容由AI生成

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
何沁教授逝世

何沁教授逝世

极目新闻
2026-11-21 16:50:35
特朗普在回国的专机上,有件事让他很着急,事关中美的“大买卖”

特朗普在回国的专机上,有件事让他很着急,事关中美的“大买卖”

麓谷隐士
2026-11-21 15:01:54
甲亢哥52小时不睡通关GTA6 却触发最差结局崩溃落泪!

甲亢哥52小时不睡通关GTA6 却触发最差结局崩溃落泪!

游民星空
2026-11-21 11:07:36
哈登51+6+6超越奥尼尔!骑士拒步行者24分逆转 米切尔20分

哈登51+6+6超越奥尼尔!骑士拒步行者24分逆转 米切尔20分

醉卧浮生
2026-11-21 10:57:09
零跑汽车回应“A10后备厢装几箱啤酒就被压露底”:系物品超过设计承重上限所致,已获得用户理解,后续将优化用车指引

零跑汽车回应“A10后备厢装几箱啤酒就被压露底”:系物品超过设计承重上限所致,已获得用户理解,后续将优化用车指引

台州交通广播
2026-11-21 01:43:49
高市早苗飞离中国,中方铺红毯、礼仗队送别,日本认为“中方失礼”,根本站不住脚

高市早苗飞离中国,中方铺红毯、礼仗队送别,日本认为“中方失礼”,根本站不住脚

蓝星杂谈
2026-11-20 13:04:01
“A10后备厢装几箱啤酒就被压露底”,零跑汽车回应:系物品超过设计承重上限所致,已与用户沟通并获得理解,后续将优化用车指引

“A10后备厢装几箱啤酒就被压露底”,零跑汽车回应:系物品超过设计承重上限所致,已与用户沟通并获得理解,后续将优化用车指引

政知新媒体
2026-11-21 09:48:46
浮嶋敏回应0-5:日本20年前也经历过!盼中国足球能认清差距+反思

浮嶋敏回应0-5:日本20年前也经历过!盼中国足球能认清差距+反思

我爱英超
2026-11-21 17:11:33
“长不大的巨婴,及时分手”!四川女生因糖葫芦被男友吃了一个暴怒,扔掉肯德基躺人行道打滚,男生满脸通红苦劝

“长不大的巨婴,及时分手”!四川女生因糖葫芦被男友吃了一个暴怒,扔掉肯德基躺人行道打滚,男生满脸通红苦劝

王老师你还好吗
2026-11-21 13:25:53
别买,全是假的!又一产品大翻车,成本只有10元,很多人长期上当

别买,全是假的!又一产品大翻车,成本只有10元,很多人长期上当

命运自认幽默
2026-11-21 07:52:54
说出来你都不敢信,美国总统飞一趟中国,花出去的钱足足能买3辆全新的劳斯莱斯!

说出来你都不敢信,美国总统飞一趟中国,花出去的钱足足能买3辆全新的劳斯莱斯!

扶苏聊历史
2026-11-20 15:37:24
姆巴佩风波后,时间给出了答案——皇马赢了,皇马5家中国赞助商也赌赢了

姆巴佩风波后,时间给出了答案——皇马赢了,皇马5家中国赞助商也赌赢了

开成运动会
2026-11-21 11:24:38
美媒发现:英伟达失去中国市场之后,最危险的对手正在中国长出来

美媒发现:英伟达失去中国市场之后,最危险的对手正在中国长出来

麓谷隐士
2026-11-21 07:19:12
外媒:印度东北部发生假酒致人中毒事件,已致至少11人死亡、180余人入院

外媒:印度东北部发生假酒致人中毒事件,已致至少11人死亡、180余人入院

环球网资讯
2026-11-21 16:27:23
七万狂跌至两万八!珠海横琴神话破灭,澳门炒客排队断供逃亡

七万狂跌至两万八!珠海横琴神话破灭,澳门炒客排队断供逃亡

珠三角港
2026-11-20 10:44:17
参与军采项目涉嫌违规,顺丰速运、八马茶业等被暂停全军采购资格,自11月19日起生效,范围为全军

参与军采项目涉嫌违规,顺丰速运、八马茶业等被暂停全军采购资格,自11月19日起生效,范围为全军

大风新闻
2026-11-21 17:03:03
普林斯顿博士生被拘事件​​​曝更多内幕:14岁移居纽约,全家申请政治庇护

普林斯顿博士生被拘事件​​​曝更多内幕:14岁移居纽约,全家申请政治庇护

小徐讲八卦
2026-11-21 10:28:27
油还没跌回6块,人已彻底跑光!2026油价“骗局”,终于被揭穿!

油还没跌回6块,人已彻底跑光!2026油价“骗局”,终于被揭穿!

娱乐圈的笔娱君
2026-11-21 05:28:53
江苏淮安一退休干部被实名举报利用职权帮助子女介入超千万地产生意!纪委回应:正在调查

江苏淮安一退休干部被实名举报利用职权帮助子女介入超千万地产生意!纪委回应:正在调查

指尖新闻沈阳晚报
2026-11-21 08:51:23
天呐!差点没认出来,电视里那么漂亮女神,原来跟普通人也没两样

天呐!差点没认出来,电视里那么漂亮女神,原来跟普通人也没两样

情感大头说说
2026-11-20 04:49:19
2026-11-21 18:03:00
千纸鹤安安
千纸鹤安安
大自然的搬运工
216文章数 4关注度
往期回顾 全部

科技要闻

老黄想回来?英伟达董事会:没门

头条要闻

历时14小时特朗普返回美国 刚下飞机就发布"重大预告"

头条要闻

历时14小时特朗普返回美国 刚下飞机就发布"重大预告"

体育要闻

脚步未停!西班牙摩托车手赤脚徒步入境中国

娱乐要闻

官媒发文 官宣赵丽颖新身份,进步很大

财经要闻

最大回撤超37%,黄金崩盘了吗?

汽车要闻

全新红旗H9最有意思的地方,是它开始有自己的豪华逻辑了

态度原创

房产
教育
旅游
健康
数码

房产要闻

黄埔商业规划曝光!科学城能级跃升,核心入场券已锁定

教育要闻

曾经“感动中国”的庞众望完成清华大学博士论文答辩,本人发声:将继续潜心钻研,在科研探索的道路上不断前行

旅游要闻

青岛冬日赏鸥地图|沿着海岸线,赴一场海鸥之约

医生眼里"很伤腰"的椅子,很多人天天坐

数码要闻

苹果公布2026古典乐年度专辑:任奫灿《哥德堡变奏曲》获奖

无障碍浏览 进入关怀版