普适环境中面向推理的上下文缓存置换算法

上下文缓存是减少上下文信息访问开销、降低信息传输数量、缓解连接中断引起的程序不可用性的有效途径.面向推理的上下文缓存置换算法CORA的目标是使上下文缓存达到较高命中率,有效节省普适计算中传输上下文的开销.CORA采用状态空间对低级上下文到高级上下文的推理进行建模,对各种上下文推理方法具有普遍适用性.CORA算法分为两个部分:1)在缓存端,该算法计算低级上下文的访问概率和预计失效时间,获得数据的缓存价值,作为上下文缓存置换的依据,以提高缓存的命中率;2)在传感器端设置相应的可变化范围,当传感器读数超出该范围时,主动更新缓存,以保证缓存数据的一致性.模拟实验将CORA和经典的缓存置换算法LRU进行对比,分别通过改变缓存容量、对上下文访问概率的不均匀程度和上下文更新访问比来考察两种算法的命中率,结果显示,当缓存容量相对上下文总数较小、访问概率分布较不均匀、更新访问比较高的情况下,CORA的命中率大大高于LRU.由此证明,CORA更适用于较为动态的普适计算环境.     

新的普适计算环境下上下文缓存置换算法

由于普适计算环境高度动态的特点以及无线环境连接易中断、传输速度低等方面的约束,使得普适计算应用对于上下文的访问开销非常大。为此,首先给出一个上下文感知系统框架,然后提出了一种基于规则的上下文缓存置换算法--RCRA,算法根据上下文的被访问概率、上下文时效性及历史访问次数决定是否将其置换出缓存。当有新的上下文需要进入缓存时执行该算法,以保证缓存中的上下文最新且最有价值。实验表明,RCRA不仅在命中率方面有较大提高,而且能够有效降低上下文访问的开销。算法应用于基于推理规则的上下文感知系统中,具有良好的可实用性。     

面向SSD寿命优化的访问序列折叠缓存替换算法*

SSD(solid state drive)的写入寿命比较有限,因此除命中率外,SSD缓存设备的写入量成为评价缓存替换算法的另一个关键指标。如何使算法提高写入数据转化为缓存命中的效率,从而延长SSD的使用寿命,具有重要的研究意义。目前,已有缓存替换算法的设计一般基于时间局部性,即刚被访问的数据短期内被访问的概率较高,因此需要频繁的数据更新和较高写入量来保证较高命中率;或是通过不低的开销屏蔽相对最差的部分数据来减少一定的写入量,还缺少用低开销获得数据长期热度规律,有效提高缓存数据质量的算法。提出了访问序列折叠的缓存替换算法,用比较低的开销定位拥有长期稳定热度的数据写入缓存,明显提高了SSD缓存数据质量,在保证命中率的同时减少了SSD的写入量。实验表明,访问序列折叠算法相比LRU(least recently used)算法可在命中率损失低于10%的情况下减少90%的写入量,与SieveStore、L2ARC(level2 adjustable replacement cache)等写入优化缓存算法相比,命中率相当时可将写入量减少50%以上,有效达到了通过缓存高质量数据,减少SSD的写入量,延长其使用寿命的目的。     

基于顺序检测的双队列缓存替换算法

缓存技术是提高存储性能最有效的技术之一,在存储系统中得到了广泛应用.由于缓存容量有限,替换算法在缓存策略中占据了重要地位.当前,缓存替换算法的研究工作主要集中在如何提高缓存系统命中率,忽略了通过降低缓存失效开销来提高缓存系统性能方面的研究.针对这一问题,本文提出了一种基于顺序检测的双队列缓存替换算法:本算法优先淘汰缓存中的顺序页面,保留随机页面,从而大大减少后续请求对磁盘进行随机访问的次数,能够显著降低缓存系统的失效开销.同时,本算法使用两个队列分别维护新加入页面和待淘汰页面,遵循时间局部性原理,保证了缓存命中率.实验结果表明,本算法在多种缓存大小及工作负载下,可以达到比LRU和ARC算法更优的性能.     

基于Hadoop视频转码缓存策略的研究

针对实时云转码系统中已转码的媒体文件重新使用率不高的情况,引入转码缓存机制,提出一种缓存替换策略。采用云存储空间缓存视频,根据视频资源的流行度、请求间隔、视频大小和未来被访问概率计算视频的效能函数值,当缓存空间不足时替换出效能值较小的视频。实验结果表明,与传统置换算法LRU、LFU和FIFO相比,该策略的资源请求命中率分别提高了2?6％,4?3％和9?2％,在一定程度上缩短了视频分发延迟,减少了用户响应时间。     

对象存储中基于高斯分布的分层缓存淘汰算法

在分布式存储系统中,引入分层缓存技术是优化系统读写的重要方法。目前分层缓存技术多使用LRU及其改进算法管理缓存空间,该方式虽然一定程度上改善了缓存性能,但有限的缓存命中率也使其成为性能瓶颈。针对此问题,本文研究聚焦于分布式对象存储在云计算场景下的应用特点,设计了一种基于高斯分布的淘汰算法。算法基于高斯分布的形态特征设计淘汰规则,规避了LRU及其改进算法采用频率估计概率的误差影响。通过仿真实验结果表明,在用户访问符合高斯分布时,本文提出的基于高斯分布的分层缓存淘汰算法能有效提高缓存命中率。     

