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

research-article

Open access

FIFO can be Better than LRU: the Power of Lazy Promotion and Quick Demotion

Authors:

K. V. RashmiAuthors Info & Claims

HOTOS '23: Proceedings of the 19th Workshop on Hot Topics in Operating Systems

Pages 70 - 79

https://doi.org/10.1145/3593856.3595887

Published: 22 June 2023 Publication History

Abstract

LRU has been the basis of cache eviction algorithms for decades, with a plethora of innovations on improving LRU's miss ratio and throughput. While it is well-known that FIFO-based eviction algorithms provide significantly better throughput and scalability, they lag behind LRU on miss ratio, thus, cache efficiency.

We performed a large-scale simulation study using 5307 block and web cache workloads collected in the past two decades. We find that contrary to what common wisdom suggests, some FIFO-based algorithms, such as FIFO-Reinsertion (or CLOCK), are, in fact, more efficient (have a lower miss ratio) than LRU. Moreover, we find that qick demotion --- evicting most new objects very quickly --- is critical for cache efficiency. We show that when enhanced by qick demotion, not only can state-of-the-art algorithms be more efficient, a simple FIFO-based algorithm can outperform five complex state-of-the-art in terms of miss ratio.

References

[1]

Alibaba block-trace. https://github.com/alibaba/block-traces. Accessed: 2023-01-12.

[2]

Better handling for one-hit-wonder objects. https://phabricator.wikimedia.org/T144187. Accessed: 2021-12-06.

[3]

Hhvm concurrent lru cache. https://github.com/facebook/hhvm/blob/master/hphp/util/concurrent-lru-cache.h. Accessed: 2023-01-25.

[4]

Memcached - a distributed memory object caching system. http://memcached.org/. Accessed: 2021-12-06.

[5]

Multi-gen lru. https://docs.kernel.org/admin-guide/mm/multigen_lru.html. Accessed: 2023-01-12.

[6]

Mysql 5.7 reference manual, 14.5.1 buffer pool. https://dev.mysql.com/doc/refman/5.7/en/innodb-buffer-pool.html. Accessed: 2023-01-12.

[7]

Page frame reclamation. https://www.kernel.org/doc/gorman/html/understand/understand013.html. Accessed: 2023-01-16.

[8]

Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. Workload Analysis of a Large-Scale Key-Value Store. In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '12, pages 53--64, New York, NY, USA, 2012. Association for Computing Machinery.

Digital Library

[9]

Nirav Atre, Justine Sherry, Weina Wang, and Daniel S. Berger. Caching with Delayed Hits. In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM '20, pages 495--513, New York, NY, USA, 2020. Association for Computing Machinery.

Digital Library

[10]

Jiwoo Bang, Chungyong Kim, Sunggon Kim, Qichen Chen, Cheongjun Lee, Eun-Kyu Byun, Jaehwan Lee, and Hyeonsang Eom. Finer-LRU: A Scalable Page Management Scheme for HPC Manycore Architectures. In 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 567--576, May 2021. ISSN: 1530-2075.

[11]

Sorav Bansal and Dharmendra S. Modha. CAR: Clock with Adaptive Replacement. In 3rd USENIX Conference on File and Storage Technologies, FAST'04, 2004.

[12]

Nathan Beckmann, Haoxian Chen, and Asaf Cidon. LHD: Improving cache hit rate by maximizing hit density. In 15th USENIX symposium on networked systems design and implementation, NSDI'18, pages 389--403, 2018.

[13]

Nathan Beckmann and Daniel Sanchez. Talus: A simple way to remove cliffs in cache performance. In 2015 IEEE 21st International Symposium on High Performance Computer Architecture, HPCA'15, pages 64--75, Burlingame, CA, USA, February 2015. IEEE.

[14]

L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2):78--101, 1966.

Digital Library

[15]

