Redis 数据结构底层实现

---

1. 概览

Redis 的高性能离不开其精心设计的底层数据结构。每种数据类型都会根据数据规模自动选择最优的编码方式：

数据类型      小规模数据             大规模数据
──────────────────────────────────────────────────
String    →  int / embstr      →  raw（SDS）
Hash      →  listpack          →  hashtable
List      →  listpack          →  quicklist
Set       →  listpack / intset →  hashtable
ZSet      →  listpack          →  skiplist + hashtable

查看某个 key 的底层编码：

SET age 18
OBJECT ENCODING age      # → int

SET name "Alice"
OBJECT ENCODING name     # → embstr

ZADD rank 9850 "Alice"
OBJECT ENCODING rank     # → listpack（元素少时）

---

2. SDS（Simple Dynamic String）

2.1. 为什么不用 C 字符串

C 字符串（char[]）以 \0 结尾，存在诸多问题：

问题	C 字符串	SDS
获取长度	O(N) 遍历	O(1)，存储 len 字段
二进制安全	❌ \0 表示结束，不能存二进制	✅ 用 len 判断结束
内存预分配	❌ 修改时重新分配	✅ 预分配，减少 malloc 次数
缓冲区溢出	❌ 无长度检查	✅ 修改前检查容量

2.2. SDS 结构

struct sdshdr {
    int    len;      // 已使用长度（O(1) 获取字符串长度）
    int    alloc;    // 总分配长度（不含 header 和结尾 \0）
    char   flags;    // 类型标识（sdshdr5/8/16/32/64）
    char   buf[];    // 数据区
};

2.3. String 的三种编码

int    → 值为整数且在 long 范围内（如 "100"）
         直接用 long 存储，无需 SDS，内存最省

embstr → 字符串长度 ≤ 44 字节
         redisObject 和 SDS 一次性分配连续内存
         只读（修改会先转为 raw）

raw    → 字符串长度 > 44 字节
         redisObject 和 SDS 分开分配，两次 malloc
         可读写

2.4. 预分配策略

修改 SDS 时的内存预分配规则：
新长度 < 1MB  → alloc = 新长度 × 2（预留同等空间）
新长度 ≥ 1MB  → alloc = 新长度 + 1MB

---

3. listpack（紧凑列表）

3.1. 结构

listpack 是 Redis 7.0 引入的紧凑列表，用连续内存存储元素，替代旧版 ziplist（ziplist 存在连锁更新问题）：

listpack 内存布局：

┌──────────┬──────────┬──────────────────────────────────────────┬─────────┐
│ total-len│  num-elem│  entry1  │  entry2  │  entry3  │  ...    │   0xFF  │
│  (4字节) │  (2字节) │          │          │          │         │  (结尾) │
└──────────┴──────────┴──────────────────────────────────────────┴─────────┘

每个 entry 结构：
┌────────────────┬──────────────┬────────┐
│ encoding(1-2B) │ content(可变)│ backlen│
└────────────────┴──────────────┴────────┘
  backlen 记录本 entry 长度，支持从尾部向前遍历

3.2. 与 ziplist 的改进

ziplist 的 prevlen 字段记录前一个 entry 的长度，若前一个 entry 长度变化会触发连锁更新（cascading update），最坏 O(N²)。listpack 的 backlen 只记录自身长度，彻底消除了连锁更新问题。

---

4. quicklist（快速列表）

List 数据类型在数据量大时使用 quicklist，它是 listpack 节点组成的双向链表：

quicklist 结构：

head ──▶ [listpack节点1] ──▶ [listpack节点2] ──▶ [listpack节点3] ──▶ tail
           [e1][e2][e3]       [e4][e5][e6]        [e7][e8][e9]

每个 listpack 节点最多存 128 个元素（可配置）

设计权衡：

纯链表：每个节点单独分配，prev/next 指针开销大，内存碎片多
纯 listpack：全部连续存储，插入/删除中间元素需大量内存拷贝

quicklist：将多个元素打包成 listpack 节点，链表串联各节点
          → 兼顾内存效率（listpack 紧凑）和操作性能（链表 O(1) 增删端点）

---

5. hashtable（哈希表）

5.1. 结构

Redis 哈希表使用链式哈希解决冲突：

dictht（哈希表）：

table[0] → [entry: k1→v1] → [entry: k3→v3] → null   （链地址法解决冲突）
table[1] → null
table[2] → [entry: k2→v2] → null
table[3] → null
...

5.2. 渐进式 rehash

当负载因子过高（或过低）时触发 rehash，但 Redis 不是一次性完成，而是渐进式分批迁移，避免阻塞主线程：

