Redis 底层原理

Redis 的底层原理

Redis 底层数据结构

动态字符串SDS

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

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

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

SDS 的本质是一个结构体：

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

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

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

若新字符串小于1M，则新空间为扩展后字符串长度的两倍 1；（ 1是为了融合C语言中的字符串末尾标识）
若新字符串大于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）

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

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

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

字典的基本结构如图：

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 算法进行淘汰