Benjamin Berg, Daniel S. Berger, Sara McAllister, Isaac Grosof, Sathya Gunasekar, Jimmy Lu, Michael Uhlar, Jim Carrig, Nathan Beckmann, Mor Harchol-Balter, and Gregory R. Ganger. The CacheLib caching engine: Design and experiences at scale. In 14th USENIX symposium on operating systems design and implementation, OSDI'20, pages 753--768. USENIX Association, November 2020.

[16]

Daniel S. Berger. Towards Lightweight and Robust Machine Learning for CDN Caching. In Proceedings of the 17th ACM Workshop on Hot Topics in Networks, Hotnets'18, pages 134--140, Redmond WA USA, November 2018. ACM.

[17]

Daniel S. Berger, Benjamin Berg, Timothy Zhu, Siddhartha Sen, and Mor Harchol-Balter. RobinHood: Tail latency aware caching - dynamic reallocation from Cache-Rich to Cache-Poor. In 13th USENIX symposium on operating systems design and implementation, OSDI'18, pages 195--212, Carlsbad, CA, October 2018. USENIX Association.

[18]

Daniel S Berger, Ramesh K Sitaraman, and Mor Harchol-Balter. Adapt-Size: Orchestrating the hot object memory cache in a content delivery network. In 14th USENIX symposium on networked systems design and implementation, NSDI'17, pages 483--498, 2017.

[19]

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

[20]

L. Breslau, Pei Cao, Li Fan, G. Phillips, and S. Shenker. Web caching and Zipf-like distributions: evidence and implications. In Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pages 126--134 vol.1, New York, NY, USA, 1999. IEEE.

[21]

Pei Cao and Sandy Irani. Cost-Aware WWW Proxy Caching Algorithms. In USENIX Symposium on Internet Technologies and Systems, USITS'97, Monterey, CA, December 1997. USENIX Association.

[22]

Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, and Mike Barnett. FASTER: A Concurrent Key-Value Store with In-Place Updates. In Proceedings of the 2018 International Conference on Management of Data, pages 275--290, Houston TX USA, May 2018. ACM.

[23]

Asaf Cidon, Daniel Rushton, Stephen M. Rumble, and Ryan Stutsman. Memshare: a dynamic multi-tenant key-value cache. In 2017 USENIX annual technical conference, ATC'17, pages 321--334, Santa Clara, CA, July 2017. USENIX Association.

[24]

Fernando J Corbato. A paging experiment with the multics system. Technical report, MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC, 1968.

[25]

MichaelDDahlin, Randolph Y Wang, Thomas E Anderson, and David A Patterson. Cooperative caching: Using remote client memory to improve file system performance. In Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, OSDI'94, pages 19--es, 1994.

[26]

Peter J Denning. The working set model for program behavior. Communications of the ACM, 11(5):323--333, 1968.

Digital Library

[27]

Peter J. Denning. Working Set Analytics. ACM Computing Surveys, 53(6):1--36, November 2021.

Digital Library

[28]

David Detlefs, Christine Flood, Steve Heller, and Tony Printezis. Garbage-first garbage collection. In Proceedings of the 4th international symposium on Memory management, pages 37--48, 2004.

Digital Library

[29]

Donghee Lee, Jongmoo Choi, Jong-Hun Kim, S.H. Noh, Sang Lyul Min, Yookun Cho, and Chong Sang Kim. LRFU: a spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Transactions on Computers, 50(12):1352--1361, December 2001.

Digital Library

[30]

Dormando. Replacing the cache replacement algorithm in memcached. https://memcached.org/blog/modern-lru/. Accessed: 2023-01-12.

[31]

Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. The design and operation of CloudLab. In Proceedings of the USENIX Annual Technical Conference (ATC), pages 1--14, July 2019.

[32]

Dominik Durner, Badrish Chandramouli, and Yinan Li. Crystal: a unified cache storage system for analytical databases. Proceedings of the VLDB Endowment, 14(11):2432--2444, July 2021.

Digital Library

[33]

Gil Einziger, Ohad Eytan, Roy Friedman, and Ben Manes. Adaptive Software Cache Management. In Proceedings of the 19th International Middleware Conference, pages 94--106, Rennes France, November 2018. ACM.

