Skip to content

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 危险。

  • 分层要点:

    1. 对象模型:每个 key/value 是 redisObject,包含 type、encoding、lru/lfu、refcount、ptr。type 是对外类型,encoding 是内部编码;OBJECT ENCODING key 能看到当前实现。同一类型会随数据量/元素长度切换编码,编码是性能与内存的取舍。
    2. String:整数用 int;短字符串(≤44 字节)用 embstr(redisObject + SDS 一次分配);长字符串用 raw(SDS 单独分配)。SDS 有 len/alloc/flags/buf,二进制安全、O(1) 取长度、预分配、惰性释放,不像 C 字符串靠 \0 截断。
    3. Hash:field 少且短用 listpack(7.0 前是 ziplist),超过 hash-max-listpack-entries(默认 128)或 field/value 超过 hash-max-listpack-value(默认 64 字节)转 hashtable(dict)。dict 是拉链哈希表,支持渐进式 rehash。
    4. List:7.0 起是 quicklist,每个节点是一个 listpack;节点过多会分裂,元素过大可退化为 plain 节点。list-max-listpack-size 控制节点大小/元素数,list-compress-depth 控制中间节点 LZF 压缩。它兼顾链表插入和数组紧凑。
    5. Set:全整数且数量 ≤ set-max-intset-entries(默认 512)用 intset(有序整数数组,二分查找);小集合且元素短可用 listpack(7.2 起,按版本);否则 hashtable(dict,value 为空)。
    6. 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)。
    7. listpack vs ziplist:ziplist 每个 entry 存 prevlen,插入大 entry 可能触发“连锁更新”;listpack 用 entry 尾部的 backlen 记录自身长度,不依赖前一个 entry,避免级联,7.0 起替代 ziplist 作为小对象编码。
    8. 大 key 与复杂度:紧凑编码只在“小”时成立,超过阈值转 dict/skiplist,内存和操作复杂度都会变化;大 key 还会阻塞删除、迁移、持久化、集群槽迁移。用 OBJECT ENCODING、MEMORY USAGE、--bigkeys/--memkeys 诊断,删除优先 UNLINK 或分批删。
  • 图/流程:

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 → 通常转 raw
text
SDS:
  +------+--------+-------+------------------+---+
  | len  | alloc  | flags | buf[]            |\0 |
  +------+--------+-------+------------------+---+
  len  已用长度
  alloc 分配长度(预分配)
  flags 头类型(sdshdr5/8/16/32/64)
  buf  二进制安全,可存 \0
text
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。
  • 类型与编码:

对外类型内部编码触发条件(常见)特点
Stringint纯整数直接存指针,省内存
Stringembstr≤44 字节一次分配,只读,修改转 raw
Stringraw>44 字节SDS 单独分配,可修改
Listquicklist所有 List链表 + listpack 节点
Hashlistpackentries ≤128 且 field/value ≤64连续内存,小数据省
Hashhashtable超阈值dict,O(1) 平均
Setintset全整数且 ≤512有序数组,二分
Setlistpack小且短(7.2+)连续内存
Sethashtable超阈值/非整数dict
ZSetlistpackentries ≤128 且 member ≤64连续内存
ZSetskiplist超阈值dict + skiplist
Streamstream所有 Streamrax + listpack
  • SDS 头类型:
类型长度字段适用说明
sdshdr55 bit很短字符串无 alloc/len 字段,flags 存长度
sdshdr81 字节<256常用
sdshdr162 字节<64KB中等
sdshdr324 字节<4GB大字符串
sdshdr648 字节更大极大字符串
  • dict 结构:
结构字段作用
dictht[2]、rehashidx、type、privdata两个哈希表,渐进式 rehash
dicthttable、size、used、sizemask一个哈希表
dictEntrykey、v、next拉链节点
负载因子used / size≥1 扩容(无 fork 时可放宽),<0.1 缩容
rehashht[0] → ht[1]每次操作搬一个桶,查找查两张表
activerehashingyes周期性增量 rehash,避免一次性卡顿
  • listpack / ziplist 对比:
