Redis 数据结构底层原理：SDS、Dict、ZipList、SkipList 全解析

Redis 快的原因常被简化为”纯内存 + 单线程 + IO 多路复用”，但很少有人追问另一个关键问题：那些数据结构（String、List、Hash、Set、ZSet）在底层到底是怎么实现的？

实际上，Redis 根据数据的大小、长度、元素类型等在编译期就选好了最合适的底层结构，而且会在运行时自动升级编码。理解这些编码的选择逻辑，才算真正吃透了 Redis。

---

SDS（Simple Dynamic String）

Redis 没有直接用 C 语言的 char* 字符串，而是自己封装了一个 SDS。

为什么不用 C 字符串

C 字符串有三个硬伤：

• 获取长度需遍历：strlen() 是 O(n) 操作。
• 非二进制安全：C 用 \0 判定字符串结尾，存二进制数据时会被截断。
• 不可修改：拼接字符串需要手动管理内存，一不小心就溢出。

SDS 结构

struct __attribute__((__packed__)) sdshdr8 {
    uint8_t len;       // buf 已保存的字节数，不含结束符
    uint8_t alloc;     // buf 申请的总字节数，不含结束符
    unsigned char flags; // 不同类型对应不同头大小
    char buf[];        // 数据区
};

SDS 有 5 种类型（sdshdr5/8/16/32/64），根据存储字符串的长度选择合适的头大小。

内存预分配策略

SDS 采用空间预分配来减少内存重分配次数：

• 如果新字符串长度 < 1MB，则分配 2 倍的 buf 空间。
• 如果新字符串长度 ≥ 1MB，则分配 原长度 + 1MB + 1 的 buf 空间。

比如存了一个 100 字节的字符串，再追加 50 字节，实际分配的容量是 150 × 2 = 300 字节。下次再追加时就有富余空间可用，不需要每次触发系统调用。

EMBSTR vs RAW vs INT

String 有三种编码方式，RedisObject 在创建时自动选择：

• INT：如果 value 是整数且在 LONG_MAX 范围内，直接存在 ptr 指针位（8 字节），不创建 SDS。
• EMBSTR：如果字符串长度 ≤ 44 字节，RedisObject 和 SDS 是一段连续内存，一次 malloc 搞定。
• RAW：长度 > 44 字节，RedisObject 和 SDS 分开存储，两次 malloc。

44 这个数字不是随便定的，它刚好让一个内存分配单元（jemalloc 的 64 字节）被充分利用。

---

IntSet

IntSet 是 Set 的一种底层编码，只存储整数且元素数量较少时使用。

typedef struct intset {
    uint32_t encoding;  // 编码方式：16/32/64 位
    uint32_t length;    // 元素个数
    int8_t contents[];  // 整数数组，有序存储
};

三个关键行为：

• 升序存储，便于二分查找。
• 自动升级编码：比如当前存的是 16 位整数 [5, 10, 20]，当插入 50000（超出 int16 范围）时，IntSet 会：
  1. 升级编码到 INTSET_ENC_INT32。
  2. 倒序复制旧元素到扩容后的位置。
  3. 在末尾插入新元素。
  4. 更新 encoding 和 length。
• 编码只能升级，不能降级。

---

Dict（字典）

Redis 的核心——所有 key-value 的映射关系都靠 Dict。

结构

typedef struct dict {
    dictType *type;    // 类型，内含不同的 hash 函数
    void *privdata;
    dictht ht[2];      // 两个哈希表，rehash 时用
    long rehashidx;    // rehash 进度，-1 表示未进行
    int16_t pauserehash;
};

ht[0] 是主哈希表，ht[1] 平时为空，rehash 时才用。

每个哈希表（dictht）内部是一个数组 + 链表：数组解决 hash 定位，链表解决 hash 冲突。

扩容与收缩

Dict 的负载因子：LoadFactor = used / size

扩容触发条件：

• LoadFactor ≥ 1，且没有执行 SAVE/REWRITEAOF 等子进程操作。
• LoadFactor > 5，强制扩容。

收缩触发条件：

• LoadFactor < 0.1（删除元素时检查）。

扩容/收缩的大小规则：第一个大于等于 used + 1 的 2^n（和 HashMap 类似）。

渐进式 Rehash

如果 Dict 里有上千万个 entry，一次性 rehash 会阻塞主线程几秒甚至几十秒。Redis 采用渐进式 rehash：

1. 给 ht[1] 分配新空间。
2. 设置 rehashidx = 0，开始 rehash。
3. 每次执行增删改查时，顺手把 ht[0] 的一个 bucket 搬运到 ht[1]。
4. rehashidx 逐步递增，直至所有数据完成迁移。
5. 交换 ht[0] 和 ht[1]，重置 rehashidx = -1。

rehash 期间的读写策略：

• 新增 → 直接写入 ht[1]。
• 查询/修改/删除 → 依次查找 ht[0] 和 ht[1]。
• 确保 ht[0] 的数据只减不增，最终清空。

---

ZipList（压缩列表）

ZipList 的设计目标只有一个：极致省内存。

为什么不直接用链表

普通链表每个节点需要两个指针（prev/next），64 位系统下就是 16 字节。对于小数据来说，指针开销甚至比数据本身还大。

结构

ZipList 是一块连续内存，每个 entry 的结构：

