Redis Underlying Data Structures Deep Dive SDS IntSet ZipList QuickList SkipList

引言

Redis 作为高性能的键值存储系统，被广泛应用于缓存、消息队列、Session 存储等场景。在日常使用中，我们接触最多的是 Redis 的五种基本数据类型：String、List、Hash、Set、Sorted Set。然而，这些上层数据类型背后所依赖的底层数据结构——SDS（简单动态字符串）、ZipList（压缩列表）、QuickList（快速列表）、IntSet（整数集合）、SkipList（跳跃表）——才是 Redis 高效性能的核心保障。

本文将深入剖析 Redis 的底层数据结构实现，并从源码级别理解 Redis 如何在不同场景下选择最优的数据结构组合，在内存占用与操作效率之间取得精妙的平衡。

一、SDS：简单动态字符串

1.1 为什么不用 C 字符串？

C 语言中，字符串被表示为字符数组，并以空字符（'\0'）作为结尾。这种设计存在若干严重缺陷：

获取字符串长度的时间复杂度为 O(n)：必须遍历整个字符数组直到遇到空字符，这对于需要频繁获取长度操作的场景是致命的性能瓶颈。

容易导致缓冲区溢出：C 字符串不记录自身长度，调用 strcat 等函数追加内容时，若分配的内存不足，会将数据覆盖到相邻内存区域。历史上因此类问题产生了无数安全漏洞。

不支持二进制安全：空字符被强制作为字符串结束标志，导致无法存储包含 '\0' 的二进制数据（如图片、压缩包、视频帧等）。

修改操作效率低下：每次追加或截断都需要重新分配内存，时间复杂度为 O(n)。

1.2 SDS 结构设计

Redis 设计了 SDS（Simple Dynamic String）结构来解决上述问题。在 Redis 3.2 版本之后，SDS 采用了多级内存结构，根据字符串长度选择不同的 header 类型：

SDS 结构大致包含三个部分：len（已使用字节长度）、alloc（分配的总字节长度，不含 header 和结束标志）、flags（header 类型标识）、buf[]（实际字符数组）。

当字符串特别短（长度不超过 44 字节）时，SDS 的 header（shdr）与 data（buf）会连续存放在同一块内存中，减少内存碎片和分配开销。

1.3 SDS 的核心优势

O(1) 获取字符串长度：SDS 结构体直接记录了 buf 中已使用字节的长度，无需遍历。

杜绝缓冲区溢出：执行 sdscat 追加内容前，会先检查是否有足够空间；若不足，自动扩容，避免了越界问题。

减少内存重分配次数：SDS 采用空间预分配策略——每次扩容不仅分配给修改所需的空间，还会额外分配未使用空间。当字符串长度小于 1MB 时，扩容为原来的两倍；大于 1MB 时，每次额外多分配 1MB。此外，缩短字符串时采用惰性空间释放，不立即回收内存，用 free 字段记录空闲空间供后续使用。

二进制安全：buf 中允许包含空字符，使用 len 作为长度判断依据，不依赖 '\0'，因此可以安全存储任意二进制数据。

二、IntSet：整数集合

2.1 IntSet 概述

IntSet 是 Redis 中 Set 数据结构的一种底层实现，当集合中的所有元素都是整数，且元素数量小于 set-max-intset-entries（默认 512）时使用。

IntSet 是值有序、无重复的底层数据结构，底层使用数组实现。其核心价值在于内存紧凑性——在少量整数场景下，比使用哈希表节省大量内存。

2.2 数据结构与升级机制

IntSet 结构包含三个字段：encoding（编码类型，决定每个元素占用多少字节）、length（元素数量）、contents[]（存储元素的整数数组）。

编码类型分为三种：INTSET_ENC_INT16（2字节）、INTSET_ENC_INT32（4字节）、INTSET_ENC_INT64（8字节）。

当新插入的元素超过当前 encoding 的表示范围时，IntSet 会进行升级（upgrade）操作：根据新元素的类型扩展数组空间，将现有所有元素转换为新类型（保持原有顺序），然后将新元素插入正确位置。

2.3 IntSet 查找与插入

查找操作使用二分查找（binary search），时间复杂度为 O(log n)，因为底层数组始终有序。

插入操作需要三个步骤：首先通过二分查找找到插入位置，然后将插入位置后的所有元素向后移动，最后填入新元素。时间复杂度为 O(n)。插入后如果总数超过 set-max-intset-entries，则自动转换为哈希表（hashtable）实现。

三、ZipList：压缩列表

3.1 ZipList 设计思想

ZipList 是 Redis 为了极致内存效率而设计的紧凑型双端链表结构。它不通过指针存储前后节点关系，而是将所有数据连续存放在一块内存中，仅在每个节点头部记录长度信息。

