qidao123.com技术社区-IT企服评测·应用市场

标题: Redis原理篇：底层数据结构，网络模型，通讯协议，内存接纳 [打印本页]

---

作者: 反转基因福娃    时间: 5 天前
标题: Redis原理篇：底层数据结构，网络模型，通讯协议，内存接纳
目录

一.Redis数据结构
1.动态字符串SDS
2.intSet
3.Dict
4.Ziplist
5.QuickList
6.SkipList
7.RedisObject
8.五种数据类型
(8.1)String
(8.2)List
(8.3)Set
(8.4)ZSet
(8.5)Hash
二.网络模型
1.用户空间和内核空间
2.阻塞IO
3.非阻塞IO
4.IO多路复用
(4.1)select
(4.2)poll
(4.3)epoll
(4.3.1)实践通知机制
(4.3.2)基于epoll的服务端流程
5.信号驱动IO
6.异步IO
7.Redis网络模型
三.通讯协议RESP
四.Redis内存接纳
1.过期key处置惩罚
2.内存镌汰策略

---

一.Redis数据结构

1.动态字符串SDS

--Redis中保存的key是字符串，value是字符串或字符串的聚集。所以字符串是Redis中最常用的一种数据结构。
--Redis没有直接使用C语言中的字符串，因为C语言获取字符串长度须要通过遍历运算，且以\0作为结束符导致字符串中出现\0会导致不安全，且字符串一旦创建无法修改，如下图：

--Redis构建了新的字符串结构，成为简单动态字符串，简称SDS。SDS是一个结构体，差别SDS可以存储的数据上限差别，源码如下图：

--SDS具备动态扩容的能力，如果要给SDS追加一段字符串，会申请新的内存空间，然后把旧的数据拷贝到新的SDS，并在后面追加新字符串：
如果新字符串小于1M，则新空间为扩容后字符串的两倍+1。
如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。
--示例，在“hi”的SDS后增长“,Amy”，如下图：

--注：每次扩容都须要内核来操纵，所以预分配可以减少内核操纵，提高服从。
--SDS长处：获取字符串长度的时间复杂度为O(1)；支持动态扩容；减少内存分配次数；二进制安全。
2.intSet

--intSet基于整数数组来实现，并且具备长度可变，有序，唯一等特征，源码如下图：

--encoding包含如下三种模式：

--intSet数据存储如下图，使用每个数据使用2字节可以存储，encoding4字节，length4字节，contents是2*3=6字节：

--当我们向其中插入50000时，超出了2字节可以表树模围，intSet会自动升级编码方式到合适巨细，流程如下：
1.升级编码方式为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组。
2.如果当前数组后有富足内存就在原地举行扩容，如果不够，就须要申请更大内存空间。所以为了防止数组数据被覆盖，须要倒序拷贝原来数组中的元素。
3.将待添加的元素放入数组末尾。
4.将intSet的encoding属性更改为INTSET_ENC_INT32，将length更改为4。
--注：当举行平凡插入不须要升级编码时会使用二分查找来确定插入位置。
3.Dict

--Redis是一个键值型数据库，可以根据键实现快速的增编削查，键与值的映射关系就是通过Dict来实现的。
--Dict由三部分组成：哈希表，哈希节点，字典，源码如下图：

--当我们向Dict添加键值对时，Redis会根据key计算出hash值，然后使用h&sizemask来计算元素应该存储到数组中哪个索引位置，其总体结构如下图：

