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

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

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

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

基于预测的Web缓存替换算法

为了提高Web缓存的性能,在缓存替换算法GDSF的基础上引入了预测机制,提出了基于预测的缓存替换算法PGDSF.先利用Web日志构造预测模型,再用预测模型对当前的用户访问序列进行预测,形成用户可能要访问的预测对象集.当缓存空间不能满足新请求对像时,则利用替换策略GDSF,将权值最小的且不属于预测对象集的对像进行替换.该算法综合考虑了各项因素对Web对象的影响,仿真实验结果表明,在一定的缓存空间内相对于GDSF替换算法有较高的文档命中率和字节命中率.     

一种面向工业边缘计算应用的缓存替换算法

工业应用对数据传输的确定性有严格要求,有必要通过合理的缓存策略保障工业边缘网络的实时服务性能保障.首先面向工业边缘计算应用场景阐述了边缘缓存问题模型.然后分析了工业应用中用户请求的动态性特点,结合工业用户请求的特征属性,给出用户请求内容流行度变化的预测方法.在此基础上提出了基于属性特征流行度预测的缓存替换(combing periodic popularity prediction and size caching strategy,PPPS)算法,根据最近周期窗口内主导属性特征的热度预测值,和尺寸参数一起确定缓存内容价值.实验结果表明:与MPC(most-popular content)、贪婪双尺寸(greedy dual size,GDS)、最近最久未使用(least recently used,LRU)、最近最少访问频次(least frequently used,LFU)、先进先出(first in first out,FIFO)这5种经典算法相比,提出的PPPS算法在缓存命中率和平均延迟2种性能指标下,在不同的用户请求模型、内容大小分布、内容种类参数下均取得最优性能,有效提升了边缘缓存的命中率,提高了缓存利用效率,降低了用户请求内容的延迟.     

基于协同过滤的Web缓存替换算法研究

针对GDSF替换算法中对访问频率缺少预测的不足,提出了一种基于协同过滤的GDSF缓存替换算法(GDSF-CF)。该算法考虑了Web对象之间相似性与用户访问时间间隔,运用协同过滤算法生成Web对象的预测访问频率,并采用齐普夫定律参数对GDSF算法的目标函数进行了改进。当需要进行缓存替换时,利用目标函数价值计算缓存空间中的每个Web对象缓存价值,将最小缓存价值的Web对象进行替换。仿真实验结果表明,该算法的命中率HR和字节命中率BHR都有较大提升。     

基于比例命中率的Web缓存区分服务

基于反馈控制理论,通过系统辨识设计了缓存控制器。动态调整不同类别缓存对象的缓存空间,可保证高优先级Web对象的高命中率,而不同类别的Web对象命中率之比保持不变。在服务器端实现了基于比例命中率的缓存区分服务。经实验验证,在GDSF,LRU,LFU缓存替换算法下,无论是请求命中率还是字节命中率,均有良好的区分效果。     

Web缓存层次模型与代价分析

Web缓存分层结构在避免单点失效、提高缓存性能方面具有重要作用.论文研究了Web缓存层次模型,提出请求分发的三种模式,并利用代价函数分析探讨了缓存模型性能.根据Web访问共同特征,实验采用数学建模方法生成模拟日志,模拟不同层采用不同替换算法(LRU、LFU、GDS)时的缓存性能.结果表明,模拟日志的高频区、低频区流行度访问特征分别服从齐普夫第一定律、第二定律,具有真实日志的特性,能够模拟用户请求评价Web缓存层次模型性能;当低层代理缓存采用LFU或LRU替换算法,高层代理缓存采用GDS替换算法时,两层缓存模型在命中率、字节命中率方面有较好的性能表现.     

混合架构下多请求模式的缓存替换模型研究

针对多类型多访问模式应用的需求,在GDSF算法的基础上,引入平均访问间隔和最近访问间隔两个特性以增强算法的适应性;建立缓存结构模型,通过双关键字索引机制,快速索引缓存对象,降低系统开销;对超过一定大小的文件采取后缀预取策略以增加缓存中数据对象的个数.在课题应用背景下,与传统算法的对比实验表明,该方法能够减少缓存的平均请求等待时间,提高对象命中率和字节命中率,增强了缓存替换算法对多类型多请求模式应用的适应性.     

一种新的基于预测的网页预取模型和缓存算法

为了提高Web缓存算法的命中率,在传统的GDSF算法基础上,提出一种新的使用预测机制的缓存替换算法。该算法使用改进后的WAP算法对Web日志挖掘生成频繁访问序列,建立预测模型,产生预测队列,当需要替换缓存中的对象时使用预测队列提供替换依据。仿真实验表明,新的算法可以在一定程度上提高缓存的文档命中率和字节命中率,尤其在缓存空间相对较小时,效果更为明显。     

Spark中一种高效RDD自主缓存替换策略研究

由于并行计算框架Spark缓存替换算法的粗糙性,LRU（least recently used）算法并未考虑RDD的重复使用导致易把高重用数据块替换出内存且作业执行效率较低等问题。通过优化权重模型和改进替换策略,提出了一种高效RDD自主缓存替换策略（efficient RDD automatic cache,ERAC）,包括高重用自主缓存算法和缓存替换分级算法,可实现高效RDD的自主缓存和缓存目标的分级替换。最后利用SNAP（Stanford network analysis project）提供的标准数据集将ERAC和LRU、RA（register allocation）等算法进行了对比实验,结果显示ERAC算法能够有效提高Spark的内存利用率和任务执行效率。     

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

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

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

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

