当前位置：首页 > news >正文

Redis 八股

news 2025/9/2 10:37:32

1. Redis Zset的底层结构与原理

Redis 中的 zset（有序集合）是一种支持按分数排序的有序数据结构，底层由跳表（Skip List）和哈希表（Hash Table）组合实现。这两者的结合使 zset 在保证元素唯一性的同时，支持快速的分数排序、范围查找和高效插入/删除操作。

1.1 跳表和哈希表在 Zset 中的协作

在 zset 的底层结构中，跳表和哈希表分别承担不同的任务：

跳表（Skip List）：负责所有与分数排序相关的操作。
- 跳表节点以分数（score）进行排序，保证插入、删除和范围查找的高效性。
- 跳表的每个节点存储了两个信息：元素值和分数。此外，每个节点包含多个指针，用于链接上、下层和前后节点。
- 所有按分数排序的操作，例如按分数范围查询、按排名范围查询，都是基于跳表实现的。因此，ZRANGEBYSCORE、ZRANK、ZREVRANGE等命令均在跳表上操作。
哈希表（Hash Table）：负责按元素值查找和分数更新。
- 哈希表用于快速查找元素，提供 O(1) 的查找复杂度。哈希表的键为元素值，值为分数。
- 当需要根据元素值查找或更新分数（如 ZSCORE、ZADD 更新已有元素的分数），会首先在哈希表中找到对应分数，再去跳表中定位到该元素并进行相应操作。

具体操作中的协作流程

添加元素 (ZADD)
1. 首先检查哈希表中是否已有该元素。如果存在，则是更新操作；如果不存在，则是新增操作。
2. 若是更新操作，先在哈希表中更新分数，再根据新分数调整跳表中的位置（即删除旧位置节点，重新插入新分数位置）。
3. 若是新增操作，先在哈希表中插入元素值和分数，然后在跳表中根据分数插入新节点。
按分数或排名查找 (ZRANGEBYSCORE、ZRANGE)
1. 按分数查找时，直接使用跳表的分数排序结构，以 O(log N + M) 的复杂度在跳表中进行范围查找。
2. 按排名查找时，跳表支持按分数排序的节点直接按排名访问，通过跳表的层级结构在指定范围内查找元素。
按元素查找 (ZSCORE、ZREM)
1. ZSCORE 或 ZREM 查询时，通过哈希表快速找到指定元素的分数。
2. 一旦在哈希表中定位到分数，则可以根据该分数直接找到跳表中的节点进行删除或返回操作。

1.2 跳表的分层结构

跳表（Skip List）是一种在链表基础上改进的、支持快速查找的有序数据结构。它在普通链表的基础上增加了多层“跳跃”层级，让查找、插入和删除操作的时间复杂度从线性的 O(N) 降低到接近 O(log N)，类似于平衡二叉树。

1. 普通链表的查找缺陷

在普通链表中，节点按顺序排列，每个节点只指向下一个节点。如果需要查找一个特定值，我们必须从头开始逐个节点遍历到目标位置，因此查找复杂度是 O(N)。

2. 跳表的分层结构

为了加快查找速度，跳表引入了“分层结构”。跳表的基本思路是，将链表中的节点划分为多层，每一层都是一个独立的链表，这些链表之间满足“分层跳跃”的关系：

每层是一个链表：
- 每个 level 是一个链表，从最高层到最低层，每层都包含当前层中的节点，并连接这些节点形成一个单独的链表。
- 最底层链表（Level 0）包含所有节点，保证了完整的元素序列，而更高层的链表节点数逐渐减少，是下一层的一个子集。
节点的链接：
- 在最底层，所有节点都按照顺序连接，形成一个完整的链表。
- 在更高层，部分节点会“升级”到当前层，成为更高层链表的一部分。高层节点往往跨度更大，可以跳过一些低层节点，从而实现“跳跃”式查找。
示例结构：
```
Level 3: 1 ------->     10 ------->     20
Level 2: 1 ----> 7 -->  10 ----> 17 --> 20
Level 1: 1 -> 5 -> 7 -> 10 -> 15 -> 17 -> 20
Level 0: 1 -> 3 -> 5 -> 7 -> 10 -> 15 -> 17 -> 20
```
- Level 3：包含节点 1 -> 10 -> 20，形成一个链表。
- Level 2：包含节点 1 -> 7 -> 10 -> 17 -> 20，形成另一个链表。
- Level 1：包含节点 1 -> 5 -> 7 -> 10 -> 15 -> 17 -> 20，也是一个链表。
- Level 0：包含所有节点，形成一个完整的链表。

