为什么Redis HyperLogLog统计基数有误差_分析概率算法与内存权衡

冬婷大大_1829

冬婷大大_1829

2026-06-20

884人浏览

原创

redis hyperloglog 的标准误差率为固定0.81%,由分桶数m=16384和调和平均公式数学推导得出,与数据分布、重复率无关,是概率算法固有设计,非bug;pfmerge合并后误差仍为0.81%,不叠加。

为什么redis hyperloglog统计基数有误差_分析概率算法与内存权衡

Redis HyperLogLog 的误差不是 bug,而是设计选择:0.81% 是固定标准误差率,由分桶数 m=16384 和调和平均公式数学推导得出,无法通过重试、多插或调参消除。

误差来自概率建模,不是哈希碰撞或数据倾斜

很多人看到 PFCOUNT 返回值和真实去重数不一致,第一反应是“哈希冲突导致漏计”或“重复元素太多影响精度”。其实不是。HyperLogLog 的误差根源在算法本身——它不记录元素,只记录每个桶中哈希值的**最大前导零位数 ρ**,再用调和平均反推基数。这个过程天然带统计偏差。

关键点:

  • 误差与输入数据分布无关:哪怕你 PFADD 一万个相同字符串,只要 MurmurHash3 输出均匀(Redis 确保这点),误差仍稳定在 ~0.81%
  • 误差是相对误差:基数为 1000 时,绝对偏差约 ±8;基数为 1000 万时,绝对偏差约 ±8 万——但比例始终是 0.81%
  • 重复元素完全被忽略:PFADD key a a a 和 PFADD key a 效果一样,不会“污染”桶状态,也不提升精度

PFMERGE 合并后误差不叠加,但有类型校验陷阱

用 PFMERGE 把多个 HLL 合并(比如按天统计后月汇总),结果的误差率仍是 ~0.81%,不是单日误差的累加。因为合并操作本质是取所有源 HLL 对应桶的 max(ρ),再用同一套公式重算——相当于把原始数据“逻辑上投喂给一个更大的虚拟 HLL”。

Redis Skill - 高性能缓存管理
Redis Skill - 高性能缓存管理

Redis 缓存和数据结构管理技能。通过自然语言操作 Redis,支持 String、Hash、List、Set、ZSet、Stream 等数据结构操作。当用户提到 Redis、缓存、消息队列、会话存储时使用此技能。

下载

但要注意实际踩坑点:

  • PFMERGE 不检查键是否存在,也不做类型预判:若误传一个 STRING 键,直接报错 WRONGTYPE Operation against a key holding the wrong kind of value
  • 合并后新键是全新结构,内存占用 = 所有源键中最大那个(稀疏/密集格式自动适配),不是简单相加
  • 不能靠合并“修复”小基数下的波动:基数 PFCOUNT 可能返回 97 或 103,合并十个这样的键,结果还是围绕真实值 ±0.81%,不会更准

为什么非要 0.81%?内存和误差的硬性权衡

理论误差公式是 1.04 / √m。Redis 选 m = 16384(即 2^14),是因为:

  • √16384 = 128,所以 1.04 / 128 ≈ 0.008125 → 0.81%
  • 若把 m 翻倍到 32768,误差降到 ~0.57%,但内存从 ~12 KB 涨到 ~16 KB,而 UV 统计场景根本不需要这 0.24% 的提升
  • 若把 m 减半到 8192,误差升到 ~1.15%,内存省不了多少,却明显增加业务误判风险(比如把 99 万 UV 估成 100 万+,触发错误告警)

这个数字不是拍脑袋定的,是 Flajolet 论文推导 + Redis 工程实测后,在“12 KB 内存封顶”硬约束下找到的最优解。

真正容易被忽略的是:误差率固定,但小基数下绝对不准——比如真实基数为 12,PFCOUNT 可能返回 10 或 14,这时别硬套 0.81% 解释,该换 SET 就换;而一旦基数过万,0.81% 就成了可信赖的工程事实。

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

5336

4

常用的数据库软件
常用的数据库软件

常用的数据库软件有MySQL、Oracle、SQL Server、PostgreSQL、MongoDB、Redis、Cassandra、Hadoop、Spark和Amazon DynamoDB。更多关于数据库软件的内容详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.11.02

4329

19

内存数据库有哪些
内存数据库有哪些

内存数据库有Redis、Memcached、Apache Ignite、VoltDB、TimesTen、H2 Database、Aerospike、Oracle TimesTen In-Memory Database、SAP HANA和ache Cassandra。更多关于内存数据库相关问题,详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.11.14

3835

11

mongodb和redis哪个读取速度快
mongodb和redis哪个读取速度快

redis 的读取速度比 mongodb 更快。原因包括:1. redis 使用简单的键值存储,而 mongodb 存储 json 格式的数据,需要解析和反序列化。2. redis 使用哈希表快速查找数据,而 mongodb 使用 b-tree 索引。因此,redis 在需要高性能读取操作的应用程序中是一个更好的选择。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.04.02

6972

6

redis怎么做缓存服务器
redis怎么做缓存服务器

redis 作为缓存服务器的答案:redis 是一款开源、高性能、分布式的键值存储,可作为缓存服务器使用。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.04.07

623

6

redis怎么解决数据一致性
redis怎么解决数据一致性

redis 提供了两种一致性模型,以维护副本数据一致性:强一致性 (sync) 确保写操作仅在复制到所有从节点后才完成;最终一致性 (async) 则在主节点上写操作后认为已完成,牺牲一致性换取性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.04.07

736

6

mysql和redis怎么保证双写一致性
mysql和redis怎么保证双写一致性

确保 mysql 和 redis 双写一致性的技术包括:1、事务性更新:同时更新 mysql 和 redis,保证一致性;2、主从复制:mysql 主服务器更改同步到 redis 从服务器;3、基于事件的更新:mysql 记录更改并发送到 redis等等。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.04.07

6622

6

redis缓存一般存些什么数据
redis缓存一般存些什么数据

redis缓存中存储的数据类型包括:字符串、哈希、列表、集合、有序集合、位图、地理空间数据和hyperloglog。这些数据类型适用于存储各种数据,从简单信息到复杂对象和地理位置。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.04.07

1160

6

redis的8种数据类型有哪些
redis的8种数据类型有哪些

redis 提供 8 种数据类型:字符串(文本、数字、二进制)、哈希(键值对)、列表(有序集合)、集合(无序唯一元素)、有序集合(按分数排序)、地理空间(地理位置)、hyperloglog(估计大数据基数)和位图(位序列存储)。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.04.07

1036

6

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
phpEnv手册
phpEnv手册

共0课时 | 0人学习

进程与SOCKET
进程与SOCKET

共6课时 | 0.5万人学习