阶段二 · 进阶数据结构与应用场景

扩展数据类型

HyperLogLog / Bitmap / GEO / Stream —— 用极小代价解决特定问题的专用武器

Redis 学习笔记 · 第 04 篇 · 大纲 · 前置：第 03 篇

总览与定位

五大基础类型（String/List/Hash/Set/ZSet）覆盖了大部分通用场景。但某些特定问题如果用基础类型硬做，要么内存爆炸，要么功能缺失。Redis 为此提供了四种"专用武器"：

类型	解决什么问题	核心优势	代价
Bitmap	海量布尔状态（是/否）	每个状态仅占 1 bit	仅适用于 ID 为连续整数的场景
HyperLogLog	海量基数统计（去重计数）	固定 12KB 统计任意量级	有 0.81% 标准误差，不能获取具体元素
GEO	地理位置存储与范围查询	原生支持经纬度、距离、半径搜索	底层是 ZSet，大数据量需分片
Stream	消息队列（支持消费者组）	原生 ACK、消费组、持久化	比 Kafka 轻量但能力上限低

1. Bitmap（位图）

Bitmap 不是独立的数据类型，本质是 String 的按位操作接口。一个 String key 最大 512MB = 2³² 个 bit 位，每个 bit 存储一个布尔值（0 或 1）。

1.1 基础操作

# 用户签到：bit 位 = 日期偏移量（0=1号，1=2号...）
# key = sign:{uid}:{yyyy-MM}

# 用户 1001 在 6 月 1 日签到
SETBIT sign:1001:2024-06 0 1    → (integer) 0  ← 返回旧值

# 6 月 3 日签到
SETBIT sign:1001:2024-06 2 1    → (integer) 0

# 查询 6 月 2 日是否签到
GETBIT sign:1001:2024-06 1      → (integer) 0  ← 未签到

# 查询 6 月 3 日
GETBIT sign:1001:2024-06 2      → (integer) 1  ← 已签到

1.2 批量统计与位运算

# 本月签到了几天
BITCOUNT sign:1001:2024-06    → (integer) 2

# 连续签到判断：找第一个为 0 的位（即第一天未签到）
BITPOS sign:1001:2024-06 0    → (integer) 1  ← 第 2 天断签

# 多用户活跃统计：哪些用户在周一和周二都活跃了？
# active:2024-06-01 → 用户ID为offset，活跃则设为1
# active:2024-06-02 → 同上
BITOP AND active:both active:2024-06-01 active:2024-06-02
BITCOUNT active:both    → 连续两天都活跃的用户数

1.3 应用场景

场景	key 设计	offset 含义	内存估算
用户签到	sign:{uid}:{month}	日期（0~30）	每人每月 4 字节
日活统计	active:{date}	用户 ID	1 亿用户 ≈ 12MB/天
功能开关	feature:{name}	用户 ID	灰度放量标记
在线状态	online	用户 ID	1 亿用户 ≈ 12MB
布隆过滤器（手动）	多个 Bitmap + 多 hash 函数	hash 值	可控

2. HyperLogLog（基数估算）

HyperLogLog（简称 HLL）用于解决基数统计（Cardinality）问题——统计一个集合中不重复元素的数量。典型需求：UV（独立访客数）、搜索关键词去重计数。

为什么不用 Set？因为当数据量到千万、亿级时，Set 需要存储每个元素，内存消耗巨大。而 HLL 固定只占 12KB，就能估算 2⁶⁴ 个不同元素的基数。

2.1 基础操作

# 统计页面 UV
PFADD page:home:uv "user_1" "user_2" "user_3"    → (integer) 1
PFADD page:home:uv "user_2" "user_4"              → (integer) 1  ← user_2重复但不影响
PFADD page:home:uv "user_2"                       → (integer) 0  ← 无变化

PFCOUNT page:home:uv    → (integer) 4    ← 去重后 4 个独立用户

# 按天统计，合并为周 UV
PFADD uv:2024-06-01 "u1" "u2" "u3"
PFADD uv:2024-06-02 "u2" "u3" "u4" "u5"

PFMERGE uv:week1 uv:2024-06-01 uv:2024-06-02
PFCOUNT uv:week1    → (integer) 5    ← 两天去重后的并集

2.2 原理直觉

2.3 原理深度拆解

第一步：掷硬币实验（概率直觉的数学化）

我隔着帘子掷硬币，不告诉你掷了多少次，只告诉你一个信息："最长连续正面的次数是 5"。

你能反推我掷了多少次吗？

• 连续 5 次正面的概率 = (1/2)⁵ = 1/32
• 要稳定地看到"5 连正"这个极端事件，大约需要掷 2⁵ = 32 次
• 同理：最长 10 连正 → 大约掷了 2¹⁰ = 1024 次

