Redis 底层原理

Redis 的底层原理

Redis 底层数据结构

动态字符串SDS

Redis 没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

• 获取字符串长度需要通过运算
• 非二进制安全（如果在字符数组中中间有个元素为\0，那么C语言会认为到了字符串末尾）
• 不可修改

故Redis 构建了一种新的字符串结构，称为简单动态字符串，简称SDS。

SDS 的本质是一个结构体：

在这里插入图片描述

例如一个包含字符串“name” 的sds 结构如下：

在这里插入图片描述

它是根据len去读取字符串的。

SDS具备动态扩容的能力，如果要给 SDS 追加一段字符串，首先先会申请新内存空间；

• 若新字符串小于1M，则新空间为扩展后字符串长度的两倍 + 1；（+1是为了融合C语言中的字符串末尾标识\0）
• 若新字符串大于1M，则新空间为扩展后字符串长度 + 1M + 1.称为内存预分配

当我们申请内存的时候应用程序无法操作硬件，跟内核进行交互，从用户态切换为内核态，申请内存这个动作非常消耗资源。故Redis提供了内存预分配，从而提高性能。

SDS的优点：

• 获取字符串长度的时间复杂度为O(1)
• 支持动态扩容
• 减少内存分配次数
• 二进制安全

IntSet

IntSet 是 Redis 中 set 集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征

结构如下：

在这里插入图片描述

其中的 encoding 包含三种模式，表示存储的整数大小不同：

在这里插入图片描述

contents[] 数组就相当于一个指针，指向数组第一个元素的位置。

为了方便查找，Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中，结构如下：

在这里插入图片描述

现在数组中的每个数字都在 int16_t 的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小位：

• encoding：4字节
• length：4字节
• contents：2字节 * 3

IntSet 升级

假如有一个intset，元素为 [5，10，20]，采用的是 INTSET_ENC_INT16，则每个整数占2字节；

在这里插入图片描述

我们向其中添加一个数字：50000，这个数字超出了 int16_t的范围，intset 会自动升级编码方式到合适的大小。

在这里插入图片描述

• 升级编码为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组
• 倒序依次将数组中的元素拷贝到扩容后的正确位置（如果正序的话，以前2个字节，现在4个字节，就会把第二个数字覆盖）
• 将待添加的元素放入数组末尾
• 最后将intset 的 encoding 属性改为 INTSET_ENC_INT32，将length 属性改为4

在这里插入图片描述

IntSet 可以看做是特殊的整数数组，具备一些特点：

1、Redis 会确保 IntSet 中的元素唯一、有序

2、具备类型升级机制，可以节省内存空间

3、底层采用二分查找方式来查询

总的来说就是如果数据量不是很大用intset合适，若数据量特别大，则intset效率会低

Dict

Redis 是一个键值型（Key-Value）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict 来实现的。

Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

在这里插入图片描述

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-flATOqlf-1665103614986)(E:/Typora%E7%AC%94%E8%AE%B0%E5%9B%BE%E7%89%87/image-20220704154557844.png)]

当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。

size - 1 才能确保低位全是1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UcMfMNjf-1665103614987)(E:/Typora%E7%AC%94%E8%AE%B0%E5%9B%BE%E7%89%87/image-20220704154340783.png)]

它添加元素的时候使用的是头插法。

字典的基本结构如图：

在这里插入图片描述

Dict的扩容

Dict 中的 HashTable 就是数组结合单链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict 在每次新增键值对时都会检查负载因子（LoadFactor = used/size），满足以下两种情况之一时会触发哈希表扩容：

• 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程
• 哈希表的 LoadFactor > 5;

在这里插入图片描述

Dict 的收缩

当每次删除元素的时候，也会对负载因子做检查，当LoadFactor < 0.1 时，会做哈希表收缩；

在这里插入图片描述

Dict 的 rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size 和 sizemask 变化，而key 的查询与 sizemask 有关，因此必须对哈希表中的每一个 key 重新计算索引，插入新的哈希表，这个过程称为 rehash。

