Redis 数据结构深水区

问题引入

2011 年，一个游戏公司用 Redis 缓存玩家状态数据。状态数据是 protobuf 序列化的二进制流，长度大约 2KB。某天运维发现，部分玩家的状态数据在取出后反序列化失败——数据似乎被"截断"了。

排查过程令人困惑：写入和读取用的同一个 key，Redis 也没有报错。最终问题定位在 Redis 的字符串实现上——早期 Redis 的某些接口内部仍使用 C 字符串处理数据，而 protobuf 序列化结果里恰好包含 \0 字节，C 字符串将其识别为结束符，导致后续数据被丢弃。

这个 bug 的深层启示是：Redis 看似简单的 "String" 背后，是一整套精心设计的内存数据结构。SDS 解决了 C 字符串的缺陷，ziplist 在极致压缩与访问效率之间走钢丝，skiplist 用概率换实现简洁，渐进式 rehash 用时间换空间平滑迁移。不理解这些数据结构的工程取舍，就永远无法回答 "Redis 为什么这样设计"。

核心概念

SDS：Simple Dynamic String

Redis 没有直接使用 C 语言的 char*，而是封装了 SDS（简单动态字符串）。它的结构头根据字符串长度分五种：

// sdshdr8（长度小于 256）
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;        // 已使用长度
    uint8_t alloc;      // 分配的总长度（不含头和空终止符）
    unsigned char flags; // 标志位，标识头部类型
    char buf[];         // 柔性数组，实际数据
};

读图导引：粉色节点是 len 字段——SDS 用 1 字节记录已使用长度，获取长度是 O(1)。蓝色节点是柔性数组 buf——存储实际字符数据，末尾仍保留 \0 以兼容 C 字符串函数，但 SDS 不以它作为结束标志。

SDS 相比 C 字符串的核心优势：

空间预分配策略（sdsMakeRoomFor）：

• 若追加后长度 < 1MB：分配 2 * (len + addlen)，即翻倍
• 若追加后长度 >= 1MB：分配 len + addlen + 1MB，即只追加 1MB

// Redis 源码简化
if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1MB
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

这个策略的 trade-off 很清晰：翻倍策略利用空间换时间，减少后续 realloc 次数；超过 1MB 后改为追加 1MB，避免大字符串的内存浪费。SDS 缩短时也不释放内存（sdsclear 只重置 len），以便后续复用。

ziplist：压缩列表的紧凑之美与级联之殇

ziplist 是 Redis 为 List、Hash、ZSet（在小数据量时）设计的紧凑内存结构。它将所有节点连续存放在一块内存中，没有前后指针，只有变长编码的 prevlen 和 encoding。

<ziplist> = <zlbytes> <zltail> <zllen> <entry>... <entry> <zlend>

<entry> = <prevlen> <encoding> <content>

读图导引：粉色节点是 entry1——作为首节点，它的 prevlen 为 0。蓝色节点是 entry2——prevlen=3 表示前节点长度是 3 字节。注意没有前后指针，所有信息都通过变长编码内联在条目中。

prevlen 的变长编码：

• 前节点长度 < 254 字节：用 1 字节存储
• 前节点长度 >= 254 字节：用 5 字节存储（首字节 0xFE + 后续 4 字节）

这带来了一个致命的副作用：级联更新（cascading update）。

假设 ziplist 中所有节点长度都是 253 字节，每个节点的 prevlen 都只占 1 字节。现在在某处插入一个 255 字节的节点，后一个节点的 prevlen 必须从 1 字节扩容到 5 字节——该节点长度从 253 变成 257，又触发后后节点的 prevlen 扩容……

读图导引：粉色节点是插入操作和第一个被触发的节点——一次插入导致后续所有节点的 prevlen 连锁扩容。ziplist 的设计将指针内联为变长编码，节省了内存，但在节点大小跨越 254 字节边界时，可能引发 O(n²) 的连锁重写。

暗面：级联更新在最坏情况下需要重写整个 ziplist。对于 Redis 这种单线程、追求微秒级响应的系统，一次插入耗时数毫秒是不可接受的。

listpack：ziplist 的演进替代品

Redis 5.0 引入 listpack，Redis 7.0 彻底用 listpack 替代 ziplist。核心改进：去掉 prevlen，改用 total length（当前元素长度）。

<listpack> = <total_bytes> <num_elements> <entry>... <entry> <end>

<entry> = <encoding> <content> <element-total-len>

