一种对LRFU置换策略的自适应改进

数据库缓冲区页面置换算法对磁盘数据库的性能有着重要的影响,页面置换算法主要有基于访问时间的置换策略、基于访问次数的置换策略、两者结合的置换策略等。LRFU算法是一系列结合LRU和LFU置换策略的置换算法,很好地实现了两种置换策略的结合,但却没有给出一种在不同的应用场景中进行动态调整的机制。提出了一种对LRFU算法进行动态调整的方法,模拟测试发现改进的LRFU算法都不同程度地提高了缓冲区命中率。

基于CAR动态调整的改进LRFU算法——CLRFU

目前,已有LRFU(Least Recently Frequently Used)方法结合了访问时间和访问次数来优化缓存,但却无法适用于操作系统、存储系统、web应用等复杂场景。为了解决LRFU算法中无法动态调整λ以及现有自适应调整算法无法兼顾多种访问模式的问题,本文提出了一种基于CAR(Clock with Adaptive Replacement)动态调整策略的改进LRFU算法——CLRFU,并将该算法与局部性定量分析模型相结合,能够在不同访问模式下动态调整λ。实验结果表明,CLRFU算法在线性、概率和强局部访问模式下都具有较好的适应性,提高了缓存整体命中率。

一种基于LRFU缓存替换策略的HDFS客户端本地缓存设计与实现

Hadoop底层基础存储框架Hadoop分布式文件系统HDFS(Hadoop Distributed File System)是采用基于Master/Slave主从构架设计的分布式文件系统。Name Node负责管理所有文件的元数据和处理客户端对文件的访问。随着应用数据的不断增加,Data Node的不断加入,Name Node维护文件元数据、处理Hadoop应用的读取和删除等文件操作的工作量就会随之增加。Name Node的性能成为整个HDFS的瓶颈。提出一种思想,即将Name Node部分任务交与HDFS客户端完成,使每个HDFS客户端在某些功能上成为Name Node。用LRFU(Least Recently Used and Least Frequently Used)缓存替换策略提出一种在HDFS客户端建立本地缓存的解决方案,从而降低Name Node负载。通过实验证明Hadoop应用可以从缓存中读取文件块信息,而不必请求Name Node,提高了数据访问效率,降低了Name Node负载。

基于局部性定量分析模型的自适应替换算法LA-LRFU

已有的LRFU(Least Recency Frequency Used)自适应算法在实际应用中根据经验调整λ值,缺乏对访问局部性强弱的量化分析,因而其可适用的访问模式有限.该文首先建立基于K阶马尔可夫链(K→∞)的局部性定量分析模型,在访问过程中根据统计信息实时量化局部性特征.然后以此分析模型为基础设计自适应替换算法LA-LRFU(Locality-Aware LRFU),随着访问特征的变化动态调整参数λ.最后应用Trace仿真对算法进行测试.实验结果显示,针对多种访问模式,LA-LRFU均可显著提高Cache命中率;在由多种访问模式构成的具体访问过程中,LA-LRFU能比现有的各类LRFU自适应算法更合理地调整参数λ.