Redis经典问题 – 内存淘汰算法

现在后端面试中比较喜欢问一些 Redis 的问题，比较常见的就是 内存淘汰算法。下面我们通过源码来分析 Redis 内存淘汰算法的实现，从而不会被面试官问到哑口无言。

Redis 内存使用限制设置

一般来说，要开启 Redis 的内存使用限制才会触发内存淘汰机制，Redis 内存使用限制通过以下配置来设置：

# 设置 Redis 最大使用内存大小为100M
maxmemory 100mb
复制代码

上面的配置设置了，当 Redis 使用的内存超过 100Mb 时就开始对数据进行淘汰。

Redis 内存淘汰算法

而 Redis 的淘汰算法有多种，如下：

• 随机

• TTL

• LRU（Least Recently Used，最近最少使用）

• LFU（Least Frequently Used，最不经常使用）

随机算法很好理解，就是从数据库中随机淘汰一些 Keys。而 TTL 算法就是从设置了过期时间的 Keys 中获取最早过期的 一批 Keys，然后淘汰这些 Keys。而 LRU 和 LFU 这两种算法在名字上比较容易混淆，所以这里介绍一下这两种算法的区别。

LRU算法

LRU 主要是通过 Key 的最后访问时间来判定哪些 Key 更适合被淘汰，如下图所示：

如上图所示，所有的 Keys 都根据最后被访问的时间来进行排序的，所以在淘汰时只需要按照所有 Keys 的最后被访问时间，由小到大来进行即可。

LFU算法

LFU算法主要通过 Key 的访问频率来统计哪些 Key 更适合被淘汰，如下图所示：

如上图所示，所有 Keys 都根据被访问次数进行排序，所以在淘汰时只需要按照所有 Keys 的被访问次数，由小到大来进行即可。

Redis 内存淘汰算法配置

可以通过 maxmemory-policy 配置项来设置 Redis 的内存淘汰算法，如下：

# maxmemory-policy 的可选值为：
# 1) volatile-lru：在设置了过期时间的Keys中，通过LRU算法来进行淘汰。
# 2) allkeys-lru：在所有的Keys中，通过LRU算法进行淘汰。
# 3) volatile-lfu：在设置了过期时间的Keys中，通过LFU算法来进行淘汰。
# 4) allkeys-lfu：在所有的Keys中，通过LFU算法进行淘汰。
# 5) volatile-random：在设置了过期时间的Keys中，通过随机算法来进行淘汰。
# 6) allkeys-random：在所有的Keys中，通过随机算法进行淘汰。
# 7) volatile-ttl：在设置了过期时间的Keys中，选择过期时间最短的Key进行淘汰。
# 8) noeviction：不对Keys进行淘汰。
maxmemory-policy volatile-lru
复制代码

可以根据应用的使用场景来选择合适的内存淘汰算法。

Redis内存淘汰实现

接下来，我们将通过分析 Redis 源码来了解其实现原理。

1. LRU淘汰算法实现

我们先来分析 Redis 的 LRU 淘汰算法的实现。

前面说过，LRU 淘汰算法是使用 Key 的最后访问时间来进行判定的，所以在 Redis 的 Key 对象中有个字段用于保存其最后被访问的时间，如下代码所示：

#define LRU_BITS 24

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; // 记录 Key 的最后被访问时间
    int refcount;
    void *ptr;
} robj;
复制代码

在 robj 对象中的 lru 字段就是用来记录 Key 的最后被访问时间。当 Key 被访问时，会调用 lookupKey 函数查找 Key 对应的值，我们可以从 lookupKey 函数中找到 lru 字段更新相关的代码：

robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict, key->ptr); // 获取 Key 对应的 Value
    if (de) {
        robj *val = dictGetVal(de);

        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                updateLFU(val);
            } else {
                val->lru = LRU_CLOCK(); // 更新 Key 最后被访问时间
            }
        }
        return val;
    } else {
        return NULL;
    }
}
复制代码

从 lookupKey 函数的实现中可以看到，当 Key 被访问时会更新其 lru 字段的值为当前时间戳。

2. LFU淘汰算法实现

由于 LRU 算法使用 Key 的最后访问时间来判定是否应该淘汰，那么就会导致以下情况出现：

如上图的情况，由于 Key2 的最后访问时间比 Key1 的要新，所以如果使用 LRU 算法进行淘汰的话，那么应该先淘汰 Key1。但通过观察发现，Key1 的访问频率明显比 Key2 高，所以应该淘汰 Key2 更为合理。

由于 LRU 算法有以上的缺点，所以 Redis 4.0 开始支持 LFU 淘汰算法。前面也说过，LFU 算法是通过访问 Key 的频率来进行淘汰的，下面我们介绍以下 Redis 的 LFU 算法是怎么实现的。

Redis 的 LFU 算法也是通过 robj 对象的 lru 字段来保存 Key 的访问频率的，LFU 算法把 lru 字段分为两部分，如下图：

• 0 ~ 7 位：用于保存 Key 的访问频率计数器。

• 8 ~ 23 位：用于保存当前时间（以分钟计算）。

由于访问频率计数器只有8个位，所以取值范围为 0 ~ 255，如果每访问 Key 都增加 1，那么很快就用完。所以 Redis 使用了一种比较复杂的算法了计算访问频率，算法如下：

• 获取一个 0 ~ 1 的浮点数随机数 r。

• 根据计数器的旧值与影响因子（通过 lfu-log-factor 配置项设置）计算出一个 0 ~ 1 的浮点数 p，计算公式为：1.0 / (计算器旧值 * 影响因子 + 1)。

• 如果 p 的值大于 r，那么就对访问频率计数器进行加一。

Redis 通过 LFULogIncr 函数来实现这个算法：

uint8_t LFULogIncr(uint8_t counter) 
{
    if (counter == 255)
        return 255;

    double r = (double)rand()/RAND_MAX;      // 获取随机数r
    double baseval = counter - LFU_INIT_VAL; // 计数器旧值

    if (baseval < 0) baseval = 0;

    // 根据计数器旧值与影响因子来计算出p
    double p = 1.0 / (baseval * server.lfu_log_factor + 1);

    if (r < p) counter++; // 如果 p 大于 r, 那么对计数器进行加以操作

    return counter;
}
复制代码

所以从上面的算法可以看出，影响访问频率计数器的增加速度有两个因素：1. 计数器的旧值；2. 影响因子。

下表展示了影响因子的取值对访问频率计数器增速的影响（从0增长到255需要访问的次数）：

从上表中可知，在影响因子为100的条件下，经过1000万次命中才能把访问频率计数器增加到255。

如果访问频率计数器只增不减的话，那么当所有 Key 到增加到 255 后，LFU 算法就不起效果了。所以 Redis 还实现了访问频率计数器的衰减算法，衰减算法的原理就是，Key 越久没被访问，衰减的程度就越大。

Redis 的访问频率计数器衰减算法是通过 LFUDecrAndReturn 函数完成的：

unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;      // 获取 Key 最后访问时间(单位为分钟)
    unsigned long counter = o->lru & 255; // 获取 Key 访问频率计数器的值
    
    // 下面是计算要衰减的数量
    // LFUTimeElapsed 函数用于获取 Key 没被访问的时间(单位为分钟)
    // lfu_decay_time 是衰减的力度，通过配置项 lfu-decay-time 设置，值越大，衰减力度约小
    unsigned long num_periods = server.lfu_decay_time
                                ? LFUTimeElapsed(ldt) / server.lfu_decay_time
                                : 0;

    // 对访问频率计数器进行衰减操作
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;

    return counter;
}
复制代码

从 LFUDecrAndReturn 函数可知，lfu-decay-time 设置越大，衰减的力度就越小。如果 lfu-decay-time 设置为1，并且 Key 在 10 分钟内没被访问的话，按算法可知，访问频率计数器就会被衰减10。

LFU 算法更新 lru 字段也是在 lookupKey 函数中完成的：

robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict, key->ptr); // 获取 Key 对应的 Value
    if (de) {
        robj *val = dictGetVal(de);

        if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { // 如果配置的是LFU淘汰算法
                updateLFU(val); // 更新LFU算法的统计信息
            } else {
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}
复制代码

我们来看看 updateLFU 函数的实现：

void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);   // 对访问频率计数器进行衰减操作
    counter = LFULogIncr(counter);                   // 增加访问频率计数器的值
    val->lru = (LFUGetTimeInMinutes()<<8) | counter; // 将当前时间与访问频率计数器组合成LFU统计信息
}
复制代码

updateLFU 函数比较简单，首先对访问频率计数器进行衰减操作，然后增加访问频率计数器的值，最后将当前时间与访问频率计数器组合成起来保存到 robj 对象的 lru 字段中。