读图导引：粉色节点是 ziplist 的 entry——prevlen 存储前节点长度，导致级联依赖。绿色节点是 listpack 的 entry——total-len 存储当前节点长度，向后遍历不受影响，彻底消除了级联更新。

listpack 的 total-len 是反向编码的（从后向前读），所以遍历和删除都不需要修改其他节点。这是一个经典的通过改变数据布局消除级联依赖的设计。

quicklist：分段哲学

Redis 3.2 引入 quicklist 作为 List 的底层实现——它是双向链表 + ziplist/listpack 的分段组合。

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        // 总元素数
    unsigned long len;          // 节点数
    int fill : QL_FILL_BITS;    // 每个节点的 ziplist 容量限制
    unsigned int compress : QL_COMP_BITS;  // 两端不压缩的节点数
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;          // 指向 ziplist/listpack
    unsigned int sz;            // ziplist 字节数
    unsigned int count : 16;    // 节点内元素数
    unsigned int encoding : 2;  // RAW or LZF
} quicklistNode;

读图导引：quicklist 是双向链表，每个节点是一个 ziplist/listpack。粉色节点展示中间节点——当单个 ziplist 超过配置阈值（默认 8KB 或 -2，即 8KB）时，会分裂出新节点。这样既保持了链表的插入删除效率，又享受了压缩列表的内存紧凑性。

fill 参数的语义（list-max-ziplist-size）：

• 正数：每个节点最多容纳的元素个数
• 负数：每个节点最大内存（-1=4KB, -2=8KB, -3=16KB, -4=32KB, -5=64KB）

compress 参数（list-compress-depth）：两端不压缩的节点数。中间节点用 LZF 压缩，减少内存占用——因为列表的访问模式通常是 LPUSH/RPOP 两端活跃，中间冷数据压缩是合理的工程取舍。

skiplist：概率换简洁的有序结构

Redis 的 ZSet（Sorted Set）底层是 "skiplist + dict" 的双索引结构：

• skiplist：按 score 排序，支持范围查询（ZRANGEBYSCORE）
• dict（哈希表）：按 member 索引，支持 O(1) 查 score（ZSCORE）

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;  // 当前最大层数
} zskiplist;

typedef struct zskiplistNode {
    sds ele;                    // member
    double score;               // score
    struct zskiplistNode *backward;  // 后退指针（仅一层）
    struct zskiplistLevel {     // 层数组
        struct zskiplistNode *forward;
        unsigned int span;      // 到下一节点的跨度
    } level[];
} zskiplistNode;

读图导引：粉色节点是 header——拥有最大层数（默认 64 层）的哨兵节点。蓝色节点是节点 C——它出现在 L1、L2、L3 三层。每个节点通过随机算法决定层数，高层指针"跳过"中间节点，实现类似二分查找的跳跃效果。

层数的随机生成（zslRandomLevel）：

int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

• ZSKIPLIST_P = 0.25：每层晋升的概率
• ZSKIPLIST_MAXLEVEL = 64：最大层数上限

概率分析：

• 层数 = 1 的概率：1 - p = 0.75
• 层数 = 2 的概率：p(1-p) = 0.1875
• 层数 = k 的概率：p^(k-1)(1-p)
• 平均层数：1 / (1-p) = 1.33

查询复杂度为 O(log n) 的概率保证——因为高层的"跳跃"能力使得搜索路径长度与层数成正比。

面试官视角：问 "为什么 Redis 用 skiplist 而不用红黑树" 的标准答案不只是 "实现简单"。skiplist 相比红黑树的核心优势是范围查询友好——ZRANGEBYSCORE 可以直接沿着底层链表顺序遍历，而红黑树需要中序遍历的递归开销；此外 skiplist 的并发修改更容易实现（不需要像红黑树那样做复杂的旋转平衡）。代价是平均层高带来的额外指针内存，以及 O(log n) 是概率保证而非确定性保证。

渐进式 rehash：双字典的时间平滑

Redis 的 dict（哈希表）在扩容或缩容时，不采用 Java HashMap 那种"一次性全量 rehash"，而是使用渐进式 rehash——维护两个哈希表 ht[0]（旧表）和 ht[1]（新表），逐步迁移数据。

typedef struct dict {
    dictType *type;
    dictEntry **ht_table[2];    // 两个哈希表
    unsigned long ht_used[2];   // 两个表的已用节点数
    long rehashidx;             // -1 表示未在进行 rehash
    int16_t pauserehash;        // 安全迭代器计数
} dict;

