动态数据处理平台分布式缓存替换算法仿真

针对传统分布式缓存替换算法路由器命中缓存性能不足的问题,提出一种动态数据处理平台分布式缓存替换算法。描述动态数据处理平台分布式数据缓存信息,构建动态数据处理平台的缓存架构表,并根据缓存情况替换缓存架构表,通过不断替换的缓存架构表改进权重替换算法,在算法中添加缓存对象这一参数,并通过改进后的算法计算缓存对象的更新权重值及其权重成本,根据计算成本替换LRU链表中的尾指针元素,当元素已存在缓存中并且被命中时、或出现被请求的新元素时,则更新LRU链,构造新的LRU链表,通过重构的LRU链表构建分布式缓存替换策略,从而实现动态数据处理平台分布式缓存替换算法的构建。为了证明动态数据处理平台分布式缓存替换算法的优越性,将其与传统分布式缓存替换算法进行比较,实验结果证明,上述算法的路由器命中缓存性能优于传统算法,更适合进行动态数据处理平台的分布式缓存替换。     

缓存替换算法研究综述

缓存技术作为提高系统性能的重要手段一直是研究的热点。随着网络存储等新技术的出现，存储的层次越来越复杂，原有的简单缓存管理技术已经不合适日趋复杂的应用。频率和时间综合考虑的缓存替换方法、多级缓存的替换技术成为研究的热点。本文综述了缓存替换算法的研究现状，首先介绍传统简单的缓存替换算法及其存在的局限性，而后对单级缓存算法和多级缓存算法当前最新的研究进行了介绍。最后对研究的趋势进行了简单的展望。     

基于最小价值的流媒体缓存替换算法

为提高基于P2P流媒体系统的服务质量,提出了一种基于最小价值的流媒体缓存替换算法SDU.研究了现有的缓存替换算法,通过对现有的缓存替换算法的理解、研究和分析,得出了现有的缓存替换算法在P2P网络节点间效率不高.对P2P网络和流媒体系统的分析研究,提出了SDU算法.该算法综合考虑了副本的供求关系、数据的紧迫度和数据的字节...     

基于谱聚类的Web多级缓存替换策略

服务器缓存性能的核心是缓存替换策略, 缓存替换策略直接影响缓存的命中率, Web缓存可以解决网络拥塞和用户访问延迟问题, 提高服务器的性能. 传统缓存替换算法的命中率往往不高, 为此文中提出了一种基于谱聚类的多级缓存替换策略. 该策略利用循环滑动窗口机制提取日志文件的多项时序特征和访问属性, 通过谱聚类对过滤后的数据集进行聚类分析从而得到访问预测结果. 多级缓存替换策略综合考虑了缓存对象的局部频率、全局频率以及资源大小能更好地对低价值资源进行剔除, 同时对高价值资源进行保留. 通过与传统替换算法LRU、LFU、RC、FIFO进行实验对比, 实验结果表明本文将谱聚类和多级缓存替换策略进行结合有效地提高了缓存请求命中率和字节命中率.     

Web缓存命中率与字节命中率关系

在研究Web缓存性能时，一般考虑2个评价指标：命中率HR和字节命中率BHR。目前大多侧重于2个指标之一，或仅通过测试2个指标的数值来评价缓存替换算法优劣，没有从2个指标关系的角度来评价缓存替换算法的性能。该文讨论了Web缓存系统中命中率与字节命中率之间的关系，提出了一种Web缓存性能评价指标——命中比（FBR），讨论了该指标在Web缓存替换算法及Web预取性能评价中的应用，为度量缓存系统的性能提供了参考依据。     

Web缓存优化模型研究

缓存模型研究的核心是替换策略的优化。分析并比较传统缓存模型IRM和MRM的思想,基于相对流行度以及字节代价的概念,提出满足命中率、字节命中率和延迟时间等不同性能指标要求的Web缓存优化模型,并给出相应算法。实验及分析表明,Web缓存优化模型替换算法的性能表现较传统算法有所提高。     

面向移动端基于社交关系的图片缓存替换算法