FUZZY REPLACEMENT ALGORITHM FOR CACHE MEMORY

This paper reports a replacement procedure for cache memories. The procedure is essentially a fuzzy algorithm that makes use of 18 rules to select the cache block to be replaced. These rules are primarily a function of three parameters: age and the frequency of usage of a cache block, and the global hit ratio of the cache system. Computationally, the proposed algorithm calculates a replacement index for each cache block and the block with highest replacement index is selected as a victim. The performance of this fuzzy procedure is compared with traditional replacement algorithms such as least recently used (LRU) and first in First out (FIFO). Our simulation experiments indicate that the proposed algorithm is a strong contender to the traditional counterparts. The unique feature of the proposed algorithm is its flexibility; that is, one can always improve its performance further by fine-tuning the rules.     

Second-level buffer cache management

Buffer caches are commonly used in servers to reduce the number of slow disk accesses or network messages. These buffer caches form a multilevel buffer cache hierarchy. In such a hierarchy, second-level buffer caches have different access patterns from first-level buffer caches because accesses to a second-level are actually misses from a first-level. Therefore, commonly used cache management algorithms such as the least recently used (LRU) replacement algorithm that work well for single-level buffer caches may not work well for second-level. We investigate multiple approaches to effectively manage second-level buffer caches. In particular, we report our research results in 1) second-level buffer cache access pattern characterization, 2) a new local algorithm called multi-queue (MQ) that performs better than nine tested alternative algorithms for second-level buffer caches, 3) a set of global algorithms that manage a multilevel buffer cache hierarchy globally and significantly improve second-level buffer cache hit ratios over corresponding local algorithms, and 4) implementation and evaluation of these algorithms in a real storage system connected with commercial database servers (Microsoft SQL server and Oracle) running industrial-strength online transaction processing benchmarks.     

基于镜像层关联的Docker注册表缓存预取策略

随着容器技术的广泛普及,大型Docker公共注册表使用对象存储服务来解决镜像数量剧增的问题,但这种松耦合的注册表设计导致较高的延迟开销。为了增强注册表性能,提出一种基于镜像层关联的Docker注册表缓存预取策略LCPA,当注册表服务器缓存未命中时,通过分析镜像元数据文件构建镜像的存储结构,由关联度模型对存储结构计算得到相关镜像层集合,并从后端存储中主动式预取回注册表中以提高缓存命中率。经真实工作负载下收集的Docker数据集测试,实验结果表明LCPA策略比LRU、LIRS和GDFS等缓存算法提高12%~29%的平均缓存命中率,拉取镜像的平均延迟节省率提高了21.1%~49.4%。与现有的LPA预取算法相比,拉取镜像的平均缓存命中率提升25.6%。仿真实验表明该策略可以有效地利用缓存空间,大幅提升注册表的缓存命中率,并降低镜像拉取的延迟开销。     

Neuro-fuzzy system in partitioned client-side Web cache

This paper proposes a novel contribution in Web caching area, especially in Web cache replacement, so-called intelligent client-side Web caching scheme (ICWCS). This approach is developed by splitting the client-side cache into two caches: short-term cache that receives the Web objects from the Internet directly, and long-term cache that receives the Web objects from the short-term cache. The objects in short-term cache are removed by least recently used (LRU) algorithm as short-term cache is full. More significantly, when the long-term cache saturates, the neuro-fuzzy system is employed efficiently in managing contents of the long-term cache. The proposed solution is validated by implementing trace-driven simulation and the results are compared with least recently used (LRU) and least frequently used (LFU) algorithms; the most common policies of evaluating Web caching performance. The simulation results have revealed that the proposed approach improves the performance of Web caching in terms of hit ratio (HR), up to 14.8% and 17.9% over LRU and LFU. In terms of byte hit ratio (BHR), the Web caching performance is improved up to 2.57% and 26.25%, and for latency saving ratio (LSR), the performance is better with 8.3% and 18.9% over LRU and LFU, respectively.     

位置感知查询中的协作缓存管理

位置感知查询（LAQ）是移动系统中常用的一种查询方式。提出了一种位置感知查询中的协作缓存管理技术（CoMA-LA）,该方法包括三方面的内容：（1）缓存中语义相近数据项的合并;（2）相邻缓存间的协作替换策略;（3）缓存间的数据一致性保证。通过仿真实验将CoMA-LA和传统的LRU算法以及一些已有的缓存替换方法进行了比较,实验结果表明采用CoMA-LA技术能够有效提高缓存利用率,从而降低平均访问时间,提高查询命中率。     

Dual queues cache replacement algorithm based on sequentiality detection

Caching is one of the most eective and commonly used mechanisms to improve performance of storage servers.Replacement policies play a critical role in the cache design due to the limited cache capacity.Recent researchers devote themselves to achieve high hit ratios,but rarely pay attention to reducing miss penalty during the design of a replacement policy.To address the issue,this paper presents a novel algorithm,called dual queues cache replacement algorithm based on sequentiality detection,which prefers to drop sequential blocks and protect random blocks.The buer cache can serve more subsequent random read requests,so the cache miss penalty could be decreased significantly.Moreover,the algorithm makes use of two queues separately maintaining new blocks and old blocks to avoid the degradation of hit ratios.Our trace-driven simulation results show that it performs better than LRU and ARC for a wide range of cache sizes and workloads.