Dict 的 rehash 并不是一次性完成的，如果 Dict 中包含数百万的 entry，要在一次 rehash 完成，极有可能导致主线程阻塞，因此 Dict 的 rehash 是多分次、渐进式的完成，因此称为渐进式 rehash。

1、计算新 hash 表的realeSize，值取决于当前要做的是扩容还是收缩：

• 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1 的 2^n
• 如果是收缩，则新size 为第一个大于等于dict.ht[0].used 的 2^n（不得小于4）

2、按照新的realeSize 申请内存空间，创建dictht，并赋值给dict.ht[1]

3、设置dict.rehashidx = 0，表示开始rehash

4、每次执行增删改查操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry 链表 rehash 到 dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash 到 dict.ht[1]

5、将dict.ht[1]赋值给 dict.ht[0]，给dict.ht[1] 初始化为空哈希表，释放原来的dict.ht[0] 的内存

6、将 rehashidx 赋值为 -1，代表 rehash 结束

7、在 rehash 过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在 dict.ht[0] 和 dict.ht[1] 依次查找并执行。这样可以确保 ht[0] 的数据只减不增，随着rehash 最终为空

ZipList（压缩链表）

ZipList 是一种特殊的 “双端链表”，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作，并且读操作的时间复杂度为O(1).

在这里插入图片描述

在这里插入图片描述

entry 长度不固定是为了节省内存，如果比如是固定8字节的话，如果有些entry只占一个字节，就会浪费内存。

ZipListEntry

ZipList 中的Entry 并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用以下结构：

在这里插入图片描述

• previous_entry_length：前一个节点的长度，占1个或5个字节
  • 如果前一个节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一个节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
• encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
• content：负责保存节点的数据，可以是字符串或整数

注：ZipList 中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412

Encoding

ZipListEntry 中的encoding 编码分为字符串和整数两种：

它是用两个二进制位来标识是字符串还是整数

字符串：如果encoding 是以 “00”、“01” 或者 “10” 开头，则证明content是字符串

在这里插入图片描述

例如我们要保存字符串：“ab” 和 “bc”

存储“ab”时

在这里插入图片描述

最后整个ZipList的结构如下：

在这里插入图片描述

整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节

在这里插入图片描述

例如，一个ZipList 中包含两个整数值：“2” 和 “5”

在这里插入图片描述

最后整个ZipList的结构如下：

在这里插入图片描述

ZipList各种各样的编码，最终的目的就是节省内存，它的使用限制是：在遍历时，只能从前遍历或者从后遍历，如果有很多节点，刚好要遍历的那个节点在中间，则效率就很低，所以ZipList在使用时对节点数量有限制

ZipList 的连锁更新问题

ZipList 的每个 Entry 都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：

• 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
• 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

假设我们有N个连续的、长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节即可表示，如图：

在这里插入图片描述

这时有一个新的entry要插入队首，并且这个entry的大小为254，故记录的时候要用5个字节记录，它原本是250字节，现在增加了4个字节，导致超出了254，后面的那些entry要记录你的长度，故后面的长度也变为254，后面的后面也是如此。

在这里插入图片描述

ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新。新增、删除都可能导致连锁更新的发生。连续更新问题会导致内存申请、销毁、数据迁移，对性能影响非常大

这种问题发生的概率极低，因为这个问题发生的条件是有N个连续的、长度为250~253字节之间的entry。目前这个问题 Redis 作者没有解决。新版的Redis作者引入了一个新的数据结构叫 ListPack（紧凑列表），只是在Stream结构底层使用了，并没有用到常见的数据结构，可能是因为改动太大，并没有修改它。

QuickList

ZipList 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请效率低。该如何做？ 我们必须限制ZipList的长度和entry的大小

我们要存储大量数据，超出了ZipList最佳的上限该怎么办？

可以创建多个 ZipList 来分片存储数据

数据拆分后比较分散，不方便管理和查找，多个 ZipList 如何建立联系

Redis 在3.2 版本引入了新的数据结构 QuickList，它是一个双端链表，只不过链表中的每个节点都是一个 ZipList。

在这里插入图片描述

为了避免 QuickList 中的每个 ZipList中的entry 过多，Reids 提供了一个配置项：list-max-ziplist-size 来限制

