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* |
相关推荐
本算法为 C++ 实现的 LFU 缓存算法,数据结构为 2 个哈希表再加上 N 个双链表,实现了 get() 和 put() 两个操作,且所有操作的平均时间复杂度均可以控制在 O(1) 内。
最近最少使用算法(LFU):最近最少使用的内容作为替换对象 最久未使用算法(LRU):最久没有访问的内容作为替换对象 非最近使用算法(NMRU):在最近没有使用的内容中随机选择一个作为替换对象 其他算法,包括变种...
为了解决现有的数据缓存回收算法不适用于混合...仿真结果显示,相比三种典型的缓存替换算法GD-Size、LRU和LFU,提出的云服务算法每年能够节约成本11.43%,同时提高了转发字节命中率、延迟节约率和缓存命中率10%以上。
现有的Web缓存器的实现主要是基于传统的内存缓存算法,由于Web业务请求的异质性,传统的替换算法不能在Web环境中有效工作。研究了Web缓存替换操作的依据,分析了以往替换算法的不足,考虑到Web文档的大小、访问代价...
在SCU-K算法的基础上,提出了基于流行度和将来访问次数的最小效用替换算法...不但避免LRU和LFU算法中出现的媒体文件被连续替换的问题,相对于LRU、LFU和SCU-2,其在缓存命中率、字节命中率和空间利用率都得到了提升。
FIFO,LFU实现页面置换算法(模拟)
mcache 增加了缓存过期时间,增加lfu算法,修改了原有arc算法的依赖结构. 后续还会源源不断增加内存算法. 特征 根据过期时间懒汉式删除过期数据,也可主动刷新过期缓存 why? 为什么要用mcache? 因缓存的使用相关需求,...
可配置的最大尺寸 ...LFU(最不常用)作为缓存算法 FIFO(先进先出)作为缓存算法 新缓存算法的可扩展性 TTL(生存时间)支持 支持不可散列的参数(字典、列表等) 自定义缓存键 按需部分缓存清除 遍历缓存
常见的缓存算法 LRU (Least recently used) 最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。 LFU (Least frequently used) 最不经常使用,如果一个数据在最近一段时间内使用次数很少,
一种针对片上众核结构共享末级缓存的改进的LFU替换算法
该算法结合了常用的LFU和LRU算法,并具有自适应调整性,可提供更好的命中率,并无需用户进行参数设置。 PrimoCache支持多种缓存策略以及灵活的缓存设置。您可轻松为您的物理硬盘创建缓存,提高硬盘的读写性能。由于...
Go的缓存基准该基准测试比较了使用加扰后的zipfian分布的缓存算法(少数情况经常发生,而其他情况则很少发生)。 也支持其他发行版,但它们产生相同的结果支持以下库: ) 结果是: zipfian size=1000 samples=10000...
mark: LRU(最近最少使用)作为缓存算法 :check_mark: :check_mark: LFU(最不常用)作为缓存算法没有支持 :check_mark: FIFO(先进先出)作为缓存算法没有支持 :check_mark: 新缓存算法的可扩展性没有支持 :check_m
java lru leetcode 缓存 具有可配置驱逐策略(LRU 或 LFU)的缓存实现 LRU 策略的灵感来自 SO 的这个解决方案: LFU 策略是使用这种方法实现的,时间复杂度为 O(1):
ARC使用学习规则来适应性地,不断地修改其有关工作负载的假设,以调整内部LRU和LFU缓存的大小。 此实现基于Nimrod Megiddo和Dharmendra S. Modha的 ,尽管绝对有用,但这仍然是一个实验,不应该视为已投入生产。 ...
最近最少频率使用缓存(LFU Cache) 线性同余生成器(Linear Congruential Generator) 最近最久未使用缓存(LRU Cache) 魔幻菱形模式(Magic Diamond Pattern) 最大子数组(Maximum Subarray) 最大子序列...
:revolving_hearts:数据结构和算法 CH LFU LRU :woman_biking:网络 :hollow_red_circle:操作系统 Linux :information:数据库 Oracle MYQL 事务 - 未学习 Redis 持久化机制 - 未学习 内存淘汰机制 - 未学习 分片机制 ...
提出了以四叉树作为缓存数据结构,结合广泛应用的LRU和LFU算法,给出了一种高效的缓存策略—基于四叉树的空间数据缓存策略,并详细描述了缓存框架和缓存策略。提出的缓存策略充分考虑了空间数据访问所具有的时间局部...
lru缓存leetcode 算法和数据结构 算法 标题 执行 在线裁判 快速排序 归并排序 堆排序 数据结构 标题 执行 在线裁判 优先队列 向量 LRU缓存 LFU缓存
缓存模拟器这是一组文件,将模拟 4 种不同的缓存算法:第二次机会、最不常用 (LFU)、最近最少使用 (LRU) 和随机。 这些都由双端队列作为主干数据类型提供支持。 所有文件都是用C编写的。 模拟这些不同算法的程序被...