跳至主要內容

底层原理

硅碳合伙人大约 17 分钟RedisSDS跳表哈希表数据结构

开篇：Redis 快的秘密藏在数据结构里

上一篇我们学了 Redis 的核心用法，知道了 String、Hash、List、Set、ZSet 各自适合什么场景。但你有没有想过：为什么 Hash 小的时候特别省内存？为什么 ZSet 的范围查询能做到 O(log N)？为什么 Redis 不用 C 语言原生的 char* 而要自己搞一个 SDS？

这些问题的答案都藏在底层数据结构里。这篇文章，我们就深入 Redis 内部，看看它到底是怎么把数据组织起来的。

一、Redis 的数据存储结构

在 Redis 中，每个键值对都会有一个 dictEntry，里面存着指向 Key 和 Value 的指针。Key 统一用 SDS（简单动态字符串）存储，Value 则存储在 redisObject 结构体中。

redisObject 包含几个关键字段：

  • type：数据类型（String、Hash、List、Set、ZSet）
  • encoding：底层编码方式（决定用哪种数据结构实现）
  • ptr：指向实际数据的指针
  • lru：最近访问时间（用于淘汰策略）
  • refcount：引用计数（用于内存管理）

同一种类型可能有不同的底层编码。比如 Hash 类型，数据量小时用 ziplist（或 listpack），数据量大时用 hashtable。Redis 会根据数据量自动切换编码方式，这种设计在小数据量时极致省内存，大数据量时保证性能。

Bitmap 和 HyperLogLog 本质上是 String 类型，GEO 本质上是 ZSet 类型。

二、SDS：不只是 char*

C 语言的字符串就是一个以 \0 结尾的字符数组。这种设计有几个严重的问题：

问题 1：获取长度需要遍历。 C 字符串要知道自己多长，得从头开始数到 \0，时间复杂度 O(n)。

问题 2：不安全。 字符串拼接时如果忘了检查空间够不够，可能导致缓冲区溢出。而且如果字符串内容本身包含 \0（比如存储图片的二进制数据），C 字符串会在 \0 处截断，丢失后面的数据。

问题 3：每次修改都可能重新分配内存。 C 字符串的内存刚好够存内容，任何增长操作都需要 realloc。频繁的内存分配和释放非常耗性能。

Redis 为了解决这些问题，自己实现了 SDS（Simple Dynamic Strings）。

2.1 SDS 的核心设计

SDS 在字符数组的基础上增加了几个字段：

  • len：当前字符串长度。获取长度直接返回 len，O(1) 复杂度。
  • alloc：分配的总空间大小。拼接时先比较 新长度 和 alloc，空间够就直接拼，不需要重新分配内存。
  • flags：类型标识（SDS 有多种类型，适配不同大小的字符串）。
+------+------+-------+----------------------------+------+
| len  | alloc| flags |       buf (字符数组)         | '\0' |
+------+------+-------+----------------------------+------+

2.2 三个关键优化

O(1) 获取长度。 不再依赖 \0 标记，直接返回 len 字段的值。

空间预分配。 当 SDS 需要扩展时：如果修改后的长度小于 1MB，额外分配和 len 相同大小的未使用空间（翻倍增长）；如果大于 1MB，额外分配 1MB。这样后续的增长操作大概率不需要再分配内存。

惰性空间释放。 SDS 缩短时不会立即回收多余的空间，而是用 alloc - len 记录下来。如果后续又需要增长，直接使用这部分空间，减少内存分配次数。

二进制安全。 SDS 用 len 判断字符串结束，而不是 \0。所以它可以存储任意二进制数据，包括图片、音频等。

2.3 String 的三种编码

String 类型在底层有三种编码方式：

  • int：当值是一个整数（能放进 long 型）时使用。Redis 启动时会预先创建 0-9999 的共享对象，如果你 SET k 100，直接指向共享对象，不需要额外分配内存。
  • embstr：当字符串长度小于等于 44 字节时使用。embstr 把 redisObject 和 SDS 分配在同一块连续内存中，减少内存碎片，只需要一次内存分配。
  • raw：当字符串长度大于 44 字节时使用。redisObject 和 SDS 分别分配内存，需要两次内存分配。

