Redis 数据结构：底层实现与性能取舍
深入 Redis 底层数据结构的实现原理：从 SDS 字符串到跳表，从 Ziplist 压缩列表到 Listpack，理解每种结构的设计动机与性能权衡，以及 Redis 7.x 的结构演进。
目录
| 章节 | 说明 |
|---|---|
| 全局哈希表与 rehash | 键值对的组织方式，渐进式 rehash |
| SDS（简单动态字符串） | 为什么不用 C 字符串 |
| 双向链表 | List 的链表实现 |
| 压缩列表 Ziplist | 内存紧凑，但有连锁更新风险 |
| Listpack（紧凑列表） | Ziplist 的改进替代品（5.0+） |
| Quicklist（快速列表） | List 的生产实现 |
| 哈希表 Dict | Hash/Set 的底层实现 |
| 整数集合 IntSet | Set 的紧凑整数实现 |
| 跳表 SkipList | ZSet 的有序索引结构 |
| Radix Tree（基数树） | Stream 的消息 ID 索引 |
| 数据类型与底层编码映射 | 类型在不同数据量下的编码切换 |
全局哈希表与 rehash
Redis 使用一个全局哈希表保存所有键值对：
redisDb
└── dict（全局哈希表）
├── ht[0]：当前哈希表
│ └── dictEntry[] → *key、*value、*next（链式解决冲突）
└── ht[1]：rehash 时的目标哈希表
查找流程：SipHash(key) & (size-1) → 定位 bucket → 链表遍历比较 key
渐进式 rehash
触发条件：
- 扩容：元素数量 / bucket 数量 ≥ 1（正常）或 ≥ 5（BGSAVE 期间）
- 缩容：元素数量 / bucket 数量 ≤ 0.1
渐进式：不是一次性完成，而是在每次 CRUD 操作时迁移 1 个 bucket，同时维护 rehashidx 指针记录进度。
rehash 期间：
读操作：先查 ht[0]，再查 ht[1]
写操作：只写入 ht[1]（避免 ht[0] 继续增长）
rehashidx 每次操作推进 1，直到 ht[0] 全部迁移完毕
为什么渐进式？ 一次性迁移百万 key 会阻塞主线程数秒，渐进式把开销分摊到每次操作，每次只多一点点额外耗时。
SDS（简单动态字符串）
Redis 用 SDS 替代 C 字符串，源码文件：sds.h / sds.c
// SDS 结构（简化，实际有多种类型适配不同长度）
struct sdshdr {
int len; // 已使用长度
int free; // 剩余预分配空间
char buf[]; // 实际字节数组（末尾仍有 \0，兼容 C 函数）
};
SDS vs C 字符串
| 对比 | C 字符串 | SDS |
|---|---|---|
| 获取长度 | O(N)（遍历到 \0） | O(1)（读 len 字段） |
| 二进制安全 | ❌（以 \0 判断结束） | ✅（以 len 判断，可存 \0） |
| 追加操作 | 每次重新分配 | 空间预分配，减少重分配 |
| 内存泄漏 | 需手动管理 | 内置长度，安全操作 |
空间预分配策略
- 修改后
len < 1MB：额外分配len大小的 free（总空间 ≈ 2×len） - 修改后
len ≥ 1MB：额外分配 1MB 的 free
这就是为什么
APPEND操作不会每次都 malloc，性能好得多。
双向链表
Redis 的 list.h 定义了双向链表，用于早期 List 类型（元素多时）：
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct list {
listNode *head;
listNode *tail;
unsigned long len;
// 函数指针：复制、释放、比较
} list;
特点：O(1) 头尾操作，但每个节点都有前后指针，内存开销大，不连续，缓存不友好。现已被 Quicklist 替代。
压缩列表 Ziplist
源码：ziplist.h / ziplist.c，用于元素少时的 List / Hash / ZSet（Redis 7 已基本被 Listpack 替代）。
内存布局
zlbytes | zltail | zllen | entry1 | entry2 | ... | zlend(0xFF)
4B 4B 2B 1B
每个 entry：
prevlen | encoding | content
1或5B 1或9B 变长
prevlen：前一个 entry 的长度，用于从尾部反向遍历encoding：数据类型（整数/字符串）+ 长度信息
连锁更新（Cascade Update）
最大缺陷：当插入一个新 entry 时，如果它的长度导致下一个 entry 的 prevlen 字段需要从 1 字节扩展到 5 字节，则会触发连锁更新，最坏情况 O(N²)。
Redis 7.0 已用 Listpack 替代 Ziplist，从根本上解决连锁更新问题。
Listpack（紧凑列表）
源码：listpack.h / listpack.c，Redis 5.0 引入，7.0 全面替代 Ziplist。
内存布局
tot-bytes | num-elements | entry1 | entry2 | ... | 0xFF
4B 2B
每个 entry：
encoding-type | content | backlen
变长，记录本 entry 的总长度
与 Ziplist 的关键区别
backlen 记录的是当前 entry 的长度（不是前一个 entry 的长度），反向遍历只需读当前 entry 的 backlen，不依赖前驱 entry，彻底消除连锁更新。
Quicklist（快速列表）
源码：quicklist.h / quicklist.c，Redis 3.2+ List 类型的实际底层实现。
结构
quicklist（双向链表）
├── head（quicklistNode）
│ └── entry = listpack（或 ziplist）
├── node2
│ └── entry = listpack
└── tail（quicklistNode）
└── entry = listpack
每个 quicklistNode 内部存储一个 Listpack，既保留了链表的灵活性，又通过 Listpack 实现了内存紧凑存储。
配置：list-max-listpack-size（默认 -2，每个节点最大 8KB）
设计精妙：通过控制每个节点的 Listpack 大小，在内存连续性和灵活性之间取得平衡。
哈希表 Dict
源码：dict.h / dict.c，Hash 类型（元素多时）和 Set 类型（非整数成员）的底层实现。
结构已在全局哈希表中描述，核心是链式哈希 + 渐进式 rehash。
哈希函数：SipHash（Redis 4.0 起，防止哈希洪水攻击）
整数集合 IntSet
源码：intset.h / intset.c，Set 中所有成员都是整数且数量较少时使用。
typedef struct intset {
uint32_t encoding; // 编码类型：INT_16/32/64
uint32_t length;
int8_t contents[]; // 有序整数数组（二分查找）
} intset;
升级（Upgrade）：当新插入整数超出当前编码范围时（如插入 65536 到 INT_16 集合），自动升级编码，重新分配内存，不会降级。
跳表 SkipList
源码：t_zset.c（内嵌在 ZSet 实现中），ZSet 类型中元素多时使用，同时配合 Dict（存 member → score 映射）。
结构
header → [level31] → [level31] → NULL
[level 0] → [level 0] → [level 0] → NULL
每个节点：
score（double）
member（SDS）
backward（后退指针，仅 level 0 有，用于反向遍历）
level[]：
forward（前进指针）
span（跨度，用于计算排名）
为什么用跳表而不是红黑树？
| 对比 | 跳表 | 红黑树 |
|---|---|---|
| 范围查询 | ✅ 天然顺序，遍历简单 | ❌ 需要中序遍历，实现复杂 |
| 实现复杂度 | 低（相对） | 高（旋转操作） |
| 内存使用 | 略高（多层指针） | 略低 |
| 并发友好 | ✅ 更容易实现无锁 | ❌ 旋转操作难并发 |
跳表的期望层数：每个节点的层数随机决定，期望层高 log₂N，查找/插入/删除期望复杂度 O(log N)。
Radix Tree（基数树）
源码：rax.h / rax.c，Stream 类型用于索引消息 ID（timestamp-seqno 格式），利用 ID 的前缀压缩实现高效存储。
特点：相邻 Stream 消息的时间戳前缀相同，前缀压缩节省大量内存，且有序。
数据类型与底层编码映射
Redis 对不同规模的数据使用不同编码，OBJECT ENCODING key 可查看当前编码。
| 数据类型 | 数量小/元素小 | 数量多/元素大 | 切换阈值（默认） |
|---|---|---|---|
| String | int（整数）/ embstr（≤44B） | raw（SDS） | 长度 > 44 字节 |
| List | listpack | quicklist | 元素 > 128 或单元素 > 64B |
| Hash | listpack | hashtable | 元素 > 128 或单 value > 64B |
| Set | listpack（全整数时 intset） | hashtable | 元素 > 128 或单元素 > 64B |
| ZSet | listpack | skiplist + hashtable | 元素 > 128 或单元素 > 64B |
| Stream | listpack（每个消息组） | radix tree | 由 Radix Tree 组织多个 listpack |
配置参数（redis.conf）：
hash-max-listpack-entries、zset-max-listpack-entries等可调整阈值。
embstr vs raw（String）：
embstr：SDS 和 RedisObject 在同一块内存，只需一次 malloc，只读（修改会直接转为 raw）raw：独立分配，两次 malloc，可修改
参考资料
- 《Redis 核心技术与实战》— 第 2 讲（蒋德钧）
- 《Redis 源码剖析与实战》— 第 2-7 讲（蒋德钧）
- Redis 设计与实现（黄健宏）
- Redis 源码 GitHub
评论 (0)