您当前的位置:首页 > 电脑百科 > 数据库 > Redis

深入解析Redis的LRU与LFU算法实现

时间:2023-07-06 15:01:24  来源:vivo互联网技术  作者:Luo Jianxin

一、前言

redis是一款基于内存的高性能NoSQL数据库,数据都缓存在内存里, 这使得Redis可以每秒轻松地处理数万的读写请求。

相对于磁盘的容量,内存的空间一般都是有限的,为了避免Redis耗尽宿主机的内存空间,Redis内部实现了一套复杂的缓存淘汰策略来管控内存使用量。

Redis 4.0版本开始就提供了8种内存淘汰策略,其中4种都是基于LRU或LFU算法实现的,本文就这两种算法的Redis实现进行了详细的介绍,并阐述其优劣特性。

二、Redis的LRU实现

在介绍Redis LRU算法实现之前,我们先简单介绍一下原生的LRU算法。

2.1 LRU算法原理

LRU(The Least Recently Used)是最经典的一款缓存淘汰算法,其原理是 :如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很低,当数据所占据的空间达到一定阈值时,这个最少被访问的数据将被淘汰掉。

如今,LRU算法广泛应用在诸多系统内,例如linux内核页表交换,MySQL Buffer Pool缓存页替换,以及Redis数据淘汰策略。

以下是一个LRU算法示意图:

图片

 

  1. 向一个缓存空间依次插入三个数据A/B/C,填满了缓存空间;
  2. 读取数据A一次,按照访问时间排序,数据A被移动到缓存头部;
  3. 插入数据D的时候,由于缓存空间已满,触发了LRU的淘汰策略,数据B被移出,缓存空间只保留了D/A/C。

一般而言,LRU算法的数据结构不会如示意图那样,仅使用简单的队列或链表去缓存数据,而是会采用Hash表 + 双向链表的结构,利用Hash表确保数据查找的时间复杂度是O(1),双向链表又可以使数据插入/删除等操作也是O(1)。

图片

 

如果你很熟悉Redis的数据类型,你会发现这个LRU的数据结构与ZSET类型OBJ_ENCODING

_SKIPLIST编码结构相似,只是LRU数据排序方式更简单一些。

2.2 Redis LRU算法实现

按照官方文档的介绍,Redis所实现的是一种近似的LRU算法,每次随机选取一批数据进行LRU淘汰,而不是针对所有的数据,通过牺牲部分准确率来提高LRU算法的执行效率。

Redis内部只使用Hash表缓存了数据,并没有创建一个专门针对LRU算法的双向链表,之所以这样处理也是因为以下几个原因:

  • 筛选规则,Redis是随机抽取一批数据去按照淘汰策略排序,不再需要对所有数据排序;
  • 性能问题,每次数据访问都可能涉及数据移位,性能会有少许损失;
  • 内存问题,Redis对内存的使用一向很“抠门”,数据结构都很精简,尽量不使用复杂的数据结构管理数据;
  • 策略配置,如果线上Redis实例动态修改淘汰策略会触发全部数据的结构性改变,这个Redis系统无法承受的。

redisObject是Redis核心的底层数据结构,成员变量lru字段用于记录了此key最近一次被访问的LRU时钟(server.lruclock),每次Key被访问或修改都会引起lru字段的更新。

#define LRU_BITS 24
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

默认的LRU时钟单位是秒,可以修改LRU_CLOCK_RESOLUTION宏来改变单位,LRU时钟更新的频率也和server.hz参数有关。

unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        atomicGet(server.lruclock,lruclock);
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}

由于lru字段仅占用了24bit的空间,按秒为单位也只能存储194天,所以可能会出现一个意想不到的结果,即间隔194天访问Key后标记的时间戳一样,Redis LRU淘汰策略局部失效。

2.3 LRU算法缺陷

LRU算法仅关注数据的访问时间或访问顺序,忽略了访问次数的价值,在淘汰数据过程中可能会淘汰掉热点数据。

图片

如上图所示,时间轴自左向右,数据A/B/C在同一段时间内被分别访问的数次。数据C是最近一次访问的数据,按照LRU算法排列数据的热度是C>B>A,而数据的真实热度是B>A>C。

这个是LRU算法的原理性问题,自然也会在Redis 近似LRU算法中呈现,为了解决这个问题衍生出来LFU算法。

三、Redis的LFU实现

3.1 LFU算法原理

LFU(Least frequently used)即最不频繁访问,其原理是:如果一个数据在近期被高频率地访问,那么在将来它被再访问的概率也会很高,而访问频率较低的数据将来很大概率不会再使用。

很多人看到上面的描述,会认为LFU算法主要是比较数据的访问次数,毕竟访问次数多了自然访问频率就高啊。实际上,访问频率不能等同于访问次数,抛开访问时间谈访问次数就是在“耍流氓”。

图片

