关于java:Redis源码剖析之内存淘汰策略Evict

Redis 作为一个成熟的数据存储中间件，它提供了欠缺的数据管理性能，比方之前咱们提到过的数据过期和明天咱们要讲的数据淘汰 (evict) 策略。在开始介绍 Redis 数据淘汰策略前，我先抛出几个问题，帮忙大家更深刻理解 Redis 的数据淘汰策略。

1. 何为数据淘汰，Redis 有了数据过期策略为什么还要有数据淘汰策略？
2. 淘汰哪些数据，有什么样的数据选取规范？
3. Redis 的数据淘汰策略是如何实现的？

何为 Evict

我先来答复第一个问题，Redis 中数据淘汰实际上是指的在内存空间有余时，清理掉某些数据以节俭内存空间。 尽管 Redis 曾经有了过期的策略，它能够清理掉有效期外的数据。但设想下这个场景，如果过期的数据被清理之后存储空间还是不够怎么办？是不是还能够再删除掉一部分数据？ 在缓存这种场景下 这个问题的答案是 能够，因为这个数据即使在 Redis 中找不到，也能够从被缓存的数据源中找到。所以在某些特定的业务场景下，咱们是能够抛弃掉 Redis 中局部旧数据来给新数据腾出空间。

如何 Evict

第二个问题，既然咱们须要有淘汰的机制，你们在具体执行时要选哪些数据淘汰掉？具体策略有很多种，但思路只有一个，那就是 总价值最大化 。咱们生在一个 不偏心的世界 里，同样数据也是，那么多数据里必然不是所有数据的价值都是一样的。所以咱们在淘汰数据时只须要抉择那些低价值的淘汰即可。

所以问题又来了，哪些数据是低价值的？这里不得不提到一个贯通计算机学科的原理 局部性原理 ，这里能够明确通知你，局部性原理在缓存场景有这样两种景象，1. 最新的数据下次被拜访的概率越高。2. 被拜访次数越多的数据下次被拜访的概率越高。 这里咱们能够简略认为被拜访的概率越高价值越大。基于上述两种景象，咱们能够指定出两种策略 1. 淘汰掉最早未被拜访的数据。2. 淘汰掉访被拜访频次最低的数据，这两种策略别离有个土气的英文名 LRU(Least Recently Used) 和 LFU(Least Frequently Used)。

Redis 中的 Evict 策略

除了 LRU 和 LFU 之外，还能够随机淘汰。这就是将数据厚此薄彼，随机选取一部分淘汰。实际上 Redis 实现了以上 3 中策略，你应用时能够依据具体的数据配置某个淘汰策略。除了上述三种策略外，Redis 还为由过期工夫的数据提供了按 TTL 淘汰的策略，其实就是淘汰残余 TTL 中最小的数据。另外须要留神的是 Redis 的淘汰策略能够配置在全局或者是有过期工夫的数据上，所以 Redis 共计以下 8 中配置策略。

源码分析

接下来咱们就从源码来看下 Redis 是如何实现以上几种策略的，MAXMEMORY_VOLATILE_和 MAXMEMORY_ALLKEYS_策略实现是一样的，只是作用在不同的 dict 上而已。另外 Random 的策略也比较简单，这里就不再详解了，咱们重点看下 LRU 和 LFU。

LRU 具体实现

LRU 的实质是淘汰最久没被拜访的数据，有种实现形式是用链表的形式实现，如果数据被拜访了就把它移到链表头部，那么链尾肯定是最久未拜访的数据，然而单链表的查问工夫复杂度是 O(n)，所以个别会用 hash 表来放慢查问数据，比方 Java 中 LinkedHashMap 就是这么实现的。但 Redis 并没有采纳这种策略，Redis 就是单纯记录了每个 Key 最近一次的拜访工夫戳，通过工夫戳排序的形式来选找出最早的数据，当然如果把所有的数据都排序一遍，未免也太慢了，所以Redis 是每次选一批数据，而后从这批数据执行淘汰策略。这样的益处就是性能高，害处就是不肯定是全局最优，只是达到部分最优。

typedef struct redisObject {
    unsigned type:4;  
    unsigned encoding:4;
    unsigned lru:LRU_BITS; 
    int refcount;      
    void *ptr;            
} robj;

LRU 信息如何存的？在之前介绍 redisObject 的文章中 咱们已提到过了，在 redisObject 中有个 24 位的 lru 字段，这 24 位保留了数据拜访的工夫戳(秒)，当然 24 位无奈保留残缺的 unix 工夫戳，不到 200 天就会有一个轮回，当然这曾经足够了。

robj *lookupKey(redisDb *db, robj *key, int flags) {dictEntry *de = dictFind(db->dict,key->ptr);
    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();  // 这里更新 LRU 工夫戳  
            }
        }
        return val;
    } else {return NULL;}
}

LFU 具体实现

lru这个字段也会被 lfu 用到，所以你在下面 lookupkey 中能够看到在应用 lfu 策略是也会更新 lru。Redis 中 lfu 的呈现稍晚一些，是在 Redis 4.0 才被引入的，所以这里复用了 lru 字段。lru 的实现思路只有一种，就是记录下 key 被拜访的次数。但实现 lru 有个问题须要思考到，尽管 LFU 是按拜访频次来淘汰数据，但在 Redis 中随时可能有新数据就来， 自身老数据可能有更屡次的拜访，新数据以后被拜访次数少，并不意味着将来被拜访的次数会少，如果不思考到这点，新数据可能一就来就会被淘汰掉，这显然是不合理的。

Redis 为了解决上述问题，将 24 位被分成了两局部，高 16 位的工夫戳(分钟级)，低 8 位的计数器。每个新数据计数器初始有肯定值，这样能力保障它能走出新手村，而后计数值会随着时间推移衰减，这样能够保障老的但以后不罕用的数据才有机会被淘汰掉，咱们来看下具体实现代码。

LFU 计数器增长

计数器只有 8 个二进制位，充其量数到 255，怎么会够? 当然 Redis 应用的不是准确计数，而是近似计数。具体实现就是 counter 概率性增长，counter 的值越大增长速度越慢，具体增长逻辑如下：

/* 更新 lfu 的 counter，counter 并不是一个精确的数值，而是概率增长，counter 的数值越大其增长速度越慢
 * 只能反映出某个工夫窗口的热度，无奈反映出具体拜访次数 */
uint8_t LFULogIncr(uint8_t counter) {if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL; // LFU_INIT_VAL 为 5
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);  // server.lfu_log_factor 可配置，默认是 10 
    if (r < p) counter++;
    return counter;
}

从代码逻辑中能够看出，counter 的值越大，增长速度会越慢，所以 lfu_log_factor 配置较大的状况下，即使是 8 位有能够存储很大的访问量。下图是不同 lfu_log_factor 在不同拜访频次下的增长状况，图片来自 Redis4.0 之基于 LFU 的热点 key 发现机制。

LFU 计数器衰减

如果说 counter 始终增长，即使增长速度很慢也有一天会增长到最大值 255，最终导致无奈做数据的筛选，所以要给它加一个衰减策略，思路就是 counter 随工夫增长衰减，具体代码如下：

/* lfu counter 衰减逻辑, lfu_decay_time 是指多久 counter 衰减 1，比方 lfu_decay_time == 10
 * 示意每 10 分钟 counter 衰减一，但 lfu_decay_time 为 0 时 counter 不衰减 */
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    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;
}

server.lfu_decay_time 也是可配置的，默认是 10 标识每 10 分钟 counter 值减去 1。

evict 执行过程

evict 何时执行

在 Redis 每次解决命令的时候，都会查看内存空间，并 尝试去执行evict，因为有些状况下不须要执行 evict，这个能够从 isSafeToPerformEvictions 中能够看出端倪。

static int isSafeToPerformEvictions(void) {
    /* 没有 lua 脚本执行超时，也没有在做数据超时 */
    if (server.lua_timedout || server.loading) return 0;

    /* 只有 master 才须要做 evict */
    if (server.masterhost && server.repl_slave_ignore_maxmemory) return 0;

    /* 当客户端暂停时，不须要 evict，因为数据是不会变动的 */
    if (checkClientPauseTimeoutAndReturnIfPaused()) return 0;

    return 1;
}

evict.c

evict 代码都在 evict.c 中。外面蕴含了每次 evict 的执行过程。

int performEvictions(void) {if (!isSafeToPerformEvictions()) return EVICT_OK;

    int keys_freed = 0;
    size_t mem_reported, mem_tofree;
    long long mem_freed; /* May be negative */
    mstime_t latency, eviction_latency;
    long long delta;
    int slaves = listLength(server.slaves);
    int result = EVICT_FAIL;

    if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
        return EVICT_OK;

    if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
        return EVICT_FAIL;  /* We need to free memory, but policy forbids. */

    unsigned long eviction_time_limit_us = evictionTimeLimitUs();

    mem_freed = 0;

    latencyStartMonitor(latency);

    monotime evictionTimer;
    elapsedStart(&evictionTimer);

    while (mem_freed < (long long)mem_tofree) {
        int j, k, i;
        static unsigned int next_db = 0;
        sds bestkey = NULL;
        int bestdbid;
        redisDb *db;
        dict *dict;
        dictEntry *de;

        if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||
            server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)
        {
            struct evictionPoolEntry *pool = EvictionPoolLRU;

            while(bestkey == NULL) {
                unsigned long total_keys = 0, keys;

                /* We don't want to make local-db choices when expiring keys,
                 * so to start populate the eviction pool sampling keys from
                 * every DB. 
                 * 先从 dict 中采样 key 并放到 pool 中 */
                for (i = 0; i < server.dbnum; i++) {
                    db = server.db+i;
                    dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ?
                            db->dict : db->expires;
                    if ((keys = dictSize(dict)) != 0) {evictionPoolPopulate(i, dict, db->dict, pool);
                        total_keys += keys;
                    }
                }
                if (!total_keys) break; /* No keys to evict. */

                /* 从 pool 中抉择最适宜淘汰的 key. */
                for (k = EVPOOL_SIZE-1; k >= 0; k--) {if (pool[k].key == NULL) continue;
                    bestdbid = pool[k].dbid;

                    if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {de = dictFind(server.db[pool[k].dbid].dict,
                            pool[k].key);
                    } else {de = dictFind(server.db[pool[k].dbid].expires,
                            pool[k].key);
                    }

                    /* 从淘汰池中移除. */
                    if (pool[k].key != pool[k].cached)
                        sdsfree(pool[k].key);
                    pool[k].key = NULL;
                    pool[k].idle = 0;

                    /* If the key exists, is our pick. Otherwise it is
                     * a ghost and we need to try the next element. */
                    if (de) {bestkey = dictGetKey(de);
                        break;
                    } else {/* Ghost... Iterate again. */}
                }
            }
        }

        /* volatile-random and allkeys-random 策略 */
        else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
                 server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
        {
            /* 当随机淘汰时，咱们用动态变量 next_db 来存储以后执行到哪个 db 了 */
            for (i = 0; i < server.dbnum; i++) {j = (++next_db) % server.dbnum;
                db = server.db+j;
                dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ?
                        db->dict : db->expires;
                if (dictSize(dict) != 0) {de = dictGetRandomKey(dict);
                    bestkey = dictGetKey(de);
                    bestdbid = j;
                    break;
                }
            }
        }

        /* 从 dict 中移除被选中的 key. */
        if (bestkey) {
            db = server.db+bestdbid;
            robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
            propagateExpire(db,keyobj,server.lazyfree_lazy_eviction);
            /* 咱们独自计算 db*Delete()开释的内存量。实际上，在 AOF 和正本流传所需的内存可能大于咱们正在开释的内存（删除 key），如果咱们思考这点的话会很绕。由 signalModifiedKey 生成的 CSC 生效音讯也是这样。因为 AOF 和输入缓冲区内存最终会被开释，所以咱们只须要关怀 key 空间应用的内存即可。*/
            delta = (long long) zmalloc_used_memory();
            latencyStartMonitor(eviction_latency);
            if (server.lazyfree_lazy_eviction)
                dbAsyncDelete(db,keyobj);
            else
                dbSyncDelete(db,keyobj);
            latencyEndMonitor(eviction_latency);
            latencyAddSampleIfNeeded("eviction-del",eviction_latency);
            delta -= (long long) zmalloc_used_memory();
            mem_freed += delta;
            server.stat_evictedkeys++;
            signalModifiedKey(NULL,db,keyobj);
            notifyKeyspaceEvent(NOTIFY_EVICTED, "evicted",
                keyobj, db->id);
            decrRefCount(keyobj);
            keys_freed++;

            if (keys_freed % 16 == 0) {
                /* 当要开释的内存开始足够大时，咱们可能会在这里破费太多工夫，不可能足够快地将数据传送到正本，因而咱们会在循环中强制传输。*/
                if (slaves) flushSlavesOutputBuffers();

                /* 通常咱们的进行条件是开释一个固定的，事后计算的内存量。然而，当咱们 * 在另一个线程中删除对象时，最好不断 * 查看是否曾经达到目标 * 内存，因为“mem\u freed”量只在 dbAsyncDelete（）调用中 * 计算，而线程能够 * 始终开释内存。*/
                if (server.lazyfree_lazy_eviction) {if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {break;}
                }

                /* 一段时间后，尽早退出循环 - 即便尚未达到内存限度 *。如果咱们忽然须要开释大量的内存，不要在这里花太多工夫。*/
                if (elapsedUs(evictionTimer) > eviction_time_limit_us) {
                    // We still need to free memory - start eviction timer proc
                    if (!isEvictionProcRunning) {
                        isEvictionProcRunning = 1;
                        aeCreateTimeEvent(server.el, 0,
                                evictionTimeProc, NULL, NULL);
                    }
                    break;
                }
            }
        } else {goto cant_free; /* nothing to free... */}
    }
    /* at this point, the memory is OK, or we have reached the time limit */
    result = (isEvictionProcRunning) ? EVICT_RUNNING : EVICT_OK;

cant_free:
    if (result == EVICT_FAIL) {
        /* At this point, we have run out of evictable items.  It's possible
         * that some items are being freed in the lazyfree thread.  Perform a
         * short wait here if such jobs exist, but don't wait long.  */
        if (bioPendingJobsOfType(BIO_LAZY_FREE)) {usleep(eviction_time_limit_us);
            if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) {result = EVICT_OK;}
        }
    }

    latencyEndMonitor(latency);
    latencyAddSampleIfNeeded("eviction-cycle",latency);
    return result;
}

执行的过程能够简略分为三步，首先按不同的配置策略填充 evictionPoolEntry，pool 大小默认是 16，而后从这 16 个 key 中依据具体策略选出最适宜被删掉的 key(bestkey)，而后执行 bestkey 的删除和一些后续逻辑。

总结

能够看出，Redis 为了性能，就义了 LRU 和 LFU 的准确性，只能说是近似 LRU 和 LFU，但在理论应用过程中也齐全足够了，毕竟 Redis 这么多年也是经验了有数我的项目的考验仍旧耸立不倒。Redis 的这种设计方案也给咱们软件设计时提供了一条新的思路，就义精确度来换取性能。

本文是 Redis 源码分析系列博文，同时也有与之对应的 Redis 中文正文版，有想深刻学习 Redis 的同学，欢送 star 和关注。
Redis 中文注解版仓库：https://github.com/xindoo/Redis
Redis 源码分析专栏：https://zxs.io/s/1h
如果感觉本文对你有用，欢送 一键三连。