精华内容
下载资源
问答
  • 缓存替换策略

    千次阅读 2019-07-09 09:50:58
    替换掉最近被请求最少的对象,这种传统策略在实际中应用最广。在CPU缓存淘汰和虚拟内存系统中效果很好。然而在直接应用与代理缓存中效果欠佳,因为Web访问的时间局部性常常变化很大。 浏览器就一般使用了LRU作为缓存...

    替代策略的具体实现就是缓存算法,这里简要介绍一下主流的缓存算法:


    (1)Least-Recently-Used(LRU)


    替换掉最近被请求最少的对象,这种传统策略在实际中应用最广。在CPU缓存淘汰和虚拟内存系统中效果很好。然而在直接应用与代理缓存中效果欠佳,因为Web访问的时间局部性常常变化很大。
    浏览器就一般使用了LRU作为缓存算法。新的对象会被放在缓存的顶部,当缓存达到了容量极限,底部的对象被去除,方法就是把最新被访问的缓存对象放到缓存池的顶部。


    (2)Least-Frequently-Used(LFU)


    替换掉访问次数最少的缓存,这一策略意图是保留最常用的、最流行的对象,替换掉很少使用的那些数据。然而,有的文档可能有很高的使用频率,但之后再也不会用到。传统的LFU策略没有提供任何移除这类文件的机制,因此会导致“缓存污染”,即一个先前流行的缓存对象会在缓存中驻留很长时间,这样,就阻碍了新进来可能会流行的对象对它的替代。


    (3)Least Recently Used 2(LRU2)


    LRU的变种,把被两次访问过的对象放入缓存池,当缓存池满了之后,会把有两次最少使用的缓存对象去除。因为需要跟踪对象2次,访问负载就会随着缓存池的增加而增加。


    (4)Two Queues(2Q)


    Two Queues是LRU的另一个变种,把被访问的数据放到LRU的缓存中,如果这个对象再一次被访问,就把他转移到第二个、更大的LRU缓存,使用了多级缓存的方式。去除缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候,把LRU换成LRU2,就比增加缓存的容量更好。


    (5)SIZE


    替换占用空间最大的对象,这一策略通过淘汰一个大对象而不是多个小对象来提高命中率。不过,可能有些进入缓存的小对象永远不会再被访问。SIZE策略没有提供淘汰这类对象的机制,也会导致“缓存污染”。


    (6)LRU-Threshold


    不缓存超过某一size的对象,其他与LRU相同。


    (7)Log(Size)+LRU


    替换size最大的对象,当size相同时,按LRU进行替换。


    (8)Hyper-G


    LFU的改进版,同时考虑上次访问时间和对象size。


    (9)Pitkow/Recker


    替换最近最少使用的对象,除非所有对象都是今天访问过的。如果是这样,则替换掉最大的对象。这一策略试图符合每日访问Web网页的特定模式。这一策略也被建议在每天结束时运行,以释放被“旧的”、最近最少使用的对象占用的空间。


    (10)Lowest-Latency-First


    替换下载时间最少的文档。显然它的目标是最小化平均延迟。


    (11)Hybrid Hybrid


    有一个目标是减少平均延迟。对缓存中的每个文档都会计算一个保留效用,保留效用最低的对象会被替换掉。位于服务器s的文档f的效用函数定义如下:
    [插图]
    Cs是与服务器s的连接时间;bs是服务器s的带宽;frf代表f的使用频率;sizef是文档f的大小,单位字节。K1和K2是常量,Cs和bs是根据最近从服务器s获取文档的时间进行估计的。


    (12)Lowest Relative Value(LRV)


    LRV也是基于计算缓存中文档的保留效用,然后替换保留效用最低的文档。


    (13)Adaptive Replacement Cache(ARC)


    ARC介于LRU和LFU之间,为了提高效果,由2个LRU组成,第一个包含的条目是最近只被使用过一次的,而第二个LRU包含的是最近被使用过两次的条目,因此,得到了新的对象和常用的对象。ARC能够自我调节,并且是低负载的。


    (14)Most Recently Used(MRU)


    MRU与LRU是相对,移除最近最多被使用的对象。当一次访问过来的时候,有些事情是无法预测的,并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算,这时会考虑MRU,在数据库内存缓存中比较常见。


    (15)First in First out(FIFO)


    FIFO通过一个队列去跟踪所有的缓存对象,最近最常用的缓存对象放在后面,而更早的缓存对象放在前面,当缓存容量满时,排在前面的缓存对象会被踢走,然后把新的缓存对象加进去。


    (16)Random Cache


    随机缓存就是随意的替换缓存数据,比FIFO机制好,在某些情况下,甚至比LRU好,但是通常LRU都会比随机缓存更好些。
    还有很多的缓存算法,例如Second Chance、Clock、Simple time-based、Extended time-based expiration、Sliding time-based expiration……各种缓存算法没有优劣之分,不同的实际应用场景,会用到不同的缓存算法。在实现缓存算法的时候,通常会考虑使用频率、获取成本、缓存容量和时间等因素

    展开全文
  • 通过优化权重模型和改进替换策略,提出了一种高效RDD自主缓存替换策略(efficient RDD automatic cache,ERAC),包括高重用自主缓存算法和缓存替换分级算法,可实现高效RDD的自主缓存和缓存目标的分级替换。...
  • 针对该问题,提出一种基于内容优先级的缓存替换策略PFC。根据节点内容对可用性的不同需求划分内容优先级,将其作为缓存替换的参考因子进行缓存替换决策,以提高重要内容的命中率和可用性。在ndnsim仿真平台上的测试...
  • 缓存替换策略 缓存在计算机世界里是非常有用的。在计算中,高速缓存算法(也经常被称为高速缓存替换算法或高速缓存替换策略)是一种优化指令或算法,该计算机程序或硬件维护结构,可以在为了管理的计算机上存储的...

    缓存替换策略

    缓存在计算机世界里是非常有用的。在计算中,高速缓存算法(也经常被称为高速缓存替换算法或高速缓存替换策略)是一种优化指令或算法,该计算机程序或硬件维护结构,可以在为了管理的计算机上存储的信息的高速缓存利用。缓存可以提高通过保持在更快或更便宜的计算比正常存储器存储存取存储器位置最近或经常使用的数据项的性能。当缓存已满时,算法必须选择以腾出空间给新的人该项目丢弃。这就不得不介绍一些缓存替换的原理以及几种策略了。

    介绍

    策略

    • Bélády算法
    • 先进先出(FIFO)
    • 后进先出(LIFO)
    • 最近最少使用(LRU)
    • TLRU
    • 最近使用(MRU)
    • Pseudo-LRU(PLRU)
    • 随机替换(Random replacement, RR)
    • 分段LRU(Segmented LRU)
    • 最不经常使用(Least-frequently used, LFU)
    • 最近最不经常使用(Least frequent recently used, LFRU)
    • 动态老化LFU (LFU with dynamic aging, LFUDA )
    • Low inter-reference recency set(LIRS)
    • Adaptive replacement cache (ARC)
    • Clock with adaptive replacement (CAR)
    • Multi queue (MQ)
    • Pannier: Container-based caching algorithm for compound objects

    参考链接

    维基百科 Cache replacement policies

    展开全文
  • 形式化地给出了语义缓存的相关概念和定义,然后重点分析了语义缓存的FAR(furthest away replacement)替换策略并对其进行改进,提出基于增量聚类的DCFAR替换策略,最后对FAR和DCFAR替换策略进行实验分析,从而在...
  • 在计算中,缓存算法(通常也称为缓存替换算法或缓存替换策略)是优化指令或算法,计算机程序或硬件维护的结构可以利用这些指令或算法来管理存储在计算机上的信息缓存。高速缓存通过将最近或经常使用的数据项保存在比...

    缓存是一个计算机思维,对于重复的计算,缓存其结果,下次再算这个任务的时候,不去真正的计算,而是直接返回结果,能加快处理速度。当然有些会随时间改变的东西,缓存会失效,得重新计算。

    在计算中,缓存算法(通常也称为缓存替换算法或缓存替换策略)是优化指令或算法,计算机程序或硬件维护的结构可以利用这些指令或算法来管理存储在计算机上的信息缓存。高速缓存通过将最近或经常使用的数据项保存在比普通内存存储区更快或更便宜的存储位置中来提高性能。当缓存已满时,算法必须选择要丢弃的项目,以便为新项目腾出空间。

    比如缓存空间只有2个,要缓存的数据有很多,1,2,3,4,5,那么当缓存空间满了,需要淘汰一个缓存出去,其中淘汰算法有 LRU,LFU,FIFO,SC二次机会,老化算法,时钟工作集算法等等。


    Least recently used (LRU)

    LRU:最近最少使用,把数据加入一个链表中,按访问时间排序,发生淘汰的时候,把访问时间最旧的淘汰掉。属于时间维度优化。

    此算法需要跟踪何时使用了什么,如果要确保算法始终丢弃最近最少使用的商品,这将非常昂贵。该技术的一般实现方式需要为缓存行保留 “age bits (年龄位)” ,并根据年龄位跟踪“最近最少使用”的缓存行。在这样的实现中,每次使用高速缓存行时,所有其他高速缓存行的寿命都会改变。

    比如有数据ABCDEDF,一旦将ABCD安装到具有序列号的块中(每个新Access的增量为1),并且当访问E时,它是未命中的,因此需要将其安装在其中一个块中。根据LRU算法,由于A具有最低的Rank(A(0))Rank(A(0)),因此E将替换A。

    在这里插入图片描述

    Most recently used (MRU)

    LRU相比,发生淘汰的时候,把访问时间最新的淘汰掉。对于随机访问模式和对大型数据集的重复扫描(有时称为循环访问模式),由于MRU缓存算法倾向于保留较旧的数据,因此它们比LRU命中率高。MRU算法在一项项目越旧,访问该项目的可能性越大的情况下最有用。
    在这里插入图片描述


    Pseudo-LRU (PLRU)

    这种技术在使用CPU高速缓存中的英特尔486和在很多处理器的PowerPC家族,如飞思卡尔 的PowerPC G4通过使用苹果电脑。

    对于具有较大关联性的CPU缓存(通常> 4种方式),LRU的实现成本变得过高。在许多CPU缓存中,几乎总是丢弃最近使用最少的一项的方案就足够了,因此许多CPU设计人员选择了PLRU算法,该算法每个缓存项只需要一位即可工作。与LRU相比,PLRU通常具有稍差的未命中率,稍稍更好的等待时间,比LRU消耗更少的功率以及更低的开销。

    该算法的工作方式如下:考虑一个二叉搜索树(BST)为所讨论的项目。树的每个节点具有一位标志,该标志指示“向左查找伪LRU元素”或“向右查找伪LRU元素”。要查找伪LRU元素,请根据标志的值遍历树。要使用对项N的访问来更新树,请遍历树以找到N,并在遍历期间将节点标志设置为表示与所取方向相反的方向。

    在这里插入图片描述
    在这里插入图片描述
    访问顺序为ABCDE。如果只看箭头,这里的原理很容易理解。当可以访问值时,说A,我们无法在缓存中找到它,然后从内存中加载它,并将其放置在箭头所指的块上,从上到下,并在放置该块时使箭头指向远离该块的底部和顶部。在上面的示例中,我们看到如何放置A,然后放置BCD。然后,当缓存已满时,E替换为A,因为那是箭头所指的时间。下次访问时,将替换保存B的块。

    该算法可能是次优的,因为它是近似值。例如,在上图中具有A,C,B,D缓存行的情况下,如果访问模式为:C,B,D,A则在逐出时我们选择B而不是C。这是因为AC在同一部分,访问A会将算法定向到不包含高速缓存行C的另一部分。


    Least-frequently used (LFU)

    LFU最近不经常使用,把数据加入到链表中,按频次排序 ,一个数据被访问过,把它的频次+1,发生淘汰的时候,把频次低的淘汰掉。属于统计维度优化。

    比如有数据 A,A,A,B,B,C
    缓存中有A(3)B(2)A(3次),B(2次)
    C加入的时候,得把后面的B淘汰,变成A(3)B(1)A(3次),B(1次)

    区别:LRU 是得把 A 淘汰,应为A最早被访问。

    显然,LRU对于循环出现的数据,缓存命中不高
    比如,这样的数据,A,A,A,B,B,B,C,D,A,A,A,B,B,B.....
    当走到C,D的时候,A,B会被淘汰掉,但是后面还有很多A,B

    LFU对于交替出现的数据,缓存命中不高
    比如,A,A,A,B,B,C,D,C,D,C,D,C,D,C,D,C,D......
    由于前面被A(3)B(2)A(3次),B(2次)
    C加入把B淘汰,D加入把C淘汰,C加入把D淘汰,然而C,D才是最需要缓存的,A出现了3次,谁也淘汰不了它了。


    Low inter-reference recency set (LIRS)

    LIRS(低相互参照新近度集)是一种页面替换算法,其性能优于LRU和许多其他更新的替换算法。这是通过使用重用距离作为对访问页面进行动态排名以做出替换决定的指标来实现的。该算法由宋江和张晓东开发。

    LIRS组织缓存页面和一些未缓存页面的元数据,并执行其替换操作,如下所述,这些操作也以示例在图中进行了说明。
    在这里插入图片描述
    在上图中,x表示在时间t访问一个块。

    假设如果在时间1访问块A1,则由于这是第一个被访问的块,因此最近度将变为0,由于IRR预测将在时间3再次访问A1,因此IRR将为1

    自访问A4以来的时间2中,由于A4是最近访问的对象,并且IRR变为4,它将继续,因此A4的新近度将变为0A1的新近度将变为1

    时间10LIRS算法将具有两组LIR集= {A1,A2}HIR集= {A3,A4,A5}。现在在时间10,如果可以访问A4,则会发生未命中。LIRS算法由于其最大的新近性,现在将逐出A5而不是A2

    实现

    leetcode上有两个题目:

    • LRU:https://leetcode.com/problems/lru-cache/description/
    • LFU:https://leetcode.com/problems/lfu-cache/description/


    参考资料:

    展开全文
  • 常用的缓存替换策略

    2016-02-18 22:47:22
    [*]LRU,最近最少使用,移除最长时间不被使用的对象,默认策略 [*]FIFO,先进先出,按对象进入缓存的顺序来移除它们 [*]SOFT,软引用,移除基于垃圾回收器状态和软引用规则的对象 [*]WEAK,弱引用,更积极地移除...
    [list]
    [*]LRU,最近最少使用,移除最长时间不被使用的对象,默认策略
    [*]FIFO,先进先出,按对象进入缓存的顺序来移除它们
    [*]SOFT,软引用,移除基于垃圾回收器状态和软引用规则的对象
    [*]WEAK,弱引用,更积极地移除基于垃圾收集器状态和弱引用规则的对象
    [/list]
    展开全文
  • 目录 ... 缓存缺失及其处理 ...缓存替换及其处理 当被替换的数据块涉及写操作时,需要进行额外处理,以保证内存与缓存数据同步 缓存性能及其分析 注;多级缓存的访问时间按照概率论的思路进行加权计算即可 ...
  • 缓存替换策略都太过于单一,缺乏灵活性。 大家好,我想设计一个算法,通过用户访问的次数C(count),内容的类型T(type,设定优先级),内容的最近一次访问的时间L(last_time),网络带宽流量消耗W(web_waste)等4个...
  • 首先,你需要了解E-ways组关联缓存的组织以及普通LRU替换算法。本文介绍一种,【近似】的LRU算法,它是借助一颗完全二叉树实现的。 考虑一个set中有n行的缓存(n-ways)。它们最近访问的时间有n!种组合(就是将...
  • 缓存替换策略

    千次阅读 2018-10-13 21:43:31
    缓存替换策略 在计算中,缓存(经常被称为缓存替换策略)是一些优化的指令或者算法,使得计算程序或者一个持有硬件的结构能统一有秩序的管理缓存信息。什么是缓存?缓存是什么?缓存和内存的区别缓存可以提高性能,...
  • 首先将单节点的缓存替换问题,建模为0/1背包问题,并根据缓存数据的大小、使用频率以及邻居副本深度等信息定义本地存储内容的缓存价值,提出基于蚁群算法的缓存替换算法。然后利用邻域协作的思想,通过路由节点之间...
  • 高速缓存替换算法 前言 替换时机 二、替换算法 1.随机算法 2.先进先出算法(FIFO) 3.最不经常使用算法(LFU) 4.最近最少使用算法(LRU) 前言 随着计算机不断发展,计算机原理这门基础课也越来越重要,本文就介绍...
  • 缓存的作用以及缓存替换算法缓存的作用缓存的生存期和生存范围缓存的生存期缓存的生存范围生存范围:状态有访问权限的物理或逻辑范围缓存的原理缓存的数据结构直接映射组相联映射全相联映射Cache 的关联度,命中与不...
  • 替换策略是高速缓存设计的一个重要方面。当不命中时,必须将相应的主存块取入高速缓存,相应地,要把其中已有的某一块替换出去。若高速缓存内有无效块,则替换是不成问题的。对于直接映射高速缓存,只有1个块可供...
  • dm_cache中缓存查询与替换策略分析

    千次阅读 2014-03-14 00:02:01
    cache_lookup函数涉及dm_cache的缓存块映射方式、查找算法及缓存替换策略,详细分析该函数有窥一斑而知全豹的效果。 注:dm-cache缓存块的几种状态 有效块(valid):与原磁盘数据块一致; 保留块(reserved):该...
  • 缓存替代策略

    2020-06-03 23:17:27
    缓存算法新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表...
  • 缓存淘汰策略

    千次阅读 2018-06-11 14:52:29
    缓存淘汰策略用于决定缓存系统中哪些数据应该被删去。常见算法类型包括LFU、LRU、ARC、FIFO、MRU。最不经常使用算法(LFU):这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法,最低访问数的...
  • 安卓中的缓存包括两种情况即内存缓存与磁盘缓存,其中内存缓存主要是使用LruCache这个类,其中内存缓存我在【安卓中的缓存策略系列】安卓缓存策略之内存缓存LruCache中已经进行过详细讲解,如看官还没看过此博客,...
  • 缓存算法:缓存法通过设计良好的数据分块、预取、顺序预取、缓存替换等算法来提高对缓存内容的命中率。缓存算法可以分为基于访问时间的策略、基于访问频率的策略、访问时间与频率兼顾策略、时间距离分布策略等类型。...
  • 缓存算法:缓存法通过设计良好的数据分块、预取、顺序预取、缓存替换等算法来提高对缓存内容的命中率。缓存算法可以分为基于访问时间的策略、基于访问频率的策略、访问时间与频率兼顾策略、时间距离分布策略等类型。...
  • Redis的持久化方式和缓存淘汰策略

    千次阅读 2019-06-21 14:35:42
    redis的持久化方式和缓存淘汰策略 每天多学一点点~ 写博客的目的不仅在于分享,也是为了方便日后复习巩固 话不多说,这就开始吧… 文章目录redis的持久化方式和缓存淘汰策略1.序2.RDB快照(snapshot)2.AOF(append-...
  • LRU-K缓存替换算法

    千次阅读 2014-03-13 16:24:44
    给定一组缓存页面N={p1,p2,p3,p4.....pn},它是我们要访问的对象(当然是缓存已命中的情形),另外再给出一组访问序列R={r1,r2,r3....rt......}, r(t)=p(p属于N,意思就是第t次访问的是p页面)。对于任意的t值,我们...
  • 十种常用的缓存替换算法

    千次阅读 2014-06-05 09:46:22
    Least-Recently-Used(LRU) - 最近最少使用 替换掉最近被请求最少的文档。这一传统策略在实际中应用最广。在CPU缓存淘汰和虚拟内存系统中效果很好。...这一策略意图保留最常用的、最流行的对象,替换掉很少使用的那些。
  • LRU缓存替换算法介绍与编程实现

    千次阅读 2015-05-22 20:22:58
    部分原有得数据,有很多种替换策略,lru就是最近最少使用的被替换,我们想要 将来被使用的数据保留下来,但我们不知道将来会使用那些数据,就按照最近使用数据近似将来也会使用的数据。原理我们要如何体现最近最少...
  • 缓存替换算法笔记 ——2Q

    千次阅读 2014-07-17 16:22:31
    参考资料 ...2Q: A Low Overhead High Performance Buffer Management Replacement ...应用最广泛的缓存替换算法应该是LRU了,其实现简单有效。但正是因为其简单,对于某些访问场景来说表现并不出色。LRU
  • 缓存系列--缓存策略

    2017-11-26 00:47:29
    常用的缓存策略 LRU, FIFO,LFU, 等

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,165
精华内容 34,866
关键字:

缓存替换策略