第二步：用 Hash 把"元素"变成"硬币序列"

Hash 函数的输出是均匀分布的伪随机比特串。把每个 bit 看作一次硬币：0 = 正面，1 = 反面，那么 hash 值的二进制"前导零个数"就是"连续正面的次数"。

hash("user_1") = 00110101 11000010 ...
                  ↑↑
                  前导零 = 2（遇到第一个 1 之前有几个连续的 0）

对于一个好的 hash 函数，前导零个数与概率的关系：

前导零个数	概率	大约需要多少个不同元素才能见到一次
0（第一位就是 1）	1/2	2⁰ = 1
1（01...）	1/4	2¹ = 2
2（001...）	1/8	2² = 4
k	(1/2)^(k+1)	2^k

所以：如果你已见过 N 个不同元素，它们中最大的前导零大约在 log₂(N) 左右。

第三步：单计数器的问题——方差太大

如果只用一个计数器记录"迄今为止最大的前导零"，会遇到致命问题：

你只添加了 1 个元素，但它的 hash 恰好是 000000001...
                                        ↑ 8 个前导零！
→ 你的估计: 2⁸ = 256 个不同元素
→ 实际: 仅 1 个

一个极端值就能让估算彻底失效。

单计数器的方差大到了不可用的程度。解决办法：多个计数器，取平均。

第四步：分桶策略（Stochastic Averaging）

取 hash 值的前 14 位用作桶编号（2¹⁴ = 16384 个桶），剩余 50 位用来数前导零：

hash("user_1") = [01101011100101] [000101011...]
                    └── 前14位 ──┘   └── 剩余50位 ──┘
                    桶编号 = 6874     数这部分的前导零 = 3

→ 桶 6874 的当前值 = max(桶旧值, 3)

每个桶只记住"这个桶里见过的最大前导零"，不存储任何具体元素。16384 个桶就是 16384 个独立的小实验，彼此互不干扰。

第五步：为什么用调和平均而不是算术平均？

算术平均的问题是：一个异常值就能毁掉整个估算。

桶的原始 M[j] 值: [5, 5, 6, 4, 5, 18, 5, 5]
                                  ↑ 撞大运的异常值

算术平均: (5+5+6+4+5+18+5+5)/8 ≈ 6.6 → 2^6.6 ≈ 97
去掉异常: (5+5+6+4+5+5+5)/7 = 5.0  → 2^5.0 = 32

一个桶撞大运，估算从 32 变成 97 —— 差了 3 倍。

调和平均天然压制极端值——因为它是对倒数求均值再取倒数：

极端值 18 的倒数是 1/18 ≈ 0.056 → 几乎不影响总和
正常值 5 的倒数是 1/5 = 0.200    → 主导贡献

所以 HLL 不使用 2^M[j] 的算术平均（被极端值绑架），而使用 2^(-M[j]) 的调和平均——极端值被倒数自动压制。

第六步：完整的估算公式

经过上述设计，HLL 的基数估算公式为：

α_m 通过大量实验确定，用于修正小基数时的系统性偏差。当 m ≥ 128 时：

α_m ≈ 0.7213 / (1 + 1.079/m)

对 m=16384，α₁₆₃₈₄ ≈ 0.7213。

第七步：为什么误差恰好是 0.81%？

这是概率论严格推导出的结果。HLL 的标准误差为：

σ ≈ 1.04 / √m

代入 m = 16384 = 2¹⁴：
σ = 1.04 / √16384 = 1.04 / 128 ≈ 0.008125 = 0.8125% ≈ 0.81%

为什么是 16384？
桶数翻 4 倍 → 误差减半，但内存也翻 4 倍。
16384 是精度与内存之间的 sweet spot —— 0.81% 误差 + 12KB 内存。

第八步：为什么刚好 12KB？

每个桶需要记录的最大前导零 ≈ log₂(2^64) = 64（实际很少超过 50）
所以每个桶用 6 bit（2⁶ = 64）

16384 个桶 × 6 bit = 98304 bit = 12288 byte = 12 KB

不多不少，恰好 12KB。不管统计的是 100 个还是一万亿个不同元素，内存开销恒定。

走一个完整例子

假设 m=8 个桶（为演示缩到极小），用 hash 的前 3 位做桶号：

元素1: hash = [010]0011...  → 桶2, 前导零=2 → 桶2记录 2
元素2: hash = [110]00010... → 桶6, 前导零=3 → 桶6记录 3
元素3: hash = [010]00001... → 桶2, 前导零=4 → 桶2更新为 max(2,4)=4
元素4: hash = [001]1...     → 桶1, 前导零=0 → 桶1记录 0
元素5: hash = [111]000100.. → 桶7, 前导零=3 → 桶7记录 3
元素6: hash = [110]01...    → 桶6, 前导零=1 → 桶6保持 max(3,1)=3