1、如果值为正，则代表 ZipList 的允许的entry个数的最大值

2、如果值为负，则代表 ZipList 的最大内存的大小，分5种情况

• -1：每个ZipList 的内存占用不能超过4kb
• -2：每个ZipList 的内存占用不能超过8kb
• -3：每个ZipList 的内存占用不能超过16kb
• -4：每个ZipList 的内存占用不能超过32kb
• -5：每个ZipList 的内存占用不能超过64kb

其默认值为 -2

除了控制 ZipList 的大小，QuickList 还可以对节点的 ZipList 做压缩。通过配置项 list-compress-depth 来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：

• 0：特殊值，代表不压缩
• 1：标示 QuickList 的首尾各有1个节点不压缩，中间节点压缩
• 2：标示 QuickList 的首尾各有2个节点不压缩，中间节点压缩
• 以此类推

默认值是 0。

QuickList 结构

在这里插入图片描述

QuickList 的特点：（结合了链表和 ZipList 的优点）

• 是一个节点为 ZipList 的双端链表
• 节点采用 ZipList，解决了传统链表的内存占用问题
• 控制了 ZipList 大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存

SkipList（跳表）

SkipList 首先是链表，但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同

在这里插入图片描述

跳表允许存储的元素量可以很大，并且查询性能也高

在这里插入图片描述

SkipList 结构：

在这里插入图片描述

SkipList 的特点：

• 跳跃表是一个双向链表，每个节点都包含 score 和 ele 值
• 节点按照 score 值排序，score值一样则按照 ele 字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单。

RedisObject

Redis 中的任意数据类型的键和值都会被封装为一个 RedisObject，也叫做 Redis对象

在这里插入图片描述

Redis 的编码方式

Redis 中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型

在这里插入图片描述

Redis 中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

在这里插入图片描述

Redis 五种数据类型

String

String 是 Redis 中最常见的数据存储类型

其基本编码方式 RAW，基于简单动态字符串（SDS）实现，存储上限为512mb

在这里插入图片描述

如果存储的SDS长度小于44字节，则会采用 EMBSTR 编码，此时 object head 与 SDS 是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高

选 44 字节的原因：

SDS 头占了3字节，尾占了1字节，合在一起就是48字节，再加上RedisObject 的头是16字节，总共64字节。64字节的特殊之处就是和Redis内存分配有关。Redis 内存分配算法在分配内存时，会以2的n次方去分配内存。64恰好是一个分片大小，故不会产生内存碎片，推荐使用String时尽可能不要让字符串超过44字节。

在这里插入图片描述

如果存储的字符串是整数值，并且大小在 LONG_MAX 范围内，则会采用INT 编码：直接将数据保存在 RedisObject 的 ptr 位置（刚好8字节），不再需要SDS了

在这里插入图片描述

List

Redis 的 List 结构类似一个双向链表，可以从首、尾操作列表中的元素：

• 在3.2版本之前，Redis 采用 ZipList 和 LinkedList 来实现 List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList 编码
• 在3.2版本后，Redis 统一采用 QuickList 来实现 List

在这里插入图片描述

在这里插入图片描述

List 的结构：

在这里插入图片描述

Set

Set 是 Redis 中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。

• 为了查询效率和唯一性，set 采用 HT 编码（Dict）。Dict 中的 key 用来存储元素，value 统一为 null。
• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set 会采用 IntSet 编码，以节省内存。

部分源码：

在这里插入图片描述

判断是否要切换编码方式

在这里插入图片描述

Set 的结构：

刚开始是IntSet 编码：

在这里插入图片描述

当插入元素：sadd s1 m1时：

在这里插入图片描述

ZSet

Zet也就是 SortedSet，其中每一个元素都需要指定一个score值和member值：

• 可以根据score值排序
• member必须唯一
• 可以根据member查询 score

故zset底层数据结构必须满足 键值存储、键必须唯一、可排序这几个需求。

1、SkipList：可以排序，并且可以同时存储score 和 ele值（member）

HT（Dict）：可以键值存储，并且可以根据key 找 value

在这里插入图片描述

ZSet结构图：

在这里插入图片描述

