More Web Proxy on the site http://driver.im/

research-article

SHARC: improving adaptive replacement cache with shadow recency cache management

Authors:

Cong LiAuthors Info & Claims

Middleware '21: Proceedings of the 22nd International Middleware Conference

Pages 119 - 131

https://doi.org/10.1145/3464298.3493389

Published: 02 December 2021 Publication History

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.

References

[1]

Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. Workload analysis of a large-scale key-value store. SIGMETRICS Perform. Eval. Rev., page 53--64, June 2012.

[2]

Sorav Bansal and Dharmendra S. Modha. CAR: Clock with adaptive replacement. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies, FAST '04, pages 187--200, 2004.

[3]

Aaron Blankstein, Siddhartha Sen, and Michael J. Freedman. Hyperbolic caching: Flexible caching for web applications. In 2017 USENIX Annual Technical Conference, USENIX ATC '17, pages 499--511, Santa Clara, CA, 2017. USENIX Association.

[4]

Pei Cao and Sandy Irani. Cost-aware www proxy caching algorithms. In Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, USITS '97, pages 193--206, 1997.

[5]

Jr. Edward G. Coffman and Peter J. Denning. Operating Systems Theory. Prentice Hall Professional Technical Reference, 1973.

Digital Library

[6]

Louis Degenaro, Arun Iyengar, Ilya Lipkind, and Isabelle Rouvellou. A middleware system which intelligently caches query results. In Middleware, volume 1795 of Lecture Notes in Computer Science, pages 24--44, 2000.

[7]

Gil Einziger, Ohad Eytan, Roy Friedman, and Ben Manes. Adaptive software cache management. In Proceedings of the 19th International Middleware Conference, Middleware '18, pages 94--106, Rennes, France, December 2018.

Digital Library

[8]

Gil Einziger, Roy Friedman, and Ben Manes. TinyLFU: A highly efficient cache admission policy. ACM Trans. Storage, 13(4):35:1--35:31, November 2017.

Digital Library

[9]

Ohad Eytan, Danny Harnik, Effi Ofer, Roy Friedman, and Ronen Kat. It's time to revisit LRU vs. FIFO. In 12th USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage '20. USENIX Association, July 2020.

[10]

Ziqi Fan, David H. C. Du, and Doug Voigt. H-ARC: A non-volatile memory based cache policy for solid state drives. In 2014 30th Symposium on Mass Storage Systems and Technologies, MSST '14, pages 1--11, 2014.

[11]

Binny S. Gill and Dharmendra S. Modha. SARC: Sequential prefetching in adaptive replacement cache. In Proceedings of the Annual Conference on USENIX Annual Technical Conference, ATEC '05, page 33, USA, 2005. USENIX Association.

[12]

Song Jiang, Feng Chen, and Xiaodong Zhang. CLOCK-Pro: An effective improvement of the CLOCK replacement. In Proceedings of the 2005 USENIX Annual Technical Conference, ATEC '05, pages 323--336, 2005.

[13]

Song Jiang, Kei Davis, and Xiaodong Zhang. Coordinated multilevel buffer cache management with consistent access locality quantification. IEEE Transactions on Computers, 56(1):95--108, 2007.

Digital Library

[14]

Song Jiang and Xiaodong Zhang. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. In Proceedings of the 2002 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '02, pages 31--42, 2002.

Digital Library

[15]

Theodore Johnson and Dennis Shasha. 2Q: A low overhead high performance buffer management replacement algorithm. In Proceedings of the 20th International Conference on Very Large Data Bases, VLDB '94, pages 439--450, 1994.

Digital Library

[16]

Chunghan Lee, Tatsuo Kumano, Tatsuma Matsuki, Hiroshi Endo, Naoto Fukumoto, and Mariko Sugawara. Understanding storage traffic characteristics on enterprise virtual desktop infrastructure. In Proceedings of the 10th ACM International Systems and Storage Conference, SYSTOR '17, New York, NY, USA, 2017. Association for Computing Machinery.

Digital Library

[17]