基于时间间隔的P2P流媒体直播系统缓存算法

针对基于分片传输机制的P2P流媒体直播系统客户端缓存问题,为提高节点间请求数据分片的命中率和避免数据分片大量冗余,提出一种依赖邻居节点请求量的节点缓存替换算法.该算法将分片在节点的缓存时间进行等间隔划分,利用马尔可夫链转移概率矩阵计算理论,预测分片在下一时刻的缓存价值.并将该算法和传统算法FIFO及LRU算法进行了对比实验,实验结果表明,在同等条件下,该算法相较于传统算法能更好地提高数据的命中率.     

基于突发集中性访问模式的缓存替换算法

随着计算机系统对突发集中性问题访问规模的不断扩大,传统的最近最少使用(LRU)、最近最不常使用(LFU)等缓存替换算法已经难以满足高命中率、低延迟的要求。为此,针对数据突发集中性访问模式的特点,基于该模式对数据内容流行度变化趋势的影响,设计一种突发集中性访问模式的策略。该策略根据缓存的访问次数、访问时间、流行度预测等缓存信息,周期性地更新数据内容的置换优先级。同时对比LRU,LFU,LIRS及新策略在各种情况下,决定其数据内容置换优先级的因素。在模拟器Simple Scalar上的仿真结果表明,该策略在突发集中性访问模式下的性能优于传统的缓存替换策略。     

一种基于有限记忆多LRU的Web缓存替换算法

Web缓存的核心是缓存内容的替换算法.在动态不确定的网络环境下,本文提出一种基于有限记忆的多LRU (LH-MLRU)Web缓存替换算法,它是一种低开销、高性能和适应性的算法.LH-MLRU综合考虑各项因素对Web对象使用多个LRU队列进行分类管理,引入Web对象最近被访问的历史作为缓存内容替换的一个关键因素,来预测对象可能再次被访问的概率.通过周期性的训练参数可以适应动态不确定的网络环境.轨迹驱动的仿真实验表明LH-MLRU在各项性能指标上均优于其他算法,可以显著的提高Web缓存的性能.     

基于分级Cache的透明计算系统

设计并实现一个基于分级Cache的透明计算系统HCTS,在系统客户端和服务端采用两级缓存来提升I/O性能。在缓存的管理策略上,针对透明计算应用环境,以提高缓存命中率为主要目标,提出一种基于访问频率计数阈值的改进LRU置换算法LRU-AFS。测试结果表明,当网络环境中的客户主机数不断增加时,与普通透明计算系统TS相比,HCTS能够在减少网络流量的同时大幅缩短客户机启动时间,提高随机读写吞吐量。     

一种集群文件系统二级缓存协同置换算法

集群文件系统二级缓存置换算法中，某一存储节点的二级缓存单点不命中会破坏集群文件系统的并行性，从而降低其他存储节点二级缓存的效率，进而降低系统缓存的整体命中率。本文提出了存储节点间协同置换的概念，并设计了置换算法CMQ。仿真结果表明，与LRU、LFU和MQ等传统置换算法相比，CMQ算法命中率有了显著提高。     

GCaching--一种网格协同缓存系统

协同缓存通过多个代理缓存服务器的协同工作,可以充分利用各服务器的缓存空间,提高缓存命中率．网格技术可以方便地共享和整合异构的服务器资源．结合网格和协同技术,提出了一种网格协同缓存系统Gcaching,它将地域上分布的多个代理缓存服务器组成缓存池,充分利用缓存资源,协同工作,为用户提供更好的服务能力．Gcaching系统设计并实现了一种缓存放置和替换算法GCPR,它使用周期缓存更新策略,根据用户访问模式自适应地调整缓存数据的分布．仿真实验表明,GCPR算法的缓存命中率和平均访问跳数都优于传统的LRU等算法．     

服务于风电系统的改进缓存替换算法研究

针对风电系统中缓存命中率较低等问题,在最近最少使用算法(Least Recently Used,LRU)、最不经常访问算法(Least Frequently Used,LFU)、SIZE以及Hybrid算法的基础上,提出了一种基于综合因素的替换算法FST(Frequency,Object Size,Access Time),从而解决了传统算法考虑因素单一、系统性能较低等问题。该算法结合了访问频率、对象大小、访问时间间隔及最久未访问等特性,并根据最近访问时间长短采取分段的处理方法。在风电系统的缓存服务器中,将FST算法与LRU,LFU和SIZE算法进行实验对比,实验结果显示FST算法在提高命中率、减少延迟时间方面具有更好的性能。     

基于树扩展朴素贝叶斯分类器的Web代理服务器缓存优化

