Learn
Redis/08-bitmap-hll-geo

Bitmap、HyperLogLog 与 GEO

这三个不是独立的数据类型，而是构建在 String 和 ZSet 之上的特殊用途结构：Bitmap 用 1 个 bit 记录一个布尔状态，HyperLogLog 用 12 KB 估算亿级基数，GEO 把经纬度编码进 ZSet 做半径搜索。它们的共同主题是：用极小的空间解决特定问题。

1. Bitmap：一个 bit 记一个状态

Bitmap 本质是 String，把它当作 bit 数组来操作。一个 512 MB 的 String 可容纳 2^32 个 bit。

1.1 基本操作

Bitmap 实现月签到
# 7 月 1 日（偏移 0）签到，返回该位的旧值
SETBIT sign:u1001:202607 0 1
# 7 月 2 日签到
SETBIT sign:u1001:202607 1 1
# 7 月 30 日签到
SETBIT sign:u1001:202607 29 1
# 7 月 2 日签过
GETBIT sign:u1001:202607 1
# 7 月 3 日没签
GETBIT sign:u1001:202607 2
# 本月共签到几天
BITCOUNT sign:u1001:202607
# 第一个 1 的位置：首次签到日
BITPOS sign:u1001:202607 1

一个用户一个月的签到只占 31 bit ≈ 4 字节；1 亿用户的月签到约 400 MB，而用 Set 存"签到用户 ID"要几十 GB。

1.2 位运算：BITOP

BITOP 算连续活跃与总活跃
# day1 / day2 分别是两天的活跃用户位图（偏移即用户 ID）
SETBIT active:day1 1001 1
SETBIT active:day1 1002 1
SETBIT active:day2 1002 1
# AND：连续两天都活跃的用户位图
BITOP AND active:both active:day1 active:day2
BITCOUNT active:both
# OR：两天内活跃过的总人数（精确去重）
BITOP OR active:any active:day1 active:day2
BITCOUNT active:any

BITOP 支持 AND/OR/XOR/NOT，连续 N 天活跃、留存率计算都是几条位运算的事。

⚠️偏移量决定内存，别用离散大 ID

SETBIT key 4000000000 1 会立即分配 500 MB 内存——Bitmap 按最大偏移量分配空间。用户 ID 作偏移的前提是 ID 连续自增；如果 ID 是雪花 ID 这种 64 位大数，直接用会撑爆内存，需要先映射成连续编号。

2. HyperLogLog：12 KB 数亿级 UV

需求："统计页面今天有多少不同用户访问"（UV）。用 Set 精确去重，1 亿个 ID 要几 GB；如果能接受 0.81% 的标准误差，HyperLogLog 只要 12 KB。

2.1 使用

HyperLogLog 估算 UV
# 返回 1 表示估算值发生了变化
PFADD uv:20260730 u1 u2 u3
# 重复元素不影响，返回 0
PFADD uv:20260730 u2
PFCOUNT uv:20260730
PFADD uv:20260729 u3 u4
# 合并多天得到周 UV：去重合并，不是相加
PFMERGE uv:week1 uv:20260729 uv:20260730
PFCOUNT uv:week1
# HLL 底层就是 String，看一眼类型
TYPE uv:week1

只有三个命令：PFADD 添加、PFCOUNT 估算基数、PFMERGE 合并。注意 HLL 只能给出数量，无法回答"某个用户来过没有"——它根本不存储元素本身。

2.2 误差从哪来：概率估计的直觉

HLL 的核心思想类似"抛硬币"：一个均匀哈希值的二进制表示中，前导零的个数服从几何分布——见过"前导 20 个零"的哈希，说明大约见过 2^20 个不同元素。单次估计方差很大，HLL 的改进是：

元素 -> hash 64bit -> 前 14 bit 选桶(共 16384 个桶)
                      剩余 bit 统计前导零个数, 桶内只保留最大值
 
  桶0   桶1   桶2  ...  桶16383
 [ 5 ] [ 3 ] [ 7 ] ... [ 4 ]      每桶 6 bit, 16384 * 6bit = 12KB
 
 基数估算 = 常数 * 桶数^2 / sum(2^-桶值)   (调和平均抗离群值)
 标准误差 = 1.04 / sqrt(16384) ≈ 0.81%

