1 介绍

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

2 Redis内存淘汰策略

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

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 更新和新增数据都发生在链表首，删除数据都发生在链表尾。
水果 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 算法。

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】即可免费领取。

阅读全文

追求性能极致 - Redis

追求性能极致 - Redis：LRU内存淘汰算法分析