[34]

Gil Einziger, Roy Friedman, and Ben Manes. TinyLFU: A Highly Efficient Cache Admission Policy. ACM Transactions on Storage, 13(4):1--31, December 2017.

Digital Library

[35]

Assaf Eisenman, Asaf Cidon, Evgenya Pergament, Or Haimovich, Ryan Stutsman, Mohammad Alizadeh, and Sachin Katti. Flashield: a hybrid key-value cache that controls flash write amplification. In 16th USENIX symposium on networked systems design and implementation, NSDI'19, pages 65--78, Boston, MA, February 2019. USENIX Association.

[36]

Assaf Eisenman, Maxim Naumov, Darryl Gardner, Misha Smelyanskiy, Sergey Pupyrev, Kim Hazelwood, Asaf Cidon, and Sachin Katti. Bandana: Using non-volatile memory for storing deep learning models. In A. Talwalkar, V. Smith, and M. Zaharia, editors, Proceedings of machine learning and systems, volume 1 of mlsys'20, pages 40--52, 2019.

[37]

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.

[38]

Bin Fan, David G Andersen, and Michael Kaminsky. MemC3: Compact and concurrent MemCache with dumber caching and smarter hashing. In 10th USENIX symposium on networked systems design and implementation, NSDI'13, pages 371--384, 2013.

[39]

Guanyu Feng, Huanqi Cao, Xiaowei Zhu, Bowen Yu, Yuanwei Wang, Zixuan Ma, Shengqi Chen, and Wenguang Chen. TriCache: A User-Transparent Block Cache Enabling High-Performance Out-of-Core Processing with In-Memory Programs. In 16th USENIX Symposium on Operating Systems Design and Implementation, OSDI'22, pages 395--411, Carlsbad, CA, July 2022. USENIX Association.

[40]

Alexander Fuerst and Prateek Sharma. FaasCache: keeping serverless computing alive with greedy-dual caching. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 386--400, Virtual USA, April 2021. ACM.

Digital Library

[41]

Xinyue Hu, Eman Ramadan, Wei Ye, Feng Tian, and Zhi-Li Zhang. Raven: belady-guided, predictive (deep) learning for in-memory and content caching. In Proceedings of the 18th International Conference on emerging Networking EXperiments and Technologies, CoNEXT '22, pages 72--90, New York, NY, USA, November 2022. Association for Computing Machinery.

Digital Library

[42]

Qi Huang, Ken Birman, Robbert van Renesse, Wyatt Lloyd, Sanjeev Kumar, and Harry C. Li. An analysis of Facebook photo caching. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP '13, pages 167--181, New York, NY, USA, November 2013. Association for Computing Machinery.

Digital Library

[43]

Song Jiang, Feng Chen, and Xiaodong Zhang. CLOCK-Pro: an effective improvement of the CLOCK replacement. In Proceedings of the annual conference on USENIX Annual Technical Conference, ATC'05, page 35, USA, April 2005. USENIX Association.

[44]

Song Jiang, Xiaoning Ding, Feng Chen, Enhua Tan, and Xiaodong Zhang. DULO: an effective buffer cache management scheme to exploit both temporal and spatial locality. In Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, volume 4 of FAST'05, pages 8--8, 2005.

Digital Library

[45]

Song Jiang and Xiaodong Zhang. LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance. In ACM SIGMETRICS Performance Evaluation Review, volume 30 of SIGMETRICS'02, pages 31--42, June 2002.

Digital Library

[46]

Xin Jin, Xiaozhou Li, Haoyu Zhang, Robert Soulé, Jeongkeun Lee, Nate Foster, Changhoon Kim, and Ion Stoica. NetCache: Balancing key-value stores with fast in-network caching. In Proceedings of the 26th symposium on operating systems principles, SOSP '17, pages 121--136, New York, NY, USA, 2017. Association for Computing Machinery.

Digital Library