--Dict的哈希表就是数组结合单向链表的实现，当聚集中元素较多时，会导致哈希辩论增多，链表过长，则查询服从会大大降低。
--Dict在每次新增键值对时都会检查负载因子(LoadFactor=used/size)，满意以下两种情况会触发哈希扩容：
1.哈希表的LoadFactor>=1,并且服务器没有实行BGSAVE或者BGREWRITEAOF等背景历程。
2.哈希表的LoadFactor>5。
--Dict在每次删除元素时，也会对负载因子做检查，当LoadFactor<0.1时，会做哈希收缩。
--不管是扩容还时收缩，必须要创建新的哈希表，导致哈希表的size和sizemask厘革，而key的查询与sizemask有关，所以必须要对哈希表中每一个key重新计算索引，插入新的哈希表，这个过程成为rehash。Dict的rehash不是一次性完成的，因为当数据很多的情况下，要再一次rehash完成，极有可能导致主线程阻塞，因此Dict的rehash是分多次，渐进式的完成，因此成为渐进式rehash，过程如下：
1.计算新的hash表的realeSize，值取决于当前要做的是扩容照旧收缩：如果是扩容，则新的realeSize为第一个大于等于dict.[0].used+1的2n次方；如果是收缩，则新的realeSize为第一个大于等于dict.[0].used的2n次方(不得小于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.[1]一次查找并实行，这样可以确保ht[0]的数据只减不增，随着rehash最终为空。
4.Ziplist

--由一系列特别编码的连续内存块组成，可以在恣意一端举行压入/弹出操纵，并且该操纵的时间复杂度为O(1)，其存储结构如下图：

--各个属性寄义如下图：

--Ziplist中的Entry不像平凡链表那样记录前后节点的指针，因为记录两个指针要占用16字节，浪费内存，而是接纳以下结构：

--previous_entry_length：前一节点的长度，占1个或5个字节。
如果前一个节点的长度小于254字节，则接纳1字节来保存这个长度值。
如果前一个字节的长度大于254字节，则接纳5字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据。
--encording：编码属性，记录content的数据类型(字符串照旧整数)以及长度，占用1、2、5字节。
--contents：负责保存节点的数据，可以是字符串或整数。
注：ZipList中全部存储长度的数值均接纳小端字节序，即低位字节在前，高位字节在后，例如：数值0x1234接纳小端字节序后为0x3412。
--ZipList中的encoding编码分为字符串和整数两种：
字符串encoding的编码如下图：

整数的encoding的编码如下图：

--ZipList存在连锁更新问题：假设由N个连续、长度为250~253字节之间的entry，因此entry的previous_entry_length用1字节表现，如下图所示：

--此时在队首插入一个254字节长度的entry，这时之前队首的previous_entry_length必须用5个字节记录，以此类推，会导致连锁反应，许多entry的previous_entry_length都要变为5字节，如下图：

--这种特别情况下产生的连续多次空间拓展成为连锁更新，新增、删除都可能导致连锁更新的发生，对性能影响非常大。
--ZipList特性：
1.压缩列表可以看作一种连续内存空间的“双向链表”。
2.列表的节点之间不是通过指针链接而是通过记录上一节点和本节点长度来寻址，内存占用较低。
3.如果列表数据过多，会导致链表过长，可能影响查询性能。
4.增或删除较大数据时有可能发生连续更新问题，再生性能降落。
5.QuickList

--是一个双向链表，每个链表中的每个节点都是一个ZipList。
--list-max-ziplist-size 控制单个ziplist 节点的最大巨细，当凌驾这个限制，Redis 的 list 类型会从压缩存储结构自动转向更强大的quicklist，其差别值的寄义如下图，默以为-2：

--list-compress-depth可以控制对ZipList节点的压缩，因为链表一般从首尾访问较多，所以首尾不压缩，详细寄义如下图，默以为0：

--QuickList和QuickListNode的结构体源码如下图：

--其大要结构如下图：

--QuickList的特点：
1.是一个节点为ZipList的双向链表。
2.节点接纳ZipList，办理了传统链表的内存占用问题。
3.控制了ZipList巨细，办理了连续内存空间申请服从问题。
4.中间节点可以压缩，进一步节省了空间。
6.SkipList

--SkipList是链表，但与传统链表差别：元素按照升序分列存储；节点可能包含多个指针，每个指针跨度差别。Redis中跳表的结构体如下图：

--其大要结构如下图，图中的每一级指针指向的下一个同一级别节点，并不是level：

--依靠跳表查询就是流程就是，起首从最高级开始查询，当遍历到下一个节点分数大于当前要查询节点分数时，就进入下一级指针在开始重复上述操纵，知道查询到相称的节点分数即可。
--SkipList的特点：
1.跳表是一个双向链表，每个节点包含score和ele值。
2.节点按照score值排序，score值一样的按照ele字典排序。
3.每个节点都可以包含多层指针，层数1到32之间的随机数。
4.差别层指针到下一节点的跨度不一样，层级越高，跨度越大。
5.增编削查服从与红黑树基本同等，实现却更简单。
7.RedisObject

--Redis中的恣意数据类型的键和值都会被封装为一个RedisObject，也叫Redis对象，源码如下图：

--由上图结构体可知一个Redis对象即使什么数据都不存储，就须要占据16字节，这也就是为什么当有大量数据要存储时，不保举使用String，因为每个String都耗费大量内存存储头信息造成数据浪费。
--11种编码方式如下图：

--Redis会根据存储的数据类型差别，选择差别的编码方式，每种数据类型使用的编码方式如下图：

8.五种数据类型

(8.1)String

--最基本的编码方式时RAW，基于简单动态字符串(SDS)实现，存储上限为512MB，结构如下图：

--如果存储的SDS长度小于44字节，则会接纳EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只须要调用一次内存分配函数，服从更改，结构如下图：

--如果存储的字符串是整数值，并且巨细在LONG_MAX范围内，则会接纳INT编码：直接将数据保存在RedisObject的ptr指针位置(刚好8字节)，不须要SDS，结构如下图：

(8.2)List

--List类型可以从首尾操纵列表中元素，故可以选择ZipList和QuickList，但由于ZipList内存占用低，存储上限低，故选择QuickList：LinkedList+ZipList，存储上限高。
--在3.2版本之前，Redis选择ZipList和LinkedList来实现List，当元素数量小于512并且元素巨细小于64字节时接纳ZipList编码，凌驾则接纳LinkedList编码。
--在3.2版本之后，Redis统一接纳QuickList来实现List，其结构如下图：

(8.3)Set

--Set是Redis中的聚集，不一定确保元素有序，可以满意元素唯一，查询服从要求极高。
--为了查询服从和唯一性，Set接纳Dict编码，Dict中的key用来存储元素，value统一为null。结构如下图：

--当存储的全部数据是整数，且元素数量不凌驾set-max-intset-entries(默以为512)时，数据量不大直接遍历全部来查询服从也不错，所以Set会接纳IntSet编码，节省内存。结构如下图：

(8.4)ZSet

--ZSet底层数据结构必须满意键值存储、键必须唯一、可排序。
--SkipList可以实现排序，并且可以存储score和ele值；Dict可以键值存储，并且可以根据key找value。所以ZSet底层实现源码如下图：

--当元素数量不多时，Dict和SkipList的优势不明显，并且更消耗内存。因此ZSet还会接纳ZipList结构来节省内存，但是须要满意以下两个条件：
1.元素数量小于zset-max-ziplist-entries(默以为128)。
2.每个元素小于zset-max-ziplist-value字节(默以为64)。
--ZipList自己没有排序功能，而且没有键值对概念，因此须要ZSet通过编码实现：score和element是紧挨在一起的两个entry，element在前，score在后；且按照score升序分列。结构如下图：

(8.5)Hash

--Hash底层接纳的编码和ZSet基本同等，只须要把排序有关的SkipList去掉即可。
--Hash结构默认接纳ZipList，用以节省内存。ZipList中相邻的两个entry分别保存key和value。
--当数据量较大时，Hash结构会转化成Dict编码，触发条件有两个：
1.ZipList中的元素数量凌驾了hash-max-ziplist-entries(默以为512)。
2.ZipList中的恣意entry巨细凌驾了hash-max-ziplist-value(默以为64)字节。
二.网络模型

1.用户空间和内核空间

--为了制止用户应用导致辩论乃至内核瓦解，所以用户与内核是分离的，如下图：
历程的寻址空间分为内核空间与用户空间。
用户空间只能实行受限命令，并且不能直接调用体系资源，必须通过内核提供的接口来访问。
内核空间可以实行特权命令，调用一切资源。

--Linux为了提高IO服从，会在用户空间与内核空间都加入缓冲区，如下图：
写数据时：把用户缓存的数据拷贝到内核缓冲区，然后写入设备。
读数据时：要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区。

2.阻塞IO

--阻塞IO就是会等待数据读取到内核缓冲区，以及数据从内核缓冲区拷贝到用户缓冲区。

3.非阻塞IO

--非阻塞IO是当内核缓冲区无数据时，不会等待数据读取到内核缓冲区，而是直接返回失败，而且会一直轮询向内核实验获取信息。之后会阻塞等待数据从内核缓冲区拷贝到用户缓冲区，如下图：

--非阻塞IO并没有提升性能，乃至有时不如阻塞IO，因为这种轮询的机制会导致CUP空转，CPU使用率暴增，但在某些场景下使用非阻塞IO会带来性能提升。
4.IO多路复用

--无论是阻塞IO还好坏阻塞IO在第一阶段都会调用recvfrom来获取数据，如果此时无数据，阻塞IO会历程阻塞，非阻塞IO则会空转，都不能完全发挥CUP功能。
--IO多路复用就是制止recvfrom的无效等待，使用单线程监听多个FD，在某个FD可读，可写时得到通知，再调用revcfrom去获取数据，充实使用CPU，如下图：
FD：文件描述符，是一个从0递增的无符号整数，用来关联Linux中的一个文件。再Linux中一切皆文件，例如常规文件、视频、硬件设备，当然也包罗网络套接字(Socket)。

--差别监听FD的方式、通知方式有很多实现：select，poll，epoll。select和poll只会通知用户历程FD停当，但不确定是哪个FD，须要用户逐个遍历FD来确认；epoll则会在通知用户历程FD停当的同时把已停当的FD写入用户空间。
(4.1)select

--select时Linux中最早的I/O多路复用的实现方案，部分源码如下图：

--起首用户空间创建一个fd_set用bit位来存储要监听的FD，然后实行select函数，并把fd_set拷贝给内核空间告诉内核空间要监听哪些FD，内核遍历fd_set检察这些FD是否停当，如果没停当就阻塞等待，如下图：

--如果有停当的，就更改fd_set中，停当的FD对应的bit位保留，未停当的删除，并且给select函数会返回停当FD的数量，内核空间将fd_set拷贝回用户空间，覆盖原先的fd_set，用户空间遍历fd_set找到停当的FD，然后实行recvfrom去获取数据，如下图：

--select模式存在的问题：
1.须要将整个fd_set从用户空间拷贝到内核空间，select结束还要再次拷贝回用户空间。
2.select无法得知详细是哪个FD停当，须要遍历整个fd_set。
3.fd_set监听的FD数量不能凌驾1024。
(4.2)poll

--poll模式对select模式做了简单改进，但性能提升不明显，部分代码如下图：

--实行流程和select非常相似：
1.创建pollfd数组，向其中添加关注的FD信息，数组巨细自定义。
2.调用poll函数，将polled数组拷贝到内核空间，转链表存储，无上限。
3.内核遍历FD，判断是否停当。
4.数据停当或超时后，拷贝polled数组到用户空间，返回停当FD数量。
5.用户历程判断停当FD数量是否大于0.
6.大于0则遍历数组，找到停当的FD。
--与select模式相比：
1.select模式中的fd_set巨细固定为1024，而pollfd再内核中接纳链表，理论上无上限。
2.固然理论无上限，但监听的FD越多，每次遍历消耗时间越久，性能反而降落。
(4.3)epoll

--epoll部分源码如下图：

--起首调用epoll_create在内核创建一个eventpoll。然后调用epoll_ctl将一个FD添加(增编削都可以)到epoll_create，同时给每个FD添加一个callback函数，当FD停当时自动触发，把对应的FD添加到list_head停当队列中。最后调用epoll_wait在用户态创建一个空的events数组，同时将list_head中的FD拷贝到events数组中，list_head为空就等一会，如下图：

--epoll长处：
1.基于epoll示例中的红黑树保存要监听的FD，理论上无上限，而且增编削查服从非常高，性能不会随着监听的FD数量增多而降落。
2.每个FD都只须要实行一次epoll_ctl添加到红黑树，以后每次epol_wait无须传递任何参数，无需重复拷贝FD到内核空间。
3.内核会将停当的FD直接拷贝到用户空间指定位置，用户历程无需遍历全部FD就能知道停当的FD是谁。
(4.3.1)实践通知机制

--LT：当FD有数据可读时，会重复通知多次，知道数据处置惩罚完成(epoll默认模式)。
--ET：当FD有数据可读时，只会被通知一次，不管数据是否处置惩罚成功。
--举例：当客户端发送来2KB数据，调用epoll_ctl将对应FD添加到list_head中，服务端调用epoll_wait，将list_head中的FD添加到events中，然后将FD从list_head中移除，服务端从FD读取了1KB，这时会检查当前事件通知机制发现是LT就将FD再次添加回list_head中。如果是ET就调用epoll_ctl函数将FD更改rb_root中的FD状态为停当，然后会被添加到list_head，或者不将其添加到list_head中，而是接纳循环非阻塞的方法一次性将数据全部读取完毕。
注：LT模式会导致惊群征象，是因为FD会一直存在list_head中，会使很多历程在调用epoll_wait函数时都会监听到该FD，但是前两个历程已经可以或许处置惩罚完。
结论：ET模式最好搭配非阻塞IO读取FD数据。
(4.3.2)基于epoll的服务端流程

--个人总结：全部客户端第一次毗连都是通过serversocket对应FD触发，然后在rb_root中注册自己的FD，后续各个客户端的全部命令都是通过自己注册的FD触发。
5.信号驱动IO

--信号驱动IO是与内核创建SIGIO的信号关联并设置回调，当内核有FD停当时，会发出SIGIO信号通知用户，期间用户无需阻塞等待，可以实行其他业务，如下图：

--缺点：
1.当有大量的IO操纵时，信号较多，SIGIO处置惩罚函数不能及时处置惩罚可能导致信号队列溢出。
2.内核空间与用户空间平凡信号交互性能也较低，因为要频仍切换内核态。
6.异步IO

--异步IO整个过程都好坏阻塞的，用户历程调用完异步API之后就去做其他事，内核等待数据并拷贝到用户空间知乎才会传递信号，通知用户历程，如下图：

--缺点：并发情况下会导致IO任务积聚过多，导致程序瓦解，所以要举行限流。
7.Redis网络模型

--Redis在处置惩罚焦点业务(命令处置惩罚)是单线程，但是总体是多线程：
Redis4.0：引入多线程异步处置惩罚一些耗时较长的任务，例如异步删除命令unlink。
Redis6.0：在焦点网络模型中引入多线程，进一步提高对于多核CUP的使用率。
--Redis焦点网络模型如下图：aeEventLoop类似epoll_create，aeApiPoll类似epoll_wait。每个客户端毗连都通过毗连应答处置惩罚器将客户端FD注册到aeEventLoop中，命令回复处置惩罚器就是读取每个注册完成的客户端的命令哀求，处置惩罚完之后结果封装成client，放入队列中，由beforsleep监听到FD写事件之后写入客户端socket中。
--beforsleep和aeApiPoll是无穷循环调用的。

--Redis6.0之后引入多线程，目的是为了提高IO读写速率，因为影响Redis服从的重要原因就是网络读写，所以就在剖析客户端命令、写相应结果时接纳多线程，焦点命令实行、IO复用依然是主线程实行，如下图：

综上Redis选择单线程原因：
1.Redis是纯内存操纵，实行速率很快，性能瓶颈是网络耽误而不是实行速率，因此多线程不会带来巨大性能提升。
2.引入多线程会导致CPU频仍线程切换，带来不须要开销。
3.多线程会导致安全问题，必须引入线程锁等安全手段，实现复杂度高，性能也会降落。
三.通讯协议RESP

--Redis是一个CS架构软件，所以客户端发送的格式、服务端相应结果的格式接纳相同规范，也就是RESP通讯协议：
Redis1.2版本引入了RESP协议。
Redis2.0版本中成为Redis服务端通讯标准，成为RESP。
Redis6.0版本中，从RESP2升级到RESP3，增长了更多数据类型，且支持6.0新特性--客户端缓存。
但由于兼容性问题，所以默认使用的依然是RESP2，我这里也重要讲解这个版本协议。
--在RESP中，通过首字节的字符来区分差别数据类型，常用数据类型包罗五种：
1.单行字符串：首字节是:+"，后面跟上单行字符串，以"\r\n"末端，例如："OK":"+OK\r\n"。
2.错误(Errors)：首字节是"-"，与单字符串格式一样，只是字符串是异常信息，例如："-Error message\r\n"。
3.数值：首字节是":"，后面跟上数字格式字符串，以"\r\n"末端，例如":10\r\n"。
4，多行字符串：首字节是"$"，后面跟上字符串长度，以及"\r\n"和字符串，以"\r\n"末端，是二进制安全的，示例如下图：

如果巨细为0，则代表空字符串："$0\r\n\r\n"。
如果巨细为-1，则代表不存在："$-1\r\n"。
5.数组：首字节是"*"，后面跟上数组元素个数，在跟上元素，元素数据类型不限，举例如下图：

四.Redis内存接纳

--单节点的Redis其内存不宜过大，会影响持久化和主从同步，我么可以通过maxmerory参数来设置Redis最大内存。
--Redis自己是一个典范的key-value内存存储数据库，因此key，value都保存在之前学习过的Dict结构中，不过在database结构体中，有两个Dict：一个用来保存key_value，另一个用来保存key-TTL，如下图：

--结构如下图：

1.过期key处置惩罚

--惰性删除：不是在TTL到期之后立即删除，而是在访问一个key的时间，检查该key的存活时间，如果已颠末期才删除
--周期删除：通过一个定时任务，周期性的抽样部分过期的key实行删除：
Redis会设置一个定时任务serverCron()，按照hz频率参数来实行key整理，模式为SLOW。
Redis的每个事件循环前会调用beforeSleep()函数，实行过期key整理，模式为FAST。
--SLOW模式规则：
1.实行频率受hz参数影响，默认是每秒实行hz/10，也就是1次，每个周期1000ms。
2.实行整理耗时由 active-expire-effort 参数控制，值越大代表每次整理的key越多，耗时越久。slow的 active-expire-effort 值一般较大。
3.逐个遍历db中哈希表的桶，抽取20个key判断是否过期。
4.如果没有到达时间上限，并且key的过期比例大于10%，就再抽样一次，否则结束。
--FAST：
1.实行频率受hz参数影响，默认是每秒实行hz，也就是10次，每个周期1000ms。
2.实行整理耗时由 active-expire-effort 参数控制，fast的 active-expire-effort 值一般较小。
3.逐个遍历db中哈希表的桶，抽取20个key判断是否过期。
4.如果没有到达时间上限，并且key的过期比例大于10%，就再抽样一次，否则结束。
注：Redis 默认不是固定 slow 或 fast，而是根据当前根据当前 Redis 服务器的运行状态自动选择，空闲就是 fast，繁忙就是 fast 模式。但因为默认 active-expire-effort是1，行为是偏向于 slow 模式 的，整理更保守，CPU 代价低。
2.内存镌汰策略

--当Redis内存到达设置的maxmerory阈值时，Redis主动挑选部分key删除以释放更多内存。Redis在每次实行命令时都会区判断内存是否到达maxmerory，如果到达就会实验删除内存。
--Redis支持8中差别策略选择要删除的key，可以通过maxmemory-policy 参数来指定：
1.noeviction:不镌汰任何key，但是内存满时不允许写入新数据，默认就是这种策略。
2.volatile-ttl：对设置了TTL的key，比较key的剩余TTL值，TTL越小越先被镌汰。
3.allkeys-random：对全体key，随机举行镌汰。也就是直接从db->dict中随机挑选 。
4.volatile-random：对设置了TTL的key，随机举行镌汰。也就是从db->expires中随机挑选。
5.allkeys-lru：对全体key，基于LRU算法举行镌汰。
6.volatile-lru：对设置了TTL的key，基于LRU算法举行镌汰。
7.allkeys-lfu：对全体key，基于LFU算法举行镌汰。
8.volatile-lfu：对设置了TTL的key，基于LFI算法举行镌汰。
LRU：最少近来使用，用当前时间减去最后一次访问时间，这个值越大则镌汰优先级越高。
LFU：最少频率使用，会统计每个key的访问频率，值越小镌汰优先级越高。
--内存镌汰所须要的指标就在RedisObject中，如下图：

--LFU的访问次数时逻辑访问次数，是因为纪录的并不是key被访问的次数，而是通过运算得出：
1.生成0~1之间的随机数R。
2.计算1/(旧次数*lfu_log_factor+1)，记录为P，lfu_log_factor默以为10。
3.如果R<，则计数器+1，但最大不凌驾255。
4.访问次数会随着时间递减，间隔上一次访问时间每隔lfu_decay_time分钟(默认1)，计数器-1。
--内存镌汰的流程如下图：起首判断内存是否到达maxmemory阈值，如果到达就检察内存镌汰策略，如果是noeviction就直接结束，然后判断是否是对设置了TTL的键举行内存镌汰，如果是就操纵db->expires，否则就操纵db->dict，然后再次判断内存策略，如果是随机选择，就直接随机选几个key删除，直到内存富足，不是随机选择，就生成一个eviction_pool池子，然后去db结构中随机选择maxmemory_samples(默认5)个，通过如图所示的计算得出每个key的idleTime，如果eviction_pool池子中数据满了，就拿抽样中的每个key的idleTime与池子中的key最小idleTime作比较，如果大于就更换该key，否则抽样的key丢弃，抽样的key都判断完之后，池子升序分列，然后从池子中倒序取出一部分key并删除，如果删除一部分之后内存照旧不够，就再次循环实行抽样的过程，直到内存富足，这样的循环也会使eviction_pool池子中的key越来越具有删除的价值。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4