16384 个桶各自独立估计再取调和平均，把误差压到 0.81%。这就是"12 KB 固定内存、亿级基数、误差不到 1%"的数学来源。

3. GEO：附近的人

GEO 把经纬度通过 GeoHash 编码成 52 bit 整数存进 ZSet 的 score——所以 GEO 的 key 用 TYPE 查看是 zset，可以直接用 ZSet 命令操作。

3.1 写入与查询

GEO 写入与半径搜索
GEOADD riders 121.4737 31.2304 "rider:1"
GEOADD riders 121.4837 31.2404 "rider:2" 121.5037 31.2104 "rider:3"
# 编码解码有厘米级精度损失
GEOPOS riders rider:1
# 两点距离，单位 km
GEODIST riders rider:1 rider:2 km
# 以坐标为圆心找 3 公里内的骑手，按距离升序
GEOSEARCH riders FROMLONLAT 121.4737 31.2304 BYRADIUS 3 km ASC WITHDIST
# GEO 底层就是 ZSet
TYPE riders

3.2 半径搜索：GEOSEARCH（6.2+，替代 GEORADIUS）

# 以某坐标为圆心找 3 公里内的骑手，按距离升序
127.0.0.1:6379> GEOSEARCH riders FROMLONLAT 121.4737 31.2304 BYRADIUS 3 km ASC WITHCOORD WITHDIST
1) 1) "rider:1"
   2) "0.0001"
   3) 1) "121.47370249032974243"
      2) "31.23039901743481792"
2) 1) "rider:2"
   2) "1.4453"
   3) 1) "121.48369997739791870"
      2) "31.24039987621843541"
# 以某成员为中心, 矩形范围搜索
127.0.0.1:6379> GEOSEARCH riders FROMMEMBER rider:1 BYBOX 4 4 km ASC COUNT 10
1) "rider:1"
2) "rider:2"

GeoHash 的原理是经纬度二分交替编码：把地球反复对半切，落在左/下记 0、右/上记 1，交织成一个整数——编码相近的点空间上也相近（Z 序曲线），因此 ZSet 的按 score 范围查找能转化为空间邻近查找，再对候选点精确算距离过滤。

骑手位置更新就是重复 GEOADD（同名成员覆盖坐标）；下线用 ZREM riders rider:1 删除。

💡三个结构的选型口诀

要"每个个体的状态"（签了没签、活跃没活跃）用 Bitmap；只要"去重后的数量"且量极大用 HyperLogLog；要"位置与距离"用 GEO。共同前提：都是单 key 结构，注意配合 TTL 与按时间分 key。

⚠️GEO 大 key 与 Cluster 注意

全城骑手放一个 GEO key，量大后是典型大 key，且在 Cluster 中无法分片。实践中按城市或网格分 key（如 riders:sh:grid:105）。另外 GEOSEARCH 半径越大扫描的候选越多，避免动辄"50 公里内"的全城搜索。

小结

  • Bitmap：bit 级布尔数组，签到、活跃、留存的空间效率之王；注意偏移量与内存的关系
  • HyperLogLog：12 KB 估算亿级基数，误差 0.81%，只有数量没有成员
  • GEO：GeoHash 进 ZSet，GEOADD 写入、GEOSEARCH 半径/矩形搜索
  • 三者都是"特化工具"：先确认业务能否接受各自的限制（精确性、可查性、精度）
  • 下一章 Stream：真正的消息队列 →
🎯练习
  1. 用 Bitmap 实现本月签到：签到 5 天，统计总签到数、查询某天是否签到、找出首次签到日。
  2. 向 HyperLogLog 写入 1 万个不同元素（脚本循环 PFADD），对比 PFCOUNT 估算值与真实值的误差百分比。
  3. GEOADD 写入 5 个门店坐标，实现"查找我 2 公里内最近的 3 家门店，返回距离"。