ZipList 被用作 Hash、List、Sorted Set 的底层实现之一——当元素数量较少且单个元素较小时使用。

3.2 ZipList 结构详解

ZipList 由以下部分组成：

• zlbytes：记录整个 ZipList 占用的字节数（用于 realloc 和计算末尾偏移）
• zltail：记录最后一个节点的偏移量，使得无需遍历即可执行 pop 操作
• zllen：记录节点数量
• entry：节点，包含 prevrawlen（前一节点长度）、len+encoding（当前节点编码和长度）、data（数据内容）
• zlend：0xFF 标志，表示列表结束

每个节点的 prevrawlen 字段具有作用：当当前节点长度小于 255 字节时，prevrawlen 占 1 字节；当长度大于等于 255 字节时，prevrawlen 占 5 字节。这种设计既能支持反向遍历，又避免了为短前驱节点分配过多的内存。

3.3 连锁更新问题

由于 prevrawlen 的变长设计（1 或 5 字节），ZipList 存在连锁更新（Cascade Update）的隐患：

当 ZipList 中存在大量长度在 250-253 字节之间的连续节点时，在其头部插入一个长度大于等于 254 字节的新节点，会导致原第一个节点的 prevrawlen 从 1 字节扩张为 5 字节，进而使其自身长度增加 4 字节，导致下一个节点的 prevrawlen 也需要从 1 字节扩张为 5 字节——如此相邻节点间的更新可能像多米诺骨牌一样传递整个列表，时间复杂度退化为 O(n²)。

Redis 通过限制使用场景（list-max-ziplist-entries、hash-max-ziplist-entries 等参数）将这种现象控制在可接受的概率范围内。Redis 7.0 之后引入了 ListPack 结构彻底解决了连锁更新问题。

四、QuickList：快速列表

4.1 为什么需要 QuickList？

ZipList 虽然内存高效，但当节点数较多时，插入/删除效率低且可能引发连锁更新。传统 Linked List 指针开销大（每个额外占用 16 字节的两个指针），且内存不连续导致缓存不友好。

Redis 4.0 引入 QuickList，将两者优点结合：宏观上是一个双向链表，每个节点是一个微观的 ZipList。这样既保证了内存的局部连续性，又避免了单一 ZipList 过大的问题。

4.2 QuickList 节点结构

QuickList 的每个节点（QuickListNode）包括：指向前驱节点的指针、指向后继节点的指针、指向 ZipList 指针、ZipList 大小（字节）、ZipList 中的元素个数。

可以理解为 QuickList 是 Mini ZipLists 的双向链表——一个宏观的链表嵌套着一个个微观的紧凑数组。

4.3 配置调优

通过 list-max-ziplist-size 参数控制单个 ZipList 的大小：

• 负值：限制 ZipList 包含的节点数量（-1: 4KB/node, -2: 8KB/node, -3: 16KB/node, -4: 32KB/node, -5: 64KB/node）
• 正值：限制 ZipList 包含的元素个数

4.4 QuickList 操作复杂度

查找指定索引元素：借助每个 QuickListNode 中记录的 fill 属性，可通过计算快速定位 ZIP，平均时间复杂度接近 O(n/节点数)。

Push/Pop 操作：O(1)，只需操作链表两端的 ZipList。

Insert/Delete 操作：若当前 ZipList 未满则 O(1)，已满则需要节点拆分，复杂度有所增加。

五、SkipList：跳跃表

5.1 SkipList 基本原理

跳跃表（Skip List）是一种基于有序链表的索引增强结构，通过在每个节点中维护多级索引，实现近似二分查找的查询效率。

与平衡树（如红黑树、AVL 树）相比，跳跃表的优势在于：内存开销更低（每个节点平均仅需 1.33 个指针）、无需旋转操作、实现简洁、支持范围查询、并发性能更友好。

5.2 Redis 中的 SkipList 实现

Redis 的跳跃表由两个结构体定义：zskiplistNode（节点）和 zskiplist（表头）。

每个 zskiplistNode 包含：

• ele：sds 类型字符串，存储成员值
• score：double 类型浮点数，存储分值（可重复）
• backward：指向前驱节点的指针（反向遍历）
• level[]：层级数组，每个 level 包含 forward（前进指针）和 span（跨度）

5.3 层级生成算法

与经典设计的固定层级不同，Redis 采用随机算法生成每个插入节点的层级：

插入新节点时，初始层级为 1，然后以概率 p=0.25 是否继续升层。即：有约 25% 概率升到 Level 2，6.25% 概率升到 Level 3，以此类推。这种随机化设计使得高层级节点数量指数级减少，形成类似树的层级结构。

Redis 中 SkipList 最大层级限制为 32（ZSKIPLIST_MAXLEVEL=32），足以支持约 42.9 亿个节点的索引。

5.4 带 Span 的范围查询

Redis 跳跃表独特之处在于 level 中的 span 字段记录了两个节点之间的距离。这使得 ZRANGEBYSCORE 和 ZRANK 操作的时间复杂度降低至 O(log n)。

例如查询排名为 rank 的元素时，从头节点最高层开始，累计 span 值，一旦累计值超过 rank 就下降层级。每次下降一层，span 累计更精确，最终到达目标节点时，累计的 span 之和就等于该节点的排名。

六、数据类型的底层组合与选择

理解了上述基本数据结构后，我们可以梳理 Redis 五种数据类型的底层编码组合：

• String：根据值的类型和长度选择 int（整数）、embstr（短字符串，SDS 结构体与字符串在同一内存块中，总长度小于等于 44 字节）或 raw（长字符串的 SDS）
• List：元素少且单个元素长度小时用 ZipList，否则用 QuickList
• Hash：键值对少且值的总长度小时用 ZipList，否则用 Dict（哈希表）
• Set：全为整数且元素数量少时用 IntSet，否则用 Dict
• Sorted Set：元素少时用 ZipList（元素和 score 交替存储），否则用 SkipList（实现排序）+ Dict（实现 O(1) 按成员查 score）

在 Redis 运行过程中，数据结构会根据插入数据规模和特征，自动升级。升级是单向的、不可逆的——一旦从紧凑结构转换为开放结构，即使后续元素减少也不会回退。这种设计体现了 Redis "内存换效率"的取舍哲学。

七、Redis 7.0 的进化：ListPack

Redis 7.0 引入 ListPack 结构取代了 ZipList 作为 Hash、List、Sorted Set 的底层实现之一。ListPack 的设计目标是消除连锁更新问题，同时保持相近的内存效率。

ListPack 与 ZipList 最大的区别在于：

• 节点不再记录前驱节点的长度，而是记录当前节点自身的长度（包括 header 和 data）
• 当前节点的长度是确定的——header 部分根据自身长度选择不同的编码
• 反向遍历时从尾部向头部解析，而不是通过前驱长度跳过节点
• 由于不依赖前驱长度信息，消除了连锁更新问题

此外，Redis Streams 功能就是基于 ListPack 实现的，用于存储消息 ID 和对应的字段值。

八、性能优化实践经验

8.1 合理设置阈值参数

掌握底层数据结构后，可以通过调整配置参数在使用场景下取得最优性能：

• hash-max-ziplist-entries 和 hash-max-ziplist-value：控制 ZipList 的 Hash 自动转换阈值，内存敏感场景可调高
• set-max-intset-entries：控制 Set 的 IntSet 转换阈值
• list-max-ziplist-size：控制 QuickList 节点的 ZipList 大小，写入密集时建议绝对值小一些（如 -2），读取密集时可调大

8.2 警惕大 Key 的危害

当 ZipList 大小接近阈值时，修改操作可能触发 ZipList 重分配、QuickList 节点拆分、甚至退化为哈希表。建议监控 Key 的大小分布，必要时主动拆分。

8.3 利用数据压缩

对于大量小规模 Hash 场景，保持 ZipList 编码状态时内存占用远低于 Dict。可在业务可接受的范围内，适当调高 hash-max-ziplist-entries 参数，以内存换性能。

8.4 Sorted Set 选型建议

数据量小于 zset-max-ziplist-entries（默认 128）时使用 ZipList 编码。若 Sorted Set 为静态数据（极少修改），ZipList 的 O(n) 查询性能在小规模数据下可以接受，且内存占用更小。

九、总结

Redis 的核心数据结构是一个精妙的内存压缩工程：SDS 解决了 C 字符串的固有缺陷，IntSet 提供纯整数场景下的极致紧凑，ZipList 以连续内存消除指针开销，QuickList 将 ZipList 与双向链表嵌套平衡性能，SkipList 用概率化的多级索引取代了复杂平衡树的旋转操作。

正是这些看似独立的底层数据结构的有机组合，才成就了 Redis 五种基础数据类型在不同场景下都能以最优的资源代价完成高性能操作。理解底层数据结构不仅是 Redis 进阶的必经之路，也为我们在面临特定性能瓶颈时提供了精准的优化方向。

十、展望

Redis 的开发仍在快速迭代。Redis 未来可能的方向包括：

• 函数式编程支持：Redis Functions API 的生态发展，推动 Redis 向可编程数据平台演进
• 向量搜索能力：RedisVL 等项目为 Redis 赋予向量数据库能力，支持 AI 语义检索
• 更智能的内存管理：基于运行时统计的自动编码转换策略
• 持久化改进：减少 RDB/AOF 对性能的影响，实现更高的数据可靠性

随着新型硬件（如 PMem、CXL）的普及和 AI 应用对数据处理的需求持续增长，Redis 的底层数据结构将持续演进，在保持极致性能的同时，拓展更多应用场景。