数据结构拆解：SDS、Dict、Listpack 与 Skiplist

本文是 Redis 系统学习系列的 L2 核心篇。前置：28. 五种数据类型的典型业务用法。学完可以配合面试题食用：01-data-structures-encoding

为什么底层数据结构重要

你写 SET key "hello" 只是存了一个字符串，但 Redis 在内存里存的不只是 "hello" 裸字符串。它包了一层结构——SDS。为什么？C 语言以 \0 结尾算长度需要 O(n)，Redis 不能容忍这个开销。

同理，Redis 的 Hash 类型、Set 类型、ZSet 类型，底层都不是"一种数据结构打天下"。Redis 会根据数据规模动态切换编码，用最紧凑的内存布局服务小数据，用最快速的结构服务大数据。

理解这四种结构，你就读懂了 Redis 内存优化的所有出厂设置。

SDS：不止是 C 字符串的包装

Redis 的字符串底层不是 char*，而是 SDS（Simple Dynamic String）。

struct sdshdr {
    int len;    // 已用长度
    int alloc;  // 总分配长度
    char buf[]; // 柔性数组
};

三个关键设计：

O(1) 长度获取：len 字段直接返回，不用遍历。C 的 strlen 是 O(n)。
预分配：修改字符串时，如果 len < 1MB，一次分配双倍空间；超过 1MB 则每次多分配 1MB。这保证了 APPEND 操作不会每次触发 realloc。
惰性释放：缩短字符串不会释放多余内存，只改 len。需要归还内存时显式调用 sdsRemoveFreeSpace。

二进制安全：SDS 用 len 判断结尾，而不是 \0。所以 SDS 可以存视频、图片、序列化对象——只要不触发 \0 截断的 API（比如 strlen 相关操作），你存什么字节都行。

补充说明：embstr 为什么是 44 字节？因为 Redis 3.0 起的 redisObject 占 16 字节，加上 SDS 头 3 字节（sdshdr8 的 len+alloc+flags），再加 \0 结尾 1 字节，64 字节 jemalloc 最小分配填满后留给内容的就是 64 - 16 - 3 - 1 = 44 字节。这就是 embstr 和 raw 的分界线——非要 45 字节，编码就升级为 raw，多一次指针间接。

Dict：渐进式 rehash 是增量迁移的教科书

Redis 的 Dict 本质是哈希表，但它的 rehash 不是一次性搬完，而是分多次、每次只搬一小批。

struct dict {
    dictEntry **ht[2];  // 双表
    int rehashidx;      // -1 表示未 rehash
};

为什么不能一次搬完？因为 Redis 是单线程。如果一次搬 100 万 entry，事件循环阻塞几秒到几十秒，所有请求排队，这就是一次生产事故。

渐进式 rehash 怎么做：

条件触发（负载因子 > 1（无 BGSAVE）或 5（有 BGSAVE））→ 分配 ht[1]，rehashidx = 0
每次增删改查，除了操作自己的表，还顺手把 ht[0][rehashidx] 整条链表搬到 ht[1]
定时任务（serverCron）每次也搬 100 个 bucket 兜底
全部搬完 → 释放 ht[0]，ht[1] 变成新 ht[0]，rehashidx = -1

SCAN 为什么安全？"渐进式"意味着一些 key 在旧表，一些在新表。SCAN 用反向二进制迭代：先从高位的最大 mask 开始，每次加 1 并翻转位。这个算法保证 rehash 过程中，同一个 bucket 的 key 不会被重复扫描或遗漏——因为 rehash 的运动方向（从低位到高位）和 SCAN 的运动方向（高位优先）正交，任何 key 在旧表和新表只被扫描恰好一次。

补充说明：rehash 期间如果在 ht[0] 没找到，会去 ht[1] 找。所以时间复杂度仍是 O(1) 均摊，但最坏情况多一次查找。

Listpack：根治 ziplist 的级联更新

Listpack 是 Redis 5.0 引入、7.0 全面取代 ziplist 的紧凑列表结构。

ziplist 的痛点：每个 entry 记录前一个 entry 的长度（prevlen）。如果前一个 entry 变长了（比如从 253 字节变成 254 字节），prevlen 从 1 字节变成 5 字节，当前 entry 就得往后挪。这一挪，下一个 entry 的 prevlen 可能又超出 254，触发连锁反应——级联更新。最坏情况 O(n²)。

Listpack 的根治方案：每个 entry 不再存前一个 entry 的长度，而是每个 entry 自己记录自己的长度。entry 末尾有一个 backlen 字段，从后往前读可以知道当前 entry 的起始位置。这样修改一个 entry 不会影响其他 entry 的位置，级联更新彻底消失。

Listpack 的代价：查找仍是 O(n)，所以它只适合小数据——hash-max-listpack-entries 512 和 hash-max-listpack-value 64 就是它的舒适区。超过这个阈值，自动升级为标准的 Dict/HashTable。

mermaid

graph LR
    subgraph ziplist
        A1[entry1<br/>prevlen=1] --> A2[entry2<br/>prevlen=253] --> A3[entry3<br/>prevlen=1]
    end
    subgraph listpack
        B1[entry1<br/>backlen] --> B2[entry2<br/>backlen] --> B3[entry3<br/>backlen]
    end
    A2 -.->|entry1 变大<br/>entry2 移位| A3
    B1 -.->|entry1 变大<br/>entry2 不动| B3

Skiplist：Redis 为什么不用红黑树