[previous_entry_length] [encoding] [content]

• previous_entry_length：前一个节点的字节长度。如果 < 254 字节，用 1 字节存储；如果 ≥ 254 字节，用 5 字节（首字节 0xFE）。
• encoding：数据类型 + 数据长度。
• content：实际数据。

连锁更新（Cascade Update）

假设一个 ZipList 中有 N 个长度都在 250～253 字节之间的 entry，每个 entry 的 previous_entry_length 占 1 字节，刚好够用。

现在在头部插入一个 254 字节的新 entry：

• 原来的 entry1 → previous_entry_length 需要从 1 字节扩到 5 字节。
• entry1 本身也变成了 254+ 字节 → entry2 也需要扩。
• 连锁反应一直传递下去。

这就是连锁更新，最坏情况是 O(n²)。但实际场景中很难触发，因为 entry 长度精确卡在 254 边界的情况极少。即使触发了，连续更新几个 entry 后就终止了。

---

QuickList

问题 1：ZipList 虽然是连续内存极省空间，但申请大块连续内存效率很低。 问题 2：那我把大量数据拆成多个小 ZipList 呢？

QuickList 就是答案——它是一个双端链表，每个节点是一个 ZipList。

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;  // 所有 ZipList 的 entry 总数
    unsigned long len;    // ZipList 节点数量
    int fill: -2;         // ZipList 大小限制
    unsigned int compress: 0; // 压缩深度
};

fill 参数控制每个 ZipList 的大小上限：

• 正数：entry 个数上限。
• 负数：内存上限，-1=4KB, -2=8KB, -3=16KB, -4=32KB, -5=64KB。

compress 参数控制中间节点的 LZF 压缩。因为链表通常从首尾访问，所以首尾不压缩：

• 0：不压缩。
• 1：首尾各 1 个节点不压缩，中间节点压缩。
• 2：首尾各 2 个节点不压缩，中间节点压缩。

List 对象底层用的就是 QuickList。

---

SkipList（跳表）

ZSet 的核心数据结构之一，用于有序的快速查找。

为什么不用平衡树

SkipList 的实现比红黑树简单得多，而且支持范围查询（范围遍历在跳表上非常自然，红黑树则需要中序遍历）。

结构

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;   // 当前最大层级，默认 1
};

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;  // 前向指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 后向指针
        unsigned long span;            // 跨度
    } level[];
};

• 底层是有序链表，节点按 score 升序排列。
• 每个节点有多层索引，上层索引跳过若干底层节点，实现”跳跃”查找。
• 跨度（span） 记录该层指针跨越了多少个节点，用于快速计算排名（ZRANK）。

SkipList 的查询、插入、删除的平均复杂度都是 O(log n)，最坏 O(n)（但实际几乎不可能出现）。

---

RedisObject：一切从这里开始

Redis 中任何数据类型最终都被封装为一个 RedisObject：

+----------+--------+--------+--------+
| type(4b) | encoding(4b) | lru(24b) |  refcount |  ptr   |
+----------+--------+--------+--------+

• type：String / List / Set / ZSet / Hash
• encoding：底层编码方式
• lru：LRU/LFU 计时信息
• refcount：引用计数
• ptr：指向真实数据结构的指针

---

五种数据类型的编码选择

String

条件	编码
整数值且在 LONG_MAX 内	INT
字符串长度 ≤ 44 字节	EMBSTR
其他	RAW

List

统一使用 QuickList。

Set

条件	编码
所有元素都是整数且数量 ≤ set-max-intset-entries（默认 512）	IntSet
超出上述条件	HT（Dict）

当插入非整数值或元素超限时，自动从 IntSet 转为 HT，不可逆转。

ZSet

条件	编码
元素数量 ≤ zset-max-ziplist-entries（128）且每个元素大小 ≤ zset-max-ziplist-value（64 字节）	ZipList
超出上述条件	SkipList + Dict

为什么 ZSet 用 ZipList 也能工作？ZipList 中 score 和 element 成对存储，score 越小越靠近队首，天然有序。查询时用二分查找。但当数据量增大后，ZipList 的插入和查询效率下降，就换成 SkipList。

ZSet 采用 SkipList + Dict 双结构：SkipList 负责有序查询和范围操作，Dict 负责 O(1) 的精确查找（ZSCORE）。

Hash

条件	编码
元素数量 ≤ hash-max-ziplist-entries（512）且每个 field/value 大小 ≤ hash-max-ziplist-value（64 字节）	ZipList
超出上述条件	HT（Dict）

Hash 的 ZipList 编码：相邻两个 entry 分别存 field 和 value。

---

总结

数据结构	核心原理	为什么省内存/快
SDS	空间预分配，O(1) 获取长度	减少内存重分配
IntSet	编码升级，有序整数数组	紧凑存储，二分查找
Dict	渐进式 rehash，双哈希表	平滑扩容，不阻塞主线程
ZipList	连续内存，去除指针	内存密度极高
QuickList	ZipList 分片 + 链表	大列表场景兼顾内存与性能
SkipList	多级索引，有序链表跳跃	实现简单，范围查询友好

理解这些编码选择，你在写代码时就会有意识地去控制数据规模，让 Redis 尽可能停留在省内存的编码上，而不是过早升级到 HT 或 SkipList 导致内存膨胀。