读图导引：粉色节点是 ht[0] 的 bucket0——这是 rehashidx 当前指向的桶位，下次增删查操作时会将 A→B 迁移到 ht[1]。蓝色节点是 ht[1] 的 bucket4——假设 A 的哈希值在新表映射到 4。绿色节点是 rehashidx 指针——记录下一次要迁移的桶位索引。

rehash 的触发条件：

1. 扩容：ht[0].used / ht[0].size >= 1 且没有执行 BGSAVE/BGREWRITEAOF，或 used / size >= 5（强制扩容，不管是否在持久化）
2. 缩容：ht[0].size > DICT_HT_INITIAL_SIZE 且 ht[0].used / ht[0].size < 0.1

渐进迁移的策略：

• 定时任务：Redis 的 serverCron 定期调用 databasesCron，后者每次执行最多 1ms 的渐进式 rehash，持续迁移桶位直到时间用完
• 增删查触发：每次对 dict 执行增删查操作时，迁移 rehashidx 指向的 1 个桶位

读图导引：粉色节点是判断点——rehash 期间（rehashidx >= 0）查询需要查两张表。蓝色节点是优先查旧表——因为新数据直接写入 ht[1]，但旧数据可能还在 ht[0]。

rehash 期间的新增策略：新数据直接写入 ht[1]，不再写入 ht[0]。删除操作先在 ht[0] 找，找不到再去 ht[1] 删。

暗面：渐进式 rehash 的代价是内存峰值期需要同时维护两张表。扩容时（如从 4 扩到 8），最坏情况下 ht[0] 和 ht[1] 都接近满载，内存占用达到平时的 2 倍。对于内存敏感的部署，需要在规划时预留这部分余量。

原理分析

为什么 SDS 需要五种头部类型

Redis 3.2 之前 SDS 只有一种头部（sdshdr），用 int 存 len 和 alloc——在短字符串上浪费严重（8 字节头部存 3 字节字符串）。3.2 之后拆分为五种：

读图导引：粉色节点是 sdshdr5——最短字符串的极致压缩，仅用 1 字节 flags 的高 5 位存储长度（0-31）。蓝色节点是 sdshdr8——最常见的短字符串场景，3 字节头部开销。

这是一个经典的**类型分片（type sharding）**优化——根据数据大小选择最小的头部类型，避免 "用大炮打蚊子"。

ziplist 向 listpack 演进的历史脉络

读图导引：粉色节点是 ziplist——解决了链表的内存不紧凑问题，但引入级联更新。蓝色节点是 listpack——Redis 5.0 引入，7.0 全面替代 ziplist，彻底消除级联更新风险。

演进逻辑不是 "新结构一定更好"，而是 "在每个历史阶段解决当时最痛的点"：

• 2.x 的链表：指针开销大（64 位系统每个指针 8 字节），内存不连续缓存不友好
• 3.0 的 ziplist：紧凑内存，但级联更新是致命伤
• 3.2 的 quicklist：用分段策略平衡插入效率和内存紧凑
• 5.0/7.0 的 listpack：保留紧凑性，消除级联更新

skiplist 的层数分布与查询路径

读图导引：粉色节点是查询起点——从 header 的最高层开始。绿色节点是直接命中的情况——如果目标节点恰好有高层指针，可以快速直达。右侧展示了未命中的搜索路径——高层跳过，逐层下降，底层顺序扫描。

skiplist 的查询效率取决于层数分布。由于 p=0.25 时平均层数仅 1.33，绝大多数节点只有 1 层指针，内存开销非常克制。作为对比：

• 红黑树：每个节点需要 3 个指针（左、右、父）+ 1 个颜色标记
• B+ 树：每个节点需要大量键和指针，实现复杂
• skiplist：平均每个节点 1.33 个 forward 指针 + 1 个 backward 指针

intset：整数集合的升级策略

当 Set 只包含整数且元素较少时，Redis 用 intset 存储。它的设计精髓是动态升级：

typedef struct intset {
    uint32_t encoding;   // INTSET_ENC_INT16/32/64
    uint32_t length;     // 元素个数
    int8_t contents[];   // 柔性数组，实际类型由 encoding 决定
} intset;

• 初始用 int16_t 存储（每个元素 2 字节）
• 当插入一个 int32_t 范围的整数时，整个集合升级到 int32_t（每个元素扩展到 4 字节）
• 当插入一个 int64_t 范围的整数时，再次升级到 int64_t（每个元素 8 字节）

读图导引：粉色节点是初始状态——所有元素用 2 字节存储。蓝色节点是第一次升级——插入一个超范围元素后，整个集合的每个元素都扩展到 4 字节。升级是单向的，不会降级——这是用空间换一致性的取舍。

