一种基于社交关系的移动缓存替换算法

近年来移动互联网尤其是Android平台和iOS平台的兴起,移动应用的数量出现了爆炸式增长。这些移动应用中,用户可以发布数据或浏览其他用户发布的数据,由此产生了大量用户生成的数据。当手机使用者想要浏览这些由其他用户生成的数据时,每次都向服务器请求数据的做法是不可取的,比较合适的方法是使用缓存技术将部分数据缓存在移动端,以此来降低数据的请求频率,减小无线网络带宽压力,提升用户体验。传统的缓存技术更多关注的是缓存的访问频率、最近访问时间等因素,但是很少关注数据生成用户之间的社交关系。在存在用户关系的移动网络中,用户相关数据的请求与用户之间的社交关系紧密联系。结合用户之间的社交关系、最近最久访问时间以及缓存中每块数据的大小,提出了一种基于社交关系的移动缓存替换算法。该算法综合计算数据的最近最久访问时间、数据产生用户与使用者之间的亲密值以及缓存占用存储空间的大小,在需要时进行缓存替换。实验证明在移动社交网络中,基于社交关系的缓存替换策略可以提高缓存命中率,使用户获得更好的体验。     

HTML5混合式移动社交应用中缓存管理机制的研究

随着移动互联网的发展,混合式开发作为一种快速开发的方式已经成为一种趋势,这种方式既可以体现Web应用可以同时适用于IOS平台和Android平台的特点,又能解决Web应用中不能调用操作系统底层资源的问题。当今社交类应用中普遍存在大量的图片,重复图片从服务器多次存取会消耗客户端流量、增加访问延迟,当今混合式开发框架中的缓存机制并不能解决这个问题。因此提出一个可以适用于混合式移动社交应用的图片缓存管理机制,提供缓存图片管理的原生模块供开发者在混合模式下使用,并将其应用于社交应用中。同时提出了一种基于社交关系的图片缓存替换算法,该算法结合了社交应用中用户之间的社交关系亲密值、LRU算法、图片占用空间大小。实际应用表明,该算法可以提高混合式移动社交应用中的缓存命中率。     

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

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

WWW中缓存模型的优化设计

ＷＷＷ提供了方便的手段来访问远程信息资源，对于Ｗｅｂ用户而言，衡量Ｗｅｂ服务质量的一个重要指标就是检索信息所花费的时间。缩短检索时间的途径很多，此文主要介绍通过设置缓存机制，降低用户对资源访问请求次数，达到缩短用户直观感觉上的检索时间的方法。并讨论一种基于Ｃ／Ｓ结构的缓存模型，提出了新的缓存替换算法，综合考虑了文档长度，网络负载等参数，实现了缓存模型的优化。经过实验验证，该算法优于目前的缓存替换算法。     

一种移动透明计算系统中的双缓存协作策略

为降低带宽对移动透明计算系统TCOS性能的影响,提出一种将本地缓存与P2P缓存相结合的缓存协作策略TC-CCS。将本地缓存用于缓存用户常用个人数据,并把P2P缓存分别用于缓存操作系统和应用软件启动数据。针对TCOS系统中数据的访问特点,设计实现TC-replace替换算法,兼顾本地和其他终端的访问情况对缓存进行替换。实验结果表明,TC-CCS策略能加快操作系统和应用软件启动速度,其中系统启动时间缩短了约40%。     

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

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

面向移动Web应用的浏览器缓存性能度量与优化

随着移动互联网的飞速发展,用户越来越多地通过移动设备访问Web应用.浏览器为Web应用提供基本的计算、渲染等运行时支撑,其缓存机制可以支持Web应用直接从本地而不是通过网络来获取可复用资源,不仅能够减少整体的执行时间从而提升应用加载速度,还能够减少网络流量使用和电池电量消耗,从而保证移动Web用户体验.近年来,围绕面向移动Web应用的浏览器缓存优化得到了国内外学术界和工业界的广泛关注.然而,现有研究工作大多都是从网络层面关注浏览器缓存的整体性能,未充分考虑移动互联网用户访问行为的差异性和动态性,以及Web应用自身持续演化对浏览器实际缓存性能的影响.针对这一问题,首先设计了一种新型主动式缓存度量实验,通过仿真用户的访问行为来分析移动Web应用实际资源使用情况,揭示了浏览器缓存的理论性能上限和实际性能之间的巨大差距,并发现了造成这一差距的3个主要原因：重复请求别名资源、启发式过期时间和保守的过期时间配置.基于此发现,从应用层和平台层分别提出了两种浏览器缓存性能优化方案,并实现了原型系统.实验结果表明,采用两种方法分别平均可减少8%~51%和4%~58%的网络流量,且系统开销较小.     