[47]

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, San Francisco, CA, USA, September 1994. Morgan Kaufmann Publishers Inc.

[48]

R. Karedla, J.S. Love, and B.G. Wherry. Caching strategies to improve disk system performance. Computer, 27(3):38--46, March 1994.

Digital Library

[49]

Ricardo Koller and Raju Rangaswami. I/o deduplication: Utilizing content similarity to improve i/o performance. ACM Transactions on Storage (TOS), 6(3):1--26, 2010.

[50]

Jinhyung Koo, Jinwook Bae, Minjeong Yuk, Seonggyun Oh, Jungwoo Kim, Jung-Soo Park, Eunji Lee, Bryan S. Kim, and Sungjin Lee. All-Flash Array Key-Value Cache for Large Objects. In Proceedings of the Eighteenth European Conference on Computer Systems, EuroSys '23, pages 784--799, New York, NY, USA, May 2023. Association for Computing Machinery.

[51]

Jinhong Li, Qiuping Wang, Patrick PC Lee, and Chao Shi. An in-depth analysis of cloud block storage workloads in large-scale production. In 2020 IEEE International Symposium on Workload Characterization (IISWC), pages 37--47. IEEE, 2020.

[52]

Yu Liang, Riwei Pan, Tianyu Ren, Yufei Cui, Rachata Ausavarungnirun, Xianzhang Chen, Changlong Li, Tei-Wei Kuo, and Chun Jason Xue. CacheSifter: Sifting Cache Files for Boosted Mobile Performance and Lifetime. In 20th USENIX Conference on File and Storage Technologies, FAST'22, pages 445--459, 2022.

[53]

Zaoxing Liu, Zhihao Bai, Zhenming Liu, Xiaozhou Li, Changhoon Kim, Vladimir Braverman, Xin Jin, and Ion Stoica. DistCache: Provable load balancing for Large-Scale storage systems with distributed caching. In 17th USENIX conference on file and storage technologies, FAST'19, pages 143--157, Boston, MA, February 2019. USENIX Association.

[54]

Bruce M. Maggs and Ramesh K. Sitaraman. Algorithmic Nuggets in Content Delivery. ACM SIGCOMM Computer Communication Review, 45(3):52--66, July 2015.

Digital Library

[55]

Sara McAllister, Benjamin Berg, Julian Tutuncu-Macias, Juncheng Yang, Sathya Gunasekar, Jimmy Lu, Daniel S. Berger, Nathan Beckmann, and Gregory R. Ganger. Kangaroo: Theory and practice of caching billions of tiny objects on flash. In ACM Transactions on Storage, volume 18 of TOS'22, August 2022.

Digital Library

[56]

Nimrod Megiddo and Dharmendra S Modha. ARC: A self-tuning, low overhead replacement cache. In 2nd USENIX conference on file and storage technologies, FAST'03, 2003.

Digital Library

[57]

Kianoosh Mokhtarian and Hans-Arno Jacobsen. Caching in video CDNs: building strong lines of defense. In Proceedings of the Ninth European Conference on Computer Systems - EuroSys '14, EuroSys'14, pages 1--13, Amsterdam, The Netherlands, 2014. ACM Press.

Digital Library

[58]

Dushyanth Narayanan, Austin Donnelly, and Antony Rowstron. MSR Cambridge traces (SNIA IOTTA trace set 388). In Geoff Kuenning, editor, SNIA IOTTA Trace Repository. Storage Networking Industry Association, March 2007.

[59]

Dushyanth Narayanan, Austin Donnelly, and Antony Rowstron. Write off-loading: Practical power management for enterprise storage. In 6th USENIX Conference on File and Storage Technologies (FAST 08), San Jose, CA, February 2008. USENIX Association.

Digital Library

[60]

Victor F. Nicola, Asit Dan, and Daniel M. Dias. Analysis of the generalized clock buffer replacement scheme for database transaction processing. In ACM SIGMETRICS Performance Evaluation Review, volume 20 of SIGMETRICS'92, pages 35--46, June 1992.

