本章内容

过期删除策略

在使用Redis缓存时，为了提高缓存命中率，一般会为缓存数据设置过期时间，到期后会根据相应的过期删除策略删除缓存数据。

Redis的缓存过期删除策略有两种：惰性删除和定期删除。

过期时间判定

在Redis中，设置了过期时间的key会被存放到Redis的过期字典中。对该Key进行读写操作时，会先检查key是否存在过期字典中，存在，则获取key的过期时间，并与系统当前时间进行比较：

• 如果过期时间大于当前时间，则判定该key未过期。
• 如果过期时间小于等于当前时间，则判定该key已过期。

过期字典

过期字典存储在redisDb结构中，代码如下：

typedef struct redisDb {
    // DatabaseID，0~15
    int id;
    // 键空间（key space），存放所有的键值对
    dict *dict;
    // 存放设置了TTL的key及其对应的TTL存活时间
    dict *expires;
    ...
}redisDb;

其中：

• 过期字典的键指向Redis数据库中的某个key。
• 过期字典的值是一个long long类型的整数，用于保存key对应的过期时间（时间戳，单位：毫秒）。

如图所示：

惰性删除

惰性删除处理逻辑，如图所示：

处理流程：

• 对key进行读写操作，判断key是否存在于过期字典中：
• 不存在，则正常进行读写操作。
• 存在，则通过比较key过期时间与系统当前时间判断key是否已过期：
• 如果key过期时间小于等于当前时间（已过期），则删除key。
• 如果key过期时间大于当前时间（未过期），则正常进行读写操作。

定期删除

定期删除处理逻辑，如图所示：

处理流程：

• Redis以100ms/次的频率从过期字典中随机抽取20个key进行检查，通过比较key过期时间与系统当前时间判断是否存在过期key：
• 如果key过期时间小于等于当前时间，则key已过期。
• 如果key过期时间大于当前时间，则key未过期。
• 存在过期key，则判断过期key数量是否超过抽取数量的25%或者执行定期删除的时长超过25ms：
• 超过25%或者执行时长超过25ms，则继续从过期字典中随机抽取20个key进行检查，按此策略一直循环，直到过期key数量不超过25%或者执行时长不超过25ms。
• 未超过25且执行时长未超过25ms，则删除过期key。
• 不存在过期key，则等待100ms后继续从过期字典中随机抽取20个key进行检查。

注意：

• Redis定期删除在主线程上执行，如果同时出现大量key过期会影响Redis的读写效率。
• Redis2.8版本后，可以通过修改配置文件redis.conf中的hz参数（默认值为10，即：每秒执行10次）来调整定期删除定时任务的执行频次。
• 参数hz：hz的取值范围为1~500，默认为10，不建议超过100，提高hz的值将会占用更多的CPU资源，只有在请求延时非常低的情况下可以考虑将hz的值提升到100。

过期删除策略总结

Redis过期删除策略采用惰性删除+定期删除是对CPU资源和内存消耗的一种权衡：

• 如果只采用惰性删除，对于那些一直未被访问的key会一直保存在内存中，造成内存资源的浪费。
• 如果只采用定期删除，当同时存在大量key过期时，会占用大量CPU资源，影响读写操作性能及系统吞吐量。

内存淘汰策略

过期删除策略是一种不完全精准的删除策略，对于那些长期未访问且经过多次定期删除未被选中的key，会一直保存在内存中，可能导致Redis的内存被耗尽，因此，Redis提供另外一种删除key的策略，即：内存淘汰策略。

设置最大内存

在配置文件redis.conf中，通过参数maxmemory <bytes>来设定最大内存（默认为无限制，通常将该参数值设定为物理内存的3/4）。

设置内存淘汰策略

当Redis内存超过参数maxmemory设定的最大内存时，会触发内存淘汰策略。内存淘汰策略通过参数maxmemory-policy进行设置，策略如下：

• volatile-lru：针对设置了过期时间的key，基于LRU算法进行淘汰（LRU：Least Recently Used，表示最久未使用）。
• allkeys-lru：针对所有key（含：设置了过期时间和未设置过期时间的key），基于LRU算法进行淘汰（生成环境常用策略）。
• volatile-lfu：针对设置了过期时间的key，基于LFU算法进行淘汰（LFU：Least Frequently Used，表示最近最少使用）。
• allkeys-lfu：针对所有key，基于LFU算法进行淘汰。
• volatile-random：针对设置了过期时间的key，基于随机淘汰方式进行淘汰。
• allkeys-random：针对所有key，基于随机淘汰方式进行淘汰。
• volatile-ttl：针对设置了过期时间的key，淘汰即将过期的key(minor TTL) 。
• noeviction：不会淘汰任何数据，当使用的内存空间超过参数maxmemory设定的值时，向Redis中写入数据时返回错误（默认策略，一般不使用）。

可见，除了比较特殊的noeviction与volatile-ttl策略，其余六种策略可以分为两类：

• 以volatile-开头的策略是根据特定算法淘汰设置了过期时间的key。
• 以allkeys-开头的策略是根据特定算法淘汰所有key。

redis.conf中内存淘汰策略相关参数：

• maxmemory：内存使用上限，默认值为0，表示不限制内存使用上限。
• maxmemory-policy：内存淘汰策略，默认策略为noeviction。
• maxmemory-samples：随机采样数量，默认值为5。