各桶最终值：

桶:   0    1    2    3    4    5    6    7
M:   [0,   0,   4,   0,   0,   0,   3,   3]

Σ(2^(-M[j])) = 1 + 1 + 1/16 + 1 + 1 + 1 + 1/8 + 1/8
             = 6 + 0.0625 + 0.25 = 6.3125

E = 0.72 × 64 / 6.3125 ≈ 7.3   ← 估计 7 个，实际 6 个（m 很小，已经很接近）

Redis 实现的偏差修正

上述公式在大基数下很准，但在极端情况下有偏。Redis 的实现加入了分段修正：

区间	策略	原因
小基数（E < 2.5m）	Linear Counting（数空桶数量线性估算）	桶未填满时调和平均有偏
正常基数	标准 HLL 公式	误差稳定在 0.81%
超大基数（E > 2³²/30）	修正公式防止溢出	接近 hash 空间上限时会有偏

原理总结

问题	解法
怎么把元素变成可统计的量？	Hash → 看作随机比特串
怎么从 hash 反推数量？	前导零的长度 ≈ log₂(基数)
单计数器方差太大怎么办？	多桶 → 随机平均（Stochastic Averaging）
用哪种平均压制异常值？	调和平均（对 2^(-M[j]) 求和）
估计有偏怎么办？	常数修正 + 大小基数分段处理

对比	Set	HyperLogLog
1 亿元素占用	~1.6 GB	12 KB
精确度	100% 精确	标准误差 0.81%
能否获取具体元素	✅ SMEMBERS	❌ 不可
能否判断某元素是否存在	✅ SISMEMBER	❌ 不可

2.4 应用场景

场景	key 设计	说明
页面 UV	uv:{page}:{date}	每日独立访客数
搜索关键词去重	search:keywords:{date}	今天有多少不同的搜索词
注册 IP 去重	register:ips:{date}	从多少不同 IP 注册
商品浏览人数	product:{id}:viewers	有多少人看过（非 PV）

3. GEO（地理位置）

GEO 提供了存储地理坐标（经纬度）并进行距离计算、范围搜索的能力。底层实现是 Sorted Set——将经纬度通过 GeoHash 编码为 52 位整数作为 score，member 是地点标识。

3.1 基础操作

# 存储几家门店的位置
GEOADD stores 116.397128 39.916527 "beijing_store"
GEOADD stores 121.473701 31.230416 "shanghai_store"
GEOADD stores 113.264385 23.129112 "guangzhou_store"
GEOADD stores 116.407526 39.904030 "tiananmen"

# 查看坐标
GEOPOS stores "beijing_store"
1) "116.39712780714035034"
2) "39.91652647362980844"

# 计算北京门店到天安门的距离
GEODIST stores "beijing_store" "tiananmen" KM
→ "1.3850"    ← 约 1.4 公里

# 北京到上海
GEODIST stores "beijing_store" "shanghai_store" KM
→ "1067.5980"

3.2 范围搜索

# 以天安门为中心，搜索 5 公里内的门店
GEOSEARCH stores FROMMEMBER "tiananmen" BYRADIUS 5 KM ASC WITHCOORD WITHDIST
1) 1) "tiananmen"
   2) "0.0000"
   3) 1) "116.40752649307250977"
      2) "39.90403009498505874"
2) 1) "beijing_store"
   2) "1.3850"
   3) 1) "116.39712780714035034"
      2) "39.91652647362980844"

# 以经纬度为中心搜索（不依赖已有 member）
GEOSEARCH stores FROMLONLAT 116.40 39.91 BYRADIUS 2 KM ASC COUNT 3 WITHDIST
1) 1) "tiananmen"
   2) "0.8245"
2) 1) "beijing_store"
   2) "0.7410"

# 矩形范围搜索
GEOSEARCH stores FROMLONLAT 116.40 39.91 BYBOX 10 10 KM ASC

3.3 应用场景

场景	key 设计	member	关键命令
附近的人/店	geo:stores	门店 ID	GEOSEARCH BYRADIUS
打车派单	geo:drivers:{city}	司机 ID	GEOSEARCH + WITHDIST
外卖配送范围	geo:riders	骑手 ID	GEOSEARCH BYRADIUS 3 KM
地理围栏	geo:devices	设备 ID	GEODIST 判断是否超出范围

4. Stream（消息流）

