Redis缓存淘汰算法—

文章目录

一、LRU 算法概述
- 1.1 LRU 算法的工作原理
- 1.2 手写LRU
二、Redis 中的 LRU 算法
- 2.1 近似 LRU 算法
- 2.2 如何判断“最近最少使用”的键？
- 2.3 Redis 中的 LRU 配置

在 Redis 中， LRU（Latest Recently Used，最近最少使用） 是一种非常常见的缓存淘汰算法。它用于管理 Redis 的内存使用，当 Redis 达到最大内存限制时，决定哪些键应该被删除，从而腾出空间给新的数据。

一、LRU 算法概述

LRU(Least Recently Used，最近最少使用)算法是一种缓存淘汰算法，其核心思想是：在缓存空间有限的情况下，当缓存满时，应该淘汰最久没有被使用的数据。换句话说，LRU 算法会清除那些最久未被访问的缓存数据，以腾出空间存储新的数据。

1.1 LRU 算法的工作原理

每当访问一个缓存项时（无论是读取还是写入），该缓存项都会被标记为最近访问过的。
当缓存空间已满，需要淘汰数据时，LRU 算法会删除最近最少访问的数据项，即链表尾部的数据项。

以下是一个LRU算法示意图：
在这里插入图片描述

向一个缓存空间依次插入三个数据A/B/C，填满了缓存空间；
读取数据A一次，按照访问时间排序，数据A被移动到缓存头部；
插入数据D的时候，由于缓存空间已满，触发了LRU的淘汰策略，数据B被移出，缓存空间只保留了D/A/C。

一般而言，LRU算法的数据结构不会如示意图那样，仅使用简单的队列或链表去缓存数据，而是会采用Hash表 + 双向链表的结构，利用Hash表确保数据查找的时间复杂度是O(1)，双向链表又可以使数据插入/删除等操作也是O(1)。

在这里插入图片描述

1.2 手写LRU

手写一个 LRU（Least Recently Used）缓存实现，通常使用 哈希表（HashMap）和 双向链表（Doubly Linked List）的组合来实现。哈希表用于存储数据项的引用，双向链表用于维护数据项的访问顺序，链表头部表示最近访问的数据，链表尾部表示最久未访问的数据。

下面是一个简单的 LRU 缓存的手写实现，使用 Java 实现了基本的 get() 和 put() 操作。

import java.util.HashMap;

public class LRUCache {

    // 双向链表节点类
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;  // 缓存最大容量
    private HashMap<Integer, Node> cache;  // 存储数据
    private Node head, tail;  // 双向链表的头尾节点

    // 构造方法，初始化容量和头尾节点
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();

        // 创建伪头尾节点，方便操作
        head = new Node(0, 0);
        tail = new Node(0, 0);

        // 初始化头尾节点连接
        head.next = tail;
        tail.prev = head;
    }

    // 获取数据
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            System.out.println("缓存中没有该数据，key: " + key);
            return -1;  // 数据不存在，返回 -1
        }
        // 将访问的节点移动到链表头部
        moveToHead(node);
        System.out.println("访问数据，key: " + key + ", value: " + node.value);
        return node.value;
    }

    // 插入数据
    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            // 如果缓存没有该数据，创建新节点
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            // 将新节点插入到链表头部
            addNode(newNode);

            System.out.println("插入新数据，key: " + key + ", value: " + value);

            if (cache.size() > capacity) {
                // 如果缓存超出容量，移除链表尾部节点
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
                System.out.println("缓存已满，淘汰最久未使用的数据，key: " + tailNode.key);
            }
        } else {
            // 如果缓存已有该数据，更新值并移动到链表头部
            node.value = value;
            moveToHead(node);
            System.out.println("更新数据，key: " + key + ", 新值: " + value);
        }

        printCacheStatus();  // 打印当前缓存状态
    }

    // 将节点移动到链表头部（表示最近访问）
    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    // 将节点添加到链表头部
    private void addNode(Node node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    // 从链表中移除节点
    private void removeNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    // 删除链表尾部节点（最久未使用的节点）
    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }

    // 打印当前缓存状态
    private void printCacheStatus() {
        System.out.print("当前缓存状态：");
        Node current = head.next;
        while (current != tail) {
            System.out.print("{" + current.key + "=" + current.value + "} ");
            current = current.next;
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2); // 设置缓存容量为 2

        cache.put(1, 1);  // 缓存: {1=1}
        cache.put(2, 2);  // 缓存: {1=1, 2=2}
        System.out.println("获取数据：key=1, 返回值=" + cache.get(1));  // 返回 1，缓存: {2=2, 1=1}

        cache.put(3, 3);  // 缓存: {1=1, 3=3}，淘汰键 2
        System.out.println("获取数据：key=2, 返回值=" + cache.get(2));  // 返回 -1 (未找到)

        cache.put(4, 4);  // 缓存: {3=3, 4=4}，淘汰键 1
        System.out.println("获取数据：key=1, 返回值=" + cache.get(1));  // 返回 -1 (未找到)
        System.out.println("获取数据：key=3, 返回值=" + cache.get(3));  // 返回 3，缓存: {4=4, 3=3}
        System.out.println("获取数据：key=4, 返回值=" + cache.get(4));  // 返回 4，缓存: {4=4, 3=3}
    }
}

