过期删除与内存淘汰策略

以下内容是根据小林网站内容自学总结的，原文见https://xiaolincoding.com/

过期删除策略一共有三种：

定时删除：在设置key的过期时间时，同时创建一个过期时间。保证过期的key被及时删除，所以对内存友好，但是过多的过期key会对CPU不友好。

惰性删除：不主动删除过期key，而是当数据库访问到key时，检测key有无过期，过期了就删除。这对CPU非常友好，但是会造成内存空间浪费。

定期删除：每隔一段时间从数据库随机取出一定数量的key，删除过期key。相比定时和惰性，定时删除策略是一种较为居中的方案。

Redis过期删除策略

Redis采用惰性删除+定期删除策略

惰性删除由db.c文件的expireIfNeeded函数实现，如果被访问的key过期，在Redis4.0之后提供了lazyfree_lazy_expire参数配置，1为异步删除，反之同步删除，返回null。如果没过期，就返回数据。

int expireIfNeeded(redisDb *db, robj *key) {
    // 判断 key 是否过期
    if (!keyIsExpired(db,key)) return 0;
    ....
    /* 删除过期键 */
    ....
    // 如果 server.lazyfree_lazy_expire 为 1 表示异步删除，反之同步删除；
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

定期删除策略：

间隔时间：Redis配置文件redis.config默认为10hz，即每秒10次检查一次数据库，这个检查是随机抽查，而且数量一定，而不是数据库全部。

抽查数量：数量是写死的，为20。在expire.c文件中的activeExpireCycle函数的ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP参数定义为20。

具体流程就是：

1.从库中随机取20个key，即从过期字典(expires dict)中随机取20个

2.检查这20个是否过期，过期了删除即可；

3.删除后，查看是否超时，超时直接退出；

4.未超时，还要看删除的数据是否大于20个的25%，也就是是否超过4个，如果超过，则继续随机取20，进行循环

伪代码如下：

do {
    //已过期的数量
    expired = 0；
    //随机抽取的数量
    num = 20;
    while (num--) {
        //1. 从过期字典中随机抽取 1 个 key
        //2. 判断该 key 是否过期，如果已过期则进行删除，同时对 expired++
    }
    
    // 超过时间限制则退出
    if (timelimit_exit) return;

  /* 如果本轮检查的已过期 key 的数量，超过 25%，则继续随机抽查，否则退出本轮检查 */
} while (expired > 20/4);

Redis内存淘汰策略

redis.conf可通过maxmemory < bytes >设置最大内存，当Redis运行内存超过设置的最大内存时，就会触发内存淘汰策略。

64位操作系统的maxmemory默认为0，即没有最大内存限制

32位操作系统默认为3G，因为运行内存最大就支持4G

Redis的内存淘汰策略有两类（共8种）：

1. 第一类就是不淘汰策略：noevication，这时Redis3.0之后默认的内存淘汰策略。表示超过内存不再提供服务，直接返回错误。
2. 第二类是进行淘汰：分为 对设置了过期时间的数据进行淘汰 以及 所有数据范围的淘汰

前者有4种：

• volatile-random:随机淘汰任意键值
• volatile-ttl:优先淘汰最早过期的key（头进尾出淘汰尾端）
• volatile-lru:优先淘汰最久未使用的key（时间间隔最久）
• volatile_lfu:优先淘汰最少使用的key（频率最低）

后者有3种：

• allkeys-random:随机淘汰任意键值
• allkeys-lru:优先淘汰最久未使用的key（时间间隔最久）
• allkeys-lfu:优先淘汰最少使用的key（频率最低）

查看当前的内存淘汰策略

• 通过命令config get maxmemory-policy

设置内存淘汰策略

• 方式1：config set maxmemory-policy <策略>，设置后立即生效，不需重启Redis，但重启就失效；
• 方式2：修改Redis配置文件，设置maxmemory-policy <策略>，必须重启，配置永久生效。

LRU和LFU

LRU

• LRU-Least Recently Used即最近最少使用（时间层面）。

传统LRU是基于链表的，新的key放链表头，最久未使用的就在链表尾。但是链表存储本身就带来额外的空间开销，而且每个节点被访问时都要将节点放到链表头部，当链表移动操作过多（key访问次数多）时，时间开销也不小。

Redis的LRU是近似的LRU算法，随机取5个值（可设置），然后淘汰最久没用的key。没有链表就没有了上面提到的额外的空间和时间的开销，但是无法避免缓存污染问题。

缓存污染指的是：某个应用一次读取了大量数据，那么这些数据会在内存中存放很久，所以这间接告诉我们要用key的使用频率来进行淘汰。

LFU

LFU-Least Frequently Used即最近不常使用（频率）。

• 在LRU算法中：在Redis对象头中，24bits的lru字段用来记录key的访问时间戳，可以对lru字段进行比较来直接淘汰最久未被使用的key.

• 在LFU算法中：在Redis对象头中，24bits的lru字段分成两段，高16bits存储ldt（），低8bit存储logc（Logistic Counter）

ldt是key的最后一次的访问时间戳；logc是key的访问频次，越小代表频次越低，初始值为5

每次key被访问都会先对logc进行衰减操作，衰减程度与当前时间和ldt的差值成正相关，也就是间隔时间越长，ldt衰减越大。

衰减完了要做增加操作，按概率增加，logc越大，增加越难。

redis.conf提供两个配置项：

• lfu-decay-time用于调整logc衰减速度，以分钟为单位，数值越大，衰减越慢
• lfu-log-facter用于调整logc的增长速度，数值越大，衰减越慢