Redis缓存淘汰算法——LRU

news/2025/2/27 11:31:08

文章目录

  • 一、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算法示意图：
在这里插入图片描述

  1. 向一个缓存空间依次插入三个数据A/B/C，填满了缓存空间；
  2. 读取数据A一次，按照访问时间排序，数据A被移动到缓存头部；
  3. 插入数据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 淘汰策略

在这里插入图片描述


http://www.niftyadmin.cn/n/5870044.html

相关文章

聚焦低空经济，峰飞航空飞行汽车开启未来出行新篇章

聚焦低空经济，峰飞航空飞行汽车开启未来出行新篇章

曾经只存在于科幻电影中的“飞行汽车”&#xff0c;如今正以eVTOL&#xff08;电动垂直起降飞行器&#xff09;的形式加速落地&#xff0c;成为全球科技竞争的新焦点。作为低空经济的核心载体之一&#xff0c;eVTOL不仅承载着缓解地面交通压力的使命&#xff0c;更被视为推动城…
阅读更多...
ue5 3dcesium中从本地配置文件读取路3dtilles的路径

ue5 3dcesium中从本地配置文件读取路3dtilles的路径

关卡蓝图中获得3dtiles的引用 拉出设置url 设置路径 至于设置的路径从哪里来 可以使用varest读取文件里的接送字符串 path中配置地址 path变量的值为: Data/VillageStartMapConfig.json此地址代表content的地下的data文件夹里的config.json文件 {"FilePath": &quo…
阅读更多...
sklearn中的决策树-分类树：泰坦尼克号生存预测

sklearn中的决策树-分类树：泰坦尼克号生存预测

分类树实例&#xff1a;泰坦尼克号生存预测 代码分解 需要导入的库 """导入所需要的库""" import pandas as pd import numpy as np from sklearn.tree import DecisionTreeClassifier from sklearn.model_selection import train_test_split f…
阅读更多...
蓝桥杯备赛-拔河

蓝桥杯备赛-拔河

问题描述 小明是学校里的一名老师&#xff0c;他带的班级共有 nn 名同学&#xff0c;第 ii 名同学力量值为 aiai​。在闲暇之余&#xff0c;小明决定在班级里组织一场拔河比赛。 为了保证比赛的双方实力尽可能相近&#xff0c;需要在这 nn 名同学中挑选出两个队伍&#xff0c…
阅读更多...
Android AsyncLayoutInflater异步加载xml布局文件，Kotlin

Android AsyncLayoutInflater异步加载xml布局文件，Kotlin

Android AsyncLayoutInflater异步加载xml布局文件&#xff0c;Kotlin implementation "androidx.asynclayoutinflater:asynclayoutinflater:1.1.0-alpha01" import android.os.Bundle import android.util.Log import android.view.View import android.view.ViewGro…
阅读更多...
Redis 高可用性：如何让你的缓存一直在线，稳定运行？

Redis 高可用性：如何让你的缓存一直在线，稳定运行？

&#x1f3af; 引言&#xff1a;Redis的高可用性为啥这么重要&#xff1f; 在现代高可用系统中&#xff0c;Redis 是一款不可或缺的分布式缓存与数据库系统。无论是提升访问速度&#xff0c;还是实现数据的高效持久化&#xff0c;Redis 都能轻松搞定。可是&#xff0c;当你把 …
阅读更多...
使用elasticdump导出/导入 -- ES数据

使用elasticdump导出/导入 -- ES数据

导出指定索引数据到指定文件夹&#xff1a; ./elasticdump --inputhttp://用户:密码IP:9201/索引名字 --output导出路径/out.json --typedata 将导出的文件导入 ./elasticdump --input路径/out.json --outputhttp://账号:密码IP:9201/索引名称 --typedata --fileTypejson 【el…
阅读更多...
【Springboot知识】Logback从1.2.x升级到1.3.x需要注意哪些点？

【Springboot知识】Logback从1.2.x升级到1.3.x需要注意哪些点？

文章目录 **1. 确认依赖版本**示例依赖配置&#xff08;Maven&#xff09;&#xff1a; **2. 处理 StaticLoggerBinder 的移除**解决方案&#xff1a; **3. 修改日志配置文件**示例 logback.xml 配置&#xff1a; **4. 检查兼容性问题**Spring Boot 2.x 的兼容性解决方案&#…
阅读更多...
最新文章

Copyright @ 2022~2023