LRU 与 LFU 缓存数据算法

2023-10-20 08:38
文章标签 算法 lru lfu 缓存数据

本文主要是介绍LRU 与 LFU 缓存数据算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2. LRU
2.1. 原理

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

2.2. 实现

最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:


1. 新数据插入到链表头部;

2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

3. 当链表满的时候,将链表尾部的数据丢弃。

2.3. 分析

【命中率】

当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

【复杂度】

实现简单。

【代价】

命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。


3. LRU-K
3.1. 原理

LRU-K中的K代表最近使用的次数,因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

3.2. 实现

相比LRU,LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下:


1. 数据第一次被访问,加入到访问历史列表;

2. 如果数据在访问历史列表里后没有达到K次访问,则按照一定规则(FIFO,LRU)淘汰;

3. 当访问历史队列中的数据访问次数达到K次后,将数据索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序;

4. 缓存数据队列中被再次访问后,重新排序;

5. 需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。

LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史访问记录清除掉。

3.3. 分析

【命中率】

LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。

【复杂度】

LRU-K队列是一个优先级队列,算法复杂度和代价比较高。

【代价】

由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象,因此内存消耗会比LRU要多;当数据量很大的时候,内存消耗会比较可观。

LRU-K需要基于时间进行排序(可以需要淘汰时再排序,也可以即时排序),CPU消耗比LRU要高。


1. LFU类

1.1. LFU
1.1.1. 原理

LFU(Least Frequently Used)算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。

1.1.2. 实现

LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。

具体实现如下:

 

1. 新加入数据插入到队列尾部(因为引用计数为1);

2. 队列中的数据被访问后,引用计数增加,队列重新排序;

3. 当需要淘汰数据时,将已经排序的列表最后的数据块删除。

1.1.3. 分析

l 命中率

一般情况下,LFU效率要优于LRU,且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录,一旦数据访问模式改变,LFU需要更长时间来适用新的访问模式,即:LFU存在历史数据影响将来数据的“缓存污染”效用。

l 复杂度

需要维护一个队列记录所有数据的访问记录,每个数据都需要维护引用计数。

l 代价

需要记录所有数据的访问记录,内存消耗较高;需要基于引用计数排序,性能消耗较高。

 

算法数据结构和实习




1.2. LFU*
1.2.1. 原理

基于LFU的改进算法,其核心思想是“只淘汰访问过一次的数据”。

1.2.2. 实现

LFU*数据缓存实现和LFU一样,不同的地方在于淘汰数据时,LFU*只淘汰引用计数为1的数据,且如果所有引用计数为1的数据大小之和都没有新加入的数据那么大,则不淘汰数据,新的数据也不缓存。

1.2.3. 分析

l 命中率

和LFU类似,但由于其不淘汰引用计数大于1的数据,则一旦访问模式改变,LFU*无法缓存新的数据,因此这个算法的应用场景比较有限。

l 复杂度

需要维护一个队列,记录引用计数为1的数据。

l 代价

相比LFU要低很多,不需要维护所有数据的历史访问记录,只需要维护引用次数为1的数据,也不需要排序。

1.3. LFU-Aging
1.3.1. 原理

基于LFU的改进算法,其核心思想是“除了访问次数外,还要考虑访问时间”。这样做的主要原因是解决LFU缓存污染的问题。

1.3.2. 实现

虽然LFU-Aging考虑时间因素,但其算法并不直接记录数据的访问时间,而是通过平均引用计数来标识时间。

LFU-Aging在LFU的基础上,增加了一个最大平均引用计数。当当前缓存中的数据“引用计数平均值”达到或者超过“最大平均引用计数”时,则将所有数据的引用计数都减少。减少的方法有多种,可以直接减为原来的一半,也可以减去固定的值等。

1.3.3. 分析

l 命中率

LFU-Aging的效率和LFU类似,当访问模式改变时,LFU-Aging能够更快的适用新的数据访问模式,效率要高。

l 复杂度

在LFU的基础上增加平均引用次数判断和处理。

l 代价

和LFU类似,当平均引用次数超过指定阈值(Aging)后,需要遍历访问列表。

 

1.4. LFU*-Aging
1.4.1. 原理

LFU*和LFU-Aging的合成体。

1.4.2. 实现

略。

1.4.3. 分析

l 命中率

和LFU-Aging类似。

l 复杂度

比LFU-Aging简单一些,不需要基于引用计数排序。

l 代价

比LFU-Aging少一些,不需要基于引用计数排序。


1.5. Window-LFU
1.5.1. 原理

Windows-LFU是LFU的一个改进版,差别在于Window-LFU并不记录所有数据的访问历史,而只是记录过去一段时间内的访问历史,这就是Window的由来,基于这个原因,传统的LFU又被称为“Perfect-LFU”。

1.5.2. 实现

与LFU的实现基本相同,差别在于不需要记录所有数据的历史访问数据,而只记录过去一段时间内的访问历史。具体实现如下:

 

1)记录了过去W个访问记录;

2)需要淘汰时,将W个访问记录按照LFU规则排序淘汰

 

举例如下:

假设历史访问记录长度设为9,缓存大小为3,图中不同颜色代表针对不同数据块的访问,同一颜色代表针对同一数据的多次访问。

样例1:黄色访问3次,蓝色和橘色都是两次,橘色更新,因此缓存黄色、橘色、蓝色三个数据块

样例2:绿色访问3次,蓝色两次,暗红两次,蓝色更新,因此缓存绿色、蓝色、暗红三个数据块

 

1.5.3. 分析

l 命中率

Window-LFU的命中率和LFU类似,但Window-LFU会根据数据的访问模式而变化,能够更快的适应新的数据访问模式,”缓存污染“问题不严重。

l 复杂度

需要维护一个队列,记录数据的访问流历史;需要排序。

l 代价

Window-LFU只记录一部分的访问历史记录,不需要记录所有的数据访问历史,因此内存消耗和排序消耗都比LFU要低。

1.6. LFU类算法对比

由于不同的访问模型导致命中率变化较大,此处对比仅基于理论定性分析,不做定量分析。

 

对比点

对比

命中率

Window-LFU/LFU-Aging > LFU*-Aging > LFU > LFU*

复杂度

LFU-Aging > LFU>  LFU*-Aging  >Window-LFU > LFU*

代价

LFU-Aging > LFU > Window-LFU > LFU*-Aging  > LFU*

这篇关于LRU 与 LFU 缓存数据算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/245974

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