维度ziplistlistpack
头部zlbytes/zltail/zllentotal-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/SETint/embstr/rawO(1)/O(N) 字符串长度
HGET/HSETlistpackO(N)(N 为 field 数)
HGET/HSEThashtableO(1) 平均
LPUSH/RPUSHquicklistO(1)
LINDEXquicklistO(节点数)
SADD/SISMEMBERintsetO(logN)
SADD/SISMEMBERhashtableO(1) 平均
ZSCOREskiplistO(1)(dict)
ZRANK/ZRANGEskiplistO(logN)/O(logN+M)
  • 关键配置:
配置默认(常见)作用
hash-max-listpack-entries128Hash 转 hashtable 的 field 数
hash-max-listpack-value64Hash field/value 长度上限
list-max-listpack-size-2quicklist 节点大小/元素数
list-compress-depth0quicklist 中间节点压缩深度
set-max-intset-entries512intset 转 hashtable 的整数个数
set-max-listpack-entries128Set listpack 元素数(7.2+)
set-max-listpack-value64Set listpack 元素长度(7.2+)
zset-max-listpack-entries128ZSet 转 skiplist 的元素数
zset-max-listpack-value64ZSet member 长度上限
activerehashingyes增量 rehash
  • 深挖点(面试官常追的 6 个):

    1. SDS 为什么不用 C 字符串:C 字符串靠 \0 结尾,不能存二进制、取长度 O(N)、拼接易溢出、修改要频繁重分配。SDS 用 len 做 O(1) 长度、alloc 做预分配(小于 1MB 翻倍,大于 1MB 每次加 1MB)、二进制安全、兼容 C 字符串函数;embstr 把 robj 和 SDS 放一次分配,减少内存碎片和两次释放。
    2. ziplist 的连锁更新与 listpack 的修复:ziplist entry 的 prevlen 在“前一个 entry <254 字节”时占 1 字节,否则占 5 字节;插入一个 ≥254 字节的 entry 可能让后续 entry 的 prevlen 变长,进而改变自身长度并继续影响下一个,最坏 O(N²)。listpack 把长度信息放在 entry 尾部 backlen,只描述自身,不依赖前驱,所以不会级联。
    3. dict 渐进式 rehash:扩容时申请 ht[1],把 rehashidx 从 0 开始,每次增删查搬一个桶;查找同时查 ht[0]/ht[1],新增只进 ht[1];全部搬完交换两张表。这样避免一次性 rehash 阻塞 Redis 单线程;activerehashing 负责在空闲周期继续推进。
    4. quicklist 的取舍:纯链表每个节点都有 prev/next 指针,内存开销大、局部性差;一个大 listpack 又会在中间插入/删除时搬移大量内存。quicklist 用“链表 + 多个 listpack 节点”折中:节点内连续、节点间链表,插入只影响一个节点;list-max-listpack-size 控制节点大小,list-compress-depth 用 LZF 压缩中间节点,用 CPU 换内存。
    5. ZSet 为什么 dict + skiplist:dict 提供 member→score 的 O(1) 查询(ZSCORE),skiplist 提供按 score 有序的范围/排名(ZRANGE、ZRANK)。只用一个都不够:只用 dict 无法范围查询,只用 skiplist 查 score 要 O(logN) 且要实现额外映射。skiplist 相比红黑树实现更简单、范围遍历自然、无需旋转;B+ 树更适合磁盘页,Redis 全内存,指针跳转可接受。
    6. 编码阈值与大 key:紧凑编码的前提是“小”,超过 entries/value 阈值就转 dict/skiplist,内存和复杂度都会变。大 key 不只是占内存:DEL 同步释放会阻塞、RDB/AOF 重写慢、集群槽迁移卡、删除/过期抖动。要用 OBJECT ENCODING 看实现、MEMORY USAGE 估算、--bigkeys/--memkeys 发现,删除用 UNLINK 或 HSCAN/SSCAN/ZSCAN 分批。
  • 追问链:

    1. Redis 对象结构? → redisObject:type、encoding、lru/lfu、refcount、ptr。
    2. type 和 encoding 区别? → type 是对外类型,encoding 是内部实现。
    3. String 有哪些编码? → int、embstr、raw。
    4. SDS 结构? → len、alloc、flags、buf,二进制安全。
    5. SDS 相比 C 字符串? → O(1) 长度、二进制安全、预分配、防溢出、兼容 C。
    6. 为什么 embstr 阈值是 44? → 64 字节 jemalloc 块:robj 16 + sdshdr8 3 + buf 44 + \0 1。
    7. embstr 修改会怎样? → 转 raw,因为 embstr 是只读的一次分配。
    8. String 什么时候是 int? → 纯整数;APPEND/SETRANGE 转 raw。
    9. Hash 小数据用什么? → 7.0+ listpack;7.0 前 ziplist。
    10. Hash 什么时候转 hashtable? → entries 超 128 或 field/value 超 64。
    11. dict 结构? → 两个 dictht、拉链、rehashidx。
    12. 渐进式 rehash 怎么做? → 每次操作搬一个桶,查找双表,新增进新表。
    13. rehash 期间查找? → 先查 ht[0],再查 ht[1]。
    14. 负载因子? → used/size;≥1 扩容,<0.1 缩容;fork 时可放宽。
    15. activerehashing 作用? → 周期性增量 rehash,避免一次性阻塞。
    16. ziplist 结构? → zlbytes/zltail/zllen/entry/zlend;entry 有 prevlen。
    17. ziplist 连锁更新? → prevlen 1→5 字节导致后续 entry 变长,级联。
    18. listpack 怎么解决? → entry 尾部 backlen,不依赖前驱。
    19. List 用什么编码? → 7.0+ quicklist(listpack 节点)。
    20. quicklist 结构? → 双向链表,每个节点是 listpack。
    21. quicklist 节点大小? → list-max-listpack-size,正数元素数/负数字节上限。
    22. quicklist 压缩? → list-compress-depth,LZF 压缩中间节点。
    23. Set 有哪些编码? → intset、listpack(7.2+)、hashtable。
    24. intset 结构? → encoding、length、有序 contents;二分查找。
    25. intset 升级? → 元素超出 16/32 位时整体升级到 32/64 位。
    26. ZSet 有哪些编码? → listpack、skiplist(dict + skiplist)。
    27. skiplist 结构? → 节点 ele/score/backward/level[],层有 forward/span。
    28. 跳表层数怎么定? → 最大 32,p=0.25,随机晋升。
    29. 为什么 ZSet 不用红黑树? → 跳表实现简单、范围遍历自然、无需旋转;内存/指针可接受。
    30. 为什么不用 B+ 树? → B+ 树为磁盘页设计,Redis 全内存,跳表更简单。
    31. ZSet 为什么还要 dict? → O(1) 查 score;skiplist 负责有序/范围。
    32. ZRANK 怎么算? → 沿层累加 span。
    33. Stream 底层? → rax 基数树 + listpack,消费者组 PEL。
    34. 大 key 危害? → 阻塞删除/过期、持久化慢、迁移卡、网络/内存抖动。
    35. 怎么发现大 key? → --bigkeys、--memkeys、MEMORY USAGE、OBJECT ENCODING、SCAN。
    36. MEMORY USAGE 精确吗? → 估算,抽样;看趋势够用。
    37. 编码会转回去吗? → 运行期通常只升不降,删除元素不自动缩回;必要时重建 key。
    38. 阈值怎么调? → 按数据分布/内存/CPU 压测;不是越大越好。
    39. listpack 查找复杂度? → O(N) 顺序,适合小对象。
    40. quicklist 查找复杂度? → 按 index 遍历节点,O(节点数 + 节点内偏移)。
    41. Redis 单线程为什么还快? → 内存操作、IO 多路复用、紧凑编码、避免锁/上下文切换;6.0 网络 IO 多线程。
    42. 编码和持久化关系? → RDB 存紧凑编码;AOF 重写按命令重建,编码可能变化。
    43. 集群和数据结构? → key 按槽分片;大 key/热 key 会造成槽倾斜。
    44. 大 key 怎么删? → UNLINK;集合用 HSCAN/SSCAN/ZSCAN 分批删;List LTRIM/LPOP 分批。
    45. Redis 7 有什么变化? → listpack 替代 ziplist 作为小对象编码;Set 7.2+ 支持 listpack。
  • 生产案例/取舍(示例,替换成你的项目):

    • 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/监控 → 生产案例与取舍。