完全掌握Redis的LRU缓存淘汰算法实现

2022-04-12 0 821

本篇文章给大家带来了关于Redis的相关知识,其中主要介绍了LRU缓存淘汰算法实现,包括了Redis的近似LRU算法实现、近似LRU算法的实际执行等等,希望对大家有帮助。

完全掌握Redis的LRU缓存淘汰算法实现

推荐学习:Redis学习教程

1 标准LRU的实现原理

LRU,最近最少使用(Least Recently Used,LRU),经典缓存算法。

LRU会使用一个链表维护缓存中每个数据的访问情况,并根据数据的实时访问,调整数据在链表中的位置,然后通过数据在链表中的位置,表示数据是最近刚访问的,还是已有段时间未访问。

LRU会把链头、尾分别设为MRU端和LRU端:

MRU,Most Recently Used 缩写,表示此处数据刚被访问LRU端,此处数据最近最少被访问的数据

LRU可分成如下情况:

case1:当有新数据插入,LRU会把该数据插入到链首,同时把原来链表头部的数据及其之后的数据,都向尾部移动一位case2:当有数据刚被访问一次后,LRU会把该数据从它在链表中当前位置,移动到链首。把从链表头部到它当前位置的其他数据,都向尾部移动一位case3:当链表长度无法再容纳更多数据,再有新数据插入,LRU去除链表尾部的数据,这也相当于将数据从缓存中淘汰掉

case2图解:链表长度为5,从链表头部到尾部保存的数据分别是5,33,9,10,8。假设数据9被访问一次,则9就会被移动到链表头部,同时,数据5和33都要向链表尾部移动一位。

完全掌握Redis的LRU缓存淘汰算法实现

所以若严格按LRU实现,假设Redis保存的数据较多,还要在代码中实现:

为Redis使用最大内存时,可容纳的所有数据维护一个链表

需额外内存空间来保存链表

每当有新数据插入或现有数据被再次访问,需执行多次链表操作

在访问数据的过程中,让Redis受到数据移动和链表操作的开销影响

最终导致降低Redis访问性能。

所以,无论是为节省内存 or 保持Redis高性能,Redis并未严格按LRU基本原理实现,而是提供了一个近似LRU算法实现

2 Redis的近似LRU算法实现

Redis的内存淘汰机制是如何启用近似LRU算法的?redis.conf中的如下配置参数:

maxmemory,设定Redis server可使用的最大内存容量,一旦server使用实际内存量超出该阈值,server会根据maxmemory-policy配置策略,执行内存淘汰操作

maxmemory-policy,设定Redis server内存淘汰策略,包括近似LRU、LFU、按TTL值淘汰和随机淘汰等

完全掌握Redis的LRU缓存淘汰算法实现

所以,一旦设定maxmemory选项,且将maxmemory-policy配为allkeys-lru或volatile-lru,近似LRU就被启用。allkeys-lru和volatile-lru都会使用近似LRU淘汰数据,区别在于:

allkeys-lru是在所有的KV对中筛选将被淘汰的数据volatile-lru在设置了TTL的KV对中筛选将被淘汰数据

Redis如何实现近似LRU算法的呢?

全局LRU时钟值的计算

如何计算全局LRU时钟值的,以用来判断数据访问的时效性

键值对LRU时钟值的初始化与更新

哪些函数中对每个键值对对应的LRU时钟值,进行初始化与更新

近似LRU算法的实际执行

如何执行近似LRU算法,即何时触发数据淘汰,以及实际淘汰的机制实现

2.1 全局LRU时钟值的计算

近似LRU算法仍需区分不同数据的访问时效性,即Redis需知道数据的最近一次访问时间。因此,有了LRU时钟:记录数据每次访问的时间戳。

Redis对每个KV对中的V,会使用个redisObject结构体保存指向V的指针。那redisObject除记录值的指针,还会使用24 bits保存LRU时钟信息,对应的是lru成员变量。这样,每个KV对都会把它最近一次被访问的时间戳,记录在lru变量。

redisObject定义包含lru成员变量的定义:

完全掌握Redis的LRU缓存淘汰算法实现

每个KV对的LRU时钟值是如何计算的?Redis Server使用一个实例级别的全局LRU时钟,每个KV对的LRU time会根据全局LRU时钟进行设置。

这全局LRU时钟保存在Redis全局变量server的成员变量lruclock

完全掌握Redis的LRU缓存淘汰算法实现

当Redis Server启动后,调用initServerConfig初始化各项参数时,会调用getLRUClock设置lruclock的值:

完全掌握Redis的LRU缓存淘汰算法实现

于是,就得注意,**若一个数据前后两次访问的时间间隔<1s,那这两次访问的时间戳就是一样的!**因为LRU时钟精度就是1s,它无法区分间隔小于1秒的不同时间戳!

getLRUClock函数将获得的UNIX时间戳,除以LRU_CLOCK_RESOLUTION后,就得到了以LRU时钟精度来计算的UNIX时间戳,也就是当前的LRU时钟值。

getLRUClock会把LRU时钟值和宏定义LRU_CLOCK_MAX(LRU时钟能表示的最大值)做与运算。

完全掌握Redis的LRU缓存淘汰算法实现

所以默认情况下,全局LRU时钟值是以1s为精度计算得UNIX时间戳,且是在initServerConfig中进行的初始化。

那Redis Server运行过程中,全局LRU时钟值是如何更新的?和Redis Server在事件驱动框架中,定期运行的时间事件所对应的serverCron有关。

serverCron作为时间事件的回调函数,本身会周期性执行,其频率值由redis.conf的hz配置项决定,默认值10,即serverCron函数会每100ms(1s/10 = 100ms)运行一次。serverCron中,全局LRU时钟值就会按该函数执行频率,定期调用getLRUClock进行更新:

完全掌握Redis的LRU缓存淘汰算法实现

这样,每个KV对就能从全局LRU时钟获取最新访问时间戳。

对于每个KV对,它对应的redisObject.lru在哪些函数进行初始化和更新的呢?

2.2 键值对LRU时钟值的初始化与更新

对于一个KV对,其LRU时钟值最初是在这KV对被创建时,进行初始化设置的,这初始化操作在createObject函数中调用,当Redis要创建一个KV对,就会调用该函数。

createObject除了会给redisObject分配内存空间,还会根据maxmemory_policy配置,初始化设置redisObject.lru。

若maxmemory_policy=LFU,则lru变量值会被初始化设置为LFU算法的计算值maxmemory_policy≠LFU,则createObject调用LRU_CLOCK设置lru值,即KV对对应的LRU时钟值。

LRU_CLOCK返回当前全局LRU时钟值。因为一个KV对一旦被创建,就相当于有了次访问,其对应LRU时钟值就表示了它的访问时间戳:

完全掌握Redis的LRU缓存淘汰算法实现

那一个KV对的LRU时钟值又是何时再被更新?

只要一个KV对被访问,其LRU时钟值就会被更新!而当一个KV对被访问时,访问操作最终都会调用lookupKey

lookupKey会从全局哈希表中查找要访问的KV对。若该KV对存在,则lookupKey会根据maxmemory_policy的配置值,来更新键值对的LRU时钟值,也就是它的访问时间戳。

而当maxmemory_policy没有配置为LFU策略时,lookupKey函数就会调用LRU_CLOCK函数,来获取当前的全局LRU时钟值,并将其赋值给键值对的redisObject结构体中的lru变量

完全掌握Redis的LRU缓存淘汰算法实现

这样,每个KV对一旦被访问,就能获得最新的访问时间戳。但你可能好奇:这些访问时间戳最终是如何被用于近似LRU算法进行数据淘汰的?

2.3 近似LRU算法的实际执行

Redis之所以实现近似LRU,是为减少内存资源和操作时间上的开销。

2.3.1 何时触发算法执行?

近似LRU主要逻辑在performEvictions。

performEvictions被evictionTimeProc调用,而evictionTimeProc函数又是被processCommand调用。

processCommand,Redis处理每个命令时都会调用:

完全掌握Redis的LRU缓存淘汰算法实现然后,isSafeToPerformEvictions还会再次根据如下条件判断是否继续执行performEvictions:

完全掌握Redis的LRU缓存淘汰算法实现

完全掌握Redis的LRU缓存淘汰算法实现

一旦performEvictions被调用,且maxmemory-policy被设置为allkeys-lru或volatile-lru,近似LRU就被触发执行了。

2.3.2 近似LRU具体执行过程

执行可分成如下步骤:

2.3.2.1 判断当前内存使用情况

调用getMaxmemoryState评估当前内存使用情况,判断当前Redis Server使用内存容量是否超过maxmemory配置值。

若未超过maxmemory,则返回C_OK,performEvictions也会直接返回。

完全掌握Redis的LRU缓存淘汰算法实现

getMaxmemoryState评估当前内存使用情况的时候,若发现已用内存超出maxmemory,会计算需释放的内存量。这个释放内存大小=已使用内存量-maxmemory。

但已使用内存量并不包括用于主从复制的复制缓冲区大小,这是getMaxmemoryState通过调用freeMemoryGetNotCountedMemory计算的。

完全掌握Redis的LRU缓存淘汰算法实现

而若当前Server使用的内存量超出maxmemory上限,则performEvictions会执行while循环淘汰数据释放内存。

为淘汰数据,Redis定义数组EvictionPoolLRU,保存待淘汰的候选KV对,元素类型是evictionPoolEntry结构体,保存了待淘汰KV对的空闲时间idle、对应K等信息:

完全掌握Redis的LRU缓存淘汰算法实现

完全掌握Redis的LRU缓存淘汰算法实现

这样,Redis Server在执行initSever进行初始化时,会调用evictionPoolAlloc为EvictionPoolLRU数组分配内存空间,该数组大小由EVPOOL_SIZE决定,默认可保存16个待淘汰的候选KV对。

performEvictions在淘汰数据的循环流程中,就会更新这个待淘汰的候选KV对集合,即EvictionPoolLRU数组。

2.3.2.2 更新待淘汰的候选KV对集合

performEvictions调用evictionPoolPopulate,其会先调用dictGetSomeKeys,从待采样哈希表随机获取一定数量K:

dictGetSomeKeys采样的哈希表,由maxmemory_policy配置项决定:若maxmemory_policy=allkeys_lru,则待采样哈希表是Redis Server的全局哈希表,即在所有KV对中采样否则,待采样哈希表就是保存着设置了TTL的K的哈希表。

完全掌握Redis的LRU缓存淘汰算法实现

dictGetSomeKeys采样的K的数量由配置项maxmemory-samples决定,默认5:

完全掌握Redis的LRU缓存淘汰算法实现

于是,dictGetSomeKeys返回采样的KV对集合。evictionPoolPopulate根据实际采样到的KV对数量count,执行循环:调用estimateObjectIdleTime计算在采样集合中的每一个KV对的空闲时间:

完全掌握Redis的LRU缓存淘汰算法实现

接着,evictionPoolPopulate遍历待淘汰的候选KV对集合,即EvictionPoolLRU数组,尝试把采样的每个KV对插入EvictionPoolLRU数组,取决于如下条件之一:

能在数组中找到一个尚未插入KV对的空位能在数组中找到一个KV对的空闲时间<采样KV对的空闲时间

有一成立,evictionPoolPopulate就能把采样KV对插入EvictionPoolLRU数组。等所有采样键值对都处理完后,evictionPoolPopulate函数就完成对待淘汰候选键值对集合的更新了。

接下来,performEvictions开始选择最终被淘汰的KV对。

2.3.2.3 选择被淘汰的KV对并删除

因evictionPoolPopulate已更新EvictionPoolLRU数组,且该数组里的K,是按空闲时间从小到大排好序了。所以,performEvictions遍历一次EvictionPoolLRU数组,从数组的最后一个K开始选择,若选到的K非空,就把它作为最终淘汰的K。

该过程执行逻辑:

完全掌握Redis的LRU缓存淘汰算法实现

一旦选到被淘汰的K,performEvictions就会根据Redis server的惰性删除配置,执行同步删除或异步删除:

完全掌握Redis的LRU缓存淘汰算法实现

至此,performEvictions就淘汰了一个K。若此时释放的内存空间还不够,即没有达到待释放空间,则performEvictions还会重复执行前面所说的更新待淘汰候选KV对集合、选择最终淘汰K的过程,直到满足待释放空间的大小要求。

performEvictions流程:

完全掌握Redis的LRU缓存淘汰算法实现

近似LRU算法并未使用耗时且耗空间的链表,而使用固定大小的待淘汰数据集合,每次随机选择一些K加入待淘汰数据集合。

最后,按待淘汰集合中K的空闲时间长度,删除空闲时间最长的K。

总结

根据LRU算法的基本原理,发现若严格按基本原理实现LRU算法,则开发的系统就需要额外内存空间保存LRU链表,系统运行时也会受到LRU链表操作的开销影响。

而Redis的内存资源和性能都很重要,所以Redis实现近似LRU算法:

首先是设置了全局LRU时钟,并在KV对创建时获取全局LRU时钟值作为访问时间戳,及在每次访问时获取全局LRU时钟值,更新访问时间戳然后,当Redis每处理一个命令,都调用performEvictions判断是否需释放内存。若已使用内存超出maxmemory,则随机选择一些KV对,组成待淘汰候选集合,并根据它们的访问时间戳,选出最旧数据淘汰

一个算法的基本原理和算法的实际执行,在系统开发中会有一定折中,需综合考虑所开发的系统,在资源和性能方面的要求,以避免严格按照算法实现带来的资源和性能开销。

推荐学习:Redis教程

收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

【声明:根据2013年1月30日《计算机软件保护条例》2次修订第17条规定: 为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存 储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬! 鉴于此,也希望大家按此说明研究软件!】
本站所有源码尽量保证原汁原味,如有特殊情况会作出声明及标注,网站资源不做任何二次加密(原版加密除外,不影响程序使用的不会做解密处理),方便您更好的学习参考。 在您的能力范围内,为了大环境的良性发展,请尽可能的选择正版资源。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

即刻码站__国内靠谱的站长资源下载平台 php教程 完全掌握Redis的LRU缓存淘汰算法实现 https://www.jike1995.com/33030.html

常见问题
  • 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用
查看详情
  • 最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度
查看详情

相关文章

发表评论
暂无评论
官方客服团队

为您解决烦忧 - 24小时在线 专业服务