Dual queues cache replacement algorithm based on sequentiality detection

• DOI: 10.1007/s11432-011-4213-z
• Publication Date: 2011-05-21T08:34:26Z
• Authors: Nong Xiao; YingJie Zhao; Fang Liu; ZhiGuang Chen
• Keywords: Cache pollution; Cache invalidation; Page cache

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 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.