当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件： ① 元素数量小于zset_max_ziplist_entries，默认值128

② 每个元素都小于zset_max_ziplist_value字节，默认值64

ziplist 本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：

• ZipList 是连续内存，因此score和element是紧挨在一起的两个entry，element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列

在这里插入图片描述

部分源代码：

在这里插入图片描述

zetAdd 方法是真正往里面添加元素，它会再判断一下：

在这里插入图片描述

Hash

Hash 结构与Redis 中的 ZSet 非常类似：

• 都是键值存储
• 都需要根据键获取值
• 键必须唯一

区别如下：

• zset的键是 member，值是 score；hash 的键和值都是任意值
• zset 要根据score 排序；hash 则无需排序

因此，Hash 底层采用的编码与 ZSet 也基本一致，只需要把排序有关的 SkipList 去掉即可：

• Hash 结构默认采用 ZipList 编码，用以节省内存。ZipList 中相邻的两个 entry 分别保存field 和 value
• 当数据量较大时，Hash 结构会转为 HT 编码，也就是Dict，触发条件有两个：
  • ZipList 中的元素数量超过了 hash-max-ziplist-entries（默认512）
  • ZipList 中的任意entry 大小超过了 hash-max-ziplist-value（默认64字节）

在这里插入图片描述

如果触发了上面两个条件之一，就会变为：

在这里插入图片描述

部分源码：

在这里插入图片描述

在这里插入图片描述

Redis 网络模型

用户空间和内核空间

为了避免用户应用导致冲突甚至内核崩溃，用户应用与内核是分离的：

• 进程的寻址空间会划分为两部分：内核空间、用户空间
• 用户空间只能执行受限的命令（Ring3），而且不能直接调用系统资源，必须通过内核提供的接口来访问
• 内核空间可以执行特权命令（Ring0），调用一切系统资源

在这里插入图片描述

Linux 系统为了提高 IO 效率，会在用户空间和内核空间都加入缓冲区：

• 写数据时，要把用户缓冲数据拷贝到内核缓冲区，然后写入设备
• 读数据时，要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区

在这里插入图片描述

在这过程中影响效率的有：用户在等待数据时要花时间，还有数据的拷贝，比较影响效率。

阻塞 IO

阻塞 IO 就是两个阶段都必须阻塞等待：

在这里插入图片描述

在数据等待和数据拷贝阶段，用户进程都处于阻塞等待状态

非阻塞 IO

非阻塞 IO 的recvfrom 操作会立即返回结果而不是阻塞用户进程。

在非阻塞IO 模型中，用户进程在第一个阶段是非阻塞，第二个阶段是阻塞状态。虽然是非阻塞，但性能并没有得到提高。而且忙等机制会导致CPU 空转，CPU使用率暴增

在这里插入图片描述

IO 多路复用

无论是阻塞 IO 还是非阻塞 IO,用户应用在一阶段都需要调用 recvfrom 来获取数据，差别在于无数据时的处理方案：

• 如果调用 recvfrom时，恰好没有数据，阻塞 IO 会使进程阻塞，非阻塞 IO 使 CPU 空转，都不能充分发挥 CPU 的作用。
• 如果调用 recvfrom 时，恰好有数据，则用户进程可以直接进入第二阶段，读取并处理数据

比如服务端处理客户端 Socket 请求时，在单线程情况下，只能依次处理每一个 socket，如果正在处理的 socket 恰好未就绪（数据不可读或不可写），线程就会被阻塞，所有其他客户端socket 都必须等待，性能自然很差。

如果要增高效率，有两种方法：

①、增加更多的线程（多线程）开销大

②、谁的数据就绪了，用户就去读取数据（用户进程如何知道内核中数据是否就绪）

文件描述符（File Descriptor）：简称FD，是一个从0开始递增的无符号整数，用来关联linux中的一个文件。在linux中一切皆文件，例如常规文件、硬件设备、网络套接字（socket）

IO 多路复用：是利用单个线程来同时监听多个FD，并在某个FD可读、可写时得到通知，从而避免无效的等待，充分利用 CPU 资源。（复用的就是这个线程）

在这里插入图片描述

监听 FD 的方式、通知的方式又有多种实现，常见的有：

