ABSTRACT
Caching is crucial for accelerating data access, employed as a ubiquitous design in modern systems at many parts of computer systems. With increasing core count, and shrinking latency gap between cache and modern storage devices, hit-path scalability becomes increasingly critical. However, existing production in-memory caches often use list-based management with promotion on each cache hit, which requires extensive locking and poses a significant overhead for scaling beyond a few cores. Moreover, existing techniques for improving scalability either (1) only focus on the indexing structure and do not improve cache management scalability, or (2) sacrifice efficiency or miss-path scalability.
Inspired by highly skewed data popularity and short-term hotspot stability in cache workloads, we propose Frozen-Hot, a generic approach to improve the scalability of list-based caches. FrozenHot partitions the cache space into two parts: a frozen cache and a dynamic cache. The frozen cache serves requests for hot objects with minimal latency by eliminating promotion and locking, while the latter leverages the existing cache design to achieve workload adaptivity. We built FrozenHot as a library that can be easily integrated into existing systems. We demonstrate its performance by enabling FrozenHot in two production systems: HHVM and RocksDB using under 100 lines of code. Evaluated using production traces from MSR and Twitter, FrozenHot improves the throughput of three baseline cache algorithms by up to 551%. Compared to stock RocksDB, FrozenHot-enhanced RocksDB shows a higher throughput on all YCSB workloads with up to 90% increase, as well as reduced tail latency.
- An object-oriented programming language. https://hacklang.org/. Accessed May 19, 2022.Google Scholar
- Anonymized Cache Request Traces from Twitter Production. https://github.com/twitter/cache-trace. Accessed Oct 14, 2022.Google Scholar
- AWS Introduces Storage-Optimized I4i Instances for IO-Heavy Workloads. https://www.infoq.com/news/2022/05/aws-ec2-I4i/. Accessed May 19, 2022.Google Scholar
- bcache. https://www.kernel.org/doc/Documentation/bcache.txt. Accessed May 19, 2022.Google Scholar
- Benchmarking Apache Samza. https://engineering.linkedin.com/performance/benchmarking-apache-samza-12-million-messages-second-single-node. Accessed May 19, 2022.Google Scholar
- cache trace. https://github.com/twitter/cache-trace/blob/master/stat/2020Mar.md. Accessed May 19, 2022.Google Scholar
- Caching at Reddit. https://news.ycombinator.com/item?id=13429314. Accessed May 19, 2022.Google Scholar
- CLHT is a very fast and scalable concurrent, resizable hash table. https://github.com/LPD-EPFL/CLHT. Accessed May 19, 2022.Google Scholar
- Cloudlab. https://www.cloudlab.us/. Accessed Feb 19, 2023.Google Scholar
- Ephemeral volatile caching in the cloud. https://netflixtechblog.com/ephemeral-volatile-caching-in-the-cloud-8eba7b124589?gi=a1f174f2ae11. Accessed May 19, 2022.Google Scholar
- HHVM project. https://github.com/facebook/hhvm.git. Accessed May 19, 2022.Google Scholar
- HHVM Scalable Concurrent Cache. https://github.com/facebook/hhvm/blob/master/hphp/util/concurrent-scalable-cache.h. Accessed May 19, 2022.Google Scholar
- Intel Optane DC Persistent Memory. https://www.intel.com/content/www/us/en/architecture-and-technology/optane-dc-persistent-memory.html. Accessed May 19, 2022.Google Scholar
- Intel: Why a 1,000-Core Chip Is Feasible? https://cacm.acm.org/opinion/interviews/103399-intel-why-a-1000-core-chip-is-feasible/fulltext?mobile=false. Communications of The ACM. Accessed May 19, 2022.Google Scholar
- Memcached. memcached - a distributed memory object caching system. http://memcached.org/. Accessed May 19, 2022.Google Scholar
- Open CAS. Open Cache Acceleration Software. https://open-cas.github.io/. Accessed May 19, 2022.Google Scholar
- Redis. https://redis.io/. Accessed May 19, 2022.Google Scholar
- Redis Approximated LRU algorithm. https://redis.io/docs/manual/eviction/#approximated-lru-algorithm. Accessed May 19, 2022.Google Scholar
- RocksDB. https://rocksdb.org/. Accessed May 19, 2022.Google Scholar
- RocksDB Block Cache. https://github.com/facebook/rocksdb/wiki/Block-Cache. Accessed May 19, 2022.Google Scholar
- RocksDB on Steroids. https://www.i-programmer.info/news/84-database/8542-rocksdb-on-steroids.html. Accessed May 19, 2022.Google Scholar
- SDC2020: Caching on PMEM: an Iterative Approach. https://www.youtube.com/watch?v=lTiw4ehHAP4. Accessed May 19, 2022.Google Scholar
- Storage networking industry association. the snia's i/o traces, tools, and analysis (iotta) repository. http://iotta.snia.org/. Accessed May 19, 2022.Google Scholar
- Maya Arbel and Hagit Attiya. Concurrent updates with rcu: Search tree as an example. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 196--205, 2014.Google ScholarDigital Library
- 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, page 53--64, New York, NY, USA, 2012. Association for Computing Machinery.Google ScholarDigital Library
- Anirudh Badam, KyoungSoo Park, Vivek S Pai, and Larry L Peterson. HashCache: Cache Storage for the Next Billion. In NSDI, volume 9, pages 123--136, 2009.Google Scholar
- 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, Renton, WA, April 2018. USENIX Association.Google Scholar
- Mateusz Berezecki, Eitan Frachtenberg, Mike Paleczny, and Kenneth Steele. Many-core key-value store. In 2011 International Green Computing Conference and Workshops, pages 1--8, 2011.Google ScholarDigital Library
- 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.Google Scholar
- Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. TAO: Facebook's Distributed Data Store for the Social Graph. In Proceedings of the 2013 USENIX Conference on Annual Technical Conference, USENIX ATC'13, page 49--60, USA, 2013. USENIX Association.Google ScholarDigital Library
- Hao Chen, Chaoyi Ruan, Cheng Li, Xiaosong Ma, and Yinlong Xu. Spandb: A fast, cost-effective lsm-tree based KV store on hybrid storage. In 19th USENIX Conference on File and Storage Technologies (FAST 21), pages 17--32, 2021.Google Scholar
- Jiqiang Chen, Liang Chen, Sheng Wang, Guoyun Zhu, Yuanyuan Sun, Huan Liu, and Feifei Li. Hotring: A hotspot-aware in-memory key-value store. In 18th USENIX Conference on File and Storage Technologies (FAST 20), pages 239--252, 2020.Google Scholar
- Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM symposium on Cloud computing, pages 143--154, 2010.Google ScholarDigital Library
- F.J. Corbató and Project MAC (Massachusetts Institute of Technology). A PAGING EXPERIMENT WITH THE MULTICS SYSTEM. Project MAC. Massachusetts Institute of Technology, 1968.Google Scholar
- Subramanya R Dulloor, Amitabha Roy, Zheguang Zhao, Narayanan Sundaram, Nadathur Satish, Rajesh Sankaran, Jeff Jackson, and Karsten Schwan. Data tiering in heterogeneous memory systems. In Proceedings of the Eleventh European Conference on Computer Systems, pages 1--16, 2016.Google ScholarDigital Library
- Gil Einziger, Roy Friedman, and Ben Manes. TinyLFU: A Highly Efficient Cache Admission Policy, 2015.Google Scholar
- 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), 2020.Google Scholar
- 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, Lombard, IL, April 2013. USENIX Association.Google Scholar
- 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), pages 1--11, 2014.Google ScholarCross Ref
- Tayler H. Hetherington, Timothy G. Rogers, Lisa Hsu, Mike O'Connor, and Tor M. Aamodt. Characterizing and evaluating a key-value store application on heterogeneous CPU-GPU systems. In 2012 IEEE International Symposium on Performance Analysis of Systems Software, pages 88--98, 2012.Google ScholarDigital Library
- Song Jiang and Xiaodong Zhang. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. ACM SIGMETRICS Performance Evaluation Review, 30(1):31--42, 2002.Google ScholarDigital Library
- 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, pages 121--136, 2017.Google ScholarDigital Library
- Theodore Johnson and Dennis Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. In VLDB, 1994.Google Scholar
- George Karakostas and Dimitrios N Serpanos. Exploitation of different types of locality for web caches. In Proceedings ISCC 2002 Seventh International Symposium on Computers and Communications, pages 207--212. IEEE, 2002.Google ScholarCross Ref
- R. Karedla, J.S. Love, and B.G. Wherry. Caching strategies to improve disk system performance. Computer, 27(3):38--46, 1994.Google ScholarDigital Library
- Jaehyung Kim, Hongchan Roh, and Sanghyun Park. Selective I/O bypass and load balancing method for write-through SSD caching in big data analytics. IEEE Transactions on Computers, 67(4):589--595, 2017.Google ScholarCross Ref
- Baptiste Lepers, Oana Balmau, Karan Gupta, and Willy Zwaenepoel. KVell: The Design and Implementation of a Fast Persistent Key-Value Store. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP '19, page 447--461, New York, NY, USA, 2019. Association for Computing Machinery.Google ScholarDigital Library
- Conglong Li and Alan L. Cox. GD-Wheel: A Cost-Aware Replacement Policy for Key-Value Stores. In Proceedings of the Tenth European Conference on Computer Systems, EuroSys '15, New York, NY, USA, 2015. Association for Computing Machinery.Google Scholar
- Xiaozhou Li, Raghav Sethi, Michael Kaminsky, David G Andersen, and Michael J Freedman. Be Fast, Cheap and in Control with SwitchKV. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), pages 31--44, 2016.Google Scholar
- Hyeontaek Lim, Dongsu Han, David G. Andersen, and Michael Kaminsky. MICA: A Holistic Approach to Fast In-Memory Key-Value Storage. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14), pages 429--444, Seattle, WA, April 2014. USENIX Association.Google ScholarDigital Library
- Zhiqi Lin, Cheng Li, Youshan Miao, Yunxin Liu, and Yinlong Xu. PaGraph: Scaling GNN Training on Large Graphs via Computation-Aware Caching. In Proceedings of the 11th ACM Symposium on Cloud Computing, SoCC '20, page 401--415, New York, NY, USA, 2020. Association for Computing Machinery.Google Scholar
- Yandong Mao, Eddie Kohler, and Robert Tappan Morris. Cache Craftiness for Fast Multicore Key-Value Storage. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys '12, page 183--196, New York, NY, USA, 2012. Association for Computing Machinery.Google Scholar
- Yandong Mao, Eddie Kohler, and Robert Tappan Morris. Cache Craftiness for Fast Multicore Key-Value Storage. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys '12, page 183--196, New York, NY, USA, 2012. Association for Computing Machinery.Google Scholar
- Dhruv Matani, Ketan Shah, and Anirban Mitra. An O (1) algorithm for implementing the LFU cache eviction scheme. arXiv preprint arXiv:2110.11602, 2021.Google Scholar
- Sara McAllister, Benjamin Berg, Julian Tutuncu-Macias, Juncheng Yang, Sathya Gunasekar, Jimmy Lu, Daniel S. Berger, Nathan Beckmann, and Gregory R. Ganger. Kangaroo: Caching Billions of Tiny Objects on Flash. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, SOSP '21, page 243--262, New York, NY, USA, 2021. Association for Computing Machinery.Google ScholarDigital Library
- Paul E McKenney. Kernel korner: using RCU in the Linux 2.5 kernel. Linux Journal, 2003(114):11, 2003.Google ScholarDigital Library
- Nimrod Megiddo and Dharmendra S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies, FAST '03, page 115--130, USA, 2003. USENIX Association.Google ScholarDigital Library
- Zviad Metreveli, Nickolai Zeldovich, and M. Frans Kaashoek. CPHASH: A Cache-Partitioned Hash Table. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '12, page 319--320, New York, NY, USA, 2012. Association for Computing Machinery.Google ScholarDigital Library
- Subramanian Muralidhar, Wyatt Lloyd, Sabyasachi Roy, Cory Hill, Ernest Lin, Weiwen Liu, Satadru Pan, Shiva Shankar, Viswanath Sivakumar, Linpeng Tang, and Sanjeev Kumar. F4: Facebook's Warm BLOB Storage System. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI'14, page 383--398, USA, 2014. USENIX Association.Google ScholarDigital Library
- Dushyanth Narayanan, Austin Donnelly, Eno Thereska, Sameh Elnikety, and Antony Rowstron. Everest: Scaling Down Peak Loads Through I/O Off-Loading. In 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI 08), San Diego, CA, December 2008. USENIX Association.Google Scholar
- Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, and Venkateshwaran Venkataramani. Scaling Memcache at Facebook. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, nsdi'13, page 385--398, USA, 2013. USENIX Association.Google ScholarDigital Library
- Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C. Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, and Venkateshwaran Venkataramani. Scaling Memcache at Facebook. In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), pages 385--398, Lombard, IL, April 2013. USENIX Association.Google ScholarDigital Library
- 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, page 297--306, New York, NY, USA, 1993. Association for Computing Machinery.Google ScholarDigital Library
- James Reinders. Intel threading building blocks: outfitting C++ for multi-core processor parallelism. " O'Reilly Media, Inc.", 2007.Google Scholar
- 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.Google Scholar
- Alan Jay Smith. Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst., 3(3):223--247, sep 1978.Google ScholarDigital Library
- Zhenyu Song, Daniel S. Berger, Kai Li, and Wyatt Lloyd. Learning Relaxed Belady for Content Distribution Network Caching . In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 529--544, Santa Clara, CA, February 2020. USENIX Association.Google ScholarDigital Library
- Linpeng Tang, Qi Huang, Wyatt Lloyd, Sanjeev Kumar, and Kai Li. RIPQ: Advanced Photo Caching on Flash for Facebook. In Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST'15, page 373--386, USA, 2015. USENIX Association.Google ScholarDigital Library
- 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 Proceedings of the 10th USENIX Conference on Hot Topics in Storage and File Systems, HotStorage'18, page 3, USA, 2018. USENIX Association.Google Scholar
- 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.Google Scholar
- Xingbo Wu, Li Zhang, Yandong Wang, Yufei Ren, Michel Hack, and Song Jiang. ZExpander: A Key-Value Cache with Both High Performance and Fewer Misses. In Proceedings of the Eleventh European Conference on Computer Systems, EuroSys '16, New York, NY, USA, 2016. Association for Computing Machinery.Google Scholar
- 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, pages 66--79, 2017.Google ScholarDigital Library
- Juncheng Yang, Ziming Mao, Yao Yue, and K. V. Rashmi. GL-Cache: Group-level learning for efficient and high-performance caching. In 21st USENIX Conference on File and Storage Technologies (FAST 23), pages 115--134, Santa Clara, CA, February 2023. USENIX Association.Google Scholar
- Juncheng Yang, Anirudh Sabnis, Daniel S Berger, KV 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, 2022.Google Scholar
- Juncheng Yang, Yao Yue, and Rashmi Vinayak. 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, 2020.Google ScholarDigital Library
- Juncheng Yang, Yao Yue, and Rashmi Vinayak. Segcache: a memory-efficient and scalable in-memory key-value cache for small objects. In NSDI, pages 503--518, 2021.Google Scholar
- Neal Young. Thek-server dual and loose competitiveness for paging. Algorithmica, 11(6):525--541, 1994.Google ScholarDigital Library
- Xiangyao Yu, George Bezerra, Andrew Pavlo, Srinivas Devadas, and Michael Stonebraker. Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores. Proc. VLDB Endow., 8(3):209--220, nov 2014.Google ScholarDigital Library
- Lei Zhang, Reza Karimi, Irfan Ahmad, and Ymir Vigfusson. Optimal Data Placement for Heterogeneous Cache, Memory, and Storage Systems. In Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '20, page 85--86, New York, NY, USA, 2020. Association for Computing Machinery.Google ScholarDigital Library
- Teng Zhang, Jianying Wang, Xuntao Cheng, Hao Xu, Nanlong Yu, Gui Huang, Tieying Zhang, Dengcheng He, Feifei Li, Wei Cao, et al. Fpga-accelerated compactions for lsm-based key-value store. In 18th USENIX Conference on File and Storage Technologies (FAST 20), pages 225--237, 2020.Google ScholarDigital Library
- Zehua Zhao, Yan Ma, and Qun Cong. GDSF-Based Low Access Latency Web Proxy Caching Replacement Algorithm. In Proceedings of the 2018 2nd International Conference on Computer Science and Artificial Intelligence, CSAI '18, page 232--236, New York, NY, USA, 2018. Association for Computing Machinery.Google Scholar
- Shengan Zheng, Morteza Hoseinzadeh, and Steven Swanson. Ziggurat: a tiered file system for non-volatile main memories and disks. In 17th USENIX Conference on File and Storage Technologies (FAST 19), pages 207--219, 2019.Google Scholar
- Xinjing Zhou, Joy Arulraj, Andrew Pavlo, and David Cohen. Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory. In Proceedings of the 2021 International Conference on Management of Data, pages 2195--2207, 2021.Google Scholar
Index Terms
- FrozenHot Cache: Rethinking Cache Management for Modern Hardware
Recommendations
Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer ArchitectureOn-die caches are a popular method to help hide the main memory latency. However, it is difficult to build large caches without substantially increasing their access latency, which in turn hurts performance. To overcome this difficulty, on-die caches ...
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 ...
Location cache: a low-power L2 cache system
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and designWhile set-associative caches incur fewer misses than direct-mapped caches, they typically have slower hit times and higher power consumption, when multiple tag and data banks are probed in parallel. This paper presents the location cache structure which ...
Comments