Redis 原理篇

原理篇-01.Redis原理篇课程介绍_哔哩哔哩_bilibili

0. 准备

redis 源码：redis 安装包下 src 目录里

1. 数据结构

1.1 动态字符串SDS

Redis 是基于 C 语言实现的，但没有直接使用 C 语言的字符串(底层是字符数组)，C 语言的字符串存在很多问题：
- 获取字符串长度需要通过运算(字符串数组以 \0 结尾)
- 非二进制安全(不能包含特殊字符)
- 不可修改(拼接字符串要申请内存空间)
Redis 创建了一种新的字符串结构，称为简单动态字符串SDS(Simple Dynamic String)
- SDS 本质是一个结构体，底层字符数组 char[] 由SDS自己管理
- 头：头中记录当前字符串的长度等信息，便于读取
- 体：真实存储字符串的char[]
源码： sds.h => 支持多种长度字符串

SDS 支持动态扩容：

优点：
- 二进制安全的：读取数据的时候不是像C中以 /0 为结束标识，而是按照长度，长度是几就读几个
SDS 因为是字节存储，所以也可以存音频，视频等(但不推荐，Redis 是基于内存的，存音频视频浪费空间)

1.2 IntSet

IntSet 是 Redis 中 set 集合的一种实现方式，基于整数数组实现(在C语言上进一步的封装)，具备长度可变、有序等特征
- 对数组的增删改查都由 IntSet 来维护

在这个数组中，每个元素的大小都是固定的，方便寻址，将来查找时就可以通过第一个元素的内存地址，再根据距离和一个元素的大小，可以通过数学表达式直接快速寻址

IntSet 升级：当 encoding 原先的每个数组大小规定为2个字节，但是现在要存储4个字节的元素，这时候就会进行升级操作：自动升级编码方式(encoding)到合适的大小
- 倒序依次将数组元素拷贝到扩容后的正确位置，如元素20，计算下标为2，每个元素变4个字节，2*4=8，其起始位置变为8
- 再把待添加的元素放入数组末尾
- 最后修改 inset 的 encoding 和 length 的属性值

源码：inset.c

总结：可以看做特殊的整数数组
- 底层采用二分查找查询
- IntSet 就是一个有序的，元素唯一的(Set集合)，长度可变的数组，只不过自己实现了升级、扩容等一些动作(具备类型升级机制,节省内存空间)
- 适合于存储一些少量的数据，因为数据量太多不方便分配一些连续的内存，数组的内存地址都是连续的

1.3 Dict

Redis 是键值型数据库，键值的映射关系通过 Dict 实现

全局哈希表和哈希节点关系：添加时链表使用头插法

把一个键分配到哈希表中的某个槽位时，最常用的方式是取余操作：index = hash(key) % N;
在 Redis 中，哈希表的大小 N 通常是 2 的幂次方，可以使用位运算（&）来代替取余操作，位运算比除法操作快得多，对于哈希表大小为 2^k，可以通过以下方法计算索引：index = hash(key) & (N - 1);
其中 N 是哈希表的大小。因为 N 是 2 的幂次方，N - 1 就是一个二进制的全 1 数字，& (N - 1) 的作用是将哈希值的低 k 位直接截取下来作为索引，相当于取余操作的结果

# 举例
假设一个哈希表大小 N = 16，即 2^4 = 16。现在有一个哈希值 hash(key) = 35，想要确定它应该放在哪个槽位

# 传统取余法：
index = 35 % 16;  # 结果是 35 % 16 = 3

# 使用 & 运算：
index = 35 & (16 - 1);  # 16 - 1 = 15，二进制是 1111
index = 35 & 15;  
# 35 的二进制是 100011，15 的二进制是 1111 
# 100011 & 1111 = 0011，结果是 3

# 两个结果都是 3，但是 & 运算比 % 更高效

字典的结构体：
- 字典中默认有2个全局哈希表
- 空的哈希表一般是 rehash 时使用 => 因为扩容/收缩必定会创建新的哈希表，需要对哈希表中每个key重新计算索引