Cong Li. DLIRS: Improving low inter-reference recency set cache replacement policy with dynamics. In Proceedings of the 11th ACM International Systems and Storage Conference, SYSTOR '18, pages 59--64, New York, NY, USA, 2018. ACM.

[18]

Cong Li. CLOCK-Pro+: Improving CLOCK-Pro cache replacement with utility-driven adaptation. In Proceedings of the 12th ACM International Conference on Systems and Storage, SYSTOR '19, pages 1--7, New York, NY, USA, 2019. ACM.

[19]

Kun Ma and Bo Yang. Access-aware in-memory data cache middleware for relational databases. In 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems, pages 1506--1511, 2015.

[20]

Nimrod Megiddo and Dharmendra S. Modha. ARC: A self-tuning, low overhead replacement cache. In Proceedings of the FAST '03 Conference on File and Storage Technologies, FAST '03, 2003.

[21]

Dushyanth Narayanan, Austin Donnelly, and Antony Rowstron. Write off-loading: Practical power management for enterprise storage. ACM Trans. Storage, 4(3), November 2008.

Digital Library

[22]

Michael N. Nelson, Brent B. Welch, and John K. Ousterhout. Caching in the Sprite network file system. ACM Trans. Comput. Syst., 6(1):134--154, February 1988.

Digital Library

[23]

Elizabeth J. O'Neil, Patrick E. O'Neil, and Gerhard Weikum. The LRU-K page replacement algorithm for database disk buffering. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, SIGMOD '93, pages 297--306, 1993.

Digital Library

[24]

Sejin Park and Chanik Park. FRD: A filtering based buffer cache algorithm that considers both frequency and reuse distance. In Proceedings of the 33rd International Conference on Massive Storage Systems and Technology, MSST '17, 2017.

[25]

Liana V. Rodriguez, Farzana Yusuf, Steven Lyons, Eysler Paz, Raju Rangaswami, Jason Liu, Ming Zhao, and Giri Narasimhan. Learning cache replacement with CACHEUS. In 19th USENIX Conference on File and Storage Technologies, FAST '21, pages 341--354. USENIX Association, February 2021.

[26]

Alan J. Smith. Disk cache - miss ratio analysis and design considerations. ACM Trans. Comput. Syst., 3(3):161--203, August 1985.

Digital Library

[27]

James Z. Teng and Robert A. Gumaer. Managing IBM Database 2 buffers to maximize performance. IBM Systems Journal, 23(2):211--218, 1984.

Digital Library

[28]

Giuseppe Vietri, Liana V. Rodriguez, Wendy A. Martinez, Steven Lyons, Jason Liu, Raju Rangaswami, Ming Zhao, and Giri Narasimhan. Driving cache replacement with ML-based LeCaR. In 10th USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage '18, Boston, MA, 2018. USENIX Association.

Digital Library

[29]

Carl Waldspurger, Trausti Saemundsson, Irfan Ahmad, and Nohhyun Park. Cache modeling and optimization using miniature simulations. In 2017 USENIX Annual Technical Conference, USENIX ATC '17, pages 487--498, Santa Clara, CA, 2017. USENIX Association.

[30]

Theodore M. Wong and John Wilkes. My cache or yours? Making storage more exclusive. In Proceedings of the General Track of the Annual Conference on USENIX Annual Technical Conference, ATEC '02, pages 161--175, 2002.

[31]

Juncheng Yang, Yao Yue, and K. V. Rashmi. A large scale analysis of hundreds of in-memory cache clusters at Twitter. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI '20, pages 191--208. USENIX Association, November 2020.

[32]

Chen Zhong, Xingsheng Zhao, and Song Jiang. LIRS2: An improved LIRS replacement algorithm. In Proceedings of the 14th ACM International Conference on Systems and Storage, New York, NY, USA, 2021. Association for Computing Machinery.

Digital Library

[33]

Yuanyuan Zhou, James Philbin, and Kai Li. The Multi-Queue replacement algorithm for second level buffer caches. In Proceedings of the General Track: 2001 USENIX Annual Technical Conference, page 91--104, USA, 2001. USENIX Association.