实战/源码

验证 SDS 的空间预分配

// 观察 SDS 的扩容行为
sds s = sdsnew("hello");    // len=5, alloc=5
s = sdscat(s, " world");    // len=11, 需要扩容
// 追加后 < 1MB，alloc 变为 22（翻倍）

通过 redis-cli 的 DEBUG SDSLEN key（需要自行编译调试版本）或阅读 sds.c 的 sdsMakeRoomFor 函数，可以验证预分配策略。

ziplist 级联更新的模拟

// 创建一个所有节点长度为 253 的 ziplist
// 插入一个 255 字节的节点，观察级联更新

在 Redis 7.0 之前，可以通过 ziplistLen 和 ziplistBlobLen 的源码阅读理解级联更新的触发条件。Redis 7.0 后 listpack 的 lpInsert 不再需要修改后续节点的长度字段。

渐进式 rehash 的触发与观察

# 往一个 hash key 中大量插入数据，触发 rehash
HSET myhash field1 value1
# ... 持续插入直到触发扩容

# 使用 redis-cli 的 DEBUG 命令观察 dict 状态
DEBUG HTSTATS 0

Redis 的 INFO commandstats 可以观察到 rehash 期间命令的执行延迟分布——虽然单次迁移很快，但在极端场景下（超大 dict + 大量写入）仍可能出现延迟抖动。

常见问题

Q1：SDS 的最大长度是多少？

sdshdr64 的 len 字段是 uint64_t，理论上最大长度为 2^64-1 字节。但实际受限于 Redis 的 proto-max-bulk-len 配置（默认 512MB）。

Q2：ziplist 被 listpack 取代后，quicklist 的节点用的是哪种？

Redis 7.0 开始，quicklist 的节点统一使用 listpack。配置项 list-max-ziplist-size 虽然名字里还有 ziplist，但实际控制的是 listpack 节点的容量。

Q3：skiplist 的 p=0.25 可以改吗？

可以，但 Redis 源码中是硬编码的。p 越大，平均层数越高，查询越快但内存消耗越大。p=0.5 时平均层数为 2，接近平衡二叉树的指针开销；p=0.25 是一个工程上的折中。

Q4：渐进式 rehash 期间，迭代器（遍历）会受影响吗？

会。Redis 提供两种迭代器：

• 安全迭代器（dictSafeIterator）：启动时暂停 rehash（pauserehash++），遍历完再恢复。保证遍历不遗漏不重复，但会阻塞 rehash 进度。
• 非安全迭代器（dictIterator）：不暂停 rehash，允许在遍历期间做 rehash，但可能重复遍历某些元素或遗漏刚迁移的元素。

Q5：为什么 Redis 的 Hash 底层也用 ziplist/listpack？

当 Hash 的字段数较少且字段/值都较短时，Redis 用 ziplist/listpack 存储（hash-max-ziplist-entries 默认 512，hash-max-ziplist-value 默认 64 字节）。将 field-value 对顺序存放在紧凑数组中，比哈希表 + dictEntry 的指针开销更省内存。超过阈值后转为真正的哈希表（dict）。

总结

Redis 数据结构的精髓，是在内存效率、访问速度、实现复杂度三者之间做精妙的工程取舍：

• SDS：用 len/alloc 头部解决 C 字符串的 O(n) 长度和缓冲区溢出问题，空间预分配（<1MB 翻倍，>=1MB 加 1MB）与惰性释放减少内存分配次数，五种头部类型实现内存的极致压缩
• ziplist → listpack：ziplist 用 prevlen 的变长编码实现紧凑存储，但 254 字节边界触发级联更新；listpack 改用 total-len 反向编码，彻底消除级联依赖
• quicklist：分段哲学——双向链表保证插入删除效率，每个节点的 listpack 保证内存紧凑，两端不压缩中间 LZF 压缩适配访问模式
• skiplist：p=0.25 的概率层数设计，平均 1.33 层指针实现 O(log n) 查询，范围查询天然友好，实现比平衡树简洁得多
• 渐进式 rehash：双字典 + 逐步迁移，避免一次性 rehash 的卡顿，代价是内存峰值期的双倍占用
• intset：动态升级策略，小范围整数用 int16 存储，超范围时整体扩展，用空间换编码一致性

理解这些数据结构的关键，是追问：这个结构节省了哪些内存？付出了什么代价？在什么条件下代价会爆发？ 从"知道 Redis 有哪些数据结构"到"懂得为什么这样设计"，是跨越初级和中级的分水岭。