在这段时间片内数据A被访问了5次,数据B与C各被访问了4次,如果按照访问次数判断数据热度值,必然是A>B=C;如果考虑到时效性,距离当前时间越近的访问越有价值,那么数据热度值就应该是C>B>A。因此,LFU算法一般都会有一个时间衰减函数参与热度值的计算,兼顾了访问时间的影响。

LFU算法实现的数据结构与LRU一样,也采用Hash表 + 双向链表的结构,数据在双向链表内按照热度值排序。如果某个数据被访问,更新热度值之重新插入到链表合适的位置,这个比LRU算法处理的流程复杂一些。

3.2 Redis LFU算法实现

Redis 4.0版本开始增加了LFU缓存淘汰策略,也采用数据随机筛选规则,然后依据数据的热度值排序,淘汰掉热度值较低的数据。

3.2.1 LFU算法代码实现

LFU算法的实现没有使用额外的数据结构,复用了redisObject数据结构的lru字段,把这24bit空间拆分成两部分去使用。

图片

  • 由于记录时间戳在空间被压缩到16bit,所以LFU改成以分钟为单位,大概45.5天会出现数值折返,比LRU时钟周期还短。
     
  • 低位的8bit用来记录热度值(counter),8bit空间最大值为255,无法记录数据在访问总次数。

LFU热度值(counter)的算法实现:

#define LFU_INIT_VAL 5
/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
  if (counter == 255) return 255;
  double r = (double)rand()/RAND_MAX;
  double baseval = counter - LFU_INIT_VAL;
  if (baseval < 0) baseval = 0;
  double p = 1.0/(baseval*server.lfu_log_factor+1);
  if (r < p) counter++;
  return counter;
}
  • counter 小于或等于 LFU_INIT_VAL 时候,数据一旦被访问命中, counter接近100%概率递增1;
  • counter 大于 LFU_INIT_VAL 时候,需要先计算两者差值,然后作为分母的一部分参与递增概率的计算;
  • 随着counter 数值的增大,递增的概率逐步衰减,可能数次的访问都不能使其数值加1;
  • 当counter 数值达到255,就不再进行数值递增的计算过程。

LFU counter的计算也并非“一尘不变”,为了适配各种业务数据的特性,Redis在LFU算法实现过程中引入了两个可调参数:

图片

热度值counter的时间衰减函数:
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

阅读完以上的内容,是否感觉似曾相似?实际上LFU counter计算过程就是对访问次数进行了数值归一化,将数据访问次数映射成热度值(counter),数值的范围也从[0,+∞)映射到另一个维度的[0,255]。

3.3.2 LFU Counter分析

仅从代码层面分析研究Redis LFU算法实现会比较抽象且枯燥,无法直观的呈现counter递增概率的算法效果,以及counter数值与访问次数的关系。

在lfu_log_factor为默认值10的场景下,利用Python/ target=_blank class=infotextkey>Python实现Redis LFU算法流程,绘制出LFU counter递增概率曲线图:

图片

可以清晰的观察到,当LFU counter数值超过LFU_INIT_VAL之后,曲线出现了垂直下降,递增概率陡降到0.2%左右,随后在底部形成一个较为缓慢的衰减曲线,直至counter数值达到255则递增概率归于0,贴合3.3.1章节分析的理论。

保持Redis系统配置默认值的情况下,对同一个数据持续的访问,并采集此数据的LFU counter数值,绘制出LFU counter数值曲线图:

图片

随着访问次数的不断增加,LFU counter数值曲线呈现出爬坡式的递增,形态趋近于根号曲线,由此推测出以下观点:

  • 在访问次数相同的情况下,counter数值不是固定的,大概率在一个范围内波动;
  • 在同一个时间段内,数据之间访问次数相差上千次,才可以通过counter数值区分出哪些数据更热,而“温”数据之间可能很难区分热度。

四、总结

通过对Redis LRU与LFU算法实现的介绍,我们可以大体了解两种算法策略的优缺点,在Redis运维过程中,可以依据业务数据的特性去选择相应的算法。

如果业务数据的访问较为均匀,OPS或CPU利用率一般不会出现周期性的陡升或陡降,数据没有体现出相对的“冷热”特性,即建议采用LRU算法,可以满足一般的运维需求。

相反,业务具备很强时效性,在活动推广或大促期间,业务某些数据会突然成为热点数据,监控上呈现出OPS或CPU利用率的大幅波动,为了能抓取热点数据便于后期的分析或优化,建议一定要配置成LFU算法。