Stream 是 Redis 5.0 引入的日志型数据结构，专为消息队列设计。相比用 List 做队列的方案，Stream 原生支持：

• 消费者组（Consumer Group）：多个消费者分摊消息，不重复消费
• 消息确认（ACK）：处理完才确认，失败可重试
• 消息持久化：消息不会因被读取而消失
• 消息 ID 有序：天然按时间排序，可回溯

4.1 基础操作

# 生产者：发送订单事件
XADD orders * user_id 1001 action "create" amount 299
→ "1717200000000-0"    ← 自动生成的消息 ID

XADD orders * user_id 1002 action "pay" amount 599
→ "1717200000001-0"

XADD orders * user_id 1001 action "cancel" amount 299
→ "1717200000002-0"

# 查看消息数
XLEN orders    → (integer) 3

# 读取全部消息
XRANGE orders - +
1) 1) "1717200000000-0"
   2) 1) "user_id" 2) "1001" 3) "action" 4) "create" 5) "amount" 6) "299"
2) 1) "1717200000001-0"
   2) 1) "user_id" 2) "1002" 3) "action" 4) "pay" 5) "amount" 6) "599"
3) 1) "1717200000002-0"
   2) 1) "user_id" 2) "1001" 3) "action" 4) "cancel" 5) "amount" 6) "299"

# 限制 Stream 最多保留 1000 条（近似裁剪用 ~）
XADD orders MAXLEN ~ 1000 * user_id 1003 action "create" amount 199

# 消费者：阻塞等待新订单（类似 BLPOP）
XREAD BLOCK 0 STREAMS orders $
# ... 阻塞等待中，有新消息时立即返回

4.2 消费者组（Consumer Group）

消费者组是 Stream 相比 List 的杀手级特性——多个消费者共同消费同一个 Stream，每条消息只会被组内一个消费者处理。

# 创建消费者组（从头开始消费）
XGROUP CREATE orders order_processors 0
OK

# 消费者 worker_1 读取消息
XREADGROUP GROUP order_processors worker_1 COUNT 1 STREAMS orders >
1) 1) "orders"
   2) 1) 1) "1717200000000-0"
         2) 1) "user_id" 2) "1001" 3) "action" 4) "create" 5) "amount" 6) "299"

# 消费者 worker_2 读取消息（获得下一条，不重复）
XREADGROUP GROUP order_processors worker_2 COUNT 1 STREAMS orders >
1) 1) "orders"
   2) 1) 1) "1717200000001-0"
         2) 1) "user_id" 2) "1002" 3) "action" 4) "pay" 5) "amount" 6) "599"

# worker_1 处理完毕，确认
XACK orders order_processors "1717200000000-0"
→ (integer) 1

# 查看未确认消息（PEL）
XPENDING orders order_processors - + 10
1) 1) "1717200000001-0"
   2) "worker_2"
   3) (integer) 30000    ← 距上次投递已过 30 秒
   4) (integer) 1        ← 投递次数

# worker_2 挂了，30 秒后将其未确认消息转给 worker_3
XCLAIM orders order_processors worker_3 30000 "1717200000001-0"
→ 1) 1) "1717200000001-0"
      2) 1) "user_id" 2) "1002" ...

4.3 应用场景与对比

场景	Stream 优势
轻量消息队列	无需引入 Kafka/RabbitMQ，减少架构复杂度
事件溯源	消息持久化、可回溯、按时间范围查询
多消费者协作	消费者组 + ACK + 故障转移
异步任务分发	比 List 更可靠（消息不丢失、可重试）

Stream vs List vs Kafka

能力	List（BLPOP）	Stream	Kafka
消费模式	点对点（取走即没）	消费者组 + 广播	消费者组 + 广播
消息确认	❌	✅ XACK	✅ offset commit
消息持久化	消费即删	保留（可设 MAXLEN）	保留（按时间/容量）
消息回溯	❌	✅ XRANGE	✅ seek offset
吞吐量上限	万级/s	万级/s	百万级/s
运维复杂度	无	低（Redis 自带）	高（独立集群）
适用定位	简单临时队列	轻中量级可靠队列	大规模流式处理

5. 四种类型选型对比

需求	选择	理由
统计"有多少"（不关心"有哪些"）	HyperLogLog	12KB 固定内存，亿级基数
海量布尔状态（签到/在线/开关）	Bitmap	1bit/状态，支持位运算
"附近的XX"	GEO	原生经纬度存储 + 范围搜索
可靠消息队列（需 ACK/消费组）	Stream	原生消费者组，消息可回溯
精确去重 + 需要查具体元素	Set	HLL 不行时的 fallback
简单任务队列（不需 ACK）	List	Stream 杀鸡用牛刀时