一种基于访问图优化的缓存替换算法

针对目前数据库缓存替换算法替换策略单一,无法预测即将执行SQL语句的不足,提出了一种基于访问图优先的缓存替换算法CG-ABR(Call Graph Optimizing Adaptive Buffer Replacement).该算法通过查询优化器获得当前数据访问类型,自动调整缓存替换算法以适应实时变化的访问类型,改进了缓存访问的管理方法,并根据SQL语句的应用逻辑执行顺序来构造访问图Call Graph,基于Call Graph以预测将要执行的SQL语句,替换出未来不会被访问的页面缓存,以达到缓存空间优化的目的.实验结果与分析表明,CG-ABR算法是有效的,对实时变化的访问类型有较好的缓存命中率,具有良好的应用价值.     

移动数据库缓存模型研究

针对移动数据库系统性能有待提高的问题,提出了一种移动数据库缓存模型。采用基于消息摘要的同步算法,通过比较移动客户端与服务器消息摘要表中的消息摘要值,完成缓存同步,维护移动客户端缓存与服务器数据的一致性;该模型还考虑了数据的时效性与事务的优先级,设计了一种基于价值函数的缓存替换算法。实验结果表明,随着缓存数据个数的增加,所提算法的缓存命中率高于最近最少使用(LRU)和LA2U算法,同时随着访问频率的增加,事务的重启率低于LRU和LA2U,有效提高了移动数据库缓存的性能。     

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

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

MySQL缓冲区自适应管理仿真研究

由于MySQL使用配置参数的方式调节线性预读的阈值以及冷热LRU算法的冷热比例,导致缓冲区存在性能瓶颈。针对以上问题,提出一种缓冲区自适应管理的方法,该方法通过遗憾最小化的强化在线学习技术设计了自适应阈值调整算法以及自适应冷热缓存替换算法。首先,对MySQL中的预读算法以及冷热缓存替换算法进行深入研究,明确了预读阈值以及冷热比例大小对两种算法的具体影响;其次,通过FIFO历史队列以及增加辅助字段的方式,设计了一套参数评估流程,实时评估当前参数是偏大或偏小;最后,设计了一种参数调整模型,该模型利用MySQL原生的预读算法以及缓存替换算法的性能监控指标,实现对参数的合理调整。在FIU数据集上进行了900组仿真实验,实验表明,相较于MySQL原生的基准预读算法以及冷热缓存算法,自适应后的两种算法能够在基本不牺牲算法运行速度的基础上,有效减少8%的磁盘I/O以及增加24%的缓存命中率;相对于最新的缓存替换算法,自适应后的冷热缓存替换算法在保证缓存命中率的前提下,将速度提升至1.6倍。     

一种闪存敏感的多级缓存管理方法

基于闪存的固态硬盘(solid state driver,简称SSD)已经广泛应用于各种移动设备、PC机和服务器.与磁盘相比,尽管SSD具有数据存取速度高、抗震、低功耗等优良特性,但SSD自身也存在读写不对称、价格昂贵等不利因素,这使得SSD 短期内不会完全取代磁盘.将SSD和磁盘组合构建混合系统,可以发挥不同的硬件特性,提升系统性能.基于 MLC 型 SSD 和 SLC 型 SSD 之间的特性差异,提出了一种闪存敏感的多级缓存管理策略——FAMC.FAMC将SSD用在内存和磁盘之间作扩展缓存,针对数据库系统、文件管理中数据访问的特点,有选择地将内存牺牲页缓存到不同类型的SSD.FAMC同时考虑写请求模式和负载类型对系统性能的影响,设计实现对SSD友好的数据管理策略.此外,FAMC基于不同的数据置换代价提出了适用于SSD的缓冲区管理算法.基于多级缓存存储系统对FAMC的性能进行了评测,实验结果表明,FAMC可以大幅度降低系统响应时间,减少磁盘I/O.     

用于二级缓存的一种改进的自适应缓存管理算法

在机群系统或数据库服务器等应用环境下,由于本地内存资源限制,某些大内存应用与磁盘交互过多,会严重损害其性能.在高速网络支持下,把其他节点内存或采用专门的内存服务器作为系统的二级缓存,可减少对磁盘访问并提高应用性能.在二级缓存应用模式下,基于LIRS算法并对其存在的缺点进行改进,提出了一种自适应缓存管理算法LIRS-A.LIRS-A可根据应用访问特征自适应调整,避免了LIRS不适应某些具有时间局部性模式的情况.在TPC-H应用中,LIRS-A比LIRS最多有7.2%的性能提升;在网络流分析数据库的典型Groupby查询中,LIRS-A比LIRS的命中率最多可提高31.2%.     

