Redis概率算法：HyperLogLog数学原理与高效基数统计实践
Redis概率算法：HyperLogLog数学原理与高效基数统计实践
【免费下载链接】redisRedis 是一个高性能的键值对数据库，通常用作数据库、缓存和消息代理。* 缓存数据，减轻数据库压力；会话存储；发布订阅模式。* 特点：支持多种数据结构，如字符串、列表、集合、散列、有序集等；支持持久化存储；基于内存，性能高。项目地址: https://gitcode.com/GitHub_Trending/re/redis
Redis 是一个高性能的键值对数据库，通常用作数据库、缓存和消息代理。其中，HyperLogLog 是 Redis 提供的一种概率算法，能够以极小的内存占用实现海量数据的基数统计，广泛应用于用户访问量统计、独立访客计数等场景。
什么是基数统计？
基数统计即计算集合中不重复元素的个数。例如统计网站的独立访客数（UV）、某个关键词的独立搜索次数等。传统方法需要存储所有元素并去重，当数据量达到百万甚至亿级时，内存消耗会变得非常巨大。
HyperLogLog 算法通过概率统计的方式，仅需约 12KB 内存就能估算接近 2^64 个元素的基数，且误差率控制在 0.81% 左右，完美解决了内存与精度的平衡问题。
HyperLogLog 的数学原理
核心思想：伯努利试验与极大似然估计
HyperLogLog 基于伯努利试验的概率特性：假设我们对一个随机数生成器进行多次独立试验，记录每次试验中首次出现连续 k 个 0 后跟着一个 1 的结果。通过观察这些结果的最大值，就能估算出试验的总次数。
在实际应用中：
- 将每个元素通过哈希函数映射为 64 位随机数
- 记录每个哈希值二进制表示中前导零的最大个数（记为
k） - 基数估算公式：
E = α * m² / Σ(2^(-k))α是修正系数（Redis 中取值0.7213475204444817）m是寄存器数量（Redis 中使用 16384 个寄存器）
Redis 中的实现优化
Redis 对标准 HyperLogLog 算法做了多项优化：
- 双模式存储：低基数时使用稀疏模式（Run-Length Encoding）节省空间，高基数时自动转为密集模式
- 64位哈希：采用 MurmurHash64A 哈希函数，避免 32 位哈希的精度限制
- 动态缓存：计算结果会缓存，避免重复计算
核心实现代码位于 src/hyperloglog.c，其中定义了两种存储结构：
struct hllhdr { char magic[4]; /* "HYLL" 魔术字 */ uint8_t encoding; /* HLL_DENSE 或 HLL_SPARSE */ uint8_t notused[3]; uint8_t card[8]; /* 缓存的基数估算值 */ uint8_t registers[]; /* 寄存器数组 */ };Redis HyperLogLog 的使用方法
基本命令
添加元素：
PFADD key element [element ...]PFADD unique_visitors alice bob charlie估算基数：
PFCOUNT key [key ...]PFCOUNT unique_visitors # 返回估算的独立用户数合并多个 HyperLogLog：
PFMERGE destkey sourcekey [sourcekey ...]PFMERGE all_visitors unique_visitors_2023 unique_visitors_2024
内存占用对比
| 数据规模 | 传统集合（Set） | HyperLogLog |
|---|---|---|
| 100万 | ~160MB | ~12KB |
| 1亿 | ~1.6GB | ~12KB |
实际应用场景
1. 网站UV统计
# 记录每个访问用户 PFADD daily_uv user1 user2 user3 ... # 获取当日UV PFCOUNT daily_uv2. 搜索关键词去重
# 记录搜索关键词 PFADD search_terms "redis" "hyperloglog" "algorithm" # 获取独立关键词数量 PFCOUNT search_terms3. 大数据量去重计数
当需要统计千万级甚至亿级数据的独立元素个数时，HyperLogLog 是最优选择。例如电商平台的商品浏览记录去重、广告曝光量统计等。
算法局限性与注意事项
- 概率估算：结果是近似值，误差约 0.81%，不适合需要精确计数的场景
- 无法获取具体元素：只能得到基数统计结果，无法获取原始元素
- 内存占用固定：无论数据量多少，均占用约 12KB 内存
总结
HyperLogLog 算法为 Redis 提供了高效的基数统计能力，通过巧妙的数学原理和工程优化，在仅使用 12KB 内存的情况下，就能处理接近 2^64 个元素的去重计数问题。这使得 Redis 在海量数据统计场景中表现出色，成为缓存、计数系统的理想选择。
掌握 HyperLogLog 的原理和使用方法，能帮助开发者在处理大数据量去重问题时，在内存占用和计算效率之间找到完美平衡。如需深入了解实现细节，可以查阅 Redis 源码中的 src/hyperloglog.c 文件。
【免费下载链接】redisRedis 是一个高性能的键值对数据库，通常用作数据库、缓存和消息代理。* 缓存数据，减轻数据库压力；会话存储；发布订阅模式。* 特点：支持多种数据结构，如字符串、列表、集合、散列、有序集等；支持持久化存储；基于内存，性能高。项目地址: https://gitcode.com/GitHub_Trending/re/redis
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考