Redis 的 LRU(Least Recently Used) 算法你了解多少？

1、简介

Redis 是基于内存存储的 key-value 数据库，我们知道内存虽然快但空间小，当物理内存达到上限时，系统就会跑的很慢，这是因为 swap 机制会将部分内存的数据转移到 swap 分区中，通过与 swap 的交换保证系统继续运行；但是 swap 属于硬盘存储，速度远远比不上内存，尤其是对于 Redis 这种 QPS 非常高的服务，发生这种情况是无法接收的。（注意如果 swap 分区内存也满了，系统就会发生错误！）​

Linux 操作系统可以通过 free -m 查看 swap 大小:

因此如何防止 Redis 发生这种情况非常重要（面试官问到 Redis 几乎没有不问这个知识点的）。​

2、maxmemory 配置

Redis 针对上述问题提供了 maxmemory 配置，这个配置可以指定 Redis 存储器的最大数据集，通常情况都是在 redis.conf 文件中进行配置，也可以运行时使用 CONFIG SET 命令进行一次性配置。redis.conf 文件中的配置项示意图：

默认情况 maxmemory 配置项并未启用，Redis 官方介绍 64 位操作系统默认无内存限制，32 位操作系统默认 3GB 隐式内存配置，如果 maxmemory 为 0，代表内存不受限。​

因此我们在做缓存架构时，要根据硬件资源+业务需求做合适的 maxmemory 配置。​

3、内存达到 maxmemory 怎么办

很显然配置了最大内存，当 maxmemory 达到了最大上限之后 Redis 不可能不干活了，那么 Redis 是怎么来处理这个问题的呢？这就是本文的重点，Redis 提供了 maxmemory-policy 淘汰策略（本文只讲述 LRU 不涉及 LFU，LFU 在下一篇文章讲述），对满足条件的 key 进行删除，辞旧迎新。maxmemory-policy 淘汰策略：

• **noeviction：**当达到内存限制并且客户端尝试执行可能导致使用更多内存的命令时返回错误，简单来说读操作仍然允许，但是不准写入新的数据，del（删除）请求可以。

• **allkeys-lru：**从全体 key 中，通过 lru（Least Recently Used - 最近最少使用）算法进行淘汰

• **allkeys-random：**从全体 key 中，随机进行淘汰

• **volatile-lru：**从设置了过期时间的全部 key 中，通过 lru（Least Recently Used - 最近最少使用）算法进行淘汰，这样可以保证未设置过期时间需要被持久化的数据，不会被选中淘汰

• **volatile-random：**从设置了过期时间的全部 key 中，随机进行淘汰

• **volatile-ttl：**从设置了过期时间的全部 key 中，通过比较 key 的剩余过期时间 TTL 的值，TTL 越小越先被淘汰

还有 volatile-lfu/allkeys-lfu 这个留到下文一起探讨，两个算法不一样！​

random 随机淘汰只需要随机取一些 key 进行删除，释放内存空间即可；ttl 过期时间小先淘汰也可以通过比较 ttl 的大小，将 ttl 值小的 key 进行删除，释放内存空间即可。那么 LRU 是怎么实现的呢？Redis 又是如何知道哪个 key 最近被使用了，哪个 key 最近没有被使用呢？​

4、LRU 算法实现

我们先用 Java 的容器实现一个简单的 LRU 算法，我们使用 ConcurrentHashMap 做 key-value 结果存储元素的映射关系，使用 ConcurrentLinkedDeque 来维持 key 的访问顺序。LRU 实现代码：

