Redis作为LRU Cache的实现（redis中lru）

公有云Redis服务：https://www.aliyun.com/product/kvstore?spm=5176.8142029.388261.37.59zzzj

背景

Redis作为目前最流行的KV内存数据库，也实现了自己的LRU（Latest Recently Used）算法，在内存写满的时候，依据其进行数据的淘汰。LRU算法本身的含义，这里不做赘述，严格的LRU算法，会优先选择淘汰最久没有访问的数据，这种实现也比较简单，通常是用一个双向链表+一个哈希表来实现O(1)的淘汰和更新操作。但是，Redis为了节省内存使用，和通常的LRU算法实现不太一样，Redis使用了采样的方法来模拟一个近似LRU算法。

下面先给一个图来直观的感受一下Redis的近似LRU算法和严格LRU算法的差异，

图中深灰色和浅灰色的点表示的key数量正好可以写满内存，绿色的点表示刚写入的key，浅灰色的点表示被淘汰的key，深灰色的点表示剩余的没有被淘汰的key。

在严格LRU算法下，图的左上部分，最先写入的一半的key，被顺序淘汰掉了，但是在Redis的近似LRU算法下，图的左下部分，可能出现很早之前写入的key，并没有被淘汰掉，写入时间更晚的key反而被淘汰了，但是也没有出现比较极端的刚刚写入不久的key就被淘汰的情况。

根据Redis作者的说法，如果访问Redis的模式呈现幂律分布，即通常说的二八分布，Redis 2.8的近似LRU算法和严格LRU算法差异不大，下面我们就来看看这个近似LRU算法是怎么实现的。

图的右半部分是Redis 3.0对于近似LRU算法的优化，后面我们会写文章再介绍，同时我们的Redis云服务内核后续也会merge该优化。

Redis LRU算法实现

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

#define REDIS_LRU_BITS 24unsigned 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;

}

}

这样计算会不会有问题呢？还是有的，即某个key就是很久很久没有访问，lruclock从头开始后，又超过了该key保存的lru访问时间，这个时间是多久呢，在现有的lru时钟1秒分辨率下，24bit可以表示的最长时间大约是194天，所以一个key如果连续194天没有访问了，Redis计算该key的idle时间是有误的，但是这种情况应该非常罕见。

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。

每个key的lru访问时间更新比较简单，但是有一点值得注意，为了避免fork子进程后额外的内存消耗，当进行bgsave或aof rewrite时，lru访问时间是不更新的。

robj *lookupKey(redisDb *db, robj *key) {

dictEntry *de = dictFind(db->dict,key->ptr); if (de) {

robj *val = dictGetVal(de); /* Update the access time for the ageing algorithm.

* Don't do it if we have a saving child, as this will trigger

* a copy on write madness. */

if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) val->lru = server.lruclock; return val;

} else { return NULL;

}

}

总结

如果采用双向链表+hash表的方式来实现严格的LRU算法，初步估计每个key要增加额外32个字节左右的内存消耗，当key数量比较多时，还是会带来相当可观的内存消耗，Redis使用近似的LRU算法，每个key只需额外24bit的内存空间，节省还是相当的大的。后面我们会介绍redis 3.x中对近似LRU算法的优化，使用尽量少的内存，使Redis的LRU算法更接近于严格LRU，敬请期待。