← 返回学习路线

SYSTEM

数据结构

八股2.1 数据结构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 调大采样数提升精度。