LRU淘汰策略执行过程

这篇具有很好参考价值的文章主要介绍了LRU淘汰策略执行过程。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1 介绍

2 Redis内存淘汰策略

2.1 设置过期时间的淘汰策略

2.2 所有 key 的淘汰策略

3 LRU淘汰策略执行过程

4 算法实现


1 介绍

Redis无论是惰性删除还是定期删除,都可能存在删除不尽的情况,无法删除完全,比如每次删除完过期的 key 还是超过 25%,且这些 key 再也不会被客户端访问。
这样的话,定期删除和堕性删除可能都彻底的清理掉。如果这种情况长时间持续下去,可能会导致内存耗尽,所以Redis必须有一个完善的内存淘汰机制来保障。这就是我们这一篇的重点,Redis内存自动淘汰机制。

2 Redis内存淘汰策略

在 redis 中总共由8种淘汰策略,默认的淘汰策略是 noeviction。

noeviction不淘汰策略(默认)
淘汰数据策略 设置过期时间的淘汰策略 valatile-random 随机淘汰算法
volatile-ttl 淘汰失效时间最短的key
volatile-lru 删除最近最少使用的key
volatile-lfu 删除访问次数最少的key
所有数据的淘汰策略 allkeys-lru 删除最近最少使用的key(全部)
allkeys-lfu 删除访问次数最少的key(全部)
allkey-random 随机淘汰算法(全部)

2.1 设置过期时间的淘汰策略

volatile-ttl、volatile-random、volatile-lru、volatile-lfu 这4种策略淘汰的数据范围为设置了过期时间的数据。

2.2 所有 key 的淘汰策略

allkeys-lru、allkeys-random、allkeys-lfu 这3种淘汰策略无论是否设置了过期时间,内存不足时都会进行淘汰。
也就是说无论它的过期时间到没到,都有可能被删除。

3 LRU淘汰策略执行过程

这边以LRU算法为例子讲解,它的全称是 Least Rencently Used,即将最近最久未使用的算法进行数据淘汰。
我们这边以图例来讲解,整个过程如下:

  • 首先设置一个淘汰池(一个链表),假设默认大小是16,里面的数据采用末尾淘汰制。如图中
    • MRU:表示链表的表头,代表着最近最常被访问的数据;
    • LRU:表示链表的表尾,代表最近最不常使用的数据。
  • 如果淘汰池中的数据被访问,则会被移动到 MRU 端,其他位置的数据则相应往后移动一位
  • 每次指令操作的时候,自旋会判断当前内存是否满足指令所需要的内存
  • 如果当前内存不能满足,会从淘汰池中的尾部拿取一个最适合淘汰的数据
    • 取样模式(配置 maxmemory-samples属性)从Redis中获取随机的取样数据,避免一次性读取All Key性能慢
    • 在取样的数据中,根据淘汰算法 找到最适合淘汰的数据
  • 将需要淘汰的数据从Redis删除,并且从淘汰池移除

LRU淘汰策略执行过程,Redis缓存,redis

这边注意,LRU 更新和新增数据都发生在链表首,删除数据都发生在链表尾。
水果 Orange 跟 Pitaya 被访问,被移动到MRU端,新增的Mango也被插入到MRU端。而最末端的Olive则被删除。

4 算法实现

以下是使用Go语言实现Redis LRU淘汰过程的示例代码,代码注释很清楚:

package main  
  
import (  
    "container/list"  
    "fmt"  
    "time"  
)  
  
type Redis struct {  
    data map[string]*list.Element // 存储缓存项的键和值,以及它们在LRU链表中的位置  
    lru *list.List // LRU链表  
}  
  
type cacheItem struct {  
    key   string  
    value string  
    // 记录该缓存项最后一次被访问的时间  
    lastAccess time.Time  
}  
  
func NewRedis() *Redis {  
    return &Redis{  
        data: make(map[string]*list.Element),  
        lru: list.New(),  
    }  
}  
  
func (r *Redis) Get(key string) (string, bool) {  
    // 从LRU链表中查找缓存项  
    if elem, ok := r.data[key]; ok {  
        // 将该缓存项移动到链表头部,表示最近被访问过  
        r.lru.MoveToFront(elem)  
        // 更新缓存项的最后访问时间  
        item := elem.Value.(*cacheItem)  
        item.lastAccess = time.Now()  
        return item.value, true  
    }  
    return "", false  
}  
  
func (r *Redis) Set(key string, value string) {  
    // 从LRU链表中查找缓存项  
    if elem, ok := r.data[key]; ok {  
        // 如果缓存项存在,更新其值和最后访问时间,并将其移动到链表头部  
        item := elem.Value.(*cacheItem)  
        item.value = value  
        item.lastAccess = time.Now()  
        r.lru.MoveToFront(elem)  
        return  
    }  
    // 如果缓存项不存在,创建新的缓存项并将其添加到LRU链表头部  
    item := &cacheItem{  
        key:    key,  
        value:  value,  
        lastAccess: time.Now(),  
    }  
    elem := r.lru.PushFront(item)  
    r.data[key] = elem  
    // 如果缓存空间已满,执行LRU淘汰操作  
    for r.lru.Len() > maxItems {  
        // 从链表尾部查找最久未被访问的缓存项  
        elem := r.lru.Back()  
        item := elem.Value.(*cacheItem)  
        // 如果该缓存项的过期时间已到达,则从链表中删除该缓存项  
        if item.lastAccess.Add(expireTime).Before(time.Now()) {  
            r.lru.Remove(elem)  
            delete(r.data, item.key)  
        } else {  
            // 否则,只从链表中删除该缓存项  
            r.lru.Remove(elem)  
        }  
    }  
}