随着移动终端深入人们的生活,移动社交APP得到了广泛使用。在移动社交APP中往往会使用大量的图片资源,如微信朋友圈、Instagram的图片分享等。在APP中浏览图片会消耗较多的网络流量,影响加载速度,因此大部分APP采用首先显示缩略图,根据用户需求再加载原图的策略。在服务器端也采用缓存技术来加快缩略图产生时间,减少磁盘I/O。但是,当前的缓存机制更多关注的是缓存的访问频率、最近访问时间等因素,并没有过多关注数据生成用户之间的社交关系,也没有考虑移动用户对缩略图和原图的不同访问模式。把缓存划分为两个部分:缩略图缓存区和原图缓存区,提出了基于社交关系的图片缓存替换算法,在传统缓存替换算法的基础上增加用户的社交关系以及缩略图和原图的关联关系,通过计算图片的缓存价值进行缓存替换。实验表明,所提出的基于社交关系的图片缓存替换算法对于缩略图和原图的缓存命中率都有明显提高。     

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

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

ACACRA:一种新的网络缓存替换算法

为了提高网络缓存的命中率,分析了背包问题与缓存替换问题之间的异同,证实了缓存替换问题是一种典型的0/1背包问题,并由此借鉴求解0/1背包的蚁群算法模型的思路,提出了一种实施在应用层的基于蚁群算法的缓存替换算法ACA-CRA.该算法综合考虑了缓存数据的大小,被命中次数和在缓存中存留的时间来判定该缓存的缓存价值,并利用蚁群算法中正反馈机制使得缓存中保持的都是缓存价值较大的缓存数据,从而提高缓存命中率.并通过仿真实验证明了该算法的可行性和有效性.     

面向网络流量的缓存替换算法比较与分析

缓存替换算法对优化网络处理应用的性能起到关键作用，但目前面向网络流量的缓存替换算法研究主要集中在算法设计和领域应用方面，较少有文献对现有的缓存替换算法在网络环境下的性能进行分析比较。对此，本文针对主要的6种缓存替换算法进行分析和比较。通过分析网络流量的新近度与频度特征，为基于最近最少使用(Least Recently Used, LRU)和最近最不常使用(Least Frequently Used, LFU)的缓存替换算法给出实际依据。对仿真环境和实际系统的实验结果表明，类LRU算法较LFU算法更适用于网络流量，而缓存空间较大时，随机替换算法较LRU算法更适用于多核环境。     

MacroTrend: A Write-Efficient Cache Algorithm for NVM-Based Read Cache

The future storage systems are expected to contain a wide variety of storage media and layers due to the rapid development of NVM(non-volatile memory)techniques.For NVM-based read caches,many kinds of NVM devices cannot stand frequent data updates due to limited write endurance or high energy consumption of writing.However,traditional cache algorithms have to update cached blocks frequently because it is difficult for them to predict long-term popularity according to such limited information about data blocks,such as only a single value or a queue that reflects frequency or recency.In this paper,we propose a new MacroTrend(macroscopic trend)prediction method to discover long-term hot blocks through blocks'macro trends illustrated by their access count histograms.And then a new cache replacement algorithm is designed based on the MacroTrend prediction to greatly reduce the write amount while improving the hit ratio.We conduct extensive experiments driven by a series of real-world traces and find that compared with LRU,MacroTrend can reduce the write amounts of NVM cache devices significantly with similar hit ratios,leading to longer NVM lifetime or less energy consumption.     

基于背包理论的流媒体缓存算法

为了使缓存总体效益最大化,基于字节命中率,利用0-1背包对代理缓存建立模型,给出流媒体缓存替换算法。实验结果表明,与传统流媒体缓存算法相比,该算法能减少占用带宽,提升缓存写入效率,具有较高的字节命中率。     

移动边缘计算中收益最大化的缓存协作策略

移动边缘计算（MEC）通过将资源部署在用户的近邻区域,可以减少移动设备的能耗,降低用户获取服务的时延;然而,大多数有关缓存方面的研究忽略了用户所请求服务的地域差异特性。通过研究区域所请求内容的特点和内容的动态性特性,提出一种收益最大化的缓存协作策略。首先,考虑用户偏好的区域性特征,将基站分为若干协作域,使每一个区域内的基站服务偏好相同的用户;然后,根据自回归移动平均（ARIMA）模型和内容的相似度预测每个区域的内容的流行度;最后,将缓存协作问题转化为收益最大化问题,根据存放内容所获得的收益,使用贪心算法解决移动边缘环境中缓存的内容的放置和替换问题。仿真实验表明,与基于MEC分组的协作缓存算法（GHCC）相比,所提算法在缓存命中率方面提高了28%,且平均传输时延低于GHCC。可见,所提算法可以有效提高缓存命中率,减少平均传输时延。     

通用缓存替换策略下的缓存强一致性研究