Digital Library

[61]

Paula Pufek, Hrvoje Grgić, and Branko Mihaljević. Analysis of garbage collection algorithms and memory management in java. In 2019 42nd International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), pages 1677--1682. IEEE, 2019.

[62]

Ziyue Qiu, Juncheng Yang, Juncheng Zhang, Cheng Li, Xiaosong Ma, Qi Chen, Mao Yang, and Yinlong Xu. Frozenhot cache: Rethinking cache management for modern software. In Twenty-third EuroSys Conference, EuroSys'23, New York, NY, USA, 2023. Association for Computing Machinery.

[63]

KV Rashmi, Mosharaf Chowdhury, Jack Kosaian, Ion Stoica, and Kannan Ramchandran. EC-Cache:load-balanced,low-latency cluster caching with online erasure coding. In 12th USENIX symposium on operating systems design and implementation, OSDI'16, pages 401--417, 2016.

[64]

Liana V. Rodriguez, Alexis Gonzalez, Pratik Poudel, Raju Rangaswami, and Jason Liu. Unifying the data center caching layer: Feasible? Profitable? In Proceedings of the 13th ACM workshop on hot topics in storage and file systems, HotStorage '21, pages 50--57, New York, NY, USA, 2021. Association for Computing Machinery.

Digital Library

[65]

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.

[66]

Arjun Singhvi, Aditya Akella, Maggie Anderson, Rob Cauble, Harshad Deshmukh, Dan Gibson, Milo M. K. Martin, Amanda Strominger, Thomas F. Wenisch, and Amin Vahdat. CliqueMap: productionizing an RMA-based distributed caching system. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference, SIGCOMM'21, pages 93--105, Virtual Event USA, August 2021. ACM.

Digital Library

[67]

Yannis Smaragdakis, Scott Kaplan, and Paul Wilson. EELRU: simple and effective adaptive page replacement. ACM SIGMETRICS Performance Evaluation Review, 27(1):122--133, May 1999.

Digital Library

[68]

Alan Jay Smith. Sequentiality and prefetching in database systems. ACM Transactions on Database Systems, 3(3):223--247, September 1978.

Digital Library

[69]

Zhenyu Song, Daniel S Berger, Kai Li, Anees Shaikh, Wyatt Lloyd, Soudeh Ghorbani, Changhoon Kim, Aditya Akella, Arvind Krishnamurthy, Emmett Witchel, and others. Learning relaxed belady for content distribution network caching. In 17th USENIX symposium on networked systems design and implementation, NSDI'20, pages 529--544, 2020.

[70]

Aditya Sundarrajan, Mingdong Feng, Mangesh Kasbekar, and Ramesh K. Sitaraman. Footprint Descriptors: Theory and Practice of Cache Provisioning in a Global CDN. In Proceedings of the 13th International Conference on emerging Networking EXperiments and Technologies, CoNEXT'17, pages 55--67, Incheon Republic of Korea, November 2017. ACM.

Digital Library

[71]

Linpeng Tang, Qi Huang, Wyatt Lloyd, Sanjeev Kumar, and Kai Li. RIPQ: Advanced photo caching on flash for facebook. In 13th USENIX Conference on File and Storage Technologies, FAST'15, pages 373--386, 2015.

[72]

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, July 2018. USENIX Association.

Digital Library

[73]

Carl A. Waldspurger, Nohhyun Park, Alexander Garthwaite, and Irfan Ahmad. Efficient MRC construction with SHARDS. In 13th USENIX conference on file and storage technologies, FAST'15, pages 95--110, Santa Clara, CA, February 2015. USENIX Association.

Digital Library

[74]

Qiuping Wang, Jinhong Li, Tao Ouyang, Chao Shi, and Lilong Huang. Separating data via block invalidation time inference for write amplification reduction in {Log-Structured} storage. In 20th USENIX Conference on File and Storage Technologies (FAST 22), pages 429--444, 2022.

[75]