每个节点会随机决定是否出现在更高层，因此跳表是一种概率性平衡的数据结构。层级越高的链表，节点数越少，跨度越大，允许跳过更多节点，从而更快接近目标值。

3. 跳表的查找流程

跳表的查找依赖于多层结构，通过高层的“跳跃”来快速接近目标区域，最后在底层链表中找到精确位置。具体查找过程如下：

从最高层开始：在最高层（例如 Level 3）链表开始，从左到右查找目标值，直到找到最接近但小于等于目标值的节点。
逐层向下：在当前层找到接近目标的节点后，转移到下一层继续查找，进一步逼近目标值。
到底层查找：在最底层链表（Level 0）中找到精确的节点或目标范围。

例如，在一个跳表中查找值 15 的流程可能如下：

Level 3: 1 ------->     10 ------->     20
Level 2: 1 ----> 7 -->  10 ----> 17 --> 20
Level 1: 1 -> 5 -> 7 -> 10 -> 15 -> 17 -> 20
Level 0: 1 -> 3 -> 5 -> 7 -> 10 -> 15 -> 17 -> 20

在 Level 3，先跳到 10，然后跳到 20（发现 20 太大）。
转到 Level 2，在 10 和 17 之间找到 10，继续向右跳到 17。
转到 Level 1，跳到 10，发现 15 还在 10 和 17 之间。
在 Level 0 找到 15。

1.3 Zset 的范围查找

假设我们有一个 zset，并要查找分数在 100 到 200 之间的所有元素。范围查找的具体步骤是：

1.从跳表的最高层开始

先从跳表的最高层开始查找，利用跳表的跨层跳跃特性快速逼近 100 分数的范围。
在最高层的链表中，从左向右跳跃，跳过所有分数小于 100 的节点，找到第一个大于或等于 100 的节点。

2.逐层向下精确定位

一旦在高层定位到分数大于或等于 100 的节点，进入下一层查找。每层跳表的跨度逐渐变小，允许更精确地找到目标范围。
逐层进入直到最底层链表（Level 0），在此层中找到第一个满足 score >= 100 的节点，作为范围查找的起点。

3.沿底层链表查找目标范围内的所有节点

从最底层链表的起点节点开始，沿着链表遍历，找到所有分数在 100 到 200 之间的节点。
遍历过程中，每个满足条件的节点都被加入结果集中。
当遇到第一个分数大于 200 的节点时，停止查找。

举例说明

假设跳表结构如下，我们执行 ZRANGEBYSCORE 100 200：

Level 3: 1 ------->     10 ------->     20
Level 2: 1 ----> 7 -->  10 ----> 17 --> 20
Level 1: 1 -> 5 -> 7 -> 10 -> 15 -> 17 -> 20
Level 0: 1 -> 3 -> 5 -> 7 -> 10 -> 15 -> 17 -> 20

从 Level 3 开始，从 1 跳到 50，再跳到 150。发现 150 在范围内，所以跳过 250。
转到 Level 2，从 100 继续向右跳到 150，再跳到 200，确认在范围内。
到 Level 1、Level 0 后，可以直接获取 100 到 200 的所有节点：100, 150, 175, 200。

这种方式让 zset 的范围查找操作复杂度接近 O(log N + M)，其中 N 为元素数，M 为结果数。跳表的高层快速跳跃，低层精确查找，使得范围查找高效又灵活。

1.4 为什么 zset 使用跳表而不是 B+ 树？

跳表更适合 Redis 的内存操作
- Redis 是内存数据库，而 B+ 树更多用于磁盘存储的数据结构。B+ 树节点较复杂，通常为一组指针和子树结构，适合在磁盘上批量读取，而在内存中会占用更多空间和复杂度。
- 跳表结构简单，指针操作相对少，占用内存更低且查找性能稳定。
跳表的实现更简单，且性能稳定
- 跳表的实现相比 B+ 树简单，且不需要复杂的旋转、节点拆分或合并操作。尤其在频繁增删的场景下，跳表的指针调整非常简单。
- 在增删节点时，跳表仅需更新部分指针，避免了 B+ 树中节点重排和树高变化的问题。
动态调整和范围查找更高效
- 跳表的层级结构是动态调整的，平均查询性能接近平衡树，适合按分数范围查询。
- 跳表天然支持范围查找，且 Redis 中跳表的实现支持快速访问节点前后元素，能够在保持顺序的同时实现高效范围查找。

2. Redis List

2.1 Redis List的底层数据结构

2.1.1 形象理解及特点

可以把 Redis List 想象成：

quicklist = 铁轨（双向链表）
node = 一节车厢（链表节点）
pack = 车厢里的座位排（连续内存块，紧凑存多个元素）

这样设计的好处：

两端操作快：铁轨让你可以在两端快速挂车厢。
减少指针开销：每节车厢装一排座位，而不是一节车厢只放一个人。
消除连锁更新问题：新的一排座位（listpack）替换旧的一排座位（ziplist）。

2.1.2 外层结构：quicklist

数据结构：双向链表
作用：把整个 list 拆分成一段段小块，每块存在一个 node 里。
每个 node 结构包含：
- 前驱指针、后继指针（prev/next）
- 当前 node 内部元素数量（count）
- 当前 node 占用字节数（sz）
- 指向内部 pack 的指针（data）
- 压缩标志位（是否启用 LZF 压缩，list-compress-depth 参数控制）

所以 quicklist = 一串 node 节点：

 head <-> [Node#1] <-> [Node#2] <-> [Node#3] <-> tail│            │             │pack          pack          pack

2.1.3 内层结构：listpack

（1）ziplist 的 prevlen 设计（连锁更新问题）

ziplist 是 Redis ≤ 6.x 的 pack 格式，本质是一块连续内存：

+-----------------+---------------------+-------+
| header (头部)   | entry1, entry2, ... | end   |
+-----------------+---------------------+-------+

header：存 ziplist 总字节数、元素个数等信息。
entry：每个元素的节点，包含：
- prevlen：前一个元素的长度（为了支持反向遍历）；
- len + encoding：当前元素的长度和编码方式；
- data：元素的数据本体。
end：特殊标志，表示 ziplist 结束。

触发条件
当插入或删除一个元素时，如果该元素的长度变化，导致 prevlen 的存储空间需要调整（例如从 1 字节扩展到 5 字节），则后续所有元素的 prevlen 都必须依次更新。

最坏情况
这种“连锁更新”可能波及整个 ziplist，时间复杂度最坏可达 O(N²)。
因此 ziplist 在插入/删除时存在严重的性能抖动问题。

（2）listpack 的 backlen 设计

Redis 7.0+ 用 listpack 取代 ziplist：

+-----------------+---------------------+-------+
| header (头部)   | entry1, entry2, ... | end   |
+-----------------+---------------------+-------+

和 ziplist 相似，但 entry 结构发生了关键改变：

不再使用 prevlen，即不记录“前一个元素的长度”。
新增 backlen：记录 当前元素起始位置到 listpack 末尾的偏移量。

好处

插入新元素时：只有新元素之后的 entry 的 backlen 需要更新（因为它们到末尾的距离变了）。
每个 backlen 独立计算，不依赖前驱元素，因此 不会产生连锁更新。
插入/删除操作性能更稳定，复杂度保持在 O(N)。

示例
假设 listpack 原有三个元素：

[A][B][C]

在 B 后插入 X，变为：

[A][B][X][C]

只有 C 的 backlen 需要更新（因为它到末尾的距离变了）。
A 和 B 的 backlen 不受影响。

这就是 listpack 相比 ziplist 最大的改进：避免了连锁更新，性能更稳定。

2.2 Redis List 的操作原理

2.2.1 两端操作（LPUSH、RPUSH、LPOP、RPOP）

找到链表的头节点或尾节点。
如果对应的 node 内部 pack 还有空间，就把元素直接放进去；
如果满了，就创建新 node 并挂到 quicklist 的头或尾。
弹出时，如果某个 pack 被清空，就把 node 节点释放掉。
摊还复杂度 O(1)。

👉 这就是为什么 Redis List 适合作队列或栈。

2.2.2 按索引访问（LINDEX）与范围读取（LRANGE）

quicklist 先判断索引更靠近头还是尾，从近的一端遍历 node；
在 node 内部的 pack 里顺序遍历找到目标元素；
复杂度 O(n)，但比单链表快一些（因为 pack 内是连续内存，局部性好）。

2.2.3 中间插入与删除（LINSERT、LREM）

Redis 会先找到目标 node；
在 pack 内部移动字节来空出或挤掉元素；
如果 pack 太大，可能会触发 分裂/合并。
复杂度 O(n)，操作代价大。
👉 所以 Redis List 不适合做随机插入/删除。

3. Redis Hash 底层结构与原理

3.1 元素个数少：listpack（旧版是 ziplist）

使用条件

field-value 对数量 ≤ 512（hash-max-listpack-entries）
每个 field/value 的长度 ≤ 64 字节（hash-max-listpack-value）

满足这两个条件，就用 listpack 紧凑存储。

结构

+-----------------+---------------------+-------+
| header (头部)   | entry1, entry2, ... | end   |
+-----------------+---------------------+-------+

header：记录总字节数、元素个数。
field/value entry：
- enc+len：本 entry 的长度和编码方式。
- data：存放真正的 field 或 value。
- backlen：记录本 entry 的总长度（放在 entry 尾部）。
end：0xFF 结束标志。

为什么不用 ziplist 了？

ziplist entry 里有 prevlen（前一个元素的长度）。
如果前一个元素变长，就可能触发后续所有元素的 prevlen 更新 → 连锁更新（最坏 O(N²)）。
listpack 改成 backlen（记录自己长度），插入/删除时只改自己和局部，不会触发连锁更新。

⚠️ 复杂度：listpack 查找和修改是 O(N)（线性扫描）。

3.2 元素个数多：hashtable（dict）

当满足以下条件之一时，Hash 会整体从 listpack 转换成 hashtable：

field 数量 > 512
任一 field 或 value 的长度 > 64 字节

一旦升级成 hashtable，不会再降级。

3.2.1 dict 结构（最外层）

dict├─ ht[0]  // 当前使用的哈希表├─ ht[1]  // rehash 时新建的哈希表└─ rehashidx  // 渐进式 rehash 的进度（=-1 表示没在 rehash）

Redis 的 dict 有两个 hashtable：
- 正常情况下只用 ht[0]；
- 当扩容/缩容时，会申请一个新的 ht[1]，然后逐步把 ht[0] 的内容搬过去。
rehashidx：记录搬迁进度，每次对 Hash 做读写操作时顺带迁移一部分，直到 ht[0] 为空为止。

3.2.2 hashtable（哈希表）

hashtable├─ table : dictEntry*[]  // 桶数组（长度为 2 的幂）├─ size  : 桶数量├─ used  : 已用元素数└─ sizemask = size - 1   // 用于快速取模

table 是一个数组，每个位置是一个桶，存放一个链表的头指针。
取模时用 hash & sizemask，快速定位桶。

3.2.3 dictEntry（链表节点）

dictEntry├─ key : field（SDS 字符串）├─ value : value（SDS 字符串）└─ next : 下一个 dictEntry（处理哈希冲突）

3.3 Redis 的渐进式 rehash （缩容和扩容都会rehash）

Redis 采用了一种巧妙的"双书架"策略：

（1）准备阶段

Redis 维护两个哈希表：旧表（ht[0]）和新表（ht[1]）
平时只使用旧表，新表空着
当旧表装得太满时（负载因子 ≥ 1），开始准备 rehash

（2）开始 rehash

为新表分配空间（通常是旧表的 2 倍大小）
设置一个"搬迁进度指针"（rehashidx），从 0 开始
重要：此时不立即搬迁数据

（3）渐进式搬迁过程

这里是关键创新：不是一次性搬完，而是每次操作时搬一点

搬迁策略

每次用户进行增删改查操作时，Redis 顺便搬迁一个桶的数据
从 rehashidx 指向的桶开始，把这个桶里的所有数据搬到新表
搬完后 rehashidx 指向下一个桶
如果遇到空桶，就跳过继续找下一个有数据的桶

数据查找

在搬迁期间，数据分布在两个表中：

查找时：先在旧表找，找不到再去新表找
添加时：新数据直接放到新表（避免旧表继续增长）
删除时：两个表都要检查

（4）完成 rehash

当所有桶都搬迁完成后，旧表变空
释放旧表空间，新表变成旧表，重新初始化新表
rehashidx 重置为 -1，表示没有在进行 rehash

4. Redis Set 的底层数据结构

4.1 元素个数少：intset（整数集合）

使用条件

Set 中的所有元素都是整数（字符串格式的数字也会转成整数存）。
元素个数 ≤ set-max-intset-entries（默认 512）。

满足条件时，Redis 会用 intset 来存储 Set。

结构

+---------+---------+---------+-------------+
| encoding| length  | contents[...]        |
+---------+---------+---------+-------------+

encoding：整数的编码方式（16 位 / 32 位 / 64 位），由能容纳的最大整数决定。
length：当前元素个数。
contents：真正的整数数组，升序排列存放。

特点

插入时会保持有序（内部是二分查找 + 内存搬移）。
查找复杂度 O(logN)（二分搜索）。
插入/删除复杂度 O(N)（因为可能要搬移数组）。
一旦出现非整数，或者元素个数超过阈值，就会升级为 hashtable。

4.2 元素个数多 / 存在非整数：hashtable（dict）

当满足以下条件之一时，Set 会整体从 intset 升级为 hashtable：

出现了非整数元素（比如字符串）。
元素个数 > 512（默认阈值 set-max-intset-entries）。

Set 的底层 直接使用 Redis 通用的 dict（哈希表结构），和 Hash 大对象时用的 hashtable 完全一样。
区别只是：
Hash 的 dictEntry 里存 key+value；
Set 的 dictEntry 里只存 key，value 固定是 NULL。

5. Redis 的高性能原因

Redis 之所以能够实现极高的性能，主要得益于它的单线程模型和Reactor 模式，再加上 I/O 多路复用的技术，使 Redis 能够在一个线程中处理大量并发请求。这一节将深入讲解 Redis 的设计理念和技术实现。

5.1 Redis 的高性能来源

Redis 的高性能主要来自以下几个方面：

纯内存操作：Redis 将数据存储在内存中，避免了传统数据库中慢速的磁盘读写操作，使得数据读写速度极快。
单线程模型：Redis 使用单线程处理请求，避免了多线程模型中的锁竞争和线程上下文切换的开销。
I/O 多路复用（Reactor 事件循环）：它用 epoll 等多路复用机制，让一个线程同时监听成千上万连接，而不是一个连接一个线程。主线程是一个事件循环（Reactor），只在连接有读写事件时被唤醒，然后顺序执行命令并写回结果。

5.2 I/O 多路复用（Reactor 事件循环）

I/O 多路复用
- 在操作系统层面使用 epoll（Linux），把所有客户端连接注册到一个等待列表。
- 一个线程调用 epoll_wait 就能一次性知道哪些连接“就绪”（有数据可读/可写）。
- 避免了传统“一连接一线程”的模式，大大减少了线程开销。
Reactor 事件循环
- Redis 主线程是一个事件循环。
- 一旦某些连接就绪（有数据可读/可写），epoll 会一次性把这些事件返回。
- Redis 就顺序处理这些事件：读数据 → 执行命令（内存操作，极快） → 写回结果。
优势
- 单线程执行命令 → 不存在锁竞争，数据结构操作简单高效；
- 事件驱动 → 只在有事件时工作，没有事件就休眠，不浪费 CPU；
- 一次唤醒可处理一批事件，减少系统调用和上下文切换。