Redis作为LRU Cache的实现

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 MongoDB,独享型 2核8GB
推荐场景:
构建全方位客户视图
简介: 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 */
AI 代码解读

默认的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;
}
AI 代码解读

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;
    }
}
AI 代码解读

这样计算会不会有问题呢?还是有的,即某个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;
                    }
                }
            }
            ......
AI 代码解读

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;
    }
}
AI 代码解读

总结

如果采用双向链表+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
目录
打赏
0
0
0
1
9134
分享
相关文章
【Azure Redis 缓存】关于Azure Cache for Redis 服务在传输和存储键值对(Key/Value)的加密问题
【Azure Redis 缓存】关于Azure Cache for Redis 服务在传输和存储键值对(Key/Value)的加密问题
【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')
【Azure Redis 缓存 Azure Cache For Redis】Redis连接池
【Azure Redis 缓存 Azure Cache For Redis】Redis连接池
大数据-47 Redis 缓存过期 淘汰删除策略 LRU LFU 基础概念
大数据-47 Redis 缓存过期 淘汰删除策略 LRU LFU 基础概念
94 2
【Azure Redis】AKS中使用Lettuce连接Redis Cache出现 timed out 问题的解决思路
【Azure Redis】AKS中使用Lettuce连接Redis Cache出现 timed out 问题的解决思路
117 1
【Azure Redis】AKS中使用Lettuce连接Redis Cache出现 timed out 问题的解决思路
【Azure Cache for Redis】Redis的导出页面无法配置Storage SAS时通过az cli来完成
【Azure Cache for Redis】Redis的导出页面无法配置Storage SAS时通过az cli来完成
【Azure Redis 缓存】Azure Cache for Redis 服务的导出RDB文件无法在自建的Redis服务中导入
【Azure Redis 缓存】Azure Cache for Redis 服务的导出RDB文件无法在自建的Redis服务中导入
【Azure Redis 缓存】VM 里的 Redis 能直接迁移到 Azure Cache for Redis ? 需要改动代码吗?
【Azure Redis 缓存】VM 里的 Redis 能直接迁移到 Azure Cache for Redis ? 需要改动代码吗?
【Azure Redis 缓存】Azure Cache for Redis 中如何快速查看慢指令情况(Slowlogs)
【Azure Redis 缓存】Azure Cache for Redis 中如何快速查看慢指令情况(Slowlogs)
【Azure Redis 缓存】Azure Cache for Redis 是否记录具体读/写(Get/Set)或删除(Del)了哪些key呢?
【Azure Redis 缓存】Azure Cache for Redis 是否记录具体读/写(Get/Set)或删除(Del)了哪些key呢?

相关产品

  • 云数据库 Tair(兼容 Redis)
  • AI助理

    你好,我是AI助理

    可以解答问题、推荐解决方案等