建立准确的缓存分析模型有助于更好地预测缓存行为,对于网络性能分析与规划具有重要作用。现有面向缓存强一致性研究的分析模型普遍基于最近最少使用（LRU）缓存替换策略,然而在实际环境中需要根据不同的应用场景和缓存节点能力采取LRU、q-LRU、先进先出等不同的缓存替换策略。为扩展缓存强一致性分析模型的适用范围,基于缓存建模的基本假设构建缓存强一致性通用分析模型,并给出被动查询、主动移除、主动更新3种缓存强一致性策略下缓存命中率和服务器负载的计算方法。利用模型计算结果绘制缓存参数变化曲线图找出使缓存性能达到最优的值,通过分析模型计算结果选出给定缓存参数时对应的最优缓存替换策略。实验结果表明,该模型在3种缓存强一致性策略下均具有较高的计算精确度,其中计算结果与仿真结果的最大误差和最小误差分别为6.92%和0.06%,适用于通过特征时间近似的缓存替换策略。     

基于序列模式的Servlet容器缓存替换

Servlet缓存能够有效地提高Servlet容器的吞吐量,缩短用户请求的响应时间.然而,Servlet缓存的性能受到缓存替换算法的影响.Servlet容器中的Servlet对应着一定的业务功能,挖掘Servlet之间的业务关联来指导缓存替换算法的设计可以提高Servlet缓存的命中率,进而提高Servlet容器的性能.然而,目前常见的LRU(least recently used),LFU(least frequently used),GDSF(greedy dual size frequency)等缓存替换算法均没有考虑上述问题.将Servlet对应的业务关联定义为Servlet容器序列模式,并提出k步可缓存转移概率图的概念加以表示,给出了序列模式发现算法KCTPG_Discovery.最后,基于Servlet容器序列模式设计了缓存替换算法KP-LRU(k-steps prediction least recently used)和KP-GDSF(k-steps prediction least frequently used).实验结果表明,KP-LRU与KP-GDSF算法比对应的LRU算法和GDSF算法具有更高的缓存命中率,有效地提高了Servlet容器的性能.     

Proxy Cache Replacement Algorithms: A History-Based Approach

Accesing and circulation of Web objects has been facilitated by the design and implementation of effective caching schemes. Web caching has been integrated in prototype and commercial Web-based information systems in order to reduce the overall bandwidth and increase system's fault tolerance. This paper presents an overview of a series of Web cache replacement algorithms based on the idea of preserving a history record for cached Web objects. The number of references to Web objects over a certain time period is a critical parameter for the cache content replacement. The proposed algorithms are simulated and experimented under a real workload of Web cache traces provided by a major (Squid) proxy cache server installation. Cache and bytes hit rates are given with respect to different cache sizes and a varying number of request workload sets and it is shown that the proposed cache replacement algorithms improve both cache and byte hit rates.     

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

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

P2P流媒体系统中基于关联规则的缓存替换策略

随着互联网的日益发展，人们对流媒体的需求不断提高，对视频服务器提出了更高的要求。P2P视频点播系统中传统的缓存替换策略无法获得很好的用户体验。针对此问题，本文对传统的缓存算法FIFO进行改进，提出基于关联规则的FIFO替换算法(FIFO-AR)。为了进一步提升缓存替换算法的性能，提出一种新的基于关联规则的缓存替换算法（CRA-AR）。根据用户的播放记录和视频段的流行度，并结合关联规则，从而得到待缓存的视频段。实验结果表明,FIFO-AR和CRA-AR相比于传统的缓存替换算法，具有较高的命中率和较少的响应时间。     

多缓存容量场景下的D2D内容缓存布设优化方案

在终端直传（D2D）缓存网络中,用户有限且各异的缓存能力是制约缓存效率的一个关键参数,然而现有文献大多考虑不同用户具有相同的缓存能力,针对这一不足有必要进行用户具有不同缓存容量下的D2D内容缓存布设方案优化。首先,鉴于用户终端的移动性和随机分布特性,利用随机几何理论将网络中不同缓存容量的用户节点建模为相互独立的齐次泊松点过程;其次,考虑本地卸载和邻近D2D链路卸载两种内容卸载方式,推导得到网络缓存命中率;最后,将最大化缓存命中率作为优化目标函数,提出了基于坐标梯度的联合缓存布设（JCP）算法,从而得到多用户多缓存容量场景下的内容缓存布设方案。仿真结果表明,与现有的缓存布设方案相比,由JCP得到的缓存布设方案可以有效提高缓存命中率。