Redis - 漫谈Redis底层数据结构

文章目录

• 概述
• 数据类型与底层结构的对应关系
• key 和 value 之间的桥梁：全局哈希表
• rehash 的代价与渐进式优化
• 集合类型的底层结构
• 操作复杂度的"四句口诀"
• 那些需要警惕的"慢操作"
• 为什么压缩列表和整数数组依然有价值
• 小结

概述

谈起 Redis，"快"几乎是绕不开的标签。一个键值操作能在微秒级完成，这在数据库圈子里相当亮眼。表面上看，"内存数据库"就是答案，但内存只是必要条件，不是充分条件——如果数据组织得糟糕，再快的内存也救不了。Redis 真正的底气，来自它对底层数据结构的精挑细选。

但同样这套数据结构，也埋着"慢操作"的暗坑。SMEMBERS 一次拉出几十万元素、HGETALL 把一个超大 Hash 全量返回，都能让单线程的 Redis 瞬间卡住。理解每种数据类型背后用了什么结构，是把 Redis 用得既快又稳的前提。

数据类型与底层结构的对应关系

我们日常说的 Redis 五大数据类型——String、List、Hash、Set、Sorted Set——只是 value 的逻辑形态。它们背后真正干活的，是六种底层数据结构：

• 简单动态字符串（SDS）
• 双向链表
• 压缩列表（ziplist）
• 哈希表
• 跳表（skiplist）
• 整数数组（intset）

对应关系大致是这样：

可以看到，除了 String 是唯一确定的实现，其他四种类型都至少有两套底层结构。Redis 会根据元素数量和单个元素大小，在两者之间动态切换：数据量小的时候选紧凑的压缩列表或整数数组，节省内存；数据量大了再切到哈希表或跳表，保住查询效率。这是 Redis 在内存利用率和访问性能之间精打细算的结果。

key 和 value 之间的桥梁：全局哈希表

不管 value 的内部结构是什么，Redis 都得先解决一个问题：怎么从 key 跳到对应的 value。它的答案是一张全局哈希表。

哈希表本质上是一个数组，每个数组元素叫一个哈希桶。每个桶里保存的是一个 entry，entry 里放着两个指针——*key 指向真正的键，*value 指向真正的值。这种"都用指针"的设计意味着，无论 value 是 String 还是集合，哈希桶的结构都不变，所有类型的查找都走同一套入口。

哈希表带来的最大好处是 O(1) 的查找复杂度。算一下 key 的哈希值，定位到桶，就能取到 entry。哈希表里有 10 万还是 100 万个 key，对查找时间几乎没有影响。这是 Redis 微秒级响应的根基。

但写入数据多了之后，哈希冲突不可避免——两个不同的 key 算出来落进了同一个桶。Redis 的解法是链式哈希：同一个桶里的多个 entry 通过 *next 指针串成一条链表。查的时候顺着链表挨个比对 key，找到目标。

链表越长，查询越慢。极端情况下，单个桶里挂着上百个 entry，O(1) 就退化成了 O(n)。这显然不能接受，于是哈希表必须扩容——也就是 rehash。

rehash 的代价与渐进式优化

Redis 默认维护两张哈希表：哈希表 1 和哈希表 2。一开始所有数据都在哈希表 1 里，哈希表 2 空着。当哈希表 1 装得太满，rehash 就开始：

如果第二步一次性完成，就要把所有 entry 全部迁移一遍。在键值对数量很大的情况下，这个过程能持续很长时间，期间 Redis 的主线程被占用，完全没法响应客户端。

Redis 的解法是渐进式 rehash：迁移工作不集中做，而是分散到每一次客户端请求里。每处理一个请求，就顺手把哈希表 1 的某一个索引位置上的所有 entry 搬到哈希表 2。请求来得越多，迁移得越快；没请求时也有定时任务推进迁移。这样把一次大停顿摊薄成无数次微小延迟，主线程几乎感受不到压力。

渐进式 rehash 期间，新写入的数据全部进哈希表 2，而读操作要同时查两张表——先查哈希表 1，没找到再查哈希表 2。等哈希表 1 完全清空，整个过程就结束了。

集合类型的底层结构

定位到 value 之后，对 String 类型来说基本就完事了；但对 Hash、List、Set、Sorted Set 这种集合类型，还要在集合内部再做一次操作。这时候底层结构就成了决定性能的关键。

整数数组是 Set 在元素都是整数且数量较少时使用的结构。元素按从小到大排好，查找用二分。结构紧凑，几乎没有额外开销，缺点是插入要移动元素。

双向链表是 List 的传统实现，节点之间通过前后指针连接。优点是头尾插入删除都是 O(1)，缺点是随机访问只能遍历，复杂度 O(n)。

压缩列表是一种"伪装成数组的链表"。表头存了三个字段：zlbytes（总长度）、zltail（尾部偏移量）、zllen（元素个数），表尾用 zlend 标记结束。这三个表头字段使得定位首尾元素都是 O(1)，但要找中间的元素，还得从头逐个扫描，复杂度 O(n)。压缩列表的核心价值在内存利用率——所有元素紧挨着存，没有多余的指针开销，CPU 缓存还特别友好。Redis 在小数据量场景下大量使用压缩列表，正是看中这一点。

哈希表前面已经聊过，用作 Hash 和 Set 的底层结构时同样提供 O(1) 的访问。

跳表专门为有序集合设计，是 Sorted Set 在数据量大时的底层实现。

普通有序链表的查找复杂度是 O(n)。跳表的思路很巧妙：在链表上方建多级索引，每一级都从下一级里抽出部分节点，索引节点之间通过指针指向下一级。查找时从最高级索引开始往下跳，逐级缩小范围。比如要在 8 个有序节点里找 33，普通链表要遍历六次，加一级索引后只要四次，再加一级二级索引只要三次。数据量越大，跳表的优势越明显，整体查找复杂度是 O(log n)。

按查找复杂度归一下类：

操作复杂度的"四句口诀"

集合类型的命令繁多，但操作的复杂度可以用四条规律快速判断。

单元素操作是基础。 像 HGET、HSET、HDEL、SADD、SREM 这些只针对单个元素的命令，复杂度由底层结构决定：用哈希表的就是 O(1)，用整数数组或链表的就是 O(n)。需要注意的是，HMSET、HMGET、SADD 这种支持一次操作多个元素的命令，复杂度会变成 O(m)，m 是参与操作的元素数。

范围操作非常耗时。 HGETALL、SMEMBERS、LRANGE、ZRANGE 这类需要返回集合中全部或一段元素的命令，复杂度通常是 O(n)。集合大的时候，这种命令足以阻塞整个 Redis。生产里要尽量避免，能用 SCAN 系列（HSCAN、SSCAN、ZSCAN）就用 SCAN——它们采用游标式遍历，每次只返回少量数据，不会一次性把 Redis 卡住。

统计操作通常高效。 LLEN、SCARD 这种取集合大小的命令复杂度是 O(1)。原因是底层结构里专门维护了元素计数字段，不需要遍历就能拿到。

例外情况只有几个。 压缩列表和双向链表都额外记录了表头表尾的偏移量，所以 List 的 LPOP、RPOP、LPUSH、RPUSH 这四个头尾操作也是 O(1)，可以放心用作队列。

掌握了这四条，遇到陌生的命令也能八九不离十地推断出复杂度。

那些需要警惕的"慢操作"

知道了哪些操作复杂度高，就知道哪些操作要绕开。下面这些是生产中最常见的雷区：

• KEYS *：扫描全部键，复杂度 O(n)，在大库上几乎必定阻塞。线上禁用，要遍历键就用 SCAN
• HGETALL、SMEMBERS 在大集合上：一次性把整个集合拉出来，网络和 CPU 双重压力
• LRANGE key 0 -1：相当于把整个 List 取出来，本质和 HGETALL 是同一个问题
• 大 key 的删除：DEL 一个上百万元素的集合也会阻塞主线程，4.0 之后可以用 UNLINK 异步释放
• 大量 key 同时过期：过期清理在主线程做，集中过期会拖慢响应
• 复杂聚合命令：SORT、SUNIONSTORE、ZUNIONSTORE 这类涉及多集合的运算复杂度普遍较高

为什么压缩列表和整数数组依然有价值

回到一个值得思考的问题：压缩列表和整数数组的查找复杂度是 O(n)，凭什么 Redis 还把它们留下来？

两个原因。

内存利用率。 数组和压缩列表都是紧凑结构，元素之间没有多余指针。Redis 是内存数据库，每节省一个字节都有意义。一个只有十几个字段的小 Hash，用哈希表存反而比压缩列表浪费——因为哈希表本身有桶数组、entry 指针这些固定开销。

CPU 缓存友好。 紧凑结构的数据在内存里连续排列，CPU 缓存行可以一次读取多个元素。在元素数量少的时候，O(n) 的扫描配合缓存命中，往往比 O(1) 的哈希计算还要快——哈希计算本身要算哈希值、跳转到对应桶，反而开销更大。

所以 Redis 的策略是设阈值切换：Hash 元素少且小时用压缩列表，超过阈值切到哈希表；Set 全是整数且数量少时用整数数组，否则切到哈希表；Sorted Set 元素少时用压缩列表，多了切到跳表。这是非常典型的"小数据省空间，大数据保性能"的工程取舍。

小结

Redis 之所以快，外层是 O(1) 的全局哈希表，里层是各种为不同场景定制的高效结构。它之所以会慢，是因为某些命令需要扫遍整个集合，而单线程的 Redis 经不起这样的折腾。

用 Redis 的关键是匹配数据结构和访问模式：需要随机访问的不要拿 List 当数组用；要范围查询的优先选 Sorted Set；要做去重和成员判断的用 Set；存对象属性的用 Hash。同时记住四句口诀——单元素操作是基础、范围操作非常耗时、统计操作通常高效、例外情况只有几个——基本上就能在没看文档的情况下判断一条命令该不该用。

工具是死的，用工具的人是活的。理解了底层结构和操作复杂度的对应关系，碰到性能问题时就不会乱猜，而是能直接定位到症结。这才是把 Redis 用透的正确姿势。