Dict 的扩容：每次添加元素，都会检查是否需要扩容
- 触发全局哈希表扩容的时机？=> 负载因子(used/size)
  - 哈希表的负载因子 >= 1，且并没有执行bgsave等后台进程(会占用较多CPU,可能会影响rehash的进程)
  - 哈希表的负载因子 > 5
- 扩容出来的倍数一定是 2^n
Dict 的收缩：每次删除元素，都会检查是否需要收缩
- 触发全局哈希表收缩的时机？
  - 当负载因子 < 0.1时，会对哈希表进行收缩
Dict 的 rehash：扩容/收缩对哈希表中每个key重新计算索引
- Redis 字典使用**两个哈希表：ht[0] 和 ht[1]**。平时所有的操作都只针对 ht[0] 进行。当哈希表的装载因子超过预设阈值（可以是扩容或缩容触发），rehash 过程就会启动
- 这个过程包括将 ht[0] 的内容逐渐迁移到 ht[1] 中，并在迁移完成后，将 ht[1] 变成新的 ht[0]，然后重新分配一个新的 ht[1] 准备下一次的 rehash
- 避免数据量大的情况下一次性rehash可能导致的主线程阻塞，rehash 的过程是分多次、渐进式的，称为 渐进式rehash

总结：

1.4 ZipList

ZipList 压缩列表是为了节省内存而设计的数据结构，内存空间是连续的，可以方便的在任意一端进行压入/弹出操作

ZipListEntry 的结构：

ZipList 的连锁更新问题：增/删较大数据时可能会发生(发生概率低)，会频繁产生内存的申请和销毁，涉及内核态的切换，影响性能

总结：Redis 从版本 6.0 开始，将 ZipList 数据结构替换为了 ListPack，仍然是一个紧凑的、序列化的数据结构，用于存储小型列表和哈希集合，但是在内部处理和存储机制上进行了优化，以减少内存碎片和连锁更新的情况

1.5 QuickList

ZipList 的问题：
- ZipList 必须申请连续内存空间，如果内存占用过多，申请内存效率很低怎么办？ => 限制 ZipList 的长度和 Entry 大小
- 如果还是要存储大量数据，超出 ZipList 上限怎么办？ => 创建多个 ZipList 来分片存储数据，分别去申请独立的连续内存空间
- 分片后如何进行关联以便查找？ => 链表
QuickList 压缩列表，底层是 LinkedList + ZipList，本质是双端链表，但每个节点都关联了一个 ZipList，兼具了链表和 ZipList 优点

总结：

1.6 SkipList-重点

ZipList 和 QuickList 查找首尾元素性能高，但是从中间随机查询性能就一般，可以使用 SkipList 跳表
- 通过多级指针提高查询效率，根据socre来做排序，要保证有序性

总结：

1.7 RedisObject

SDS(简单动态字符串) 、IntSet(整型数组) Dict(字典[哈希表])、ZipList(压缩列表)、QuickList(双端链表)、SkipList(跳表)
- 最终都是作为 value 底层存储的数据结构，而存在形式又会被封装为一个 RedisObject (Redis 对象)的类型
- RedisObject 是 Redis 内部用于管理所有键值对的结构体。每一个键或值都被封装为一个 RedisObject
  - RedisObject 是 Redis 中存储数据的基本抽象，每个键或值都由 RedisObject 表示
  - Type：RedisObject 的 type 字段标识了该对象的类型（如 String、List、Hash 等）
  - Encoding：RedisObject 的 encoding 字段表示该数据类型的具体底层存储方式（如 raw、ziplist、skiplist 等）
  - Ptr：实际的数据存储在 RedisObject 的 ptr 字段中，指向的是相应的底层数据结构。

Redis 的编码方式：encoding 字段

redis会根据存储数据的类型不同，选择不同的编码方式
- 每一种 Redis 的高层数据类型，都可能对应不同的底层数据结构
- Redis 会根据数据的规模、访问模式等动态选择不同的数据结构来优化性能和内存使用

举例：键值均为字符串

1.8 五种数据类型

1.8.1 String

String 类型的基本编码方式是 RAW，基于SDS(简单动态字符串)实现，存储上限为 512MB，会根据SDS长度来决定采用什么编码方式
- 如果存储的 SDS 长度小于 44 字节，会使用 EMBSTR 编码，其 Object Head 和 SDS 是一段连续空间，申请内存只要调用一次函数，效率更高
- 如果存储的字符串是整数值，并且大小在 LONG_MAX 内，会采用 INT 编码，直接将数据保存在 RedisObject 的指针位置

