LRU Cache #

LRU 全称是 Least Recently Used，即最近最久未使用的意思。

LRU 算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

LRU-K #

LRU-K 中的 K 代表最近使用的次数，因此 LRU 可以认为是 LRU-1。

LRU-K 的主要目的是为了解决 LRU 算法 “缓存污染” 的问题，其核心思想是将 “最近使用过 1 次” 的判断标准扩展为 “最近使用过 K 次”。

Redis 的 LRU 实现 #

如果按照 HashMap 和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以 Redis 采用了一个近似的做法，就是随机取出若干个 key，然后按照访问时间排序后，淘汰掉最不经常使用的，具体分析如下：

为了支持 LRU，Redis 2.8.19 中使用了一个全局的 LRU 时钟，server.lruclock，定义如下，

#define REDIS_LRU_BITS 24
unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */

默认的 LRU 时钟的分辨率是 1 秒，可以通过改变 REDIS_LRU_CLOCK_RESOLUTION 宏的值来改变，Redis 会在 serverCron() 中调用 updateLRUClock 定期的更新 LRU 时钟，更新的频率和 hz 参数有关，默认为 100ms 一次，如下，

#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1 /* LRU clock resolution in seconds */

void updateLRUClock(void) {
    server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) &
                                                REDIS_LRU_CLOCK_MAX;
}

server.unixtime 是系统当前的 unix 时间戳，当 lruclock 的值超出 REDIS_LRU_CLOCK_MAX 时，会从头开始计算，所以在计算一个 key 的最长没有访问时间时，可能 key 本身保存的 lru 访问时间会比当前的 lrulock 还要大，这个时候需要计算额外时间，如下，

/* Given an object returns the min number of seconds the object was never
 * requested, using an approximated LRU algorithm. */
unsigned long estimateObjectIdleTime(robj *o) {
    if (server.lruclock >= o->lru) {
        return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
    } else {
        return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) *
                    REDIS_LRU_CLOCK_RESOLUTION;
    }
}

Redis 支持和 LRU 相关淘汰策略包括，

volatile-lru 设置了过期时间的 key 参与近似的 lru 淘汰策略
allkeys-lru 所有的 key 均参与近似的 lru 淘汰策略

当进行 LRU 淘汰时，Redis 按如下方式进行的，

......
            /* volatile-lru and allkeys-lru policy */
            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            {
                for (k = 0; k < server.maxmemory_samples; k++) {
                    sds thiskey;
                    long thisval;
                    robj *o;

                    de = dictGetRandomKey(dict);
                    thiskey = dictGetKey(de);
                    /* When policy is volatile-lru we need an additional lookup
                     * to locate the real key, as dict is set to db->expires. */
                    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
                        de = dictFind(db->dict, thiskey);
                    o = dictGetVal(de);
                    thisval = estimateObjectIdleTime(o);

                    /* Higher idle time is better candidate for deletion */
                    if (bestkey == NULL || thisval > bestval) {
                        bestkey = thiskey;
                        bestval = thisval;
                    }
                }
            }
            ......

Redis 会基于 server.maxmemory_samples 配置选取固定数目的 key，然后比较它们的 lru 访问时间，然后淘汰最近最久没有访问的 key，maxmemory_samples 的值越大，Redis 的近似 LRU 算法就越接近于严格 LRU 算法，但是相应消耗也变高，对性能有一定影响，样本值默认为 5。

总结

看来，虽然一个简单的概念，在工业界的产品中，为了追求空间的利用率，也会采用权衡的实现方案。

LRU Cache #

LRU-K #

Redis 的 LRU 实现 #

参考 #