前言

作为一台服务器来说，内存并不是无限的，所以总会存在内存耗尽的情况，那么当 Redis 服务器的内存耗尽后，如果继续执行请求命令，Redis 会如何处理呢？

内存回收

使用Redis 服务时，很多情况下某些键值对只会在特定的时间内有效，为了防止这种类型的数据一直占有内存，我们可以给键值对设置有效期。Redis 中可以通过 4 个独立的命令来给一个键设置过期时间：

• expire key ttl：将 key 值的过期时间设置为 ttl 秒。
• pexpire key ttl：将 key 值的过期时间设置为 ttl 毫秒。

• expireat key timestamp：将 key 值的过期时间设置为指定的 timestamp 秒数。
• pexpireat key timestamp：将 key 值的过期时间设置为指定的 timestamp 毫秒数。

PS：不管使用哪一个命令，最终 Redis 底层都是使用 pexpireat 命令来实现的。另外，set 等命令也可以设置 key 的同时加上过期时间，这样可以保证设值和设过期时间的原子性。

设置了有效期后，可以通过 ttl 和 pttl 两个命令来查询剩余过期时间（如果未设置过期时间则下面两个命令返回 -1，如果设置了一个非法的过期时间，则都返回 -2）：

• ttl key 返回 key 剩余过期秒数。
• pttl key 返回 key 剩余过期的毫秒数。

过期策略

如果将一个过期的键删除，我们一般都会有三种策略：

• 定时删除：为每个键设置一个定时器，一旦过期时间到了，则将键删除。这种策略对内存很友好，但是对 CPU 不友好，因为每个定时器都会占用一定的 CPU 资源。
• 惰性删除：不管键有没有过期都不主动删除，等到每次去获取键时再判断是否过期，如果过期就删除该键，否则返回键对应的值。这种策略对内存不够友好，可能会浪费很多内存。

• 定期扫描：系统每隔一段时间就定期扫描一次，发现过期的键就进行删除。这种策略相对来说是上面两种策略的折中方案，需要注意的是这个定期的频率要结合实际情况掌控好，使用这种方案有一个缺陷就是可能会出现已经过期的键也被返回。

在 Redis 当中，其选择的是策略 2 和策略 3 的综合使用。不过 Redis 的定期扫描只会扫描设置了过期时间的键，因为设置了过期时间的键 Redis 会单独存储，所以不会出现扫描所有键的情况：

typedef struct redisDb {
dict *dict; //所有的键值对
dict *expires; //设置了过期时间的键值对
dict *blocking_keys; //被阻塞的key,如客户端执行BLPOP等阻塞指令时
dict *watched_keys; //WATCHED keys
int id; //Database ID
//... 省略了其他属性
} redisDb;

8 种淘汰策略

假如 Redis 当中所有的键都没有过期，而且此时内存满了，那么客户端继续执行 set 等命令时 Redis 会怎么处理呢？Redis 当中提供了不同的淘汰策略来处理这种场景。

首先 Redis 提供了一个参数 maxmemory 来配置 Redis 最大使用内存：

maxmemory <bytes>

或者也可以通过命令 config set maxmemory 1GB 来动态修改。

如果没有设置该参数，那么在 32 位的操作系统中 Redis 最多使用 3GB 内存，而在 64 位的操作系统中则不作限制。

Redis 中提供了 8 种淘汰策略，可以通过参数 maxmemory-policy 进行配置：

PS：淘汰策略也可以直接使用命令 config set maxmemory-policy <策略> 来进行动态配置。

当使用 volatile-lru 、 volatile-random 、 volatile-ttl
这三种策略时，如果没有key可以被淘汰，则和 noeviction 一样返回错误

volatile-ttl

volatile-ttl 针对的是设置了过期时间的数据，把这些数据中剩余存活时间最短的筛选出来并淘汰掉。但是这样的方式，并不能保证我们淘汰的是一个非热点的数据。

volatile-random

volatile-random 针对的是设置了过期时间的数据，从中随机选取一个淘汰，这样的方式，具有不确定性，万一在高峰期淘汰了一个热点数据，那对我们的整体系统的性能会产生波动。

volatile-LRU

采用了LRU算法，来选择淘汰数据，也就是最近最少使用。在java中，有一个LinkedHashMap就实现了LRU的算法，也就是首先淘汰最长时间未被使用的数据。具体在Redis中的实现，是用了保存在RedisObject中一个lru的信息，这里保存了数据最近一次被访问的时间，于是在淘汰时，淘汰一个lru最小的。

这里是截取网上的一张图，形象的说明了整个过程