内存淘汰策略选择：

• 如果数据呈现幂等分布（即：部分数据访问频率较高，其余部分访问频率较低），建议选择allkeys-lru或allkeys-lfu策略。
• 如果数据呈现平等分布（即：所有数据访问概率大致相等），建议选择allkeys-random策略。
• 如果需要通过设置不同的ttls来确定数据过期的顺序，建议选择volatile-ttl策略。
• 如果部分数据需要长期保存，部分数据可以清除，建议选择volatile-lru或volatile-random策略。

注意：由于设置过期时间会消耗额外的内存，为了避免Redis因判断key过期时间消耗额外的内存，可以选择allkeys-lru策略。

查看当前Redis使用的内存淘汰策略：config get maxmemory-policy。

修改内存淘汰策略：

• config set maxmemory-policy <策略>：立即生效，重启恢复默认。
• 修改配置文件redis.conf中的参数maxmemory-policy <策略>：重启生效。

Redis-近似LRU算法

Redis-近似LRU算执行过程：

• 随机抽取N（N由参数maxmemory-samples设定，默认值为5）个key，找出其中最久未被访问的key（时间判断是通过redisObject中的lru属性与系统当前时间进行比较）并删除该Key。
• 再次判断系统内存是否超过内存使用上限，仍超过内存使用上限，则继续上述过程。

LRU算法缺陷

LRU算法仅关注数据的访问时间或访问顺序，忽略了访问次数的价值，在淘汰数据过程中可能会淘汰热点数据。

如图所示：

图中，时间轴自左向右，数据A/B/C在同一段时间内被分别访问的数次。数据C是最近一次访问的数据，按照LRU算法排列数据的热度是C>B>A，而数据的真实热度是B>A>C。

Redis为什么不直接采用LRU算法？

如果采用LRU算法（基于HashMap+双向链表：后续会专门分享一篇LRU算法），需要消耗额外内存存储双向链表节点中的prev和next指针，从而降低Redis的存储空间。

参数maxmemory-samples的默认值为什么是5？

当抽取数量为5时，执行效率已经非常接近标准的LRU算法，虽然抽取数量设置为>5时可以更接近LRU算法，但是这样会消耗更多的CPU资源，因此，抽取数量默认值为5是LRU算法执行效率与CPU资源消耗进行权衡的结果。

Redis-LFU算法

LFU（全称Least Frequently Used）表示最近最少使用，它与key的访问次数有关，核心思想是：如果一个数据在近期被高频率地访问，那么在将来它被再访问的概率也会很高，而访问频率较低的数据将来很大概率不会再使用。

注意：LFU算法的访问频率不能等同于访问次数。如图所示：

图中，数据A被访问了5次，数据B与C各被访问了4次：

• 如果按照访问次数判断数据热度值为：A>B=C。
• 如果考虑到时效性，距离当前时间越近的访问越有价值，那么数据热度值为：C>B>A。

因此，LFU算法一般都会有一个时间衰减函数参与热度值的计算，兼顾了访问时间的影响。

LFU算法实现

LFU算法的实现没有使用额外的数据结构，复用了redisObject数据结构的lru字段。

redisObject数据结构：

typedef struct redisObject{
    // 类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    // 指向底层数据结构的指针
    void *ptr;
    // 引用计数
    int refcount;
    // 24bits，用于记录对象的访问信息
    unsigned lru:24;
} robj;

其中，lru字段在LRU算法和LFU算法中使用方式存在差异：

• 在LRU算法中，lru字段用来记录key的访问时间戳，因此，可以根据lru字段记录的值与当前时间进行比较，淘汰最久未被访问的key。
• 在LFU算法中，lru字段被分成两段来存储，高16bit存储ldt（Last Decrement Time），低8bit存储logc（Logistic Counter）。

LFU算法中lru字段，如图所示：

其中：

• ldt：用来记录key的访问时间戳。
• logc：用来记录key的访问频次（即：热度值），logc的值越小，表示访问频次越低，越有可能被淘汰，新加入key的logc初始值为5（目的是防止新key马上被淘汰，新加入key的访问次数很可能比不被访问的老key小）。

LFU访问频次（Logistic Counter）算法实现：

#define LFU_INIT_VAL 5
/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

其中：

• counter小于或等于LFU_INIT_VAL时，数据一旦被访问命中， counter接近100%概率递增1。
• counter大于LFU_INIT_VAL时，需要先计算两者差值，然后作为分母的一部分参与递增概率的计算。
• 随着counter数值的增大，递增的概率逐步衰减，可能数次的访问都不能使其数值加1。
• 当counter数值达到255时，就不再进行数值递增的计算过程。

为了适配各种业务数据的特性，Redis在LFU算法实现过程中引入了两个可调参数：

• lfu-decay-time：时间衰减因子，以分钟为单位，默认值为1，该参数值值越大，衰减越慢。
• lfu-log-factor：递增衰减因子，默认值为10，该参数值越大，递增概率越低。

【阅读推荐】

更多精彩内容，如：

• Redis系列

• 数据结构与算法系列

• Nacos系列

• MySQL系列

• JVM系列

• Kafka系列

请移步【南秋同学】个人主页进行查阅。内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～