1.8.2 List

Redis 的 List 可以从首、尾操作列表中的元素，元素按照插入时的顺序进行存储
数据结构的选择：
- LinkedList：普通链表，内存占用较高，内存碎片较多
- ZipList：压缩列表，内存占用低，存储上限低
- QuickList：快表，底层是 LinkedList + ZipList，内存占用较低，包含多个 ZipList，存储上限高

1.8.3 Set

Set 是单列集合：
- 无序
- 不可重复(可以判断元素是否存在)
- 可求交集、并集、差集
数据结构的选择：（对查询元素的效率要求高）
- 哈希表 ht，也就是 Redis 中的字典 Dict（存key，value统一为null）
  - 类似 Java 的 HashSet
  - 但是内存占用多
- IntSet 整数数组

1.8.4 ZSet

Zset 也就是 SortedSet，每个元素都要指定一个 score 值和 member 值（可以看作 member 是键，score 是值）
- 可以根据 score 值排序
- member 必须唯一
- 可以根据 member 查询分数

数据结构的选择：满足键值存储，键必须唯一，可排序
- SkipList：可排序，并且可以同时存储score和ele值(member)，但是只能根据 score 进行高效查询
- HT（Dict）：可以键值存储，也可以根据 key 找 value，但无法排序
- 初始化时会判断，初始方案是zipList，最终方案是SkipList + 哈希表
实现方式一：SkipList + Dict 跳表+哈希表 => 性能好但太占内存
- 利用Dict(哈希表)实现键唯一键值存储
- 利用SkipList(跳表)实现有序性

实现方式二：当元素数量不多时采用 ZipList 来存储，节省空间
- 需满足以下两个条件
  - 元素个数不超过 128
  - 元素大小不超过 64 字节
- ZipList 实现 Zset 的”键值存储””键唯一””支持有序”通过编码结合业务逻辑来实现

1.8.5 Hash

Hash 结构与 ZSet 类似，都是键值存储、需要根据键获取值、键唯一
- 区别在于 ZSet 的值是 score(数字)，而Hash对键值类型任意，并且 Hash 不需要排序(所以底层结构参考 ZSet 并删掉和排序相关的跳表即可)
Hash 特点：
- 键值存储
- 键唯一
- 无序

数据结构选择：
- 数据量较少的话，使用ZipList编码
- 数据量较大时，会采用哈希表HT编码(Dict)
- 触发条件：
  - 元素数量超过512
  - 元素大小超过64字节

1.9 总结

时间复杂度
- O(1): 哈希表
- O(logN): SkipList
- O(n): InteSet ZipList QuickList
- 注意: ZipList操作列表头部和尾部时的时间复杂度为O(1),头信息中记录了尾偏移量等信息

2. 网络模型

2.1 用户空间和内核空间

**用户态 (User Mode)**：
- 运行应用程序的环境
- 只能执行非特权指令，对硬件资源的访问受限
- 需要执行特权操作（如I/O操作、进程管理等）时，必须通过系统调用切换到内核态
**内核态 (Kernel Mode)**：
- 操作系统核心运行的模式
- 可执行特权指令，管理硬件资源和执行系统级操作
- 提供系统调用接口（System Call Interface），允许用户态程序请求内核执行任务
地址空间:
- 用户空间和内核空间在内存中占据不同的区域，通常内核空间位于高地址，用户空间位于低地址
- 内核空间直接映射到物理内存，提供高效的内存访问
在操作系统中处理I/O操作尤其是文件和网络I/O时，涉及多个步骤，每个步骤都有潜在的性能影响，特别是在高负载或大量数据传输时
- 用户空间到内核空间的切换：每次进行系统调用，如读写文件或网络数据时，需要从用户态切换到内核态，这种模式切换涉及保存和加载寄存器，栈的切换等操作，消耗CPU资源
- 数据复制：数据需要在用户空间和内核空间之间复制，例如，从用户缓冲区到内核缓冲区（或反之），数据复制会占用CPU周期，并可能导致缓存失效，影响其他进程的性能
- 等待设备I/O：设备I/O通常是操作系统中最慢的操作之一，尤其是磁盘和网络I/O；在等待数据从设备加载（如硬盘读取或网络数据接收）期间，进程可能会被阻塞，增加响应时间