当然这里Redis没有说，去所有的数据中比较出一个最小值来，这样的做法明显不够Redis。因为知道LinkedHashMap的都知道，在实现LRU中，需要维持一个链表的结构，当有数据访问时，需要移动数据在链表中的位置，当有数据淘汰时，移除队尾的数据。在Redis中，我们把所有的数据都用链表维持起来，不太现实，而且会频繁的移动。所以Redis会取N个数据，来维护一个链表结构，当需要淘汰数据时，就会从N个数据中，采用LRU的方式去淘汰。当后续再需要淘汰时，会从所有的数据中选取比当前数据池中最小lru小的数据进入候选池。

N的数量可以通过maxmemory-samples修改

Redis的整体风格有一种以小见大的味道，后面的LFU和针对时间到期删除的数据都有体现。

Redis为什么不使用原生LRU算法？

• 原生LRU算法需要 双向链表 来管理数据，需要额外内存；
• 数据访问时涉及数据移动，有性能损耗；

• Redis现有数据结构需要改造；

volatile-LFU

采用了LFU算法来淘汰数据，最近最不常用。对每一个数据记录一个使用次数和使用的时间，优先淘汰使用次数最少的元素，假如使用次数一样的多，那在比较时间，使用时间最早的淘汰。

这里是截取网上的一张图，形象的说明了整个过程

Redis基于LRU的基础上改造,在RedisObject中只维护了一个lru的信息，并没有再额外维护一个count的信息来记录，所以这里把一个lru分成2部分来使用，
ldt 值：lru 字段的前 16bit，表示数据的访问时间戳；
counter 值：lru 字段的后 8bit，表示数据的访问次数。

这样的做法在编程中非常的场景，如java中的ReentrantReadWriteLock、线程池等，等有过类似的设计，把一个变量，分成2部分来表示。

当有了访问次数和访问时间后，那就可以完成LRU,当然也是基于N个候选区去淘汰的。但是依旧存在2个问题，一个是counter只有8位，最高可以到255，另一个是counter需要一个衰减机制，不然对于一个瞬时的热点数据来说，可能热点已经过去了不在需要这个数据了，但是由于他的counter比较高，所以他不会淘汰。

counter增加方案

对于redis来说，一个数据的访问次数是有可能非常高的，255次明显无法区分出来热点数据，所以Redis的做法还是以小见大，每当数据被访问一次时，首先，用计数器当前的值乘以配置项 lfu_log_factor 再加 1，再取其倒数，得到一个 p 值；然后，把这个 p 值和一个取值范围在（0，1）间的随机数 r 值比大小，只有 p 值大于 r 值时，计数器才加 1。这样只要lfu_log_factor控制得当，数据需要访问很多很多次才能被+1，这样的情况下255可以代表一个非常大的访问量。并在初期赋予一个初始值5，防止因为刚创建次数少而立即被淘汰。下面是网上的一个测试数据

counter衰减方案

LFU策略会计算这一次访问的时间和上一次访问的时间的差值，并且差值除以 lfu_decay_time配置项，获得counter需要衰减的值，隔得越久，counter需要衰减的越多。

这个方案来看似乎是没有问题的，但是实际上，衰减的方案需要再次访问，才能触发，如果一个数据一开始的访问量很高，后面再也没有人访问，那么在业务上，我们是可以优先放弃这个数据的缓存的，可是在Redis淘汰时，并不是优先选择这个数据。

allkeys-random

与volatile-ranom相似，变的只是，选取数据的范围变了，变成了所有key中选取

allkeys-LRU

与volatile-LRU相似，变的只是，选取数据的范围变了，变成了所有key中选取

allkeys-LFU

与volatile-LFU相似，变的只是，选取数据的范围变了，变成了所有key中选取

相关面试

redis为什么要使用自己的时钟

• 获取系统时间戳将调用系统底层提供的方法；
• 单线程的Redis对性能要求极高，从缓存中获取时间戳将极大提升性能。

拓展：LRU和LFU算法

LRU

标准LRU实现方式

1. 新增key value的时候首先在链表结尾添加Node节点，如果超过LRU设置的阈值就淘汰队头的节点并删除掉HashMap中对应的节点。

2. 修改key对应的值的时候先修改对应的Node中的值，然后把Node节点移动队尾。

3. 访问key对应的值的时候把访问的Node节点移动到队尾即可。

Redis的LRU实现