• select
• poll
• epoll

差异：

• select 和 poll 只会通知用户进程有 FD 就绪，但不确定具体是哪个FD，需要用户进程逐个遍历 FD 来确认。
• epoll 则会在通知用户进程 FD 就绪的同时，把已就绪的 FD 写入用户空间。

IO 多路复用-select

IO 多路复用-poll

IO 多路复用-epoll

信号驱动 IO

信号驱动 IO 是内核建立 SIGIO 的信号关联并设置回调，当内核有 FD 就绪时，会发出 SIGIO 信号通知用户，期间用户应用可以执行其它业务，无需阻塞等待

在这里插入图片描述

缺点：当有大量 IO 操作时，信号较多，SIGIO 处理函数不能及时处理可能导致信号队列溢出；而且内核空间与用户空间的频繁信号交互性能也较低

异步 IO

异步 IO 的整个过程都是非阻塞的，用户进程调用完异步 API 后就可以去做其它事情，内核等待数据就绪并拷贝到用户空间后才会递交信号，通知用户进程。

在这里插入图片描述

在异步 IO 模型中，用户进程在两个阶段都是非阻塞状态 。

缺点：在高并发情境下，不停的去处理请求，不停地交给内核去处理，内核中积累的IO读写的任务越来越多，因为 IO 读写的效率低，每增加一次任务，可能就有大量的内存消耗。在高并发下，很有可能导致系统因为内存占用过多导致崩溃。

如果要使用异步IO，必须做好对高并发访问的限流

Redis 网络模型

Redis 到底是单线程还是多线程？

• Redis 的核心业务部分（命令处理），是单线程
• 整个 Redis 是多线程

在 Redis 版本迭代过程中，在两个重要的时间节点上引入了多线程的支持：

• Redis v4.0：引入多线程异步处理一些耗时较长的任务，例如异步删除命令 unlink
• Redis v4.0：在核心网络模型中引入多线程，进一步提高对于多核 CPU 的利用率

为什么 Redis 要选择单线程？

• 抛开持久化，Redis 是纯内存操作，执行速度非常快，它的性能瓶颈是网络延迟而不是执行速度，因此多线程并不会带来巨大的性能提升
• 多线程会导致过多的上下文切换，带来不必要的开销
• 引入多线程会面临线程安全问题，必然要引入线程锁这样的安全手段，实现复杂度增高，而且性能也会大打折扣。

Redis 内存回收

过期策略

在 Redis 中可以通过 expire 命令给 Redis 的 key 设置TTL（存活时间）

在这里插入图片描述

当 key 的 TTL 到期以后，再次访问 name 返回的是 nil，说明这个key已经不存在了，对应的内存也得到释放。从而起到内存回收的目的。

过期策略-DB结构

Redis 本身是一个典型的 key-value 内存存储数据库，因此所有的key、value都保存在 Dict 结构中。不过在其 database 结构体中，有两个 Dict：一个用来记录 key-vlaue；另一个用来记录 key-TTL。

问题： ① Redis 是如何知道一个 key 是否过期呢？

• 利用两个 Dict 分别记录 key-value 对及 key-ttl 对

在这里插入图片描述

在这里插入图片描述

② 是不是TTL到期就立即删除了呢？

• 惰性删除
• 周期删除

过期策略-惰性删除

惰性删除：并不是在 TTL 到期后就立即删除，而是在访问一个key的时候，检查该 key 的存活时间，如果已经过期才执行删除。

部分代码：

在这里插入图片描述

存在问题：有一些key 已经过期了，但是很长很长时间都没有人来访问它们，极端情况下再也没人访问，那么这些key 永远不会被删除。

过期策略-周期删除

周期删除：是通过一个定时任务，周期性的抽样部分过期的key，然后执行删除。执行周期有两种：

• Redis 会设置一个定时任务serverCron()，按照server.hz的频率来执行过期key清理，清理模式为SLOW（低频长时间的清理，清理效果会好）
• Redis的每个事件循环前会调用beforeSleep()函数，执行过期key清理，模式为FAST（高频低时长清理）

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

SLOW模式规则：

• 执行频率受 server.hz 影响，默认是10，即每秒执行10次，每个周期执行100ms
• 执行清理耗时不超过一次执行周期的25%
• 逐个遍历db，逐个遍历db 中的 bucket，抽取20个 key 判断是否过期
• 如果没达到时间上限（25ms）并且过期 key 比例大于10%，再进行一次抽样，否则结束。

FAST模式规则（过期key 比例小于10%不执行）：

• 执行频率受 beforeSleep() 调用频率影响，但两次 FAST 模式间隔不低于2ms
• 执行清理耗时不超过1ms
• 逐个遍历db，逐个遍历db 中的 bucket，抽取20个 key 判断是否过期
• 如果没达到时间上限（1ms）并且过期 key 比例大于10%，再进行一次抽样，否则结束。

FAST 它不会对主线程造成太多的阻塞。

淘汰策略

**内存淘汰：**就是当 Redis 内存使用达到设置的阈值时，Redis 主动挑选 部分key 删除以释放更多内存的流程.

Redis 会在处理客户端命令的方法 processCommand() 中尝试做内存淘汰：

在这里插入图片描述

Redis 支持8中不同策略来选择要删除的 key：

• noeviction：不淘汰任何key，但是内存满时不允许写入新数据，默认就是这种策略。
• volatile-ttl：对设置了TTL 的key，比较key的剩余TTL值，TTL越小越先被淘汰
• allkeys-random：对全体key，随机进行淘汰。也就是直接从db->dict 中随机挑选
• volatile-random：对设置了TTL 的key，随机进行淘汰。也就是从 db->expires中随机挑选。
• allkeys-lru：对全体key，基于LRU 算法进行淘汰
• volatile-lru：对设置了 TTL的 key，基于 LRU 算法进行淘汰
• allkeys-lfu：对全体key，基于 LFU 算法进行淘汰
• volatile-lfu：对设置了TTL 的key，基于 LFU 算法进行淘汰

容易混淆的有两个：

LRU（Least Recently Used），最少最近使用。用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高。

LFU（Least Frequently Used），最少频率使用。会统计每个 key 的访问频率，值越小淘汰优先级越高。

Redis 的数据都会被封装为 RedisObject 结构：

在这里插入图片描述

LFU 的访问次数之所以叫做 逻辑访问次数，是因为并不是每次key 被访问都计数，而是通过运算：

① 生成0~1之间的随机数R

② 计算 1 / (旧次数 * lfu_log_factor + 1)，记录为P，lfu_log_factor 默认为10

③ 如果 R < P，则计数器 + 1，且最大不超过255

④ 访问次数会随着时间衰减，距离上一次访问时间每隔 lfu_decay_time 分钟(默认1)，计数器 - 1

淘汰流程图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aUGBJucF-1665103615003)(E:\Typora笔记图片\image-20220721100906139.png)]

om：对设置了TTL 的key，随机进行淘汰。也就是从 db->expires中随机挑选。

• allkeys-lru：对全体key，基于LRU 算法进行淘汰
• volatile-lru：对设置了 TTL的 key，基于 LRU 算法进行淘汰
• allkeys-lfu：对全体key，基于 LFU 算法进行淘汰
• volatile-lfu：对设置了TTL 的key，基于 LFU 算法进行淘汰

容易混淆的有两个：

LRU（Least Recently Used），最少最近使用。用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高。

LFU（Least Frequently Used），最少频率使用。会统计每个 key 的访问频率，值越小淘汰优先级越高。

Redis 的数据都会被封装为 RedisObject 结构：

[外链图片转存中…(img-SATXcXQ3-1665103615003)]

LFU 的访问次数之所以叫做 逻辑访问次数，是因为并不是每次key 被访问都计数，而是通过运算：

① 生成0~1之间的随机数R

② 计算 1 / (旧次数 * lfu_log_factor + 1)，记录为P，lfu_log_factor 默认为10

③ 如果 R < P，则计数器 + 1，且最大不超过255

④ 访问次数会随着时间衰减，距离上一次访问时间每隔 lfu_decay_time 分钟(默认1)，计数器 - 1

淘汰流程图

在这里插入图片描述