Redis系列19:LRU内存淘汰算法分析
阅读原文时间:2023年08月22日阅读:3

Redis系列1:深刻理解高性能Redis的本质

Redis系列2:数据持久化提高可用性

Redis系列3:高可用之主从架构

Redis系列4:高可用之Sentinel(哨兵模式)

Redis系列5:深入分析Cluster 集群模式

追求性能极致:Redis6.0的多线程模型

追求性能极致:客户端缓存带来的革命

Redis系列8:Bitmap实现亿万级数据计算

Redis系列9:Geo 类型赋能亿级地图位置计算

Redis系列10:HyperLogLog实现海量数据基数统计

Redis系列11:内存淘汰策略

Redis系列12:Redis 的事务机制

Redis系列13:分布式锁实现

Redis系列14:使用List实现消息队列

Redis系列15:使用Stream实现消息队列

Redis系列16:聊聊布隆过滤器(原理篇)

Redis系列17:聊聊布隆过滤器(实践篇)

Redis系列18:过期数据的删除策略

1 介绍

上一期我们介绍了 Redis系列18:过期数据的删除策略 ,但是无论是惰性删除还是定期删除,都可能存在删除不尽的情况,无法删除完全,比如每次删除完过期的 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

随机淘汰算法(全部)

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

allkeys-lru、allkeys-random、allkeys-lfu 这3种淘汰策略无论是否设置了过期时间,内存不足时都会进行淘汰。

也就是说无论它的过期时间到没到,都有可能被删除。

3 LRU淘汰策略执行过程

这边以LRU算法为例子讲解,它的全称是 Least Rencently Used,即将最近最久未使用的算法进行数据淘汰。

我们这边以图例来讲解,整个过程如下:

  • 首先设置一个淘汰池(一个链表),假设默认大小是16,里面的数据采用末尾淘汰制。如图中

    • MRU:表示链表的表头,代表着最近最常被访问的数据;
    • LRU:表示链表的表尾,代表最近最不常使用的数据。
  • 如果淘汰池中的数据被访问,则会被移动到 MRU 端,其他位置的数据则相应往后移动一位

  • 每次指令操作的时候,自旋会判断当前内存是否满足指令所需要的内存

  • 如果当前内存不能满足,会从淘汰池中的尾部拿取一个最适合淘汰的数据

    • 取样模式(配置 maxmemory-samples属性)从Redis中获取随机的取样数据,避免一次性读取All Key性能慢
    • 在取样的数据中,根据淘汰算法 找到最适合淘汰的数据
  • 将需要淘汰的数据从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淘汰操作,从链表尾部查找最久未被访问的缓存项,并从链表中删除它。注意,我们还检查了缓存项的过期时间,如果该缓存项已过期,则也会从链表中删除它。

5 总结

第4小节基本来自baidu文心一言的组织,非常感谢。

这一篇我们介绍了Redis的几种内存淘汰策略,并且详细分析了LRU算法的实现原理。下一篇我们分析下 LFU 算法。

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章