在Used_memory接近Maxmemory的情况下,Redis一直都采用随机的方式筛选数据,且筛选的个数极其有限,所以,LFU算法无法展现出较大的优势,也可能会淘汰掉比较热的数据。



Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  Search: Redis  点击:(12)  评论:(0)  加入收藏
Redis“叛逃”开源,得罪了几乎所有人
内存数据库供应商Redis近日在开源界砸下了一块“巨石”。Redis即将转向双许可模式,并实施更为严格的许可条款。官方对此次变更的公告直截了当:从Redis 7.4版本开始,Redis将在Re...【详细内容】
2024-03-25  Search: Redis  点击:(10)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  Search: Redis  点击:(18)  评论:(0)  加入收藏
Redis不再 “开源”
Redis 官方今日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause 开...【详细内容】
2024-03-21  Search: Redis  点击:(9)  评论:(0)  加入收藏
在Redis中如何实现分布式锁的防死锁机制?
在Redis中实现分布式锁是一个常见的需求,可以通过使用Redlock算法来防止死锁。Redlock算法是一种基于多个独立Redis实例的分布式锁实现方案,它通过协调多个Redis实例之间的锁...【详细内容】
2024-02-20  Search: Redis  点击:(49)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  Search: Redis  点击:(40)  评论:(0)  加入收藏
工作中Redis有哪些好用的运维工具
工作中使用 Redis 时,如果大家公司没有专业运维,可能开发人员就会面临这些运维的工作,包括 Redis 的运行状态监控,数据迁移,主从集群、切片集群的部署和运维等等。本文我就从这三...【详细内容】
2024-02-06  Search: Redis  点击:(56)  评论:(0)  加入收藏
深入Go底层原理,重写Redis中间件实战
Go语言以其简洁、高效和并发性能而闻名,深入了解其底层原理可以帮助我们更好地利用其优势。在本文中,我们将探讨如何深入Go底层原理,以及如何利用这些知识重新实现一个简单的Re...【详细内容】
2024-01-25  Search: Redis  点击:(67)  评论:(0)  加入收藏
批量执行Redis命令的四种方式!
前言在我们的印象中Redis命令好像都是一个个单条进行执行的,如果有人问你如何批量执行Redis命令,你能回答的上吗,或者说能答出几种方式呢?最容易想到的是Redis的一些批量命令,例...【详细内容】
2024-01-17  Search: Redis  点击:(60)  评论:(0)  加入收藏
Redis 实现多规则限流的思考与实践
市面上很多介绍redis如何实现限流的,但是大部分都有一个缺点,就是只能实现单一的限流,比如1分钟访问1次或者60分钟访问10次这种,但是如果想一个接口两种规则都需要满足呢,我们的...【详细内容】
2024-01-03  Search: Redis  点击:(109)  评论:(0)  加入收藏
▌简易百科推荐
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  dbaplus社群    Tags:Redis   点击:(12)  评论:(0)  加入收藏
Redis“叛逃”开源,得罪了几乎所有人
内存数据库供应商Redis近日在开源界砸下了一块“巨石”。Redis即将转向双许可模式,并实施更为严格的许可条款。官方对此次变更的公告直截了当:从Redis 7.4版本开始,Redis将在Re...【详细内容】
2024-03-25    51CTO  Tags:Redis   点击:(10)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  后端Q  微信公众号  Tags:Redis   点击:(18)  评论:(0)  加入收藏
Redis不再 “开源”
Redis 官方今日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause 开...【详细内容】
2024-03-21  OSC开源社区    Tags:Redis   点击:(9)  评论:(0)  加入收藏
在Redis中如何实现分布式锁的防死锁机制?
在Redis中实现分布式锁是一个常见的需求,可以通过使用Redlock算法来防止死锁。Redlock算法是一种基于多个独立Redis实例的分布式锁实现方案,它通过协调多个Redis实例之间的锁...【详细内容】
2024-02-20  编程技术汇    Tags:Redis   点击:(49)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  楼仔  微信公众号  Tags:Redis   点击:(40)  评论:(0)  加入收藏
工作中Redis有哪些好用的运维工具
工作中使用 Redis 时,如果大家公司没有专业运维,可能开发人员就会面临这些运维的工作,包括 Redis 的运行状态监控,数据迁移,主从集群、切片集群的部署和运维等等。本文我就从这三...【详细内容】
2024-02-06  waynaqua    Tags:Redis   点击:(56)  评论:(0)  加入收藏
批量执行Redis命令的四种方式!
前言在我们的印象中Redis命令好像都是一个个单条进行执行的,如果有人问你如何批量执行Redis命令,你能回答的上吗,或者说能答出几种方式呢?最容易想到的是Redis的一些批量命令,例...【详细内容】
2024-01-17  小许code  微信公众号  Tags:Redis命令   点击:(60)  评论:(0)  加入收藏
Redis 实现多规则限流的思考与实践
市面上很多介绍redis如何实现限流的,但是大部分都有一个缺点,就是只能实现单一的限流,比如1分钟访问1次或者60分钟访问10次这种,但是如果想一个接口两种规则都需要满足呢,我们的...【详细内容】
2024-01-03  架构精进之路  微信公众号  Tags:Redis   点击:(109)  评论:(0)  加入收藏
一站式Redis解决方案
Redis是一个高效的内存数据库,它支持包括String、List、Set、SortedSet和Hash等数据类型的存储,在Redis中通常根据数据的key查询其value值,Redis没有模糊条件查询,在面对一些需...【详细内容】
2024-01-01  大雷家吃饭    Tags:Redis   点击:(66)  评论:(0)  加入收藏
站内最新
站内热门
站内头条