在这个示例中,我们使用了一个map来存储缓存项的键和值,以及它们在LRU链表中的位置。我们使用了一个LRU链表来存储缓存项,并按照访问时间将它们排序。在Get方法中,我们从LRU链表中查找缓存项,并将其移动到链表头部,表示最近被访问过。在Set方法中,如果缓存项已存在,我们更新其值和最后访问时间,并将其移动到链表头部;如果缓存项不存在,我们创建新的缓存项并将其添加到LRU链表头部。如果缓存空间已满,我们执行LRU淘汰操作,从链表尾部查找最久未被访问的缓存项,并从链表中删除它。注意,我们还检查了缓存项的过期时间,如果该缓存项已过期,则也会从链表中删除它。文章来源地址https://www.toymoban.com/news/detail-667430.html

到了这里,关于LRU淘汰策略执行过程的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LinkedHashMap如何实现LRU缓存淘汰策略?

    LRU,Least Recently Used, 最近最少使用 ,也就是优先淘汰最近最少使用的元素。 简而言之,就是将LinedHashMap的accessOrder设为true即可。 demo实现如下: 测试一下: 3.1 LinkedHashMap简介 LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以用

    2023年04月24日
    浏览(45)
  • cache教程1.LRU 缓存淘汰策略

    这一节实现LRU算法,要理解明白其使用的数据结构。 Cache的缓存全部存储在内存中,内存是有限的,因此不可能无限制地添加数据。当占用内存超过了给定的内存大小时候,就需要从缓存中移除一条或多条数据了。我们肯定希望尽可能移除“没用”的数据,那如何判定数据“

    2024年02月04日
    浏览(47)
  • Redis的内存淘汰策略

    Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时,怎么处理需要新写入且需要申请额外空间的数据。 noeviction :当内存不足以容纳新写入数据时,新写入操作会报错。 allkeys-lru :当内存不足以容纳新写入数据时,在键空间中,移除最近最少使用的key。(这个是最常用

    2024年02月10日
    浏览(37)
  • Redis 内存淘汰策略详解

    Redis 是一款高性能的非关系型数据库,它支持多种数据结构,如字符串、哈希、列表、集合、有序集合和 HyperLogLog。Redis 可以用于缓存、消息队列、应用程序中的数据结构存储等场景,它的优点是响应速度快、支持丰富的数据结构和扩展性好。 Redis 将所有数据都存储在内存中

    2024年02月10日
    浏览(57)
  • Redis中的淘汰策略

    本文主要说明在Redis面临key过期和内存不足的情况时,可以采用什么策略进行解决问题。 正如我们知道的Redis是基于内存的、单线程的一个中间件,在面对过期数据的时候,Redis并不会去直接把它从内存中进行剔除,因为Redis是单线程的,如果出现了过期key就立马去删除,可能

    2024年02月11日
    浏览(44)
  • redis 7.x 内存过期淘汰策略

    1.查看redis默认内存大小 config  get  maxmemory config set  maxmemory    1024 注意:在64-bit系统下,maxmemory设置为0表示不限制redis的内存使用。 LRU: 最近最少使用页面置换算法 ,查看页面最后一次被使用到发生调度的时间长度,首先淘汰最长时间未被使用的页面。 LFU:最近最不经常

    2024年02月07日
    浏览(47)
  • Redis内存兜底策略——内存淘汰及回收机制

    Redis内存淘汰及回收策略都是Redis 内存优化兜底 的策略,那它们是如何进行 兜底 的呢?先来说明一下什么是内存淘汰和内存回收策略: Redis内存淘汰:当Redis的内存使用 超过配置 的限制时,根据一定的策略删除一些键,以 释放内存空间 Redis内存回收:Redis通过 定期删除 和

    2024年02月06日
    浏览(42)
  • Redis 从入门到精通【进阶篇】之过期和淘汰策略详解

    当涉及Redis中的过期和淘汰策略时,有很多值得探讨的内容。以下是一个关于Redis过期和淘汰策略的详细解释,希望对你有所帮助。 Redis中的过期策略是指在Redis中设置的键值对的生存时间过期后,系统如何处理这些过期的键值对。Redis采用了两种主要的过期策略:定期删除和

    2024年02月16日
    浏览(46)
  • LRU 缓存淘汰算法

    Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。 接收一个参数 capacity 作为缓存的最大容量 实现一个函数 put() 添加数据到缓存 实现一个函数 get() 查询缓存中的数据 以上函数应该在 (O(1)) 的时间内完成 满足以上需求的数据结构 —

    2024年02月11日
    浏览(60)
  • Redis支持的数据结构有哪些?Redis使用单线程还是多线程?Redis的持久化机制有哪些?Redis的缓存淘汰策略有哪些?

    Redis支持的数据结构包括: 字符串(string):存储一个字符串。 列表(list):按照插入顺序存储多个字符串。 集合(set):存储多个不重复的字符串。 有序集合(sorted set):存储多个不重复的字符串,并为每个字符串关联一个分数,可以根据分数进行排序。 哈希表(has

    2024年02月12日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包