为什么是 44 字节？因为 jemalloc 分配内存时会按 2 的幂次对齐，64 字节是一个常用的分配单元。redisObject 占 16 字节，SDS 头部占 3 字节，加上结尾的 \0 占 1 字节，64 - 16 - 3 - 1 = 44。

一个有趣的细节：embstr 是只读的。一旦你修改了一个 embstr 编码的字符串，它会先转成 raw 再修改，即使修改后的长度仍然小于 44 字节。

三、哈希表：渐进式 rehash

Redis 的全局键空间就是一个哈希表，Hash 类型的数据量大时也使用哈希表。理解 Redis 的哈希表实现，重点是理解渐进式 rehash。

3.1 为什么需要 rehash？

哈希表有一个"负载因子"的概念：当元素数量接近数组长度时，哈希冲突会急剧增加，性能下降。这时候需要扩容——通常是把数组大小翻倍，然后把所有元素重新计算哈希值并放到新的位置，这个过程叫 rehash。

Java 的 HashMap 是一次性完成 rehash 的：扩容时遍历所有元素，逐个迁移到新数组。对于内存中的小 HashMap 来说，这没什么问题。

但 Redis 不一样。Redis 的哈希表可能有几百万甚至上亿个元素。一次性 rehash 意味着主线程要花几秒甚至更长的时间来迁移数据，在此期间所有客户端请求都会被阻塞。这对于一个高性能内存数据库来说是不可接受的。

3.2 渐进式 rehash 的实现

Redis 的解决方案是渐进式 rehash：不是一次性迁移所有数据，而是在后续的每次增删改查操作中，顺便迁移一小批数据。

Redis 的哈希表内部维护了两个哈希表：ht[0] 和 ht[1]，以及一个 rehashindex（初始值 -1，表示没有在进行 rehash）。

扩容触发：当元素数量达到数组长度时（负载因子 >= 1），开始 rehash。把 ht[1] 的大小设为 ht[0] 的两倍，rehashindex 设为 0。

渐进迁移：每当有增删改查操作时，除了执行本身的操作外，还会把 ht[0] 中 rehashindex 位置的桶里的所有元素迁移到 ht[1]，然后 rehashindex + 1。

查询策略：在 rehash 期间，查询时先查 ht[0]，没找到再查 ht[1]。新增元素只往 ht[1] 中插入。

完成切换：当 ht[0] 中的所有数据都迁移完成后，交换 ht[0] 和 ht[1] 的指针，把 ht[1] 置为空，rehashindex 设回 -1。

初始状态：
ht[0]: [A][B][C][D][][][] (数据都在这里)
ht[1]: (空)
rehashindex: -1

开始 rehash，ht[1] 扩容为 2 倍：
ht[0]: [A][B][C][D][][][]
ht[1]: [][][][][][][][][][][][][][]
rehashindex: 0

第一次操作后（迁移 ht[0] 第 0 个桶）：
ht[0]: [ ][B][C][D][][][]
ht[1]: [][][A][][][][][][][][][][]   (A 被迁移到新位置)
rehashindex: 1

...逐步迁移，直到 ht[0] 清空...

完成：交换 ht[0] 和 ht[1]

这样做的好处是每次操作只迁移一个桶，开销非常小，均摊到每次操作中几乎不影响性能。缺点是在 rehash 期间，内存使用会短暂翻倍（两个哈希表同时存在）。

3.3 Redis Hash vs Java HashMap

面试中经常问两者的区别，核心差异有三点：

对比维度Redis HashJava HashMap
底层结构ziplist/listpack + hashtable数组 + 链表 + 红黑树
线程安全天然安全（Redis 单线程）不安全，需用 ConcurrentHashMap
扩容方式渐进式 rehash（分批迁移）一次性 rehash

四、跳表：有序集合的引擎

ZSet 的范围查询之所以高效，靠的就是跳表（SkipList）。

4.1 从链表到跳表

普通有序链表查找一个元素需要从头遍历到尾，时间复杂度 O(n)。怎么优化？

想象一栋大楼的电梯系统。普通链表就像只有楼梯——要到 20 楼就得一层层爬。跳表就像加了电梯——先坐电梯到大概的楼层，再走楼梯到精确的位置。

跳表的做法是：在原始链表的基础上建立多级索引。

Level 3:  1 ─────────────────────────── 26
Level 2:  1 ──────── 9 ──────── 17 ──── 26
Level 1:  1 ──── 6 ── 9 ── 12 ─ 17 ──── 26
Level 0:  1 - 3 - 6 - 7 - 9 - 12 - 17 - 26

查找 12 的过程：

  1. 从最高层开始：1 → 26，26 > 12，降到下一层
  2. Level 2：1 → 9 → 17，17 > 12，降到下一层
  3. Level 1：9 → 12，找到了

原来需要遍历 5 个节点（1, 3, 6, 7, 9, 12），现在只需要访问 4 个节点（1, 9, 17, 12）。数据量越大，跳表的优势越明显。

4.2 跳表的性能

跳表的查找、插入、删除操作的平均时间复杂度都是 O(log N)，和平衡二叉树（AVL 树、红黑树）相当。

那为什么 Redis 选择跳表而不是红黑树？Redis 的作者给出过解释：

  1. 实现简单：跳表的代码量远少于红黑树，更容易理解、调试和维护
  2. 范围查询高效：跳表找到起始元素后，沿着最底层链表顺序遍历即可。红黑树需要中序遍历，实现更复杂
  3. 插入性能好：跳表的插入不需要像红黑树那样做旋转操作来保持平衡

跳表也有缺点：维护多级索引需要额外的内存开销，而且新增或删除元素时需要更新索引。但对于 Redis 的使用场景来说，这些开销是可以接受的。

4.3 ZSet 的双重数据结构

ZSet 在底层同时使用了跳表和哈希表（dict）：

typedef struct zset {
    dict *dict;       // member -> score 的映射
    zskiplist *zsl;   // 按 score 排序的跳表
} zset;
  • 跳表负责按分数排序和范围查询，ZRANGEBYSCORE、ZRANGE 等命令走跳表
  • 哈希表负责 member 到 score 的快速映射，ZSCORE 命令走哈希表，O(1) 复杂度

两种结构共享同一份数据（通过指针），不会有数据冗余。这就是为什么 ZSet 既能支持 O(log N) 的范围查询，又能以 O(1) 获取元素分数。

五、压缩列表 → listpack 的演进

5.1 ziplist：用时间换空间

ziplist（压缩列表）是一种紧凑编码格式，本质是一块连续的内存。不像链表那样每个节点有前驱/后继指针，ziplist 的每个 entry 只存储前一个 entry 的长度和自身的数据。

+--------+--------+--------+---------+---------+-----+---------+--------+
| zlbytes| zltail | zllen  | entry_1 | entry_2 | ... | entry_N | zlend  |
+--------+--------+--------+---------+---------+-----+---------+--------+
  4字节    4字节    2字节                                          1字节

每个 entry 的结构是：

+----------+----------+---------+
| prevlen  | encoding | content |
+----------+----------+---------+
  • prevlen：前一个 entry 的长度。如果小于 254 字节，用 1 个字节存；否则用 5 个字节存
  • encoding：当前 entry 的类型和长度
  • content：实际数据

ziplist 的优势是极致省内存。普通链表每个节点至少有两个指针（前驱 + 后继），在 64 位系统上就是 16 字节。如果存储的数据本身只有几个字节，指针的开销比数据还大，非常浪费。ziplist 把所有数据挤在一块连续内存里，没有指针开销，内存局部性也更好（CPU 缓存友好）。

但 ziplist 也有缺点：查找某个元素需要从头遍历（O(n)），插入和删除需要移动后面所有数据。所以 ziplist 只适合存少量数据。

5.2 ziplist 的级联更新问题

ziplist 有一个臭名昭著的问题：级联更新（Cascade Update）。

prevlen 字段的大小不是固定的。当前一个 entry 长度小于 254 字节时，prevlen 用 1 字节表示；大于等于 254 字节时，prevlen 需要 5 字节。

假设有连续多个 entry，每个长度恰好是 253 字节。现在在中间插入一个长度为 300 字节的新 entry。新 entry 后面的那个 entry 的 prevlen 需要从 1 字节扩展到 5 字节（因为前面的 entry 现在超过 254 了）。扩展后这个 entry 自身的总长度也超过了 254，导致后面的 entry 也要跟着扩展......

插入前：  [253字节] [253字节] [253字节] ...
插入后：  [253字节] [300字节] [257字节] [257字节] ...
                             ↑ prevlen 从 1→5   ↑ 也跟着变

最坏情况下，一个插入操作会触发整条链路的级联更新。虽然这种极端情况在实际中很少发生，但它确实是一个设计缺陷。

5.3 listpack：告别级联更新

Redis 5.0 引入了 listpack（紧凑列表）来替代 ziplist。在 Redis 7.0 中，ZSet、Hash 等结构已经彻底使用 listpack 替代 ziplist。

listpack 的核心改进很简单：不再存储前一个 entry 的长度。取而代之的是，每个 entry 在末尾用一个 backlen 字段记录自身的总长度。

ziplist  entry:  [prevlen] [encoding] [content]
listpack entry:  [encoding] [content] [backlen]

这样一来，每个 entry 只记录自己的长度，不关心相邻 entry。插入或删除一个元素时，只影响自己，不会触发级联更新。

特性ziplistlistpack
前一个 entry 长度存储在 prevlen 中不存储
自身长度隐含在 encoding 中显式存储在 backlen 中
级联更新可能发生不会发生
版本Redis <= 6.2Redis >= 5.0（7.0+ 默认）

六、对象编码与类型映射

Redis 的每种数据类型在不同条件下会使用不同的底层编码。以下是完整的映射关系：

String

条件编码
值是整数且能放进 long 型int
字符串长度 <= 44 字节embstr
字符串长度 > 44 字节raw

Hash

条件编码
元素数量 <= 128 且所有 key/value 长度 <= 64 字节listpack（7.0 前是 ziplist）
不满足上述条件hashtable

List

所有 List 都使用 quicklist——一个双向链表，每个节点是一个 listpack（或 ziplist）。兼顾了链表的灵活性和压缩列表的内存效率。

Set

条件编码
所有元素都是整数且数量 <= 512intset
不满足上述条件hashtable

ZSet

条件编码
元素数量 <= 128 且所有 member 长度 <= 64 字节listpack（7.0 前是 ziplist）
不满足上述条件skiplist + dict

这些阈值可以通过配置修改，比如 hash-max-listpack-entries、zset-max-listpack-value 等。

编码转换是自动的、单向的——只能从紧凑编码升级到通用编码，不能降级。比如 Hash 从 listpack 升级到 hashtable 后，即使删除元素让数量减少到阈值以下，也不会退回 listpack。

七、内存管理

7.1 内存碎片

Redis 的内存碎片是指：被分配给 Redis 的内存空间中，没有被实际使用的部分。

主要原因是内存分配器无法做到精准按需分配。Redis 默认使用 jemalloc 分配器，它按固定大小（8B、16B、32B...4KB）划分内存页。当你要存 5 字节数据时，jemalloc 会分配 8 字节，剩下 3 字节就成了碎片。

查看碎片情况：

INFO memory

# 关键指标
used_memory: 1000000          # Redis 实际使用的内存
used_memory_rss: 1200000      # 操作系统分配给 Redis 的物理内存
mem_fragmentation_ratio: 1.20 # 碎片率 = rss / used_memory
  • 碎片率 1.0-1.5：正常范围
  • 碎片率 > 1.5：碎片较多，需要处理

7.2 碎片整理

Redis 4.0 提供了主动碎片整理功能：

CONFIG SET activedefrag yes
CONFIG SET active-defrag-threshold-lower 50   # 碎片率 > 50% 开始整理
CONFIG SET active-defrag-cycle-max 75         # CPU 使用率上限

原理是 Redis 在后台扫描内存中的小对象，通过移动数据和释放旧内存来减少碎片。整个过程对性能有一定影响，所以通过 CPU 使用率上限来控制。

最暴力的方案当然是直接重启 Redis，从 RDB/AOF 恢复数据后内存是连续的，碎片自然消失。

7.3 共享对象池

Redis 启动时会预先创建 0-9999 这 10000 个整数的 redisObject 共享对象。当你 SET k 100 时，value 的 redisObject 直接指向共享对象池中的 100，不需要额外分配内存。

这意味着，如果你的业务中大量使用小整数作为 Value（比如计数器、状态码），内存占用会非常低。

注意：只有 int 编码的 String 才能使用共享对象。如果 Value 是字符串（即使是 "100" 这样的数字字符串），Redis 仍然需要分配新的 SDS 对象。

7.4 为什么 quicklist 是 List 的最终方案？

早期的 Redis 中，List 类型在数据量小时用 ziplist，数据量大时用 linkedlist（双向链表）。但这两种方案各有问题：

  • ziplist 在数据量大时插入删除太慢（需要移动大量数据）
  • linkedlist 每个节点有两个指针（16 字节），加上内存分配器的开销，小数据时浪费严重

Redis 3.2 引入了 quicklist，它是二者的结合：一个双向链表，每个节点内部是一个 ziplist（现在是 listpack）。

quicklist 整体是双向链表：
  node1 ←→ node2 ←→ node3 ←→ node4

每个 node 内部是一个 listpack：
  node1: [entry_a][entry_b][entry_c]
  node2: [entry_d][entry_e][entry_f]
  ...

这样做的好处是：每个节点内部的 listpack 保证了内存紧凑，节点之间的链表保证了插入删除高效。通过配置 list-max-listpack-size 可以控制每个节点的 listpack 大小，在内存效率和操作性能之间取得平衡。

八、常见面试题

Q1：Redis 为什么要自己实现 SDS？

C 语言字符串有三个问题：获取长度需要 O(n) 遍历、不是二进制安全（\0 截断）、每次修改都可能重新分配内存。SDS 通过 len 字段实现 O(1) 获取长度，通过 len 而非 \0 判断结束实现二进制安全，通过空间预分配和惰性释放减少内存分配次数。

Q2：什么是渐进式 rehash？

Redis 哈希表扩容时，不是一次性把所有数据从旧表迁移到新表，而是在后续的每次操作中顺便迁移一个桶。这样把迁移开销均摊到每次操作中，避免了长时间阻塞。代价是 rehash 期间内存短暂翻倍。

Q3：ZSet 为什么数据量小时用 listpack，大时用 skiplist？

listpack 的优势是极致省内存（连续内存、无指针开销），但增删改查是 O(n)。skiplist 的优势是 O(log N) 的高效操作，但内存开销大（多级索引指针）。数据量小时，O(n) 和 O(log N) 差别不大，listpack 的内存优势更重要；数据量大时，性能差距显著，必须切换到 skiplist。

Q4：ziplist 的级联更新是什么？listpack 如何解决？

ziplist 的每个 entry 都存储前一个 entry 的长度（prevlen），prevlen 用 1 或 5 字节表示。当插入或修改导致某个 entry 长度跨越 254 字节阈值时，后续 entry 的 prevlen 字段需要扩展，可能引发连锁反应。listpack 不再存储 prevlen，改为在 entry 末尾存储自身长度（backlen），每个 entry 只关心自己，彻底消除级联更新。

Q5：ZSet 为什么能同时支持 O(1) 获取分数和 O(log N) 范围查询？

因为 ZSet 底层同时使用了哈希表和跳表。哈希表存储 member → score 的映射，ZSCORE 走哈希表，O(1)。跳表按 score 排序存储所有元素，ZRANGEBYSCORE 走跳表，O(log N)。两种结构通过指针共享数据，不会造成内存冗余。

小结

这篇文章深入了 Redis 的底层世界：

  • SDS：O(1) 长度获取、空间预分配、二进制安全，全面优于 C 字符串
  • 哈希表：渐进式 rehash 避免一次性迁移的阻塞
  • 跳表：多级索引实现 O(log N) 的查找和范围查询，比红黑树实现更简单
  • ziplist → listpack：从级联更新问题到 backlen 方案的优雅解决
  • 编码映射：同一类型在不同数据量下自动切换编码，平衡内存和性能

理解了底层数据结构，你会对 Redis 的性能特征有更深刻的认知——为什么某些操作快、为什么某些配置会影响内存使用、为什么大 Key 是问题。这些都不再是需要死记硬背的知识点，而是从数据结构设计中自然推导出来的结论。