package com.lizba.redis.lru;
import java.util.Arrays;import java.util.List;import java.util.concurrent.ConcurrentHashMap;import java.util.concurrent.ConcurrentLinkedDeque;
/** * <p> *      LRU简单实现 * </p> * * @Author: Liziba * @Date: 2021/9/17 23:47 */public class SimpleLru {
    /** 数据缓存 */    private ConcurrentHashMap<String, Object> cacheData;    /** 访问顺序记录 */    private ConcurrentLinkedDeque<String> sequence;    /** 缓存容量 */    private int capacity;
    public SimpleLru(int capacity) {        this.capacity = capacity;        cacheData = new ConcurrentHashMap(capacity);        sequence = new ConcurrentLinkedDeque();    }

    /**     * 设置值     *     * @param key     * @param value     * @return     */    public Object setValue(String key, Object value) {        // 判断是否需要进行LRU淘汰        this.maxMemoryHandle();        // 包含则移除元素，新访问的元素一直保存在队列最前面        if (sequence.contains(key)) {            sequence.remove();        }        sequence.addFirst(key);        cacheData.put(key, value);        return value;    }

    /**     * 达到最大内存，淘汰最近最少使用的key     */    private void maxMemoryHandle() {        while (sequence.size() >= capacity) {            String lruKey = sequence.removeLast();            cacheData.remove(lruKey);            System.out.println("key: " + lruKey + "被淘汰！");        }    }

    /**     * 获取访问LRU顺序     *     * @return     */    public List<String> getAll() {        return Arrays.asList(sequence.toArray(new String[] {}));    }}

测试代码：

package com.lizba.redis.lru;
/** * <p> *      测试最近最少使用 * </p> * * @Author: Liziba * @Date: 2021/9/18 0:00 */public class TestSimpleLru {
    public static void main(String[] args) {        SimpleLru lru = new SimpleLru(8);        for (int i = 0; i < 10; i++) {            lru.setValue(i+"", i);        }        System.out.println(lru.getAll());    }
}

测试结果：

从上数的测试结果可以看出，先加入的 key0，key1 被淘汰了，最后加入的 key 也是最新的 key 保存在 sequence 的队头。通过这种方案，可以很简单的实现 LRU 算法；但缺点也十分明显，方案需要使用额外的数据结构来保存 key 的访问顺序，这样会使 Redis 内存消耗增加，本身用来优化内存的方案，却要消耗不少内存，显然是不行的。​

5、Redis 的近似 LRU

针对这种情况，Redis 使用了近似 LRU 算法，并不是完完全全准确的淘汰掉最近最不经常使用的 key，但是总体的准确度也可以得到保证。近似 LRU 算法非常简单，在 Redis 的 key 对象中，增加 24bit 用于存储最近一次访问的系统时间戳，当客户端对 Redis 服务端发送 key 的写入相关请求时，发现内存达到 maxmemory，此时触发惰性删除；Redis 服务通过随机采样，选择 5 个满足条件的 key（注意这个随机采样 allkeys-lru 是从所有的 key 中随机采样，volatile-lru 是从设置了过期时间的所有 key 中随机采样），通过 key 对象中记录的最近访问时间戳进行比较，淘汰掉这 5 个 key 中最旧的 key；如果内存仍然不够，就继续重复这个步骤。​

注意，5 是 Redis 默认的随机采样数值大小，它可以通过 redis.conf 中的 maxmemory_samples 进行配置：

针对上述的随机 LRU 算法，Redis 官方给出了一张测试准确性的数据图：

• 最上层浅灰色表示被淘汰的 key，图一是标准的 LRU 算法淘汰的示意图

• 中间深灰色层表示未被淘汰的旧 key

• 最下层浅绿色表示最近被访问的 key

在 Redis 3.0 maxmemory_samples 设置为 10 的时候，Redis 的近似 LRU 算法已经非常的接近真实 LRU 算法了，但是显然 maxmemory_samples 设置为 10 比 maxmemory_samples 设置为 5 要更加消耗 CPU 计算时间，因为每次采样的样本数据增大，计算时间也会增加。Redis3.0 的 LRU 比 Redis2.8 的 LRU 算法更加准确，是因为 Redis3.0 增加了一个与 maxmemory_samples 相同大小的淘汰池，每次淘汰 key 的时候，先与淘汰池中等待被淘汰的 key 进行比较，最后淘汰掉最老旧的 key，其实就是被选中淘汰的 key 放到一起再比较一下，淘汰其中最旧的。

6、存在问题

LRU 算法看似比较好用，但是也存在不合理的地方，比如 A 和 B 两个 key，在发生淘汰时的前一个小时前同一时刻添加到 Redis，A 在前 49 分钟被访问了 1000 次，但是后 11 分钟没有被访问；B 在这一个小时内仅仅第 59 分钟被访问了 1 次；此时如果使用 LRU 算法，如果 A、B 均被 Redis 采样选中，A 将会被淘汰很显然这个是不合理的。针对这种情况 Redis 4.0 添加了 LFU 算法，(Least frequently used) 最不经常使用，这种算法比 LRU 更加合理，下文将会一起学习中淘汰算法，如有需要请关注我的专栏。