Qiuping Wang, Jinhong Li, Wen Xia, Erik Kruus, Biplob Debnath, and Patrick PC Lee. Austere flash caching with deduplication and compression. In 2020 USENIX Annual Technical Conference (USENIX ATC 20), ATC, pages 713--726, 2020.

[76]

Alex Wiggins and Jimmy Langston. Enhancing the scalability of memcached. Intel document, 2012.

[77]

Analytics/data lake/traffic/caching. https://wikitech.wikimedia.org/wiki/Analytics/Data_Lake/Traffic/Caching. Accessed: 2020-05-06.

[78]

Kan Wu, Zhihan Guo, Guanzhou Hu, Kaiwei Tu, Ramnatthan Alagappan, Rathijit Sen, Kwanghyun Park, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. The storage hierarchy is not a hierarchy: Optimizing caching on modern storage devices with orthus. In 19th USENIX conference on file and storage technologies, FAST'21, pages 307--323. USENIX Association, February 2021.

[79]

Gang Yan and Jian Li. Towards Latency Awareness for Content Delivery Network Caching. ATC'22, pages 789--804, 2022.

[80]

Juncheng Yang, Reza Karimi, Trausti Sæmundsson, Avani Wildani, and Ymir Vigfusson. Mithril: mining sporadic associations for cache prefetching. In Proceedings of the 2017 Symposium on Cloud Computing, SoCC '17, pages 66--79, New York, NY, USA, September 2017. Association for Computing Machinery.

Digital Library

[81]

Juncheng Yang, Anirudh Sabnis, Daniel S. Berger, K. V. Rashmi, and Ramesh K. Sitaraman. C2DN: How to harness erasure codes at the edge for efficient content delivery. In 19th USENIX symposium on networked systems design and implementation, NSDI'22, pages 1159--1177, Renton, WA, April 2022. USENIX Association.

[82]

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.

[83]

Juncheng Yang, Yao Yue, and Rashmi Vinayak. Segcache: a memory-efficient and scalable in-memory key-value cache for small objects. In 18th USENIX Symposium on Networked Systems Design and Implementation, NSDI'21, pages 503--518. USENIX Association, April 2021.

[84]

Tzu-Wei Yang, Seth Pollen, Mustafa Uysal, Arif Merchant, and Homer Wolfmeister. CacheSack: Admission Optimization for Google Datacenter Flash Caches. In 2022 USENIX Annual Technical Conference, ATC'22, pages 1021--1036, Carlsbad, CA, July 2022. USENIX Association.

[85]

Lei Zhang, Reza Karimi, Irfan Ahmad, and Ymir Vigfusson. Optimal Data Placement for Heterogeneous Cache, Memory, and Storage Systems. In Proceedings of the ACM on Measurement and Analysis of Computing Systems, volume 4 of SIGMETRICS'20, pages 1--27, May 2020.

Digital Library

[86]

Lei Zhang, Juncheng Yang, Anna Blasiak, Mike McCall, and Ymir Vigfusson. When is the Cache Warm? Manufacturing a Rule of Thumb. 2020.

[87]

Yu Zhang, Ping Huang, Ke Zhou, Hua Wang, Jianying Hu, Yongguang Ji, and Bin Cheng. Tencent block storage traces (SNIA IOTTA trace set 27917). In Geoff Kuenning, editor, SNIA IOTTA Trace Repository. Storage Networking Industry Association, October 2018.

[88]

Yu Zhang, Ping Huang, Ke Zhou, Hua Wang, Jianying Hu, Yongguang Ji, and Bin Cheng. OSCA: An Online-Model based cache allocation scheme in cloud block storage systems. In 2020 USENIX Annual Technical Conference (USENIX ATC 20), pages 785--798. USENIX Association, July 2020.

[89]

Yuchao Zhang, Pengmiao Li, Zhili Zhang, Bo Bai, Gong Zhang, Wendong Wang, Bo Lian, and Ke Xu. AutoSight: Distributed Edge Caching in Short Video Network. IEEE Network, 34(3):194--199, May 2020.

[90]

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, SYSTOR'21, pages 1--12, Haifa Israel, June 2021. ACM.

Digital Library

[91]

Ke Zhou, Si Sun, Hua Wang, Ping Huang, Xubin He, Rui Lan, Wenyan Li, Wenji Liu, and Tianming Yang. Tencent photo cache traces (SNIA IOTTA trace set 27476). In Geoff Kuenning, editor, SNIA IOTTA Trace Repository. Storage Networking Industry Association, February 2016.

[92]

Yuanyuan Zhou, James Philbin, and Kai Li. The multi-queue replacement algorithm for second level buffer caches. In Proceedings of the annual conference on USENIX Annual Technical Conference, ATC'01, pages 91--104, USA, 2001. USENIX Association.

Cited By

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
Jia RChen ZWu CLi JGuo MHuang H(2024)RL-Cache: An Efficient Reinforcement Learning Based Cache Partitioning Approach for Multi-Tenant CDN Services2024 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER59578.2024.00025(202-213)Online publication date: 24-Sep-2024
https://doi.org/10.1109/CLUSTER59578.2024.00025
Cha HKim IKim T(2024)Using a random forest to predict quantized reuse distance in an SSD write bufferComputing10.1007/s00607-024-01343-5106:12(3967-3986)Online publication date: 5-Sep-2024
https://doi.org/10.1007/s00607-024-01343-5

Recommendations

Modeling LRU cache with invalidation

Least Recently Used (LRU) is a very popular caching replacement policy. It is very easy to implement and offers good performance, especially when data requests are temporally correlated, as in the case of web traffic.When the data content can change ...
An Adaptive Demotion Policy for High-Associativity Caches
HEART '17: Proceedings of the 8th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies

Although the Least Recently Used (LRU) policy is known as a simple but high-performance cache replacement policy, high-associativity caches hardly adopt the LRU policy because of an increase in the hardware overheads. The Re-Reference Interval ...
LRU-SP: A Size-Adjusted and Popularity-Aware LRU Replacement Algorithm for Web Caching
COMPSAC '00: 24th International Computer Software and Applications Conference

This paper presents LRU-SP, a size-adjusted and popularity-aware extension to Least Recently Used (LRU) for caching web objects. The standard LRU, focusing on recently used and equal sized objects, is not suitable for the web context because web objects ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HOTOS '23: Proceedings of the 19th Workshop on Hot Topics in Operating Systems

June 2023

247 pages

ISBN:9798400701955

DOI:10.1145/3593856

General Chair:
Malte Schwarzkopf,
Program Chairs:
Andrew Baumann,
Natacha Crooks

Copyright © 2023 Owner/Author(s).

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2023

Check for updates

Qualifiers

Research-article

Funding Sources

NFS CNS
NFS CNS:

Conference

HOTOS '23

Sponsor:

SIGOPS

HOTOS '23: 19th Workshop on Hot Topics in Operating Systems

June 22 - 24, 2023

RI, Providence, USA

Upcoming Conference

HOTOS '25

Sponsor:
sigops

Workshop on Hot Topics in Operating Systems

May 14 - 16, 2025

Banff or Lake Louise , AB , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
2,643
Total Downloads

Downloads (Last 12 months)1,873
Downloads (Last 6 weeks)217

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Jia RChen ZWu CLi JGuo MHuang H(2024)RL-Cache: An Efficient Reinforcement Learning Based Cache Partitioning Approach for Multi-Tenant CDN Services2024 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER59578.2024.00025(202-213)Online publication date: 24-Sep-2024
https://doi.org/10.1109/CLUSTER59578.2024.00025
Cha HKim IKim T(2024)Using a random forest to predict quantized reuse distance in an SSD write bufferComputing10.1007/s00607-024-01343-5106:12(3967-3986)Online publication date: 5-Sep-2024
https://doi.org/10.1007/s00607-024-01343-5

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents