您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

缓存淘汰之 LRU 算法

时间:2023-06-26 16:04:00  来源:今日头条  作者:阿瑟杰克斯

LRU算法

  • 根据最近访问时间,离当前时间最远的数据优点被淘汰
  • 实现 LRU 算法除了需要 key/value 字典外,还需要附加一个链表,链表中的元素按照一定的顺序进行排列。
  • 当空间满的时候,会踢掉链表尾部的元素。当字典的某个元素被访问时,它在链表中的位置会被移动到表头。
    • 链表的元素排列顺序就是元素最近被访问的时间顺序。

近似 LRU 算法

  • redis 使用的不是完全 LRU 算法
    • 不使用 LRU 算法,为了节省内存,采用随机 LRU 算法
    • Redis 为每一个 key 增加了一个 24bit 的字段,用来记录这个 ke y 最后一次被访问的时间戳
  • Redis 3.0 对 LRU 进行了优化
    • 它会维护一个大小 16 的候选池,其数据根据【访问时间】进行排序
    • 第一次随机选取的 5 个 key 都会放入池中
    • 后续每次随机选取的 key,只有【访问时间】小于候选池中【最小时间】的 key 才会放入池中,直到候选池被放满。
      • 也就是比候选池更老的数据才会放入
    • 当放满后,如果有新的 key 放入,则移除候选池中【访问时间】最小的 key
    • 当需要淘汰时,则直接淘汰候选池中【访问时间】最小的 key
  • 如何采样就是看 maxmemory-policy 的配置
    • 如果是 allkeys 就是从所有的 key 字典中随机
    • 如果是 volatile 就从带过期时间的 key 字典中随机。
  • 每次采样多少个 key 看的是 maxmemory_samples 的配置,默认为 5

LFU

  • Redis 4.0 里引入了一个新的淘汰策略 —— LFU(Least Frequently Used) ,作者认为它比 LRU 更加优秀。
  • LFU 表示按照最近【访问频率】进行淘汰,它比 LRU 更加精准地表示了一个 key 被访问的热度
    • 如果一个 key 长时间不被访问,只是刚刚偶然被用户访问了一下,那么在使用 LRU 算法下它是不容易被淘汰的,因为 LRU 算法认为当前这个 key 是很热的。
    • 而 LFU 是需要追踪最近一段时间的访问频率,如果某个 key 只是偶然被访问一次是不足以变得很热的,它需要在近期一段时间内被访问很多次才有机会被认为很热。

Redis 对象热度的数据结构

Redis 的所有对象头中都有一个字段,用来记录对象的热度, 大小为 24bit

// redis 的对象头
typedef struct redisObject {
    unsigned type:4; // 对象类型如 zset/set/hash 等等
    unsigned encoding:4; // 对象编码如 ziplist/intset/skiplist 等等
    unsigned lru:24; // lfu:热度/ lru:时间戳
    int refcount; // 引用计数
    void *ptr; // 对象的 body
} robj;

LRU 模式

  • 在 LRU 模式下,lru 字段存储的是 Redis 时钟 server.lruclock
  • 它是一个 24bit 的时间戳
    • 默认是 Unix 时间戳对 2^24 取模的结果,大约 97 天清零一次。
  • 当某个 key 被访问一次,它的对象头的 lru 字段值就会被更新为 server.lruclock。

LFU 模式

  • 在 LFU 模式下,lru 字段 24 个 bit 用来存储两个值,它分别是访问频次(logc,logistic counter)和上一次访问的更新时间(ldt,last decrement time)
  • 访问频次
    • logc 是 8 个 bit,用来存储访问频次
    • 因为 8 个 bit 能表示的最大整数值为 255,存储频次肯定远远不够,所以这 8 个 bit 存储的是频次的对数值,并且这个值还会随时间衰减。
    • 如果它的值比较小,那么就很容易被回收。为了确保新创建的对象不被回收,新对象的这 8 个 bit 会初始化为一个大于零的值,默认是 LFU_INIT_VAL=5。
  • 上一次访问频次的更新时间
    • ldt 是 16 个位,用来存储上一次 logc 的更新时间
    • 因为只有 16 位,所以精度不可能很高。
    • 它取的是分钟时间戳对 2^16 进行取模,大约每隔 45 天就会折返


Tags:LRU 算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
缓存淘汰之 LRU 算法
LRU算法 根据最近访问时间,离当前时间最远的数据优点被淘汰 实现 LRU 算法除了需要 key/value 字典外,还需要附加一个链表,链表中的元素按照一定的顺序进行排列。 当空间满的时...【详细内容】
2023-06-26  Search: LRU 算法  点击:(330)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(13)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(50)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(44)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(77)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(95)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(63)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(108)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(165)  评论:(0)  加入收藏
站内最新
站内热门
站内头条