rehash 过程：

同时维护 ht[0]（旧表）和 ht[1]（新表，容量为旧表 2 倍）
    │
    ▼
每次处理请求时，顺带迁移 ht[0] 中 rehashidx 位置的 bucket
    │
    ├── 写操作：只写 ht[1]
    ├── 读操作：先查 ht[0]，再查 ht[1]
    │
    ▼
ht[0] 全部迁移完成 → ht[1] 变为 ht[0]，rehash 结束

rehashidx：记录当前迁移进度，初始为 0，每迁移一个 bucket +1

为什么是渐进式

如果一次性 rehash，数据量大时会阻塞主线程数秒。渐进式 rehash 将迁移工作分散到每次请求中，单次迁移开销极小，保证 Redis 响应时间稳定。

---

6. intset（整数集合）

Set 中所有元素为整数且数量较少时使用 intset，内存极为紧凑：

typedef struct intset {
    uint32_t encoding;  // 编码方式（INT_ENC_INT16/32/64）
    uint32_t length;    // 元素数量
    int8_t   contents[];// 元素数组（有序存储，支持二分查找）
};

intset 内存布局（存储 [10, 20, 30, 40, 50]）：

┌──────────┬──────────┬────┬────┬────┬────┬────┐
│ encoding │  length  │ 10 │ 20 │ 30 │ 40 │ 50 │
│  INT16   │    5     │    │    │    │    │    │
└──────────┴──────────┴────┴────┴────┴────┴────┘

元素有序存储 → 查找时使用二分搜索 O(log N)

升级机制： 若插入的新整数超过当前编码范围（如 INT16 中插入超过 32767 的数），intset 自动升级编码并迁移所有元素，一次性完成，无法降级。

---

7. skiplist（跳表）

ZSet 在数据量大时使用跳表 + 哈希表双索引结构：

7.1. 跳表结构

跳表是一种多层索引的有序链表：

level 4: head ─────────────────────────────────────────▶ [Alice:9850] → null
level 3: head ──────────────────────▶ [Bob:8720] ───────▶ [Alice:9850] → null
level 2: head ──────────▶ [Carol:7600] ─▶ [Bob:8720] ──▶ [Alice:9850] → null
level 1: head ─▶ [Dave:6300] ─▶ [Carol:7600] ─▶ [Bob:8720] ─▶ [Alice:9850] → null

查找 Bob：
  从 level 4 开始，发现 Alice(9850) > Bob(8720)，下降到 level 3
  发现 Bob，找到目标，时间复杂度 O(log N)

7.2. 为什么用跳表而不用红黑树

对比项	跳表	红黑树
实现复杂度	简单 ✅	复杂（旋转/着色）
范围查询	高效（定位后顺序遍历）✅	需中序遍历，较繁琐
内存占用	略高（多层指针）	中等
并发优化	易于实现无锁并发	较复杂

7.3. 跳表 + 哈希表双索引

ZSet 同时维护跳表和哈希表，两者共享 member 和 score 对象（不重复存储）：

ZSet 内部结构：

hashtable：member → score  （O(1) 查询某个 member 的 score）
skiplist：  按 score 有序排列  （O(log N) 范围查询、排名查询）

ZSCORE key member   → 走 hashtable，O(1)
ZRANK  key member   → 走 skiplist，O(log N)
ZRANGE key s e      → 走 skiplist，O(log N + M)

---

8. 编码升级触发条件速查

数据类型	小规模编码	触发升级条件	大规模编码
String	int / embstr	长度 > 44 字节 / 修改操作	raw（SDS）
Hash	listpack	字段数 > 128 或任意值 > 64 字节	hashtable
List	listpack	元素数 > 128 或任意元素 > 64 字节	quicklist
Set	listpack	元素数 > 128 或含非整数	hashtable
Set	intset	元素数 > 512 或含非整数	hashtable
ZSet	listpack	元素数 > 128 或任意 member > 64 字节	skiplist + hashtable

编码升级不可降级

一旦触发升级（如 listpack → hashtable），即使后续删除元素使数量低于阈值，编码也不会自动降级回去。生产环境要合理控制单个 key 的数据量，避免意外升级后内存暴增。

调整编码阈值

编码升级阈值可通过 redis.conf 调整，例如：

hash-max-listpack-entries 128   # Hash listpack 最大元素数
hash-max-listpack-value   64    # Hash listpack 单值最大字节
zset-max-listpack-entries 128   # ZSet listpack 最大元素数

适当调大阈值可以延长 listpack 的使用时间，节省内存；但阈值过大会导致操作性能下降。