HyperLogLog
HyperLogLog(HLL)是一种概率算法数据结构，用于统计基数（唯一元素数量），仅需12KB内存即可统计近2^64个元素。
HyperLogLog原理
基数统计问题
Bash
基数统计：统计集合中不重复元素的数量
示例：
数据集 = [1, 2, 3, 1, 2, 4, 5]
基数 = 5（不重复元素为1,2,3,4,5）
传统方法：
- Set存储：内存消耗大
- 位图：需要连续ID
- HyperLogLog：极小内存估算
算法原理
Bash
HyperLogLog基于概率统计：
1. 使用哈希函数将元素映射为二进制串
2. 计算二进制串中前导零的最大长度
3. 前导零越长，元素越稀疏
4. 根据统计规律估算基数
数学原理：
- 伯努利试验概率分布
- 分桶统计提高精度
- 空间复杂度O(log log N)
精度与内存
Bash
标准误差：约0.81%
内存占用：固定12KB（16384个桶，每桶6bit）
统计范围：最多2^64个元素
对比：
1亿元素Set存储：约200MB+
1亿元素HyperLogLog：12KB
HyperLogLog是估算值，误差约0.81%，适合大数据量基数统计。
HyperLogLog命令
PFADD添加元素
Bash
# 基本语法
PFADD key element [element ...]
# 添加单个元素
PFADD hll:users "user:1000"
# 返回: 1（基数变化）
# 添加多个元素
PFADD hll:users "user:1001" "user:1002" "user:1003"
# 返回: 1（基数变化）
# 添加重复元素
PFADD hll:users "user:1000"
# 返回: 0（基数不变）
PFCOUNT获取基数
Bash
# 获取单个key的基数
PFCOUNT hll:users
# 返回: 3（估算的不重复元素数）
# 获取多个key的合并基数
PFADD hll:page1 "user:1" "user:2" "user:3"
PFADD hll:page2 "user:2" "user:3" "user:4"
PFCOUNT hll:page1 hll:page2
# 返回: 4（合并后的唯一元素数）
PFMERGE合并HyperLogLog
Bash
# 基本语法
PFMERGE destkey sourcekey [sourcekey ...]
# 合并多个HyperLogLog
PFMERGE hll:total hll:page1 hll:page2
# 获取合并后的基数
PFCOUNT hll:total
# 返回: 4
命令速查表
| 命令 | 说明 | 示例 |
|---|---|---|
| PFADD | 添加元素 | PFADD k e1 e2 |
| PFCOUNT | 获取基数 | PFCOUNT k |
| PFMERGE | 合合并 | PFMERGE dest src |
内部实现
密集存储
Bash
标准HyperLogLog：
- 16384个桶（2^14）
- 每桶6bit存储最大前导零长度
- 总计16384 * 6 / 8 = 12288字节（12KB）
稀疏存储
Bash
元素较少时使用稀疏存储：
- 只存储非零桶的信息
- 减少内存占用
- 添加元素到一定数量后转为密集存储
存储转换
Bash
# 初始为稀疏存储
PFADD hll:new "a"
# 内存占用很小
# 元素增多后转为密集存储
for i in {1..1000}; do PFADD hll:new "user$i"; done
# 内存固定12KB
应用场景
1. UV统计（独立访客）
每日UV
Bash
# 记录每日访问用户
PFADD uv:daily:2024:01:01 "user:1000"
PFADD uv:daily:2024:01:01 "user:1001"
PFADD uv:daily:2024:01:01 "user:1000" # 重复添加不影响
# 获取当日UV
PFCOUNT uv:daily:2024:01:01
每周UV
Bash
# 合并7天数据
PFMERGE uv:weekly:2024:01 uv:daily:2024:01:01 uv:daily:2024:01:02 ...
# 获取周UV
PFCOUNT uv:weekly:2024:01
每月UV
Bash
# 合整月数据
PFMERGE uv:monthly:2024:01 uv:daily:2024:01:*
# 获取月UV
PFCOUNT uv:monthly:2024:01
2. 页面访问统计
Bash
# 各页面UV
PFADD page:index:uv "user:1000"
PFADD page:detail:uv "user:1001"
# 获取页面UV
PFCOUNT page:index:uv
# 全站UV（合并所有页面）
PFMERGE site:total:uv page:index:uv page:detail:uv
PFCOUNT site:total:uv
3. 搜索词统计
text
# 记录搜索词
PFADD search:terms "redis教程"
PFADD search:terms "redis持久化"
PFADD search:terms "redis教程" # 重复不影响
# 获取独立搜索词数量
PFCOUNT search:terms
4. IP访问统计
text
# 记录访问IP
PFADD ip:daily:2024:01:01 "192.168.1.100"
PFADD ip:daily:2024:01:01 "192.168.1.101"
# 获取独立IP数
PFCOUNT ip:daily:2024:01:01
精度分析
误差范围
text
理论误差：约0.81%
实际误差示例：
- 统计1000元素：误差约±8
- 统计10000元素：误差约±81
- 统计100000元素：误差约±810
- 统计1000000元素：误差约±8100
误差验证
text
# 精确统计（Set）
SADD exact:users "user:1" ... "user:10000"
SCARD exact:users
# 返回: 10000
# HLL估算
PFADD hll:users "user:1" ... "user:10000"
PFCOUNT hll:users
# 返回: 约9981-10081（误差约±81）
适用场景
text
适合：
- 大数据量统计（>1000）
- 允许一定误差
- 内存敏感场景
- UV、PV统计
不适合：
- 小数据量精确统计
- 需要精确数值
- 不能接受误差
与Set对比
| 特性 | Set | HyperLogLog |
|---|---|---|
| 精度 | 精确 | 估算（误差0.81%） |
| 内存 | 随数据增加 | 固定12KB |
| 获取元素 | 支持 | 不支持 |
| 删除元素 | 支持 | 不支持 |
| 范围 | 内存限制 | 最多2^64 |
| 适用 | 小数据精确 | 大数据估算 |
与位图对比
| 特性 | 位图 | HyperLogLog |
|---|---|---|
| 精度 | 精确 | 估算 |
| 内存 | 与ID范围相关 | 固定12KB |
| ID要求 | 连续整数 | 无要求 |
| 查询元素 | 支持 | 不支持 |
| 适用 | 连续ID | 任意元素 |
注意事项
无法获取元素
text
# HyperLogLog只存储基数估算值
# 无法获取具体的元素列表
# 不支持删除元素
PFADD hll:users "user:1" "user:2"
# 无法知道具体有哪些用户
# 只能知道用户数量约为2
误差理解
text
- HyperLogLog是估算值
- 存在约0.81%误差
- 误差随数据量增加绝对值变大
- 适合趋势分析而非精确统计
合并注意事项
text
# PFMERGE合并后原key仍存在
PFMERGE dest src1 src2
# dest包含合并后的基数估算
# src1、src2仍可继续添加元素
# 如需重新合并，再次执行PFMERGE
性能特点
时间复杂度
text
PFADD：O(1)
PFCOUNT：O(1)（单个key）
PFCOUNT多key：O(N)
PFMERGE：O(N)
内存固定
text
优点：
- 内存占用固定12KB
- 不随数据增加而增长
- 适合海量数据统计
约束：
- 即使添加1个元素也是12KB（密集模式）
- 稀疏模式可能更小
要点总结
- HyperLogLog用12KB内存统计最多2^64个元素的基数
- 误差约0.81%，适合大数据量估算
- PFADD添加元素，PFCOUNT获取基数估算值
- PFMERGE合并多个HyperLogLog的基数
- UV统计、页面访问、搜索词、IP统计适合HLL
- 无法获取具体元素列表，只返回估算数量
- 无法删除元素，只能估算基数
- 小数据量精确统计使用Set，大数据估算使用HLL
- 连续整数ID使用位图更精确，任意元素使用HLL更省内存
- 固定内存不随数据增长，适合海量数据场景
📝 发现内容有误？点击此处直接编辑