2.2 Linux 五种 IO 模型

IO 读取数据：流程简化为两个主要阶段：等待数据就绪和读取数据

2.2.1 阻塞 IO

等待数据就绪和读取数据这两个阶段都需要阻塞等待
- 系统调用时，应用程序从用户态切换到内核态
- 如果数据未就绪，系统会让当前线程阻塞，直至数据准备完毕，整个等待过程中线程无法执行其他任务
- 由于阻塞等待，当前线程会闲置，无法做其他工作，这会导致线程资源浪费
- 在单线程程序中，I/O阻塞会阻止线程处理后续任务，严重影响整体性能

2.2.2 非阻塞 IO

等待数据阶段是非阻塞的，数据拷贝阶段依然阻塞：
- 应用程序发起 I/O 操作时，无论数据是否到达或事件是否就绪，系统调用都会立即返回，不会阻塞线程
  - 虽然线程不会被阻塞，但应用程序需要不断向内核询问数据是否就绪，这种循环询问（轮询）称为“盲等”
  - 每次轮询都涉及从用户态切换到内核态，并返回用户态，频繁的态切换增加了系统开销，但大量的态切换和无效的 CPU 占用，导致性能并不理想
- 当数据准备好后，内核将数据从内核空间拷贝到用户空间，这一过程依然是阻塞的，因为数据拷贝时需要保证一致性

2.2.3 IO 多路复用

阻塞 I/O 和 非阻塞 I/O 在单线程情况下都存在效率问题：
- 阻塞 I/O：线程在等待数据到达时被阻塞，不能执行其他任务
- 非阻塞 I/O：虽然线程不被阻塞，但会不断轮询检查数据是否就绪，造成CPU的空转，浪费资源
I/O 多路复用解决了单线程处理多个 I/O 事件时的低效问题
- 通过一个线程配合**selector(选择器)**来监听多个文件描述符fd
- 当某个文件描述符有数据到达或事件就绪时，selector 会通知线程进行处理，提升 CPU 的利用效率

工作原理：
- **文件描述符 (fd)**：每个文件描述符代表一个 I/O 资源（如 socket、文件），I/O 多路复用通过监听这些描述符来判断它们的状态（可读、可写、出错等）
- Selector（选择器）：
  - 应用程序将多个文件描述符注册到 selector，selector 负责监听这些文件描述符的状态
  - 当有数据到达或者事件就绪时，selector 会通知线程处理该事件
  - 好处是避免了线程轮询所有描述符的状态，只有当真正有数据时，线程才会被唤醒处理

根据监听文件描述符通知的方式不同，主要有三种实现：前两者只会通知用户进程有fd就绪，并不确定是哪个，需要用户进程遍历fd确定，最后一个 epoll 在通知用户进程fd就绪时会把fd写入用户空间
- select
- poll
- epoll

select

select 是 Linux 中最早的I/O多路复用的实现方案，监听的事件类型：
- 可读事件
- 可写事件
- 异常事件

执行流程：fd集合在保存fd时是按照比特位保存的，每一个比特位代表一个fd，下边以8个比特位为例（实际源码里是1024个比特位）
- 调用select()函数会将监听的FD集合拷贝到内核空间，后续有事件就绪还会将FD集合拷贝回用户空间，不过依旧需要轮询的方式来查找就绪事件

缺点：
- 监听FD的数量有限
- 每次调用select函数,都需要将监听的FD集合拷贝到内核空间,如果很多的话,拷贝很费性能(epoll_ctl只调用一次,剩余都epoll_await)
- 监听的事件就绪时,要采用轮询方式来查找,效率很低!(epoll_await只返回已经就绪的事件,不会全都返回)

poll

poll 模式对 select 模式做了简单改进，仅仅解决了监听的FD集合数量有限的问题
- 内核空间将拷贝的 pollfd 数组转链表存储，理论上无上限
- 性能提升并不明显，也是每次poll()时会将FD集合从内核空间拷贝到用户空间，会有多次的拷贝的过程

