一文详解Redis中的LRU算法

大明小哥_8788

大明小哥_8788

2021-10-13

5227人浏览

转载

本篇文章带大家了解一下redis中的lru(least recently used),希望对大家有所帮助!

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

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

1.png

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

2、maxmemory配置

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

2.png

默认情况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实现代码:

Sentinal Redis
Sentinal Redis

监控Redis服务器健康状况、内存、性能及BullMQ队列。检查队列深度、失败任务,分析慢查询并诊断问题。

下载
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> 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[] {}));
    }
}复制代码</string></string></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 <p><strong>测试结果:</strong>\</p><p><img src="https://img.php.cn/upload/image/775/594/750/1634091918234875.png?x-oss-process=image/resize,p_40" title="1634091918234875.png" alt="3.png"></p><p>从上数的测试结果可以看出,先加入的key0,key1被淘汰了,最后加入的key也是最新的key保存在sequence的队头。<br>通过这种方案,可以很简单的实现LRU算法;但缺点也十分明显,方案需要使用额外的数据结构来保存key的访问顺序,这样会使Redis内存消耗增加,本身用来优化内存的方案,却要消耗不少内存,显然是不行的。<br></p><h2 data-id="heading-4">5、Redis的近似LRU</h2><p>针对这种情况,Redis使用了近似LRU算法,并不是完完全全准确的淘汰掉最近最不经常使用的key,但是总体的准确度也可以得到保证。<br>近似LRU算法非常简单,在Redis的key对象中,增加24bit用于存储最近一次访问的系统时间戳,当客户端对Redis服务端发送key的写入相关请求时,发现内存达到maxmemory,此时触发惰性删除;Redis服务通过随机采样,选择5个满足条件的key(注意这个随机采样<strong>allkeys-lru</strong>是从所有的key中随机采样,<strong>volatile-lru</strong>是从设置了过期时间的所有key中随机采样),通过key对象中记录的最近访问时间戳进行比较,淘汰掉这5个key中最旧的key;如果内存仍然不够,就继续重复这个步骤。<br></p><p><strong>注意,5是Redis默认的随机采样数值大小,它可以通过redis.conf中的maxmemory_samples进行配置:</strong>\</p><p><img src="https://img.php.cn/upload/image/866/655/134/1634091929131285.png?x-oss-process=image/resize,p_40" title="1634091929131285.png" alt="4.png"></p><p><strong>针对上述的随机LRU算法,Redis官方给出了一张测试准确性的数据图:</strong></p>
  • 最上层浅灰色表示被淘汰的key,图一是标准的LRU算法淘汰的示意图
  • 中间深灰色层表示未被淘汰的旧key
  • 最下层浅绿色表示最近被访问的key

5.png

在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更加合理,下文将会一起学习中淘汰算法,如有需要请关注我的专栏。

更多编程相关知识,请访问:编程教学!!

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

redis

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

0

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

0

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

0

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

0

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

0

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

0

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

160

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

120

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

100

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Go-Zero官方文档
Go-Zero官方文档

共0课时 | 0人学习