SYSTEM
数据结构
src/content/notes/system/数据结构.md 二、Redis
2.1 数据结构
五种基本类型及底层实现
| 类型 | 底层结构 | 典型场景 |
|---|---|---|
| String | SDS(Simple Dynamic String) | 缓存、计数器、分布式锁 |
| List | quicklist(双向链表 + listpack 节点) | 消息队列、最新列表 |
| Hash | listpack(小) / hashtable(大) | 对象存储(用户信息) |
| Set | intset(纯整数) / hashtable | 去重、标签、共同好友 |
| ZSet | listpack(小) / skiplist + dict(大) | 排行榜、延迟队列 |
String 底层 SDS:相比 C 字符串,SDS 记录了 len 和 free 长度,获取长度 O(1),二进制安全(不依赖 \0 判断结尾),空间预分配和惰性释放减少内存重分配次数。
ZSet 底层 skiplist + dict:ZSet 同时需要排序(按 score)和查找(按 member)。skiplist(跳表)支持按 score 范围查询 O(logN),dict 支持 O(1) 按 member 查 score。两者组合让 ZSet 既能范围查询又能快速点查。
# ZSet 排行榜示例
ZADD ranking 100 alice 90 bob 85 charlie
# 按 score 降序取前3名
ZREVRANGE ranking 0 2 WITHSCORES
# 查看 alice 的排名
ZREVRANK ranking alice
HyperLogLog、Bitmap
- HyperLogLog:用于基数统计(UV 统计),12KB 内存可统计 2^64 个不同元素,误差率约 0.81%。不存储原始数据,不能取出具体值。
- Bitmap:位图,操作 String 的位,适合状态标记。1 亿用户签到只需约 12MB。
# HyperLogLog 统计 UV
PFADD uv:20260101 user1 user2 user3
PFCOUNT uv:20260101 # 返回基数
# Bitmap 签到
SETBIT sign:202601:uid001 0 1 # 1月1日签到
SETBIT sign:202601:uid001 1 1 # 1月2日签到
BITCOUNT sign:202601:uid001 # 统计签到天数
面试题
Q:Redis 有哪些数据类型?ZSet 底层是什么?
A:五种基本类型:String(SDS)、List(quicklist)、Hash(listpack/hashtable)、Set(intset/hashtable)、ZSet(listpack/skiplist+dict)。扩展类型有 HyperLogLog(基数统计)、Bitmap(位图)、GeoHash(地理位置)、Stream(消息流)。ZSet 底层在元素较少时用 listpack(紧凑连续内存),元素较多时切换为 skiplist + dict 的组合结构:skiplist 按 score 有序支持范围查询,dict 按 member 索引支持 O(1) 查找。切换条件是元素数超过 128 或单个元素长度超过 64 字节(可通过 zset-max-listpack-entries 和 zset-max-listpack-value 配置)。
2.2 持久化
RDB vs AOF
| RDB | AOF | |
|---|---|---|
| 原理 | 全量快照,fork 子进程生成二进制 dump 文件 | 追加写日志,记录每条写命令 |
| 触发方式 | save(阻塞)/ bgsave(后台)/ 自动触发 | always / everysec / no |
| 恢复速度 | 快(直接加载二进制文件) | 慢(需重放命令) |
| 数据安全 | 两次 RDB 之间的数据可能丢失 | everysec 最多丢 1 秒 |
| 文件大小 | 小(压缩二进制) | 大(文本命令,需 rewrite 压缩) |
RDB 为什么用 fork 子进程:Redis 是单线程处理命令的,生成快照时不能阻塞主线程。fork 后子进程共享主进程的内存页(写时复制 COW),子进程遍历内存生成快照,主进程继续处理请求。如果主进程修改了某页数据,操作系统才复制那一页。
AOF 的三种刷盘策略:always(每条命令刷盘,最安全但性能最差)、everysec(每秒刷盘,性能和安全折中,默认)、no(由操作系统决定,性能最好但可能丢数据)。
混合持久化(RDB + AOF)
Redis 4.0 引入混合持久化。AOF rewrite 时不再生成纯命令日志,而是先写 RDB 格式的全量数据,再追加 AOF 增量命令。恢复时先加载 RDB 快速恢复大部分数据,再重放 AOF 末尾的少量增量命令,兼顾恢复速度和数据安全。
AOF 文件结构(混合持久化):
[RDB binary data] [AOF command 1] [AOF command 2] ...
面试题
Q:RDB 和 AOF 的区别?怎么选?
A:RDB 是全量快照,fork 子进程生成二进制文件,恢复快但两次快照间可能丢数据;AOF 是追加写日志,记录每条写命令,数据安全但恢复慢。选择上:如果对数据安全性要求不高(如纯缓存),用 RDB 即可。如果不能丢数据,用 AOF + everysec,最多丢 1 秒。Redis 4.0 后推荐混合持久化,AOF 文件以 RDB 全量开头 + AOF 增量结尾,恢复时先快速加载 RDB 再重放少量 AOF 命令,兼顾速度和安全。生产中通常同时开启 RDB(用于冷备和快速重启)和 AOF(用于数据安全)。
2.3 过期策略
定期删除 + 惰性删除
Redis 对带过期时间的 key 采用两种策略配合:
- 定期删除:Redis 每 100ms 随机抽取部分设置了过期时间的 key 检查,删除已过期的。如果过期 key 比例超过 25%,继续抽样删除,循环直到比例降低。这是主动清理。
- 惰性删除:不主动检查,而是在 key 被访问时检查是否过期,过期则删除返回 nil。这是被动清理。
两种策略互补:定期删除清理大部分过期 key,惰性删除兜底处理定期删除遗漏的 key。如果大量过期 key 既没被定期删除命中,也没被访问触发惰性删除,内存会持续增长,这时由淘汰策略兜底。
面试题
Q:Redis 的过期策略是什么?
A:Redis 用定期删除 + 惰性删除的组合策略。定期删除是每隔 100ms 随机抽查一批带过期的 key,删除已过期的,如果过期比例超 25% 就继续抽样。惰性删除是访问 key 时才检查是否过期,过期就删掉。两种策略互补——定期删除处理大量过期的 key,惰性删除兜底处理定期删除没抽到的。如果两种策略都没及时清理,内存仍持续增长,就由内存淘汰策略兜底,当内存达到 maxmemory 限制时触发淘汰。
2.4 淘汰策略
8 种淘汰策略
当 Redis 内存使用达到 maxmemory 限制时,根据淘汰策略选择 key 删除以腾出空间:
| 策略 | 淘汰范围 | 算法 | 适用场景 |
|---|---|---|---|
| noeviction | 不淘汰 | — | 内存满时拒绝写入,适合不能丢数据的场景 |
| allkeys-lru | 所有 key | LRU | 缓存场景,淘汰最久未访问的 |
| allkeys-lfu | 所有 key | LFU | 缓存场景,淘汰访问频率最低的 |
| allkeys-random | 所有 key | 随机 | 无明显热点时 |
| volatile-lru | 设了过期的 key | LRU | 混合持久化和缓存时 |
| volatile-lfu | 设了过期的 key | LFU | 同上 |
| volatile-ttl | 设了过期的 key | 优先淘汰 TTL 短的 | 优先淘汰快过期的 |
| volatile-random | 设了过期的 key | 随机 | 同上 |
LRU vs LFU:LRU(最近最少使用)淘汰最久未访问的 key,但可能把偶尔被访问一次的冷数据保留。LFU(最不经常使用)淘汰访问频率最低的,更适合有稳定热点的场景。Redis 的 LRU 是近似实现,通过随机采样(默认采样 5 个)选最久未用的淘汰,而非维护全局链表,牺牲精度换性能。
# 配置淘汰策略
CONFIG SET maxmemory-policy allkeys-lru
# 配置 LRU 采样数量
CONFIG SET maxmemory-samples 10
面试题
Q:Redis 内存满了怎么办?
A:Redis 内存达到 maxmemory 限制时,根据淘汰策略处理。8 种策略分三类:noeviction 不淘汰直接拒绝写入;allkeys-* 在所有 key 中淘汰;volatile-* 只在设了过期时间的 key 中淘汰。算法有 LRU(淘汰最久未用)、LFU(淘汰最少使用)、TTL(优先淘汰快过期的)、random(随机)。纯缓存场景推荐 allkeys-lru 或 allkeys-lfu,有持久化数据时用 volatile-lru 只淘汰缓存不淘汰持久化数据。Redis 的 LRU 是近似算法,随机采样 5 个 key 选最久未用的淘汰,不是精确 LRU,可通过 maxmemory-samples 调大采样数提升精度。