输出：
在这里插入图片描述

二、Redis 中的 LRU 算法

Redis 实现 LRU 算法时并没有精确计算每个数据的使用顺序，而是采用了 近似算法 来提高效率。Redis 利用 采样算法 来模拟 LRU 行为，而不是每次访问时都更新所有元素的访问顺序，Redis 的 LRU 实现称为 LRU-K（LRU-K Sampling）。

Redis内部只使用Hash表缓存了数据，并没有创建一个专门针对LRU算法的双向链表，之所以这样处理也是因为以下几个原因：

筛选规则，Redis是随机抽取一批数据去按照淘汰策略排序，不再需要对所有数据排序；
性能问题，每次数据访问都可能涉及数据移位，性能会有少许损失；
内存问题，Redis对内存的使用一向很“抠门”，数据结构都很精简，尽量不使用复杂的数据结构管理数据；
策略配置，如果线上Redis实例动态修改淘汰策略会触发全部数据的结构性改变，这个Redis系统无法承受的。

2.1 近似 LRU 算法

Redis的LRU 近似算法是指每次访问数据时并不会更新所有元素的顺序，而是通过随机抽取一定数量的键，估算这些键的使用频率来决定哪些键应该被淘汰。这种近似的方式避免了每次都精确计算访问顺序，减少了性能开销。在缓存满的时候，Redis 选择最近最少使用的元素进行淘汰。

2.2 如何判断“最近最少使用”的键？

它的基本思路是：

定期从缓存中随机挑选一部分数据。
对这些随机选中的数据，检查它们的使用情况，找出最久未使用的键进行淘汰。

采样的大小 是一个重要的参数。默认情况下，Redis 会随机抽取 10 个键，通过这些键来估算哪个是最近最少使用的。抽样的数量可以通过配置参数调整。

2.3 Redis 中的 LRU 配置

Redis 提供了两个关键的配置项来控制 LRU 淘汰策略：

maxmemory：配置 Redis 的最大内存。一旦Redis 的内存使用超过该阈值，Redis 会根据maxmemory-policy配置策略，执行内存淘汰操作。
maxmemory-policy：配置内存达到限制时，Redis 应该使用哪种淘汰策略。Redis 支持多种内存淘汰策略，其中与 LRU 相关的有以下几种：
allkeys-lru：对所有的键使用 LRU 淘汰策略，即当内存达到限制时，Redis 会移除最久未被访问的键。
volatile-lru：仅对设置了过期时间的键使用 LRU 淘汰策略，意味着只有那些设置了 TTL（过期时间）的键会根据 LRU 策略被淘汰。
allkeys-random：随机移除键，使用随机的方式淘汰数据。
volatile-random：仅删除那些设置了过期时间的键，并且使用随机策略。
volatile-ttl：仅删除设置了过期时间的键，并且删除那些即将过期的键。

示例：

maxmemory 100mb           # 设置最大内存为 100MB
maxmemory-policy allkeys-lru  # 设置内存达到限制时，使用 LRU 淘汰策略

在这里插入图片描述