当前位置: 首页 > news >正文

LRU算法 vs Redis近似LRU算法

LRU(Least Recently Use)算法,是用来判断一批数据中,最近最少使用算法。它底层数据结构由Hash和链表结合实现,使用Hash是为了保障查询效率为O(1),使用链表保障删除元素效率为O(1)。

LRU算法是用来判断最近最少使用到元素,常被用在缓存中数据清理、内存淘汰相关的场景,它底层是由Hash表和双向链表构成,Hash主要用来存储key和指向链表节点的指针,双向链表就是用来实现最近最少使用算法的数据结构,新访问的元素会加入到头部或者尾部(就看最终从哪个反向取了,我们这里定为头部),如果是已经访问的元素,并不会新添加到链表中,而是将链表中原来存在的这个节点移动到头部,最终链表中越靠近尾部的元素,代表最近最少使用的元素。

为什么要额外组合使用Hash和链表?单个数据结构也能完成不是吗?

为了提交效能,Hash的优势是查找元素为O(1),但是移动元素是O(n),链表查找元素复杂度是O(n),但是移动元素复杂度是O(1),所以为了提高效率,结构两种数据结构各自的优势,利用Hash的O(1),来查找元素是否存在,利用链表的O(1)来移动元素位置。

Redis近似LRU算法

什么是Redis近似LRU算法,为什么Redis不直接使用LRU算法?

近似LRU算法是Redis采用LRU算法思想,实现一个近似LRU的算法,在原LRU算法中需要维护一个Hash和链表,而Redis本身可以理解为一个大的字典,那就需要额外的去维护一个链表数据结构,Redis本身就是要经受大量数据的冲击的,所以这个链表将会占用更大的内存。Redis的宗旨就是高效,所以它没有使用这样的一个链表。它的做法如下:

Redis最开始的做法
1、当设置了LRU回收策略之后,对元素进行访问时,会调用一次server.lruclock方法,获取Redis时钟时间戳(redis时钟默认1毫秒更新一次)并进行取模(防止时间戳递增,最后超过了24bit),记录在元素value中lru属性中。
2、当内存达到maxmemory时,会随机抽取5(可以通过maxmemory-policy设定)个样本key进行时间戳判断,淘汰时间戳最小的(也就是最久远的一个key)

优点:不用额外的维护一个链表,节省了内存,同时随机采样淘汰方式也避免了大数据量key遍历处理的耗时。

缺点:因为是随机采样删除,所以会出现更早key迟迟没有被采样删除的情况。钉子户

Redis3.0 做了LRU算法升级

Redis在3.0之后对LRU算法做了升级,加入了候选池Pool(16字节),首次抽样5个会放入都Pool中,并按照时间大小lru排序,后续每次选取的Key的lru必须要小于pool的最小值(也就是key要比pool中的更早),才放入pool中,直到pool满,当有新元素加入时,只需要将pool中最万的key(也就是最大的)删除即可。

升级之后的算法,可以更大密度的将更久没有使用的key删除,减少了钉子户的存在。

RedisLFU算法

在Redis4.0 推出了LFU算法,这个是基于访问次数维护的回收算法,算法和LRU差不多,就是在lru中加入了请求次数的计数count维护。从时间和频次两个维度来计算key的热度。他的好处是,如果一个key很就没有被访问到,突然最近被访问了一次,在LRU算法中,它是不容易被淘汰的,但是在LRF算法中,会统计它访问频次,发现不足定位很热的key,所以还是会被删除。所以LFU算法很适合用于热点数据的删除策略。

相关文章:

LRU算法 vs Redis近似LRU算法

LRU(Least Recently Use)算法,是用来判断一批数据中,最近最少使用算法。它底层数据结构由Hash和链表结合实现,使用Hash是为了保障查询效率为O(1),使用链表保障删除元素效率为O(1)。 LRU算法是用来判断最近最少使用到元素&#xf…...

浅析ARMv8体系结构:异常处理机制

文章目录 概述异常类型中断终止Abort复位Reset系统调用 异常处理流程异常入口异常返回异常返回地址 堆栈选择 异常向量表异常向量表的配置 同步异常解析相关参考 概述 异常处理指的是处理器在运行过程中发生了外部事件,导致处理器需要中断当前执行流程转而去处理异…...

Golang开发--Goroutine的使用

Go 语言天生支持并发编程,提供了丰富的原语和工具来编写并发程序。Goroutine 是 Go 语言中的轻量级执行单位。它们是由 Go 运行时(runtime)管理的,并且能够在单个线程上运行成千上万个 Goroutine。创建 Goroutine 非常高效&#x…...

【Linux】package ‘python-yaml‘ has no installation candidate 如何解决

要解决此问题,可以尝试以下几个步骤: 确保系统已经更新到最新版本。可以使用以下命令进行系统更新: sudo apt update sudo apt upgrade确保您的软件源列表中包含了正确的软件源。可以使用以下命令编辑软件源列表: sudo nano /etc/…...

Selector选择器在AspNetCore中的用法

Selector选择器在AspNetCore中的用法 背景 项目编辑过程中会选择其所属的上级项目,而上级项目在数据结构中是以ParentID的方式表达,而非Project类型,用户不会记录也不应该记录ID值,因此应提供Selector项目下拉框供用户选择。 但…...

anaconda3最新版安装|使用详情|Error: Please select a valid Python interpreter

Win11查看安装的Python路径及安装的库 anaconda3最新版安装|使用详情|Error: Please select a valid Python interpreter 介绍开源包管理系统和环境管理系统 ,包括多种语言的包安装,运行,更新,删除,最重要的是可以解…...

java八股文面试[多线程]——锁的分类

1.1 可重入锁、不可重入锁 Java中提供的synchronized,ReentrantLock,ReentrantReadWriteLock都是可重入锁。 重入:当前线程获取到A锁,在获取之后尝试再次获取A锁是可以直接拿到的。 不可重入:当前线程获取到A锁&…...

儿童安全门和围栏,以及游戏围栏等美国站要求的合规标准是什么?

儿童安全门和围栏 儿童安全门和围栏用于在门口(如门道)内设置围栏,或用作自支撑围栏,将幼儿可能在其中活动的区域围起来。这些商品可能由塑料、金属、乙烯树脂或木制组件等材料制成。此政策包括但不限于可扩展围栏、伸缩安全门和…...

kafka配合ElasticStack技术栈的搭配使用

今日内容: - kafka生产环境调优; - kafka配合ElasticStack技术栈的搭配使用; - zookeeper集群部署; - zookeeper的ACL; - zookeeper的调优; - PB级别项目; - ES8集群搭建/elk; (待定...) 订阅1个的topic: 老男孩: 10 多个不同的主题…...

对极几何与三角化求3D空间坐标

一&#xff0c;使用对极几何约束求R,T 第一步&#xff1a;特征匹配。提取出有效的匹配点 void find_feature_matches(const Mat &img_1, const Mat &img_2,std::vector<KeyPoint> &keypoints_1,std::vector<KeyPoint> &keypoints_2,std::vector&l…...

英语语法笔记

1.英语五大句型 主谓&#xff08;主语动词&#xff09; 主谓宾&#xff08;主语动词宾语&#xff09; 主谓宾宾&#xff08;主语动词简接宾语直接宾语&#xff09; 主谓宾补&#xff08;主语动词宾语宾语补语&#xff09; 主系表&#xff08;主语系动词主语补语&#xff09; 1…...

ES6的面向对象编程以及ES6中的类和对象

一、面向对象 1、面向对象 &#xff08;1&#xff09;是一种开发思想&#xff0c;并不是具体的一种技术 &#xff08;2&#xff09;一切事物均为对象&#xff0c;在项目中主要是对象的分工协作 2、对象的特征 &#xff08;1&#xff09;对象是属性和行为的结合体 &#x…...

ConfigMaps in K8s

摘要 ConfigMaps是Kubernetes&#xff08;K8s&#xff09;中用于存储应用程序配置信息的一种资源对象。它将key-value对存储为Kubernetes集群中的一个资源&#xff0c;并可以在Pod中以卷或环境变量的形式使用。 ConfigMaps的设计目的是将应用程序配置与应用程序本身解耦。它可…...

《机器人学一(Robotics(1))》_台大林沛群 第 6 周 【轨迹规划_直线转折处抛物线平滑】Quiz 6

步骤&#xff1a; 1、 编程 将PPT 的例子 跑一遍&#xff0c; 确保代码无误 2、根据题目 修改 相关参数 文章目录 求解代码_Python 解决的问题&#xff1a; 线段间转折点 的 速度 不连续 解决方法&#xff1a; 将直线段 两端 修正为 二次方程式 二次项圆滑 求解代码_Python …...

关于vscode的GitLens插件里的FILE HISTORY理解

最近在用vscode的GitLens插件开发项目遇到这个疑问&#xff0c;先看图&#xff1a; 每当我点击FILE HISTORY 一个commit时&#xff0c;正常来说显示器会自动将点击的提交版本和它上一个提交版本进行比较&#xff0c;如果单纯这么理解的话就错了&#xff0c;因为GitLens的File …...

通过idea实现springboot集成mybatys

概述 使用springboot 集成 mybatys后&#xff0c;通过http请求接口&#xff0c;使得通过http请求可以直接直接操作数据库&#xff1b; 完成后端功能框架&#xff1b;前端是准备上小程序&#xff0c;调用https的请求接口用。简单实现后端框架&#xff1b; 详细 springboot 集…...

力扣(LeetCode)算法_C++——移位字符串分组

给定一个字符串&#xff0c;对该字符串可以进行 “移位” 的操作&#xff0c;也就是将字符串中每个字母都变为其在字母表中后续的字母&#xff0c;比如&#xff1a;“abc” -> “bcd”。这样&#xff0c;我们可以持续进行 “移位” 操作&#xff0c;从而生成如下移位序列&am…...

Vue2 与Vue3的区别?面试题

Vue 2和Vue 3是Vue.js框架的不同版本&#xff0c;在面试中经常涉及到它们之间的区别。以下是Vue 2和Vue 3的主要区别&#xff1a; 性能提升&#xff1a;Vue 3在性能方面进行了优化。Vue 3引入了更高效的Diff算法&#xff0c;提高了渲染性能。此外&#xff0c;Vue 3还进行了代码…...

java代码:Random和Scanner应用的小例子-猜数字小游戏

//java代码&#xff1a;Random和Scanner应用的小例子-猜数字小游戏 package com.test; import java.util.Random; import java.util.Scanner; /* * 需求&#xff1a;猜数字小游戏。 * 系统产生一个1-100之间的随机数&#xff0c;请猜出这个数据是多少? * * 分析…...

python调用git出错:ImportError: Failed to initialize: Bad git executable.

报错信息 #报错信息 Traceback (most recent call last): File “”, line 1, in File “C:\Python27\lib\site-packages\git_init_.py”, line 85, in raise ImportError(‘Failed to initialize: {0}’.format(exc)) ImportError: Failed to initialize: Bad git executab…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...