SHARC
Authors:
Open Access
- 2 December 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 119-131
Abstract
Adaptive Replacement Cache (ARC) is a state-of-the-art cache replacement policy with a constant-time complexity per request. It uses a recency list and a frequency list to balance between access recency and access frequency. In this paper, we re-examine the ARC policy and demonstrate its weaknesses: 1) some entries in the recency list are not recent; and 2) the constraint of the recency list length limits the capability in identifying weak locality. We then propose a new policy, Shadow ARC (SHARC), to overcome those weaknesses with shadow recency cache management. In SHARC, we track the virtual time of the accesses. We allow the shadow recency cache to grow on demand, but proactively identify unpromising entries for eviction based on a comprehensive eviction criterion. While the criterion is calculated from the virtual time, we provide the theoretical justification that in scenarios of strong locality, it tightly bounds the recency distance of the entries. In scenarios of relatively weak locality, the criterion dynamically determines the size of the shadow recency cache based on the activeness of the frequency cache items and the promotion activities of the recency items. Experimental results indicate that SHARC outperforms the state-of-the-art policies of ARC, Low Inter-Reference Recency Set (LIRS), and Dynamic LIRS.Keywords
This publication has 12 references indexed in Scilit:
- TinyLFUACM Transactions on Storage, 2017
- Understanding storage traffic characteristics on enterprise virtual desktop infrastructure2017
- H-ARC: A non-volatile memory based cache policy for solid state drives2014
- Write off-loadingACM Transactions on Storage, 2008
- LIRS2002
- A Middleware System Which Intelligently Caches Query ResultsLecture Notes in Computer Science, 2000
- The LRU-K page replacement algorithm for database disk buffering1993
- Caching in the Sprite network file systemACM Transactions on Computer Systems, 1988
- Disk cache—miss ratio analysis and design considerationsACM Transactions on Computer Systems, 1985
- Managing IBM Database 2 buffers to maximize performanceIBM Systems Journal, 1984