epoll

epoll 模式是对 select 和 poll 的改进，提供了三个函数：
- epoll_create：负责在内核空间中创建eventpool的实例，一个eventpool维护了
  - 一个红黑树(记录要监听的FD) [未就绪时在这里]
  - 一个链表(记录已经就绪的FD) [就绪了之后就在这里]
- epoll_ctl：将要监听的FD拷贝到内核态的 eventpoll 的实例中，并为每一个要监听的FD设置一个callback()函数
  - 当事件就绪时会将红黑树中的该FD放到就绪的FD的链表中去，表示当前事件已经就绪
  - 注意这里只有一次FD的拷贝，区别于select和poll每次的拷贝
- epoll_await：内核会检查eventpool中维护的就绪链表(维护了已经就绪的FD)是否为空，不为空则返回就绪的FD的数量

epoll 解决的问题：
- 解决了监听的FD数量的限制：通过红黑树的数据结构来管理文件描述符，支持大量的并发连接
- FD 拷贝和调用过程优化：
  - select 和 poll 每次调用时，都会将监听的所有文件描述符从用户空间拷贝到内核空间，并在内核中轮询是否有 I/O 就绪事件。这导致了大量的内核态和用户态切换，浪费系统资源
  - epoll 优化了这一过程：
    - 通过 epoll_ctl() 将文件描述符添加到内核的红黑树中，这个操作只在监听的文件描述符发生变化时进行，比如注册、删除或修改监听的 FD，这意味着文件描述符只需要拷贝一次
    - 当事件发生时，epoll 通过回调机制(callback函数)将事件加入到就绪链表中
    - 后续只要不断调用epoll_wait() 只处理链表上就绪的文件描述符，不需重复的将要监听的FD从用户空间拷贝到内核空间
- 减少内核和用户空间之间的拷贝：
  - select 和 poll 在每次 I/O 事件发生时，会将所有的文件描述符集合（无论是否就绪）从内核空间拷贝回用户空间，应用程序再遍历这个集合来查找哪些文件描述符是就绪的，带来了额外的性能开销
  - epoll 只将已经就绪的文件描述符拷贝回用户空间，这减少了无效的拷贝和无效的轮询操作
**epoll 的ET和LT模式(事件通知机制)**：
- 调用epoll_await()时如果有可读/可写的事件就绪了，就会得到事件的通知告诉你有事件就绪了，但事件通知的方式分为两种：
  - LT(水平触发)：当FD有数据可读时,会重复通知多次,直到数据处理完成. 且是默认方式
  - ET(边缘触发)：只会在FD从不可读变成可读时通知一次,不管数据是否处理完.如果没有处理完,后面不会再返回未处理完的事件了
- 每次调用epoll_await()时，如果就绪链表中有就绪的事件，会看当前时LT还是ET，如果是ET则会直接将链表的指针断开，后续就没有该就绪FD了；如果是LT则不会断开，下次依旧可以返回上次未处理完的FD
- LT的缺陷：
  - 因为需要不断的epoll_await(),需要多次重复通知,所以性能上会有一定消耗
  - 会有”惊群现象”，多个进程同时在监听一个FD，当FD就绪后,会导致所有的进程都会被通知到

基于 epoll 的服务端流程：
- epoll_create 用于创建一个 epoll 实例
- epoll_ctl 用来操作 epoll 实例的内部监视列表，这里用它将 server socket (负责监听来自客户端连接的 socket) 注册到 epoll 实例上
- epoll_wait 被用来等待注册的文件描述符上的事件，例如有新的连接尝试，或者一个已连接的 socket 有数据可读，当 epoll_wait 检测到事件后，会返回这些事件的列表
- 对于新的连接，使用 accept 接收并创建一个新的 socket；对于数据接收，从 socket 读取数据

2.2.4 信号驱动 IO

使用信号（signal）来通知应用程序何时可以开始非阻塞地执行IO操作，当内核有FD就绪时会发出SIGIO信号通知用户，期间用户可以执行其他业务，无需阻塞等待(相比非阻塞IO，这里真正实现非阻塞)
- 缺点：当大量IO操作，信号队列可能溢出，而且内核和用户空间的频繁信号交互性能也较低

2.2.5 异步 IO

等待数据就绪和读取数据两个过程都是非阻塞的，等到内核中数据就绪并拷贝到用户空间后才递交信号通知用户进程
- 缺点：用户进程不阻塞就又会处理新的用户请求，高并发情况下容易导致内核积累过多IO读写任务，需要编码做好限流工作，代码实现复杂度高

2.2.6 对比总结

使用较多的还是IO多路复用，少数情况下也会使用异步IO

同步IO VS 异步IO：同步和异步的区别关键在于内核与用户空间的数据拷贝过程是阻塞还是非阻塞的(所以即使是阻塞IO，本质还是同步的)

2.7 Redis 网络模型

2.7.1 问题辨析

Redis 是单线程还是多线程？
- 如果只是针对一些核心业务部分(命令处理)，对数据的访问、操作等都是单线程，且结合多路复用的IO模型，此情况下是单线程
- 但是对于整个redis而言是多线程，比如持久化时并不会由主进程来完成，而是fork一个子进程来完成操作
Redis 为什么要选择单线程？
- redis 是纯内存操作，内存的执行速度是非常快，redis 的性能瓶颈从来都不是执行速度而是网络延迟，所以即使加入了多线程其实也不会有更多的提升
- 多线程会导致大量的上下文切换，带来不必要开销
- 多线程间需要有合理的系统架构来控制多线程间的协调性，否则一味的线程多甚至效率更低，并且多线程下还有进行共享数据的并发访问控制，提高了很多复杂度

2.7.2 IO多路复用和事件派发机制

Redis 网络模型基于多路复用IO来提升网络性能，并且支持多种不同的多路复用实现都进行了封装，提供统一的API库AE
整体来看Redis的网络模型就是基于**”IO多路复用 + 事件派发机制”**
- 客户端请求来了之后做多路复用的事件监听，无论是什么类型的事件，提前定义好各种各样的事件处理器，对于不同的事件就派发给不同的事件处理器来处理
- 在单线程模型下，性能瓶颈存在于网络IO => 命令解析和响应结果的输出 => 多线程改进

3. 通信协议

3.1 RESP 协议

Redis 是 CS 架构，通信一般分为两步(不包括pipeline和pubsub)

Redis 采用的是 RESP(Redis Serialization Protocol) 协议，Redis6出的 RESP3 和之前的 RESP2 不太兼容，所以默认使用的还是 RESP2，以下学习中使用 RESP2 举例
数据类型：RESP 中，通过首字母的字符来区分不同的数据类型
- 单行字符串：首字节为 +，不允许出现特殊字符，如 \r\n => 二进制不安全，常用于服务端的返回响应
- **错误(Errors)**：首字节为 -，常用于服务端的返回响应，类似单行字符串，只是内容是异常信息
- 数值：首字节为 :，数字格式的字符串
- 多行字符串：首字节为 $，二进制安全(底层记录了字符串占用字节大小)，最大支持 512MB
- 数组：首字节为 *，后面跟上数组元素个数，再跟上元素，元素类型不限，一般客户端用数组发请求

4. 内存策略

4.1 内存过期策略

4.1.1 DB 结构

Redis 如何知道一个 key 是否过期：一个库中有专门的一个Dict字典来保存key和TTL(过期时间)的映射

是不是TTL到期就立刻删除了？
- 不一定，取决于过期策略

4.1.2 删除策略

**惰性删除(单个删除)**：访问一个key的时候会检查是否过期，如果过期了再删除（用到的时候才删除）
- 问题：如果过期的key就再也没有人访问了呢？ => 周期删除
**周期删除(批量删除)**：通过一个定时任务[针对所有key的]，周期性的抽样部分的key，然后删除过期的key（最终确保所有Dict中的数据都会被抽到），执行周期有两种：
- SLOW模式: 低频高时长的清理
  - 执行频率默认为10，每次不超过25ms
- FAST模式: 高频低时长的清理
  - 执行频率不固定，但两次间隔不低于2ms，每次耗时不超过1ms
  - FAST 策略会减少对主线程的影响，因为每次执行非常快