ZSet 的底层是 skiplist + dict 的组合。dict 保 O(1) 的元素查分，skiplist 保 O(log n) 的范围查询。

概率层数：每个新节点随机决定层数。概率 p=1/4，每层晋升概率 25%。期望层数 ≈ 1.33，所以实际上一半以上的节点只有 1 层，深度通常在 32 层封顶（ZSKIPLIST_MAXLEVEL）。

为什么不用红黑树／平衡树？三个原因：

范围查询好写：skiplist 的 ZRANGE / ZREVRANGE 就是沿着链表走，不需要中序遍历，不需要回溯。红黑树取某个范围的门槛高得多。
实现简单：skiplist 增删改不涉及旋转和颜色调整，工程上排错成本低。
并发修改友善：虽然 Redis 单线程不涉及锁，但 skiplist 的局部性——修改只影响相邻节点——在涉及多线程的场景（如 Redis 的社区 fork 版本）更容易改造。

补充说明：skiplist 查找最坏情况还是 O(n)（如果层级全随机到 1 层），但概率极低。实际运行中 ZSet 上百万元素时 ZRANK 仍在微秒级——这么低的常数，工程上完全够用。

动手实操

用 TYPE 和 OBJECT ENCODING 观察编码切换，再演示 SCAN 在渐进式 rehash 期间的稳定性。

bash

# 启动 Redis
docker run --rm -p 6379:6379 redis:7-alpine

# 1. 观察 SDS 编码切换
redis-cli SET short "hello"
redis-cli OBJECT ENCODING short        # embstr
redis-cli APPEND short "a"$(python3 -c "print('x'*50)")
redis-cli STRLEN short                 # 56
redis-cli OBJECT ENCODING short        # raw（超过 44 字节）

# 2. 观察 Listpack 升级为 Hashtable
redis-cli HSET small field1 value1
redis-cli OBJECT ENCODING small        # listpack
# 写入 513 个字段（超过 hash-max-listpack-entries 512）
for i in $(seq 1 513); do
  redis-cli HSET big f$i v$i
done
redis-cli OBJECT ENCODING big          # hashtable（自动升级）

# 3. SCAN 在 rehash 期间的稳定性
redis-cli CONFIG SET hash-max-listpack-entries 4   # 手动调低触发阈值
for i in $(seq 1 100); do
  redis-cli HSET rehashdemo f$i v$i
done
# 此时 obj encoding 是 hashtable，已经有 rehash 条件
# 运行 SCAN 三次，观察是否每个 key 都被扫描到
redis-cli SCAN 0 MATCH f* COUNT 50
redis-cli SCAN 0 MATCH f* COUNT 50    # 换一个游标继续

代码解释：

OBJECT ENCODING 是 Redis 官方的调试命令，可以直接看到每种 key 的底层编码名（embstr/raw/listpack/hashtable/skiplist/quicklist）
编码升级是不可逆的（hashtable 不会降级回 listpack），所以在生产环境评估好阈值
SCAN 在 rehash 期间不会丢 key 也不会重复返回 key，你可以拿 SCAN 0 COUNT 10000 反复跑验证

常见误区与小结

误区：SDS 就是 C 字符串。不对，C 字符串以 \0 结尾截断，SDS 用 len 判断长度，所以二进制安全，能存 \0 字节。
误区：渐进式 rehash 会降低写入性能。分摊到每次操作，额外开销是搬一条链表+一次 memcpy，均摊后仍是 O(1)。真正的瓶颈在 serverCron 兜底——如果写入太慢，定时任务兜底的压力会越来越大。
误区：Listpack 和 ziplist 差不多。根本区别在于级联更新：Listpack 改一个 entry 不影响其他 entry，ziplist 可能触发整表迁移。Redis 7.0 全面弃用 ziplist 就是因为它扛不住大数据量时的级联更新.
误区：Skiplist 比红黑树慢。范围查询场景下 skiplist 比红黑树快（不需要中序遍历重建线性序），而且实现简单，bug 少。Redis 选它是因为工程收益超过理论复杂度上的微小劣势。
误区：OBJECT ENCODING 在生产环境随便跑。OBJECT ENCODING 本身是 O(1) 不阻塞，但 OBJECT 子命令 DEBUG 和 FREQ 会触发额外计算，生产环境别滥用。

小结：SDS 解决 C 字符串的 O(n) 长度问题；Dict 用渐进式 rehash 解决百万级扩容的阻塞问题；Listpack 用自包含长度解决级联更新；Skiplist 用概率层数解决范围查询的工程实现。这四个结构并非 Redis 独创，但 Redis 在每个上都做了极致的内存优化和生产可用的工程妥协。

下一篇：30. 内存模型与编码切换：内存都花在哪了——从"什么编码"到"占多少内存"。

参考

参考：Redis 源码 src/sds.c、src/dict.c、src/listpack.c、src/t_zset.c（skiplist 实现均在 t_zset.c 中）参考：Redis 官方文档 Redis Data Types 和 Redis Memory Optimization

数据结构拆解：SDS、Dict、Listpack 与 Skiplist ​

为什么底层数据结构重要 ​

SDS：不止是 C 字符串的包装 ​

Dict：渐进式 rehash 是增量迁移的教科书 ​

Listpack：根治 ziplist 的级联更新 ​

Skiplist：Redis 为什么不用红黑树 ​

动手实操 ​

常见误区与小结 ​

参考 ​