Redis维护了一个24位时钟，可以简单理解为当前系统的时间戳，每隔一定时间会更新这个时钟。每个key对象内部同样维护了一个24位的时钟，当新增key对象的时候会把系统的时钟赋值到这个内部对象时钟。比如我现在要进行LRU，那么首先拿到当前的全局时钟，然后再找到内部时钟与全局时钟距离时间最久的（差最大）进行淘汰，这里值得注意的是全局时钟只有24位，按秒为单位来表示才能存储194天，所以可能会出现key的时钟大于全局时钟的情况，如果这种情况出现那么就两个相加而不是相减来求最久的key。

struct redisServer { pid_t pid; char *configfile; //全局时钟 unsigned lruclock:LRU_BITS; ... }; typedef struct redisObject { unsigned type:4; unsigned encoding:4; /* key对象内部时钟 */ unsigned lru:LRU_BITS; int refcount; void *ptr; } robj;

Redis中的LRU与常规的LRU实现并不相同，常规LRU会准确的淘汰掉队头的元素，但是Redis的LRU并不维护队列，只是根据配置的策略要么从所有的key中随机选择N个（N可以配置）要么从所有的设置了过期时间的key中选出N个键，然后再从这N个键中选出最久没有使用的一个key进行淘汰。

下图是常规LRU淘汰策略与Redis随机样本取一键淘汰策略的对比，浅灰色表示已经删除的键，深灰色表示没有被删除的键，绿色表示新加入的键，越往上表示键加入的时间越久。从图中可以看出，在redis 3中，设置样本数为10的时候能够很准确的淘汰掉最久没有使用的键，与常规LRU基本持平。

为什么要使用近似LRU？

1、性能问题，由于近似LRU算法只是最多随机采样N个key并对其进行排序，如果精准需要对所有key进行排序，这样近似LRU性能更高

2、内存占用问题，redis对内存要求很高，会尽量降低内存使用率，如果是抽样排序可以有效降低内存的占用

3、实际效果基本相等，如果请求符合长尾法则，那么真实LRU与Redis LRU之间表现基本无差异

4、在近似情况下提供可自配置的取样率来提升精准度，例如通过 CONFIG SET maxmemory-samples <count> 指令可以设置取样数，取样数越高越精准，如果你的CPU和内存有足够，可以提高取样数看命中率来探测最佳的采样比例。

LFU

LFU是在Redis4.0后出现的，LRU的最近最少使用实际上并不精确，考虑下面的情况，如果在|处删除，那么A距离的时间最久，但实际上A的使用频率要比B频繁，所以合理的淘汰策略应该是淘汰B。LFU就是为应对这种情况而生的。

A~~A~~A~~A~~A~~A~~A~~A~~A~~A~~~|

B~~~~~B~~~~~B~~~~~B~~~~~~~~~~~~B|

LFU把原来的key对象的内部时钟的24位分成两部分，前16位还代表时钟，后8位代表一个计数器。16位的情况下如果还按照秒为单位就会导致不够用，所以一般这里以时钟为单位。而后8位表示当前key对象的访问频率，8位只能代表255，但是redis并没有采用线性上升的方式，而是通过一个复杂的公式，通过配置如下两个参数来调整数据的递增速度。

lfu-log-factor 可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。

lfu-decay-time 是一个以分钟为单位的数值，可以调整counter的减少速度。

所以这两个因素就对应到了LFU的Counter减少策略和增长策略，它们实现逻辑分别如下。

降低LFUDecrAndReturn

1、先从高16位获取最近的降低时间ldt以及低8位的计数器counter值

2、计算当前时间now与ldt的差值（now-ldt），当ldt大于now时，那说明是过了一个周期，按照65535-ldt+now计算（16位一个周期最大65535）

3、使用第2步计算的差值除以lfu_decay_time，即LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去n个lfu_decay_time，则将counter减少n。

增长LFULogIncr

1、获取0-1的随机数r

2、计算0-1之间的控制因子p，它的计算逻辑如下

//LFU_INIT_VAL默认为5 baseval = counter - LFU_INIT_VAL; //计算控制因子 p = 1.0/(baseval*lfu_log_factor+1);

3、如果r小于p，counter增长1

p取决于当前counter值与lfu_log_factor因子，counter值与lfu_log_factor因子越大，p越小，r小于p的概率也越小，counter增长的概率也就越小。增长情况如下图：

从左到右表示key的命中次数，从上到下表示影响因子，在影响因子为100的条件下，经过10M次命中才能把后8位值加满到255.

新生KEY策略

另外一个问题是，当创建新对象的时候，对象的counter如果为0，很容易就会被淘汰掉，还需要为新生key设置一个初始counter。counter会被初始化为LFU_INIT_VAL，默认5。