Redis---LRU原理与算法实现

server/2025/3/5 1:43:52/

文章目录

    • LRU概念理解
    • LRU原理
    • 基于HashMap和双向链表实现LRU
    • Redis中的LRU的实现
      • LRU时钟
      • 淘汰策略
      • 近似LRU的实现
      • LRU算法的优化
    • Redis LRU的核心代码逻辑
    • Redis LRU的核心代码逻辑
    • Redis LRU的配置参数
    • Redis LRU的优缺点
    • Redis LRU的优缺点

LRU概念理解

LRU（Least Recently Used） 最近最少使用算法，是一种常用的页面置换算法，广泛应用于操作系统中的内存管理和缓存系统。LRU 的基本思想是：当缓存空间满时，当需要置换页面时，选择最近最少使用的页面进行淘汰。

LRU原理

可以用一个特殊的栈来保存当前正在使用的各个页面的页面号。当一个新的进程访问某页面时，便将该页面号压入栈顶，其他的页面号往栈底移，如果内存不够，则将栈底的页面号移除。这样，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未访问的页面的页面号。

在一般标准的操作系统教材里，会用下面的方式来演示 LRU 原理，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。

img

基于HashMap和双向链表实现LRU

HahsMap用于快速查找到结点所在位置，然后将使用到的结点放在对头，这样最近最少使用的结点自然就落入到队尾。双向链表提供了良好的灵活性，两边可达。如下图所示。

img

假设我们需要执行如下操作

save(“key1”, 7)

save(“key2”, 0)

save(“key3”, 1)

save(“key4”, 2)

get(“key2”)

save(“key5”, 3)

get(“key2”)

save(“key6”, 4)

使用HashMap + 双向链表数据结构实现的LRU操作双向链表部分的轨迹如下。

img

核心操作的步骤：

  • save(key, value)
    • 首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。
    • 如果不存在，需要构造新的节点，并且尝试把节点塞到队头。
    • 如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
  • get(key)，通过 HashMap 找到 LRU 链表节点，把节点插入到队头，返回缓存的值。

完整基于Java的代码参考如下

package LRU;import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;public class LRUCache {// 定义双向链表的节点类class DLinkedNode {String key; // 节点的键int value; // 节点的值DLinkedNode pre; // 前驱节点DLinkedNode post; // 后继节点}// 使用ConcurrentHashMap来存储缓存数据，保证线程安全private ConcurrentMap<String, DLinkedNode> cache = new ConcurrentHashMap<String, DLinkedNode>();private int count; // 当前缓存中的元素数量private int capacity; // 缓存的最大容量private DLinkedNode head, tail; // 双向链表的头节点和尾节点// 构造函数，初始化LRU缓存public LRUCache(int capacity) {this.count = 0;this.capacity = capacity;// 初始化头节点和尾节点head = new DLinkedNode();head.pre = null;tail = new DLinkedNode();tail.post = null;// 头节点和尾节点相互连接head.post = tail;tail.pre = head;}// 获取缓存中的值public int get(String key) {DLinkedNode node = cache.get(key);if(node == null){return -1; // 如果缓存中没有该键，返回-1}// 将该节点移动到链表头部，表示最近使用moveToHead(node);return node.value;}// 向缓存中插入或更新值public void put(String key, int value) {DLinkedNode node = cache.get(key);if (node != null) {// 如果键已存在，更新值并将节点移动到链表头部node.value = value;moveToHead(node);return;}// 创建新节点DLinkedNode newNode = new DLinkedNode();newNode.key = key;newNode.value = value;// 将新节点加入缓存和链表头部cache.put(key, newNode);addNode(newNode);++count;// 如果缓存已满，移除链表尾部的节点（最久未使用的节点）if(count > capacity){DLinkedNode tail = popTail();cache.remove(tail.key);--count;}}// 将节点添加到链表头部private void addNode(DLinkedNode node){node.pre = head;node.post = head.post;head.post.pre = node;head.post = node;}// 从链表中移除节点private void removeNode(DLinkedNode node){DLinkedNode pre = node.pre;DLinkedNode post = node.post;pre.post = post;post.pre = pre;}// 将节点移动到链表头部private void moveToHead(DLinkedNode node){removeNode(node);addNode(node);}// 移除链表尾部的节点并返回该节点private DLinkedNode popTail(){DLinkedNode res = tail.pre;removeNode(res);return res;}
}

测试LRUCache

package LRU;public class LRUCacheTest {public static void main(String[] args) {// 创建一个容量为 3 的 LRU 缓存LRUCache cache = new LRUCache(3);// 插入键值对cache.put("key1", 1);cache.put("key2", 2);cache.put("key3", 3);// 测试获取操作System.out.println("key1 的值: " + cache.get("key1")); // 应返回 1System.out.println("key2 的值: " + cache.get("key2")); // 应返回 2System.out.println("key3 的值: " + cache.get("key3")); // 应返回 3// 插入新键值对，触发淘汰策略（key1 是最久未使用的，应被淘汰）cache.put("key4", 4);// 测试淘汰策略System.out.println("key1 的值: " + cache.get("key1")); // 应返回 -1，因为 key1 已被淘汰System.out.println("key4 的值: " + cache.get("key4")); // 应返回 4// 更新现有键的值，并测试是否移动到链表头部cache.put("key2", 20);System.out.println("key2 更新后的值: " + cache.get("key2")); // 应返回 20// 插入新键值对，触发淘汰策略（key3 是最久未使用的，应被淘汰）cache.put("key5", 5);// 测试淘汰策略System.out.println("key3 的值: " + cache.get("key3")); // 应返回 -1，因为 key3 已被淘汰System.out.println("key5 的值: " + cache.get("key5")); // 应返回 5// 打印当前缓存中的所有键值对System.out.println("当前缓存内容:");System.out.println("key2: " + cache.get("key2")); // 应返回 20System.out.println("key4: " + cache.get("key4")); // 应返回 4System.out.println("key5: " + cache.get("key5")); // 应返回 5}
}

输出结果：

image-20250228090835350

Redis中的LRU的实现

Redis 的 LRU 实现与传统的 LRU 算法有所不同。由于 Redis 是一个高性能的内存数据库，完全实现标准的 LRU 算法会带来较大的性能开销。因此，Redis 采用了一种 近似 LRU（Approximated LRU） 算法，在保证性能的同时，尽可能接近标准的 LRU 行为。

LRU时钟

Redis 为每个对象（键值对）维护一个 lru 字段，用于记录该对象最后一次被访问的时间戳。这个时间戳是一个 24 位的整数，表示从 Redis 启动开始计算的秒数的低 24 位。

  • LRU 时钟的更新：
    • 每次访问一个键时（例如 GET 或 SET），Redis 会更新该键的 lru 字段为当前的 LRU 时钟值。
    • LRU 时钟的值会定期更新（默认每 100 毫秒更新一次）。

淘汰策略

当 Redis 需要淘汰键时（例如内存不足时），会根据配置的淘汰策略选择一个键进行删除。Redis 支持多种淘汰策略，其中与 LRU 相关的策略包括：

  • volatile-lru：从设置了过期时间的键中，淘汰最近最少使用的键。
  • allkeys-lru：从所有键中，淘汰最近最少使用的键。

近似LRU的实现

Redis 并不完全遍历所有键来找到最久未使用的键，而是通过以下方式近似实现 LRU：

  • 随机采样：Redis 会随机选择一定数量的键（默认是 5 个），然后从这些键中淘汰 lru 值最小的键（即最久未使用的键）。
  • 采样数量：可以通过配置 maxmemory-samples 参数来调整采样数量。采样数量越多，淘汰的精度越高，但性能开销也越大。

LRU算法的优化

为了进一步优化性能，Redis 做了一些额外的优化：

  • 惰性删除：Redis 不会在每次访问时都更新 lru 字段，而是通过一些启发式方法减少更新频率。
  • 淘汰池：Redis 维护一个淘汰池（eviction pool），用于缓存一些候选键，避免每次淘汰时都需要重新采样。

Redis LRU的核心代码逻辑

以下是 Redis 中 LRU 实现的核心逻辑（伪代码）：

// 更新键的 LRU 时间戳
void updateLRU(redisObject *obj) {obj->lru = getCurrentLRUClock();
}// 获取当前的 LRU 时钟
unsigned int getCurrentLRUClock() {return (server.unixtime & LRU_CLOCK_MAX) | (server.lruclock & ~LRU_CLOCK_MAX);
}// 近似 LRU 淘汰算法
void evictKeysUsingLRU() {int sample_count = server.maxmemory_samples;redisObject *best_key = NULL;unsigned int best_lru = LRU_CLOCK_MAX;// 随机采样for (int i = 0; i < sample_count; i++) {redisObject *key = getRandomKey();if (key->lru < best_lru) {best_key = key;best_lru = key->lru;}}// 淘汰最久未使用的键if (best_key != NULL) {deleteKey(best_key);}
}

Redis LRU的核心代码逻辑

以下是 Redis 中 LRU 实现的核心逻辑（伪代码）：

// 更新键的 LRU 时间戳
void updateLRU(redisObject *obj) {obj->lru = getCurrentLRUClock();
}// 获取当前的 LRU 时钟
unsigned int getCurrentLRUClock() {return (server.unixtime & LRU_CLOCK_MAX) | (server.lruclock & ~LRU_CLOCK_MAX);
}// 近似 LRU 淘汰算法
void evictKeysUsingLRU() {int sample_count = server.maxmemory_samples;redisObject *best_key = NULL;unsigned int best_lru = LRU_CLOCK_MAX;// 随机采样for (int i = 0; i < sample_count; i++) {redisObject *key = getRandomKey();if (key->lru < best_lru) {best_key = key;best_lru = key->lru;}}// 淘汰最久未使用的键if (best_key != NULL) {deleteKey(best_key);}
}

Redis LRU的配置参数

  1. maxmemory：
    • 设置 Redis 实例的最大内存限制。
    • 当内存使用达到该限制时，Redis 会根据淘汰策略删除键。
  2. maxmemory-policy：
    • 设置淘汰策略，支持以下选项：
      • volatile-lru：从设置了过期时间的键中淘汰最近最少使用的键。
      • allkeys-lru：从所有键中淘汰最近最少使用的键。
      • volatile-random：从设置了过期时间的键中随机淘汰键。
      • allkeys-random：从所有键中随机淘汰键。
      • volatile-ttl：从设置了过期时间的键中淘汰剩余生存时间（TTL）最短的键。
      • noeviction：不淘汰任何键，直接返回错误。
  3. maxmemory-samples：
    • 设置 LRU 淘汰时的采样数量。
    • 默认值为 5，表示每次淘汰时随机选择 5 个键，然后淘汰其中最久未使用的键。
    • 增加该值可以提高淘汰的精度，但会增加 CPU 开销。

Redis LRU的优缺点

优点：

  1. 高性能：
    • 通过随机采样和近似算法，Redis 的 LRU 实现避免了完全遍历所有键的开销。
  2. 灵活性：
    • 支持多种淘汰策略，可以根据业务需求灵活配置。
  3. 内存友好：
    • 每个键只需要额外存储 24 位的 lru 字段，内存开销较小。

缺点：

  1. 近似性：
    • Redis 的 LRU 是近似的，可能无法完全准确地淘汰最久未使用的键。
  2. 采样数量影响精度：
    • 采样数量较少时，淘汰的精度可能较低。
      择 5 个键，然后淘汰其中最久未使用的键。
    • 增加该值可以提高淘汰的精度，但会增加 CPU 开销。

Redis LRU的优缺点

优点：

  1. 高性能：
    • 通过随机采样和近似算法，Redis 的 LRU 实现避免了完全遍历所有键的开销。
  2. 灵活性：
    • 支持多种淘汰策略，可以根据业务需求灵活配置。
  3. 内存友好：
    • 每个键只需要额外存储 24 位的 lru 字段，内存开销较小。

缺点：

  1. 近似性：
    • Redis 的 LRU 是近似的，可能无法完全准确地淘汰最久未使用的键。
  2. 采样数量影响精度：
    • 采样数量较少时，淘汰的精度可能较低。

http://www.ppmy.cn/server/172478.html

相关文章

构建私有化AI知识库：基于CentOS的Ollama + DeepSeek-R1 +ragflow 整合部署教程

构建私有化AI知识库：基于CentOS的Ollama + DeepSeek-R1 +ragflow 整合部署教程

操作系统&#xff1a;CentOS 7.9 CPU&#xff1a;支持 AVX 指令集的 x86_64 处理器 内存&#xff1a;64GB 存储&#xff1a;SSD 1TB 以上 GPU&#xff08;可选&#xff09; 一、组件介绍 Ollama Ollama 是一个专为在本地机器上部署和运行大型语言模型&#xff08;LLM&a…
阅读更多...
Spring学习笔记03——Spring Boot的文件结构

Spring学习笔记03——Spring Boot的文件结构

Spring boot常见的文件结构&#xff1a; src/ ├── main/ │ ├── java/ │ │ └── com.example.demo/ │ │ ├── DemoApplication.java # 主入口 │ │ ├── config/ # 配置类 │ │ ├── controller/ …
阅读更多...
Switch开关的防抖监听器

Switch开关的防抖监听器

一、这代码到底解决了什么问题&#xff1f;&#xff08;先唠点实在的&#xff09; 作为一个在安卓坑里摸爬滚打多年的老码农&#xff0c;肯定都遇到过这种场景&#xff1a;用户疯狂点击Switch开关&#xff0c;结果触发一堆重复回调。这种防抖需求就跟吃饭喝水一样常见。传统实…
阅读更多...
腾讯云对象存储服务（COS）

腾讯云对象存储服务（COS）

腾讯云对象存储服务&#xff08;COS&#xff09; 安全、可扩展、低成本的云存储解决方案 腾讯云 对象存储服务&#xff08;COS&#xff0c;Cloud Object Storage&#xff09; 是一种高可靠、高性能、可扩展的云存储服务&#xff0c;专为海量非结构化数据&#xff08;如图片、…
阅读更多...
思维链 Chain-of-Thought Prompting

思维链 Chain-of-Thought Prompting

论文: Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (Wei et al., 2022) 核心贡献: 首次提出通过显式的中间推理步骤&#xff08;即思维链&#xff09;提升大语言模型的复杂推理能力。该方法通过示例展示多步推理过程&#xff0c;引导模型生成逻辑…
阅读更多...
【QT网络问题】关于QT在调用天气等类似api接口时报错

【QT网络问题】关于QT在调用天气等类似api接口时报错

报错内容 qt.network.ssl: QSslSocket::connectToHostEncrypted: TLS initialization failed Error: "TLS initialization failed"问题原因 Openssl库不匹配或者未安装&#xff0c;可以通过qdebug版本打印当前所需要的的openssl库&#xff0c;自己去官网下载 qDeb…
阅读更多...
【零基础C语言】第四节 数组

【零基础C语言】第四节 数组

【零基础C语言系列】 【零基础C语言】第一节 C语言概述【数制进制码制】-CSDN博客 【零基础C语言】第二节 数据类型、运算符、表达式-CSDN博客 【零基础C语言】第三节 控制结构-CSDN博客 一、一维数组
阅读更多...
第 三十九：作用域插槽 v-solt 和 solt 对应的作用域

第 三十九：作用域插槽 v-solt 和 solt 对应的作用域

3. 作用域插槽 理解&#xff1a;数据在组件的自身&#xff0c;但根据数据生成的结构需要组件的使用者来决定。&#xff08;新闻数据在News组件中&#xff0c;但使用数据所遍历出来的结构由App组件决定&#xff09; 具体编码&#xff1a; 父组件中&#xff1a;<Game v-slot&…
阅读更多...
最新文章

Copyright @ 2022~2023