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

Dual queues cache replacement algorithm based on sequentiality detection

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

Caching is one of the most effective 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 buffer cache can serve more subsequent random read requests,so the cache miss penalty decreases 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.