RACE: A Robust Adaptive Caching Strategy for Buffer Cache
Authors:
- 27 November 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 57 (1) , 25-40
Abstract
Although many block replacement algorithms for buffer caches have been proposed to address the well-known drawbacks of the LRU algorithm, they are not robust and cannot maintain a consistent performance improvement over all workloads. This paper proposes a novel and simple replacement scheme, called the Robust Adaptive buffer Cache management schemE (RACE), which differentiates the locality of I/O streams by actively detecting access patterns that are inherently exhibited in two correlated spaces, that is, the discrete block space of program contexts from which I/O requests are issued and the continuous block space within files to which I/O requests are addressed. This scheme combines the global I/O regularities of an application and the local I/O regularities of individual files that are accessed in that application to accurately estimate the locality strength, which is crucial in deciding which blocks are to be replaced upon a cache miss. Through comprehensive simulations on 10 real-application traces, RACE is shown to have higher hit ratios than LRU and all other state-of-the-art cache management schemes studied in this paper.Keywords
This publication has 25 references indexed in Scilit:
- Making LRU Friendly to Weak Locality Workloads: A Novel Replacement Algorithm to Improve Buffer Cache PerformanceIEEE Transactions on Computers, 2005
- Learning to classify parallel input/output access patternsIEEE Transactions on Parallel and Distributed Systems, 2002
- Design, implementation, and performance evaluation of a detection-based adaptive block replacement schemeIEEE Transactions on Computers, 2002
- LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policiesIEEE Transactions on Computers, 2001
- Compiler-based I/O prefetching for out-of-core applicationsACM Transactions on Computer Systems, 2001
- Implementation and performance of integrated application-controlled file caching, prefetching, and disk schedulingACM Transactions on Computer Systems, 1996
- Improving disk cache hit-ratios through cache partitioningIEEE Transactions on Computers, 1992
- Basic Local Alignment Search ToolJournal of Molecular Biology, 1990
- Cache operations by MRU changeIEEE Transactions on Computers, 1988
- Analysis of the Optimal, Look-Ahead Demand Paging AlgorithmsSIAM Journal on Computing, 1976