Digital Library

Cited By

Ait-Oucheggou LRubini SBattou ABoukhobza J(2025)QM-ARC: QoS-aware Multi-tier Adaptive Cache Replacement StrategyFuture Generation Computer Systems10.1016/j.future.2024.107548163(107548)Online publication date: Feb-2025
https://doi.org/10.1016/j.future.2024.107548
Sun HTong HYue YQin X(2024)LAC: A Workload Intensity-Aware Caching Scheme for High-Performance SSDsIEEE Transactions on Computers10.1109/TC.2024.338529073:7(1738-1752)Online publication date: Jul-2024
https://doi.org/10.1109/TC.2024.3385290
Li YHu HLei CZhou XQian W(2024)Hill-Cache: Adaptive Integration of Recency and Frequency in Caching with Hill-Climbing2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00302(3947-3960)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00302
Show More Cited By

Index Terms

SHARC: improving adaptive replacement cache with shadow recency cache management
1. Information systems
  1. Information storage systems
    1. Storage management
2. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
      1. Caching and paging algorithms

Recommendations

Counter-Based Cache Replacement and Bypassing Algorithms

Recent studies have shown that in highly associative caches, the performance gap between the Least Recently Used (LRU) and the theoretical optimal replacement algorithms is large, motivating the design of alternative replacement algorithms to improve ...
CRUISE: cache replacement and utility-aware scheduling
ASPLOS XVII: Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems

When several applications are co-scheduled to run on a system with multiple shared LLCs, there is opportunity to improve system performance. This opportunity can be exploited by the hardware, software, or a combination of both hardware and software. The ...
CRUISE: cache replacement and utility-aware scheduling
ASPLOS '12

When several applications are co-scheduled to run on a system with multiple shared LLCs, there is opportunity to improve system performance. This opportunity can be exploited by the hardware, software, or a combination of both hardware and software. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Middleware '21: Proceedings of the 22nd International Middleware Conference

December 2021

398 pages

ISBN:9781450385343

DOI:10.1145/3464298

General Chairs:
Kaiwen Zhang
ÉTS, Canada
,
Abdelouahed Gherbi
ÉTS, Canada
,
Program Chairs:
Nalini Venkatasubramanian
UC Irvine
,
Luís Veiga
IST (U.Lisboa) & INESC-ID, Portugal

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

In-Cooperation

USENIX Assoc: USENIX Assoc
IFIP

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 December 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Middleware '21

Sponsor:

ACM

Middleware '21: 22nd International Middleware Conference

December 6 - 10, 2021

Québec city, Canada

Acceptance Rates

Overall Acceptance Rate 203 of 948 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ait-Oucheggou LRubini SBattou ABoukhobza J(2025)QM-ARC: QoS-aware Multi-tier Adaptive Cache Replacement StrategyFuture Generation Computer Systems10.1016/j.future.2024.107548163(107548)Online publication date: Feb-2025
https://doi.org/10.1016/j.future.2024.107548
Sun HTong HYue YQin X(2024)LAC: A Workload Intensity-Aware Caching Scheme for High-Performance SSDsIEEE Transactions on Computers10.1109/TC.2024.338529073:7(1738-1752)Online publication date: Jul-2024
https://doi.org/10.1109/TC.2024.3385290
Li YHu HLei CZhou XQian W(2024)Hill-Cache: Adaptive Integration of Recency and Frequency in Caching with Hill-Climbing2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00302(3947-3960)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00302
Einziger GHimelbrand OWaisbard E(2023)Boosting Cache Performance by Access Time MeasurementsACM Transactions on Storage10.1145/357277819:1(1-29)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3572778
Ait-Oucheggou LRubini SBattou ABoukhobza J(2023)Investigating Multi-Tier and QoS-Aware Caching Based on ARC2023 31st International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS59514.2023.10387601(1-4)Online publication date: 16-Oct-2023
https://doi.org/10.1109/MASCOTS59514.2023.10387601

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents