Redis 源码剖析与实战
蒋德钧
中科院计算所副研究员
17049 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 47 讲
Redis 源码剖析与实战
15
15
1.0x
00:00/00:00
登录|注册

15 | 为什么LRU算法原理和代码实现不一样?

你好,我是蒋德钧。
从这节课开始,我们就进入了课程的第三个模块:缓存模块。在接下来的三节课当中,我会给你详细介绍 LRU、LFU 算法在 Redis 源码中的实现,以及 Redis 惰性删除对缓存的影响。
学习这部分内容,一方面可以让你掌握这些经典缓存算法在一个实际系统中该如何设计和实现;另一方面,你也可以学习到在计算机系统设计实现中的一个重要原则,也就是在进行系统设计开发的过程中,需要均衡算法复杂度和实现复杂度。另外,你还可以学习到缓存替换、惰性删除是如何释放 Redis 内存的。内存资源对 Redis 来说是非常宝贵的,所以掌握了这一点,你就可以有效减少 Redis 的内存使用问题了。
好,那么今天这节课呢,我们就先来学习下 LRU 算法在 Redis 中的实现。

LRU 算法的基本原理

首先,我们需要理解 LRU 算法的基本原理。LRU 算法就是指最近最少使用(Least Recently Used,LRU)算法,这是一个经典的缓存算法。
从基本原理上来说,LRU 算法会使用一个链表来维护缓存中每一个数据的访问情况,并根据数据的实时访问,调整数据在链表中的位置,然后通过数据在链表中的位置,来表示数据是最近刚访问的,还是已经有一段时间没有访问了。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Redis 源码剖析与实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(11)

  • 最新
  • 精选
  • Kaito
    1、实现一个严格的 LRU 算法,需要额外的内存构建 LRU 链表,同时维护链表也存在性能开销,Redis 对于内存资源和性能要求极高,所以没有采用严格 LRU 算法,而是采用「近似」LRU 算法实现数据淘汰策略 2、触发数据淘汰的时机,是每次处理「请求」时判断的。也就是说,执行一个命令之前,首先要判断实例内存是否达到 maxmemory,是的话则先执行数据淘汰,再执行具体的命令 3、淘汰数据时,会「持续」判断 Redis 内存是否下降到了 maxmemory 以下,不满足的话会继续淘汰数据,直到内存下降到 maxmemory 之下才会停止 4、可见,如果发生大量淘汰的情况,那么处理客户端请求就会发生「延迟」,影响性能 5、Redis 计算实例内存时,不会把「主从复制」的缓冲区计算在内,也就是说不管一个实例后面挂了多少个从库,主库不会把主从复制所需的「缓冲区」内存,计算到实例内存中,即这部分内存增加,不会对数据淘汰产生影响 6、但如果 Redis 内存已达到 maxmemory,要谨慎执行 MONITOR 命令,因为 Redis Server 会向执行 MONITOR 的 client 缓冲区填充数据,这会导致缓冲区内存增长,进而引发数据淘汰 课后题:为什么键值对的 LRU 时钟值,不是直接通过调用 getLRUClock 函数来获取? 本质上是为了性能。 Redis 这种对性能要求极高的数据库,在系统调用上的优化也做到了极致。 获取机器时钟本质上也是一个「系统调用」,对于 Redis 这种动不动每秒上万的 QPS,如果每次都触发一次系统调用,这么频繁的操作也是一笔不小的开销。 所以,Redis 用一个定时任务(serverCron 函数),以固定频率触发系统调用获取机器时钟,然后把机器时钟挂到 server 的全局变量下,这相当于维护了一个「本地缓存」,当需要获取时钟时,直接从全局变量获取即可,节省了大量的系统调用开销。
    6
    32
  • Darren
    6.2的版本中,增加了maxmemory-eviction-tenacity配置,目的是控制大量淘汰内存空间阻塞客户端的时间。 6.2的版本中没有了freeMemoryIfNeeded 和 freeMemoryIfNeededAndSafe函数,而是被performEvictions替代 然后在执行内存释放期间,耗时统计,超过限制时间,新增时间事件,然后结束循环,流程继续往下执行。 // 如果执行释放空间超过限制时间,则添加一个时间事件,时间事件中继续释放内存 if (elapsedUs(evictionTimer) > eviction_time_limit_us) { // We still need to free memory - start eviction timer proc if (!isEvictionProcRunning) { isEvictionProcRunning = 1; // 新增时间时间 aeCreateTimeEvent(server.el, 0, evictionTimeProc, NULL, NULL); } break; } 如果一次时间事件没结束,则该时间事件不结束,等待一段时间,继续执行 // 如果返回值不是AE_NOMORE,则继续把当前事件间隔retval毫秒后继续执行 if (retval != AE_NOMORE) { te->when = now + retval * 1000; } else { te->id = AE_DELETED_EVENT_ID; }
    8
  • Ethan New
    server.lruclock相当于是一个缓存值,serverCron每100ms更新一次server.lruclock,避免了频繁进行系统调用获取系统时钟
    4
  • 曾轼麟
    首先回答老师的问题: 是为了均衡性能和精度才这样设计的,如果server.hz设置的值小,精度要求小于LRU_CLOCK_RESOLUTION全局的频率精度,那么直接获预先计算的值对性能友好。如果server.hz设置的值较大,精度要求高于LRU_CLOCK_RESOLUTION的精度,那么就会在每次通过getLRUClock函数计算出结果。此外atomicGet的方法证明server.lruclock这个值是可能并发修改。此外在getLRUClock方法中,其本身是调用gettimeofday这个操作系统级别的API获取的。 本篇文章老师介绍了Redis-LRU的实现: 1、为了妥协性能和资源,Redis使用的是,近似LRU算法,并且通过全局时钟去预计算LRU时钟的值。 2、通过每次调用命令都访问freeMemoryIfNeeded函数,判断是否需要释放内存,从而保证Redis能及时通过淘汰算法进行数据驱逐,而保证服务正常运行。 3、serverCron时间事件,会定期执行全局LRU时钟的更新,而在后续的运行中如果精度设置的要求不高基本上都会使用预先计算好的值。
    3
  • Geek_3b4ae8
    假设第一次执行lru。数组里面没有元素。随机采样5个,那此时这5个都能插入数组,也就都会被淘汰。但是这5个不一定是最近最少使用的啊,甚至可能是最近最常使用的啊。这里不太明白。感觉就是随机的,并不是lru
    1
    1
  • 可怜大灰狼
    getLRUClock内部是通过gettimeofday系统调用来获取时间。redis的QPS每秒近10w,如果始终通过系统调用,会导致用户态和内核态来回切换,会造成很大的性能损失。
    1
  • JJPeng
    老师,您好。我认为您原文中”如果一个数据前后两次访问的时间间隔小于 1 秒,那么这两次访问的时间戳就是一样的。“这句话的描述是有误的。 因为一秒钟表示一个时间跨度,如果对一个数据的访问分别是在前一秒的结束和后一秒的开始,这样的话,虽然两次操作的时间间隔小于1秒,但LRU时间戳的值应该是不一样的。 反之,如果您的描述正确的话,那在每次时间间隔小于1秒的情况下连续对某个键进行访问,那该键的LRU时间戳就始终与第一次访问时的时间戳保持一致,这样应该是有问题的。
    1
  • 末日,成欢
    while (k < EVPOOL_SIZE && pool[k].key && pool[k].idle < idle) k++; 如果在当前集合中找到一个空闲时间小于采用数据的空闲时间,不应该k++,不是不会增加吗? 应该是大于把?
    1
  • 末日,成欢
    如果配置的时候没有配置maxmemory会怎么样?是不是redis使用内存就无上限了吗?
    1
  • ikel
    这篇开始源码版本又回到5.xx了么
收起评论
显示
设置
留言
11
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部