Redis作为LRU Cache的实现

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

背景

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

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

Redis作为LRU Cache的实现

图中深灰色和浅灰色的点表示的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 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;
    }
}

这样计算会不会有问题呢?还是有的,即某个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子进程后额外的内存消耗,当进行bgsaveaof 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,敬请期待。

上一篇:20210226计算机科学速成课40集(31-33)


下一篇:系统的入门脑机接口&神经科学,一个网站就够了 - NeuroTechEDU