Appearance
Redis 底层数据结构
Redis 的高性能不仅因为内存操作，更因为精心设计的底层数据结构。从 SDS 到跳表，从压缩列表到快速列表，每个结构都在时间和空间上做了极致优化。本章深入源码，剖析 Redis 的数据结构设计。
一、SDS（简单动态字符串）
1.1 为什么不用 C 字符串？
c
// C 原生字符串的问题
char *str = "hello";
strlen(str); // O(n) 遍历，每次都要扫描
// 拼接操作
strcat(str1, str2); // 如果 str1 空间不够 → 缓冲区溢出1.2 SDS 结构
c
struct sdshdr {
int len; // 已使用长度
int free; // 剩余可用空间
char buf[]; // 字节数组（柔性数组）
};
// 存储 "hello" 的 SDS
// len=5, free=0
// buf = ['h','e','l','l','o','\0']1.3 SDS vs C 字符串
| 维度 | C 字符串 | SDS |
|---|---|---|
| 获取长度 | O(n) 遍历 | O(1) 直接读 len |
| 缓冲区溢出 | 可能溢出 | 自动扩容，不会溢出 |
| 内存分配 | N 次修改 N 次分配 | 预分配 + 惰性释放 |
| 二进制安全 | 不能存 \0 | 用 len 判断结束，可存二进制 |
| 兼容性 | - | 兼容 C 字符串 API |
空间预分配：
SDS 扩容时，不仅分配需要的空间，还会额外分配：
len < 1MB：分配 len + len + 1（翻倍）
len ≥ 1MB：分配 len + 1MB + 1
减少内存分配次数，提升性能惰性空间释放：
缩短字符串时，不立即释放空间，而是增加 free 值
需要时调用 SDS API 真正释放二、Dict（字典）
2.1 结构
c
typedef struct dict {
dictType *type; // 类型特定函数
void *privdata; // 私有数据
dictht ht[2]; // 两个哈希表（用于渐进式 rehash）
int rehashidx; // rehash 进度（-1 = 不在 rehash）
} dict;
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 掩码（size - 1）
unsigned long used; // 已使用节点数
} dictht;
typedef struct dictEntry {
void *key;
union { void *val; uint64_t u64; int64_t s64; } v;
struct dictEntry *next; // 链表法解决冲突
} dictEntry;2.2 哈希冲突解决
链地址法：同一个槽位上的多个元素通过链表连接
table[3] → entry1(key="a") → entry2(key="m") → NULL
↑ ↑
hash("a")%size=3 hash("m")%size=32.3 渐进式 Rehash
Redis 是单线程，如果一次性 rehash 全量数据，会阻塞服务。因此采用渐进式 rehash，分多次完成。
渐进式 Rehash 流程：
1. 为 ht[1] 分配空间（通常为 ht[0] 的两倍）
2. 设置 rehashidx = 0（开始 rehash）
3. 每次对字典的增删改查操作，顺带将 ht[0] 在 rehashidx 上的键值对迁移到 ht[1]
4. rehashidx++（指向下一个要迁移的槽）
5. 迁移完成后，ht[1] 变为 ht[0]，释放旧 ht[0]，rehashidx = -1
ht[0]（旧表） ht[1]（新表，2 倍大）
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │ │ │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘
↑ rehashidx=0
逐步迁移
查询时：先查 ht[0]，再查 ht[1]
新增时：直接写入 ht[1]触发条件：
扩容：
- 没有 BGSAVE/AOF 重写：负载因子 ≥ 1
- 有 BGSAVE/AOF 重写：负载因子 ≥ 5
缩容：
- 负载因子 < 0.1
负载因子 = used / size三、Skiplist（跳表）
3.1 为什么用跳表？
有序数据结构对比：
┌──────────┬──────────┬──────────┬──────────┐
│ │ 查找 │ 插入 │ 删除 │
├──────────┼──────────┼──────────┼──────────┤
│ 数组 │ O(log N) │ O(N) │ O(N) │
│ 链表 │ O(N) │ O(1) │ O(1) │
│ 平衡树 │ O(log N) │ O(log N) │ O(log N) │
│ 跳表 │ O(log N) │ O(log N) │ O(log N) │
└──────────┴──────────┴──────────┴──────────┘
跳表 vs 平衡树：
✅ 实现简单（不需要旋转）
✅ 范围查找快（找到起点后沿第 0 层遍历）
✅ 适合 ZSet 的范围查询（ZRANGE、ZRANGEBYSCORE）3.2 跳表原理
普通链表（O(n)）：
1 ──→ 3 ──→ 5 ──→ 7 ──→ 9 ──→ 12 → NULL
查找 12：遍历 6 次
跳表（O(log N)）：
层级
4: 1 ──────────────────────→ 12 ← 高速通道
3: 1 ──────────→ 7 ────────→ 12
2: 1 ────→ 5 ──→ 7 ──→ 9 ──→ 12
1: 1 → 3 → 5 → 7 → 9 → 12 → NULL ← 原始链表
查找 12：
4 层：1 → 12（12 不大于 12，找到）
查询 3 次
查找 8：
4 层：1 → 12 > 8，回退到 1
3 层：1 → 7 < 8，前进
3 层：7 → 12 > 8，回退到 7
2 层：7 → 9 > 8，回退到 7
1 层：7 → 9 > 8，回退到 7
结果：8 不存在
查询 5 次3.3 Redis 跳表结构
c
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length; // 节点数量
int level; // 最大层数
} zskiplist;
typedef struct zskiplistNode {
sds ele; // 元素值
double score; // 分数
struct zskiplistNode *backward; // 后退指针
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned long span; // 跨度（到下一个节点的距离）
} level[]; // 柔性数组，每层一个
} zskiplistNode;层数生成：
c
// 随机生成层数，概率分布
// 第 1 层：100%
// 第 2 层：25%
// 第 3 层：6.25%
// 第 4 层：1.56%
// ...
int zslRandomLevel() {
int level = 1;
while ((random() & 0xFFFF) < (0.25 * 0xFFFF))
level += 1;
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}四、Ziplist（压缩列表）
4.1 结构
ziplist 内存布局：
┌────────┬────────┬────────┬────────┬─────┬────────┬────────┐
│zlbytes │zltail │zllen │entry1 │ ... │entryN │zlend │
│4 字节 │4 字节 │2 字节 │ │ │ │1 字节 │
└────────┴────────┴────────┴────────┴─────┴────────┴────────┘
zlbytes：整个 ziplist 占用的字节数
zltail：最后一个 entry 的偏移量（用于从尾部遍历）
zllen：entry 数量（超过 2^16-1 时需要遍历统计）
zlend：结束标记 0xFF
每个 entry 的结构：
┌───────────┬───────────┬───────────┐
│prevlen │encoding │data │
│前一个长度 │编码+长度 │实际数据 │
└───────────┴───────────┴───────────┘4.2 特点
优点：
✅ 连续内存，无指针，内存利用率高
✅ 利用 CPU 缓存，遍历效率高
缺点：
❌ 插入/删除时可能触发连锁更新（cascade update）
❌ 不能存储大量数据
适用场景：
Hash 小对象（field < 512 且 value < 64 字节）
ZSet 小集合（元素 < 128 且 value < 64 字节）
List 小列表（3.2 之前）4.3 连锁更新
问题：prevlen 字段受前一个 entry 长度影响
entry1（250 字节）→ prevlen=1 字节
entry2（250 字节）→ prevlen=1 字节
entry3（250 字节）→ prevlen=1 字节
如果 entry1 更新为 254 字节：
entry2 的 prevlen 需要从 1 字节 → 5 字节 → entry2 长度增加
entry3 的 prevlen 需要从 1 字节 → 5 字节 → entry3 长度增加
... 连锁反应
这就是 Redis 限制 ziplist 大小的原因五、Quicklist（快速列表）
5.1 结构
Redis 3.2+ 的 List 底层实现：
quicklist = ziplist 的链表
┌──────────┐ ┌──────────┐ ┌──────────┐
│quicklist │→ │quicklist │→ │quicklist │
│ Node │ │ Node │ │ Node │
│ ┌──────┐ │ │ ┌──────┐ │ │ ┌──────┐ │
│ │ziplist│ │ │ │ziplist│ │ │ │ziplist│ │
│ │(8KB) │ │ │ │(8KB) │ │ │ │(8KB) │ │
│ └──────┘ │ │ └──────┘ │ │ └──────┘ │
└──────────┘ └──────────┘ └──────────┘
每个 quicklist Node 包含一个 ziplist（默认最大 8KB）
节点间通过链表连接5.2 设计思想
问题：纯 ziplist 插入删除慢，纯 linkedlist 指针开销大
解决：quicklist = 两者结合
ziplist 的好处：连续内存，无指针开销
linkedlist 的好处：插入删除快，无连锁更新
quicklist：将大 ziplist 切成多个小 ziplist
✅ 每个 ziplist 较小，避免连锁更新
✅ 节点间用链表连接，插入删除快
✅ 内存利用率高，指针开销可控六、Intset（整数集合）
6.1 结构
c
typedef struct intset {
uint32_t encoding; // 编码方式：INTSET_ENC_INT16/32/64
uint32_t length; // 元素数量
int8_t contents[]; // 元素数组（实际类型取决于 encoding）
} intset;6.2 编码升级
当 Set 全是整数时，使用 intset 存储：
Set {1, 2, 3} → encoding=INT16，每个元素 2 字节
SADD 40000 → 40000 > INT16_MAX → 升级到 INT32
→ 分配新数组，复制旧数据，新元素追加
升级后不可降级（即使删除大元素，仍保持 INT32）七、数据结构与类型的对应关系
| 数据类型 | 底层实现（小数据） | 底层实现（大数据） |
|---|---|---|
| String | SDS | SDS |
| List | quicklist | quicklist |
| Set | intset | dict |
| ZSet | ziplist | skiplist + dict |
| Hash | ziplist | dict |
转换阈值：
conf
# Hash
hash-max-ziplist-entries 512 # field 数量
hash-max-ziplist-value 64 # 单个 value 长度
# ZSet
zset-max-ziplist-entries 128 # 元素数量
zset-max-ziplist-value 64 # 单个元素长度
# Set
set-max-intset-entries 512 # 元素数量八、面试要点
Q1：SDS 和 C 字符串相比有什么优势？
O(1) 获取长度、自动扩容防溢出、预分配减少内存分配、惰性释放减少内存碎片、二进制安全（可存任意字节）。
Q2：跳表是如何实现的？
多层索引的链表结构。每层节点按概率随机生成（第 1 层 100%，第 2 层 25%，逐层递减）。查找时从最高层开始，逐层下降，时间复杂度 O(log N)。
Q3：渐进式 Rehash 是什么？
Redis 字典扩容时，不一次性迁移所有数据，而是分多次迁移，每次操作顺带迁移一部分。避免了单线程阻塞，保证服务不中断。
Q4：为什么 ZSet 同时用跳表和字典？
跳表按 score 排序，支持范围查询（ZRANGEBYSCORE）；字典按 member 查询分数，O(1) 获取 score。两者互补，同时维护。