网络存储系统中低开销高性能的第二级缓存替换算法的研究

针对网络存储访问特性所带来的第二级缓存性能降低的问题,提出了一种高性能的第二级缓存替换算法。本算法采用顺序页面检测机制,能根据缓存页面顺序程度的不同做出替换选择,以减少缓存失效引起随机访问磁盘的次数,避免不必要的磁头寻道和旋转开销,从而改善整个存储系统的性能。实验结果表明,在多种缓存大小下,本文算法能显著降低有效响应时间,使网络存储系统达到更优的性能。     

基于序列模式的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容器的性能.     

Web video thumbnail recommendation with content-aware analysis and query-sensitive matching

In this paper, a unified and adaptive web video thumbnail recommendation framework is proposed, which recommends thumbnails both for video owners and browsers on the basis of image quality assessment, image accessibility analysis, video content representativeness analysis and query-sensitive matching. At the very start, video shot detection is performed and the highest image quality video frame is extracted as the key frame for each shot on the basis of our proposed image quality assessment method. These key frames are utilized as the thumbnail candidates for the following processes. In the image quality assessment, the normalized variance autofocusing function is employed to evaluate the image blur and ensures that the selected video thumbnail candidates are clear and have high image quality. For accessibility analysis, color moment, visual salience and texture are used with a support vector regression model to predict the candidates’ accessibility score, which ensures that the recommended thumbnail’s ROIs are big enough and it is very accessible for users. For content representativeness analysis, the mutual reinforcement algorithm is adopted in the entire video to obtain the candidates’ representativeness score, which ensures that the final thumbnail is representative enough for users to catch the main video contents at a glance. Considering browsers’ query intent, a relevant model is designed to recommend more personalized thumbnails for certain browsers. Finally, by flexibly fusing the above analysis results, the final adaptive recommendation work is accomplished. Experimental results and subjective evaluations demonstrate the effectiveness of the proposed approach. Compared with the existing web video thumbnail generation methods, the thumbnails for video owners not only reflect the contents of the video better, but also make users feel more comfortable. The thumbnails for video browsers directly reflect their preference, which greatly enhances their user experience.     

一种数据块关系指导的缓存替换方法

提出了一种数据块关系指导的缓存替换方法BDP(block correlations directed replacement policy).数据块关系所表示的空间局部性可以用来指导存储系统的缓存替换策略.BDP利用历史访问信息和实时访问信息,预测数据块未来的空间局部性特征,并设计数据块驻留时间的控制策略,减少现有替换算法对空间局部性预测失败带来的失效惩罚.同时给出了BDP的有效缓存模型.模拟结果显示,对大多数实际系统工作负载,BDP的失效率相对LRU算法下降11%～38%,优于现有的考虑空间局部性的替换算法.     

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

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

移动数据库技术的缓存管理策略研究

移动数据库的缓存技术使客户机通过缓存少量的服务器数据项,便能拥有较高的处理速度,而且,它也是解决移动数据库频繁断接性问题的关键技术。文章研究了缓存管理策略在移动数据库中的应用,重点研究了缓存管理策略三大关键问题：缓存粒度、缓存一致性以及缓存替换,提出了一种基于统计与优先级原则解决缓存一致性问题的新思路。     

Linked instruction caches for enhancing power efficiency of embedded systems

The power consumed by memory systems accounts for 45% of the total power consumed by an embedded system, and the power consumed during a memory access is 10 times higher than during a cache access. Thus, increasing the cache hit rate can effectively reduce the power consumption of the memory system and improve system performance. In this study, we increased the cache hit rate and reduced the cache-access power consumption by developing a new cache architecture known as a single linked cache (SLC) that stores frequently executed instructions. SLC has the features of low power consumption and low access delay, similar to a direct mapping cache, and a high cache hit rate similar to a two way-set associative cache by adding a new link field. In addition, we developed another design known as a multiple linked caches (MLC) to further reduce the power consumption during each cache access and avoid unnecessary cache accesses when the requested data is absent from the cache. In MLC, the linked cache is split into several small linked caches that store frequently executed instructions to reduce the power consumption during each access. To avoid unnecessary cache accesses when a requested instruction is not in the linked caches, the addresses of the frequently executed blocks are recorded in the branch target buffer (BTB). By consulting the BTB, a processor can access the memory to obtain the requested instruction directly if the instruction is not in the cache. In the simulation results, our method performed better than selective compression, traditional cache, and filter cache in terms of the cache hit rate, power consumption, and execution time.