Web代理服务器缓存能在一定程度上减少网络拥塞现象和用户的访问延迟,减轻服务器负载。然而Web代理缓存的缓存命中率和字节命中率较低,并不能很好地起到加速网络请求响应的效果。为此,研究监督学习方法,使用树扩展朴素贝叶斯分类器对Web日志数据进行分类,进而预测可能会再次访问到的Web对象,并结合最近最少使用(LRU)算法,提出一种新的缓存策略。实验结果表明,树扩展的贝叶斯分类器在精度和召回率指标上优于朴素贝叶斯和BP神经网络等分类器,通过树扩展的贝叶斯分类器优化后的缓存策略与普通LRU算法相比,不仅可以提高缓存的效率,而且可有效提高Web代理缓存的请求命中率和字节命中率。     

基于NB分类器重访概率预测的Web缓存替换策略

Web缓存是用来解决网络访问延迟和网络拥塞问题，缓存替换策略直接影响缓存的命中率。为此，提出一种朴素贝叶斯（NB）分类器重访概率预测的Web缓存替换策略；根据用户之前访问日志，通过分区操作提取多项特征来表示每次访问的对象，并构建特征数据集；训练NB分类器，用来确定缓存中对象被再次访问的概率，为对象分配权重；结合LRU策略来合理删除一些对象。仿真结果表明，提出的策略在保证较高命中率的同时有效降低了执行时间。     

一种基于重用距离预测与流检测的高速缓存替换算法

传统的缓存替换算法由于不能适应应用程序的流式访问行为而导致缓存性能不佳.设计基于周期检测的预测方法,分析程序访存重用距离的规律性和流式访问的复杂性,提出用重用距离预测能同时适应简单流和复杂流访问模式的RDP算法.RDP的基本思想是预测重用距离并动态维护重用距离计数,动态调整缓存数据的替换顺序,通过流采样缩减存储开销.实验结果表明,RDP算法能够很好地适应程序中多样化的流访问模式,其总体性能优于LRU算法和DIP算法,在32MB缓存上比传统LRU算法平均减少了27.5%的缓存缺失.     

基于高斯混合模型的Web代理服务器缓存替换策略

Web代理服务器缓存能够在一定程度上解决用户访问延迟和网络拥塞问题,Web代理缓存的缓存替换策略直接影响缓存的命中率,从而影响网络请求响应的效果;为此,使用一种通过固定大小的循环滑动窗口提取Web日志数据的多项特征,并使用高斯混合模型对Web日志数据进行聚类分析,预测在窗口时间内可能再次访问到Web对象,结合最近最少使用(LRU)算法,提出一种新的基于高斯混合模型的Web代理服务器缓存替换策略;实验结果表明,与传统的缓存替换策略LRU、LFU、FIFO、GDSF相比,该策略有效提高了Web代理缓存的请求命中率和字节命中率。     

一种改进的基于缓存池机制的小文件I/O策略

Lustre文件系统对大文件的I/O性能较好,但对小文件不佳。针对这个问题,提出建立一个基于MDS节点的小文件缓存池机制,在缓存池里缓存经常被访问的小文件。在该机制中,小文件缓存池与OST使用全相联映射方式对应,并且使用贯穿读出式和直写式策略保持文件的一致性;缓存池更新策略综合考虑了文件的访问时间和次数等因素,使用改进的近期最少使用算法（LRU）更新替换。实验结果表明,改进后的Lustre文件系统减少了小文件的网络传输开销和访问时间,对小文件的I/O性能有较明显的提高。虽然它对大文件的I/O性能有所降低,但在可接受范围之内,仍具有一定的实用价值。     

普适计算中基于上下文信息的缓存管理算法

普适计算的一个常见的难题是断连操作,而移动设备在断连状态下对数据进行操作又是必要的.为了支持断连操作,需要在移动客户端上进行数据缓存.数据收集的目的是在断连前把用户将来可能访问的数据预先存储到本地缓存,因此收集过程的结果将对断连操作的性能产生重大影响.目前针对断连操作的数据收集算法,对缓存命中都有一定效果,为了进一步提高缓存命中率,本文根据上下文信息进行数据收集算法;然后在访问数据时同步建立数据之间的关联,并在数据关联的基础上自动选择要收集的数据集;最后将结果按缓存驻留时间和访问次数进行缓存替换.模拟试验结果表明,此算法对于存储容量小的手持移动设备可以有效地提高断连操作时的缓存命中率,可以更好的支持移动设备的断连操作.     

基于频繁序列挖掘的文件系统缓存算法设计

传统缓存算法存在命中率低、交换率高等问题,且现有缓存算法在分布式大数据存储系统中并不适用,为此提出了一种基于频繁序列挖掘的自适应缓存策略。该方法使用数据挖掘算法挖掘历史访问窗口内的频繁序列,将频繁序列模糊合并后构建匹配模式集合以供查询。当新的访问来临时,将固定访问长度内的子序列与匹配模式集合进行匹配,然后根据匹配结果预取数据,同时结合修改后的S4LRU(4-segmented least recently used)数据结构进行缓存数据换出。在公开的大数据处理trace集上进行了仿真实验,实验结果表明,在不同的缓存大小下,提出算法与现有典型缓存算法相比,平均命中率提高了0.327倍,平均交换率降低了0.33倍,同时具有低开销和高时效的特点。此结果表明,该方法较传统替换算法而言是一个更为有效的缓存策略。