Redis作为LRU Cache的实现

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
云数据库 MongoDB,独享型 2核8GB
推荐场景:
构建全方位客户视图
云原生多模数据库 Lindorm,多引擎 多规格 0-4节点
简介: Redis作为目前最流行的KV内存数据库,也实现了自己的`LRU`(`Latest Recently Used`)算法,在内存写满的时候,依据其进行数据的淘汰。但是,`Redis`为了节省内存使用,和通常的LRU算法实现不太一样,Redis使用了采样的方法来模拟一个`近似LRU`算法。

公有云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算法的差异,

lru_comparison.png

图中深灰色和浅灰色的点表示的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,敬请期待。

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
2月前
|
存储 缓存 NoSQL
【Azure Redis 缓存】关于Azure Cache for Redis 服务在传输和存储键值对(Key/Value)的加密问题
【Azure Redis 缓存】关于Azure Cache for Redis 服务在传输和存储键值对(Key/Value)的加密问题
|
2月前
|
NoSQL Unix 网络安全
【Azure Cache for Redis】Python Django-Redis连接Azure Redis服务遇上(104, 'Connection reset by peer')
【Azure Cache for Redis】Python Django-Redis连接Azure Redis服务遇上(104, 'Connection reset by peer')
【Azure Cache for Redis】Python Django-Redis连接Azure Redis服务遇上(104, 'Connection reset by peer')
|
2月前
|
缓存 弹性计算 NoSQL
【Azure Redis 缓存 Azure Cache For Redis】Redis连接池
【Azure Redis 缓存 Azure Cache For Redis】Redis连接池
|
2月前
|
NoSQL 网络协议 Redis
【Azure Redis】AKS中使用Lettuce连接Redis Cache出现 timed out 问题的解决思路
【Azure Redis】AKS中使用Lettuce连接Redis Cache出现 timed out 问题的解决思路
【Azure Redis】AKS中使用Lettuce连接Redis Cache出现 timed out 问题的解决思路
|
2月前
|
NoSQL Redis 容器
【Azure Cache for Redis】Redis的导出页面无法配置Storage SAS时通过az cli来完成
【Azure Cache for Redis】Redis的导出页面无法配置Storage SAS时通过az cli来完成
|
2月前
|
存储 缓存 NoSQL
【Azure Redis 缓存 Azure Cache For Redis】如何设置让Azure Redis中的RDB文件暂留更久(如7天)
【Azure Redis 缓存 Azure Cache For Redis】如何设置让Azure Redis中的RDB文件暂留更久(如7天)
|
2月前
|
缓存 NoSQL Redis
【Azure Redis 缓存】Azure Cache for Redis 服务的导出RDB文件无法在自建的Redis服务中导入
【Azure Redis 缓存】Azure Cache for Redis 服务的导出RDB文件无法在自建的Redis服务中导入
|
2月前
|
缓存 开发框架 NoSQL
【Azure Redis 缓存】VM 里的 Redis 能直接迁移到 Azure Cache for Redis ? 需要改动代码吗?
【Azure Redis 缓存】VM 里的 Redis 能直接迁移到 Azure Cache for Redis ? 需要改动代码吗?
|
2月前
|
缓存 NoSQL Unix
【Azure Redis 缓存】Azure Cache for Redis 中如何快速查看慢指令情况(Slowlogs)
【Azure Redis 缓存】Azure Cache for Redis 中如何快速查看慢指令情况(Slowlogs)
|
2月前
|
缓存 NoSQL Redis
【Azure Redis 缓存】Azure Cache for Redis 是否记录具体读/写(Get/Set)或删除(Del)了哪些key呢?
【Azure Redis 缓存】Azure Cache for Redis 是否记录具体读/写(Get/Set)或删除(Del)了哪些key呢?

相关产品

  • 云数据库 Tair(兼容 Redis)