Appearance
4.2-2 Redis 数据结构实现:SDS、listpack、quicklist、skiplist
所属:04 数据存储 / 4.2 Redis 分级:A 状态:◐ 初稿 关联:4.2-1、4.2-3、4.2-4、4.2-6、4.2-9、4.2-12、4.2-14
题型:原理 / 结构 / 对比
一句话结论:Redis 对外只有 String/List/Hash/Set/ZSet/Stream,对内是
redisObject+ 多种编码:String 用 SDS/int/embstr/raw;List 用 listpack/quicklist;Hash/Set/ZSet 小数据用 listpack/intset,大数据用 dict/skiplist。理解“编码切换阈值 + 内存布局 + 操作复杂度”,才能解释 Redis 为什么省内存、为什么 O(1)/O(logN)、为什么大 key 危险。分层要点:
- 对象模型:每个 key/value 是
redisObject,包含type、encoding、lru/lfu、refcount、ptr。type是对外类型,encoding是内部编码;OBJECT ENCODING key能看到当前实现。同一类型会随数据量/元素长度切换编码,编码是性能与内存的取舍。 - String:整数用
int;短字符串(≤44 字节)用embstr(redisObject+ SDS 一次分配);长字符串用raw(SDS 单独分配)。SDS 有len/alloc/flags/buf,二进制安全、O(1) 取长度、预分配、惰性释放,不像 C 字符串靠\0截断。 - Hash:field 少且短用
listpack(7.0 前是 ziplist),超过hash-max-listpack-entries(默认 128)或 field/value 超过hash-max-listpack-value(默认 64 字节)转hashtable(dict)。dict 是拉链哈希表,支持渐进式 rehash。 - List:7.0 起是
quicklist,每个节点是一个listpack;节点过多会分裂,元素过大可退化为 plain 节点。list-max-listpack-size控制节点大小/元素数,list-compress-depth控制中间节点 LZF 压缩。它兼顾链表插入和数组紧凑。 - Set:全整数且数量 ≤
set-max-intset-entries(默认 512)用intset(有序整数数组,二分查找);小集合且元素短可用listpack(7.2 起,按版本);否则hashtable(dict,value 为空)。 - ZSet:元素少且 member 短用
listpack;超过zset-max-listpack-entries(128)或zset-max-listpack-value(64)转 dict + skiplist。dict 存 member→score,支持 O(1)ZSCORE;skiplist 按 score 有序,支持范围/排名 O(logN)。 - listpack vs ziplist:ziplist 每个 entry 存
prevlen,插入大 entry 可能触发“连锁更新”;listpack 用 entry 尾部的backlen记录自身长度,不依赖前一个 entry,避免级联,7.0 起替代 ziplist 作为小对象编码。 - 大 key 与复杂度:紧凑编码只在“小”时成立,超过阈值转 dict/skiplist,内存和操作复杂度都会变化;大 key 还会阻塞删除、迁移、持久化、集群槽迁移。用
OBJECT ENCODING、MEMORY USAGE、--bigkeys/--memkeys诊断,删除优先UNLINK或分批删。
- 对象模型:每个 key/value 是
图/流程:
text
redisObject:
type String/List/Hash/Set/ZSet/Stream
encoding int/embstr/raw/listpack/quicklist/intset/hashtable/skiplist
lru/lfu 淘汰信息
refcount 引用计数
ptr 指向具体结构text
String 编码:
纯整数 → int
≤44 字节 → embstr(robj + SDS 一次分配,只读)
>44 字节 → raw(robj + SDS 分开)
APPEND/SETRANGE → 通常转 rawtext
SDS:
+------+--------+-------+------------------+---+
| len | alloc | flags | buf[] |\0 |
+------+--------+-------+------------------+---+
len 已用长度
alloc 分配长度(预分配)
flags 头类型(sdshdr5/8/16/32/64)
buf 二进制安全,可存 \0text
Hash/Set/ZSet 编码决策:
小且短 → listpack(Hash/ZSet;Set 7.2+)
全整数小集合 → intset
超过阈值 → hashtable / skiplist
阈值看 entries + value 长度,任一超限就转换text
ziplist:
[zlbytes][zltail][zllen][entry...][zlend]
entry: [prevlen][encoding][data]
插入大 entry → 后续 prevlen 变长 → 连锁更新
listpack:
[total-bytes][num-elements][entry...][0xFF]
entry: [encoding][data][backlen]
backlen 记录自身长度 → 不依赖前一个 entry → 无连锁更新text
quicklist:
quicklist
↔ node(listpack) ↔ node(listpack) ↔ node(listpack)
每个 node 是一段连续 listpack
list-max-listpack-size 控制 node 大小
list-compress-depth 控制中间 node 压缩text
skiplist:
level 3 head ─────────────────────→ node ─────────→ nil
level 2 head ───────→ node ───────→ node ─────────→ nil
level 1 head → node → node → node → node → node → nil
node: ele, score, backward, level[] {forward, span}版本/源码锚点:
- Redis 3.2:
embstr阈值 44 字节;SDS 五种头类型。 - Redis 5.0:Stream 引入,listpack 首次用于 Stream。
- Redis 7.0:Hash/ZSet/List 的小对象编码从 ziplist 切换为 listpack;
hash-max-listpack-*、zset-max-listpack-*、list-max-listpack-size。 - Redis 7.2:小 Set 增加 listpack 编码(
set-max-listpack-entries/set-max-listpack-value,以版本为准)。 - 源码:
src/sds.c、src/object.c、src/t_string.c、src/t_hash.c、src/t_list.c、src/t_set.c、src/t_zset.c、src/ziplist.c、src/listpack.c、src/quicklist.c、src/dict.c、src/server.c。
- Redis 3.2:
类型与编码:
| 对外类型 | 内部编码 | 触发条件(常见) | 特点 |
|---|---|---|---|
| String | int | 纯整数 | 直接存指针,省内存 |
| String | embstr | ≤44 字节 | 一次分配,只读,修改转 raw |
| String | raw | >44 字节 | SDS 单独分配,可修改 |
| List | quicklist | 所有 List | 链表 + listpack 节点 |
| Hash | listpack | entries ≤128 且 field/value ≤64 | 连续内存,小数据省 |
| Hash | hashtable | 超阈值 | dict,O(1) 平均 |
| Set | intset | 全整数且 ≤512 | 有序数组,二分 |
| Set | listpack | 小且短(7.2+) | 连续内存 |
| Set | hashtable | 超阈值/非整数 | dict |
| ZSet | listpack | entries ≤128 且 member ≤64 | 连续内存 |
| ZSet | skiplist | 超阈值 | dict + skiplist |
| Stream | stream | 所有 Stream | rax + listpack |
- SDS 头类型:
| 类型 | 长度字段 | 适用 | 说明 |
|---|---|---|---|
sdshdr5 | 5 bit | 很短字符串 | 无 alloc/len 字段,flags 存长度 |
sdshdr8 | 1 字节 | <256 | 常用 |
sdshdr16 | 2 字节 | <64KB | 中等 |
sdshdr32 | 4 字节 | <4GB | 大字符串 |
sdshdr64 | 8 字节 | 更大 | 极大字符串 |
- dict 结构:
| 结构 | 字段 | 作用 |
|---|---|---|
dict | ht[2]、rehashidx、type、privdata | 两个哈希表,渐进式 rehash |
dictht | table、size、used、sizemask | 一个哈希表 |
dictEntry | key、v、next | 拉链节点 |
| 负载因子 | used / size | ≥1 扩容(无 fork 时可放宽),<0.1 缩容 |
| rehash | ht[0] → ht[1] | 每次操作搬一个桶,查找查两张表 |
activerehashing | yes | 周期性增量 rehash,避免一次性卡顿 |
- listpack / ziplist 对比:
| 维度 | ziplist | listpack |
|---|---|---|
| 头部 | zlbytes/zltail/zllen | total-bytes/num-elements |
| entry 前向长度 | prevlen | 无 |
| entry 尾部 | 无 | backlen |
| 连锁更新 | 可能(prevlen 变长) | 不会(backlen 只描述自身) |
| 查找 | O(N) 顺序 | O(N) 顺序 |
| 适用 | 旧版本小对象 | 7.0+ 小对象、Stream |
- quicklist 关键点:
| 项 | 说明 |
|---|---|
| 结构 | 双向链表,每个节点是 listpack |
| 节点大小 | list-max-listpack-size:正数=元素数,负数=字节上限(-2 约 8KB) |
| 压缩 | list-compress-depth:0 不压缩,>0 压缩中间节点(LZF) |
| 大元素 | 单个元素过大时节点可为 plain,不塞进 listpack |
| 查找 | 按 index 需遍历节点,O(节点数 + 节点内偏移) |
| 适用 | 队列/栈/最新列表,兼顾插入与内存 |
- skiplist 关键点:
| 项 | 说明 |
|---|---|
| 最大层数 | ZSKIPLIST_MAXLEVEL = 32 |
| 晋升概率 | ZSKIPLIST_P = 0.25 |
| 平均层数 | 约 1/(1-p) = 1.33 |
| 节点 | ele、score、backward、level[] |
| 层 | forward 前进指针、span 跨度 |
| 排名 | 通过 span 累加,ZRANK O(logN) |
| 范围 | 按 score 顺序遍历,ZRANGE O(logN+M) |
| 最坏 | 概率极低,期望 O(logN) |
- 复杂度速查:
| 操作 | 编码 | 复杂度 |
|---|---|---|
GET/SET | int/embstr/raw | O(1)/O(N) 字符串长度 |
HGET/HSET | listpack | O(N)(N 为 field 数) |
HGET/HSET | hashtable | O(1) 平均 |
LPUSH/RPUSH | quicklist | O(1) |
LINDEX | quicklist | O(节点数) |
SADD/SISMEMBER | intset | O(logN) |
SADD/SISMEMBER | hashtable | O(1) 平均 |
ZSCORE | skiplist | O(1)(dict) |
ZRANK/ZRANGE | skiplist | O(logN)/O(logN+M) |
- 关键配置:
| 配置 | 默认(常见) | 作用 |
|---|---|---|
hash-max-listpack-entries | 128 | Hash 转 hashtable 的 field 数 |
hash-max-listpack-value | 64 | Hash field/value 长度上限 |
list-max-listpack-size | -2 | quicklist 节点大小/元素数 |
list-compress-depth | 0 | quicklist 中间节点压缩深度 |
set-max-intset-entries | 512 | intset 转 hashtable 的整数个数 |
set-max-listpack-entries | 128 | Set listpack 元素数(7.2+) |
set-max-listpack-value | 64 | Set listpack 元素长度(7.2+) |
zset-max-listpack-entries | 128 | ZSet 转 skiplist 的元素数 |
zset-max-listpack-value | 64 | ZSet member 长度上限 |
activerehashing | yes | 增量 rehash |
深挖点(面试官常追的 6 个):
- SDS 为什么不用 C 字符串:C 字符串靠
\0结尾,不能存二进制、取长度 O(N)、拼接易溢出、修改要频繁重分配。SDS 用len做 O(1) 长度、alloc做预分配(小于 1MB 翻倍,大于 1MB 每次加 1MB)、二进制安全、兼容 C 字符串函数;embstr把robj和 SDS 放一次分配,减少内存碎片和两次释放。 - ziplist 的连锁更新与 listpack 的修复:ziplist entry 的
prevlen在“前一个 entry <254 字节”时占 1 字节,否则占 5 字节;插入一个 ≥254 字节的 entry 可能让后续 entry 的prevlen变长,进而改变自身长度并继续影响下一个,最坏 O(N²)。listpack 把长度信息放在 entry 尾部backlen,只描述自身,不依赖前驱,所以不会级联。 - dict 渐进式 rehash:扩容时申请
ht[1],把rehashidx从 0 开始,每次增删查搬一个桶;查找同时查ht[0]/ht[1],新增只进ht[1];全部搬完交换两张表。这样避免一次性 rehash 阻塞 Redis 单线程;activerehashing负责在空闲周期继续推进。 - quicklist 的取舍:纯链表每个节点都有 prev/next 指针,内存开销大、局部性差;一个大 listpack 又会在中间插入/删除时搬移大量内存。quicklist 用“链表 + 多个 listpack 节点”折中:节点内连续、节点间链表,插入只影响一个节点;
list-max-listpack-size控制节点大小,list-compress-depth用 LZF 压缩中间节点,用 CPU 换内存。 - ZSet 为什么 dict + skiplist:dict 提供 member→score 的 O(1) 查询(
ZSCORE),skiplist 提供按 score 有序的范围/排名(ZRANGE、ZRANK)。只用一个都不够:只用 dict 无法范围查询,只用 skiplist 查 score 要 O(logN) 且要实现额外映射。skiplist 相比红黑树实现更简单、范围遍历自然、无需旋转;B+ 树更适合磁盘页,Redis 全内存,指针跳转可接受。 - 编码阈值与大 key:紧凑编码的前提是“小”,超过 entries/value 阈值就转 dict/skiplist,内存和复杂度都会变。大 key 不只是占内存:
DEL同步释放会阻塞、RDB/AOF 重写慢、集群槽迁移卡、删除/过期抖动。要用OBJECT ENCODING看实现、MEMORY USAGE估算、--bigkeys/--memkeys发现,删除用UNLINK或HSCAN/SSCAN/ZSCAN分批。
- SDS 为什么不用 C 字符串:C 字符串靠
追问链:
- Redis 对象结构? →
redisObject:type、encoding、lru/lfu、refcount、ptr。 - type 和 encoding 区别? → type 是对外类型,encoding 是内部实现。
- String 有哪些编码? → int、embstr、raw。
- SDS 结构? → len、alloc、flags、buf,二进制安全。
- SDS 相比 C 字符串? → O(1) 长度、二进制安全、预分配、防溢出、兼容 C。
- 为什么 embstr 阈值是 44? → 64 字节 jemalloc 块:robj 16 + sdshdr8 3 + buf 44 + \0 1。
- embstr 修改会怎样? → 转 raw,因为 embstr 是只读的一次分配。
- String 什么时候是 int? → 纯整数;
APPEND/SETRANGE转 raw。 - Hash 小数据用什么? → 7.0+ listpack;7.0 前 ziplist。
- Hash 什么时候转 hashtable? → entries 超 128 或 field/value 超 64。
- dict 结构? → 两个 dictht、拉链、rehashidx。
- 渐进式 rehash 怎么做? → 每次操作搬一个桶,查找双表,新增进新表。
- rehash 期间查找? → 先查 ht[0],再查 ht[1]。
- 负载因子? → used/size;≥1 扩容,<0.1 缩容;fork 时可放宽。
activerehashing作用? → 周期性增量 rehash,避免一次性阻塞。- ziplist 结构? → zlbytes/zltail/zllen/entry/zlend;entry 有 prevlen。
- ziplist 连锁更新? → prevlen 1→5 字节导致后续 entry 变长,级联。
- listpack 怎么解决? → entry 尾部 backlen,不依赖前驱。
- List 用什么编码? → 7.0+ quicklist(listpack 节点)。
- quicklist 结构? → 双向链表,每个节点是 listpack。
- quicklist 节点大小? →
list-max-listpack-size,正数元素数/负数字节上限。 - quicklist 压缩? →
list-compress-depth,LZF 压缩中间节点。 - Set 有哪些编码? → intset、listpack(7.2+)、hashtable。
- intset 结构? → encoding、length、有序 contents;二分查找。
- intset 升级? → 元素超出 16/32 位时整体升级到 32/64 位。
- ZSet 有哪些编码? → listpack、skiplist(dict + skiplist)。
- skiplist 结构? → 节点 ele/score/backward/level[],层有 forward/span。
- 跳表层数怎么定? → 最大 32,p=0.25,随机晋升。
- 为什么 ZSet 不用红黑树? → 跳表实现简单、范围遍历自然、无需旋转;内存/指针可接受。
- 为什么不用 B+ 树? → B+ 树为磁盘页设计,Redis 全内存,跳表更简单。
- ZSet 为什么还要 dict? → O(1) 查 score;skiplist 负责有序/范围。
- ZRANK 怎么算? → 沿层累加 span。
- Stream 底层? → rax 基数树 + listpack,消费者组 PEL。
- 大 key 危害? → 阻塞删除/过期、持久化慢、迁移卡、网络/内存抖动。
- 怎么发现大 key? →
--bigkeys、--memkeys、MEMORY USAGE、OBJECT ENCODING、SCAN。 MEMORY USAGE精确吗? → 估算,抽样;看趋势够用。- 编码会转回去吗? → 运行期通常只升不降,删除元素不自动缩回;必要时重建 key。
- 阈值怎么调? → 按数据分布/内存/CPU 压测;不是越大越好。
- listpack 查找复杂度? → O(N) 顺序,适合小对象。
- quicklist 查找复杂度? → 按 index 遍历节点,O(节点数 + 节点内偏移)。
- Redis 单线程为什么还快? → 内存操作、IO 多路复用、紧凑编码、避免锁/上下文切换;6.0 网络 IO 多线程。
- 编码和持久化关系? → RDB 存紧凑编码;AOF 重写按命令重建,编码可能变化。
- 集群和数据结构? → key 按槽分片;大 key/热 key 会造成槽倾斜。
- 大 key 怎么删? →
UNLINK;集合用HSCAN/SSCAN/ZSCAN分批删;ListLTRIM/LPOP分批。 - Redis 7 有什么变化? → listpack 替代 ziplist 作为小对象编码;Set 7.2+ 支持 listpack。
- Redis 对象结构? →
生产案例/取舍(示例,替换成你的项目):
- Hash 存 100 万 field,超过 128 转 hashtable,内存暴涨;拆 key 或分桶。
- ZSet 榜单 100 万 member,skiplist 支撑
ZRANGE;按业务分榜降低单 key 大小。 - List 当队列,
list-max-listpack-size调小降低单节点延迟,调大省内存。 - Set 用户标签全整数,intset 很省;混入字符串后转 hashtable,内存上升。
- String 存 1MB JSON,
raw+ 大 key;压缩/拆分/换 Hash。 - 旧 Redis 6 的 ziplist 连锁更新导致偶发卡顿;升级 7.0 listpack。
OBJECT ENCODING发现 Hash 提前转 hashtable,原因是某个 value 超过 64 字节;治理超长 value。--bigkeys发现 500 万元素的 ZSet;ZSCAN分批清理 +UNLINK。- 集群某槽有大 key,迁移卡住;拆分 key 后迁移。
- 取舍:listpack 省内存但 O(N),hashtable O(1) 但指针多;quicklist 折中插入/内存;skiplist 换范围能力,代价是指针/概率最坏;压缩换内存,代价是 CPU。
易错点:
- 认为 String 就是 C 字符串。
- 认为 embstr 可以原地修改。
- 认为 String 永远是 int/embstr/raw 之一不变。
- 认为 Hash 小数据一定是 ziplist(7.0+ 是 listpack)。
- 混淆 ziplist 和 listpack。
- 认为 ziplist/listpack 查找是 O(1)。
- 认为 listpack 还会连锁更新。
- 认为 quicklist 是纯链表。
- 认为 quicklist 每个元素一个节点。
- 认为 Set 只有 intset/hashtable(7.2+ 还有 listpack)。
- 认为 intset 查找 O(1)(二分 O(logN))。
- 认为 ZSet 只靠 skiplist(还有 dict)。
- 认为跳表层数固定/最坏也是 O(logN)。
- 认为编码转换可逆,删元素就省内存。
- 认为阈值越大越好。
- 认为大 key 只影响内存。
- 用
KEYS *找大 key。 - 生产随便
DEBUG OBJECT。 - 认为
MEMORY USAGE精确到字节。 - 认为 listpack 一定比 hashtable 快。
- 忽略 AOF 重写/迁移后编码变化。
- 认为 Redis 7 所有旧编码都不存在(旧 RDB 兼容仍要认识 ziplist)。
30 秒口述稿:
Redis 对外是五种类型,对内是
redisObject+ 编码。String 用 SDS,整数 int、短字符串 embstr、长字符串 raw;List 是 quicklist,节点是 listpack;Hash/Set/ZSet 小数据用 listpack/intset,超过阈值转 dict 或 skiplist。listpack 用 backlen 解决了 ziplist 的连锁更新;quicklist 用链表套 listpack 兼顾插入和内存;ZSet 用 dict + skiplist,dict 查 score,skiplist 做范围/排名。编码阈值和大 key 是性能和内存的关键。
- 3 分钟展开顺序:结论(对象 + 编码)→ String/SDS/embstr 44 → Hash/listpack/dict 渐进 rehash → List/quicklist → Set/intset/listpack → ZSet/skiplist/dict → ziplist vs listpack 连锁更新 → 阈值/大 key/监控 → 生产案例与取舍。