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

research-article

TTLs Matter: Efficient Cache Sizing with TTL-Aware Miss Ratio Curves and Working Set Sizes

Authors:

Michael StummAuthors Info & Claims

EuroSys '24: Proceedings of the Nineteenth European Conference on Computer Systems

Pages 387 - 404

https://doi.org/10.1145/3627703.3650066

Published: 22 April 2024 Publication History

Abstract

In-memory caches play a pivotal role in optimizing distributed systems by significantly reducing query response times. Correctly sizing these caches is critical, especially considering that prominent organizations use terabytes and even petabytes of DRAM for these caches. The Miss Ratio Curve (MRC) and Working Set Size (WSS) are the most widely used tools for sizing these caches.

Modern cache workloads employ Time-to-Live (TTL) limits to define the lifespan of cached objects, a feature essential for ensuring data freshness and adhering to regulations like GDPR. Surprisingly, none of the existing MRC and WSS tools accommodate TTLs. Based on 28 real-world cache workloads that contain 113 billion accesses, we show that taking TTL limits into consideration allows an average of 69% (and up to 99%) lower memory footprint for in-memory caches without a degradation in the hit rate.

This paper describes how TTLs can be integrated into today's most important MRC generation and WSS estimation algorithms. We also describe how the widely used HyperLogLog (HLL) cardinality estimator can be extended to accommodate TTLs, and show how it can be used to efficiently estimate the WSS. Our extended algorithms maintain comparable performance levels to the original algorithms. All our extended approximate algorithms are efficient, run in constant space, and enable more resource-efficient and cost-effective cache management.

References

[1]

Memcached.org. Memcached. https://memcached.org. [Online; 2023].

[2]

Brad Fitzpatrick. Distributed caching with Memcached. Linux J., 2004(124), 5 2004.

Digital Library

[3]

Redis Labs. Redis. https://redis.io. [Online; 2023].

[4]

Amazon. Amazon Elasticache. https://aws.amazon.com/elasticache/. [Online; 2023].

[5]

Google. Google Memorystore. https://cloud.google.com/memorystore. [Online; 2023].

[6]

Microsoft. Microsoft Azure cache. https://azure.microsoft.com/en-us/services/cache/. [Online; 2023].

[7]

Huawei. Huawei Distributed Cache Service. https://www.huaweicloud.com/en-us/product/dcs.html. [Online; 2023].

[8]

IBM. IBM Cloud Databases for Redis. https://www.ibm.com/cloud/databases-for-redis. [Online; 2023].

[9]

Oracle. Using caches in Oracle application container cloud service. https://docs.oracle.com/en/cloud/paas/app-container-cloud/cache/index.html. [Online; 2023].

[10]

DigitalOcean. Managed Redis. https://www.digitalocean.com/products/managed-databases-redis/. [Online; 2023].

[11]

Alibaba. ApsaraDB for Memcache. https://www.alibabacloud.com/product/apsaradb-for-memcache. [Online; 2023].

[12]

ObjectRocket. ObjectRocket for Redis. https://www.objectrocket.com/managed-redis/. [Online; 2023].

[13]

Tencent. TencentDB for Redis. https://intl.cloud.tencent.com/product/crs. [Online; 2023].

[14]

Timothy Zhu, Anshul Gandhi, Mor Harchol-Balter, and Michael A Kozuch. Saving cash by using less cache. In Proc. 4th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud'12), 2012.

[15]

Azure. Azure cache for Redis pricing. https://azure.microsoft.com/en-us/pricing/details/cache/. [Online; 2023].

[16]

Doug Beaver, Sanjeev Kumar, Harry C Li, Jason Sobel, Peter Vajgel, et al. Finding a needle in Haystack: Facebook's photo storage. In Proc. 9th Conf. on Operating Systems Design and Implementation (OSDI'10), pages 1--8, 2010.

[17]

Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, et al. Scaling Memcache at Facebook. In Proc. 10th USENIX Symp. on Networked Systems Design and Implementation (NSDI'13), pages 385--398, 2013.

Digital Library

[18]

Jeffrey Dean and Luiz André Barroso. The tail at scale. Communications of the ACM, 56(2):74--80, 2013.

Digital Library

[19]

Alex Hall, Alexandra Tudorica, Filip Buruiana, Reimar Hofmann, Silviu-Ionut Ganceanu, and Thomas Hofmann. Trading off accuracy for speed in powerdrill. Google Research, 2016.

[20]

Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. Workload analysis of a large-scale key-value store. In Proc. 12th Intl. Conf. on Measurement and Modeling of Computer Systems (SIGMETRICS'12), pages 53--64, 2012.

Digital Library

[21]

Qi Huang, Ken Birman, Robbert Van Renesse, Wyatt Lloyd, Sanjeev Kumar, and Harry C Li. An analysis of Facebook photo caching. In Proc. 24-th Symp. on Operating Systems Principles (SOSP'13), pages 167--181, 2013.

Digital Library

[22]

Asaf Cidon, Assaf Eisenman, Mohammad Alizadeh, and Sachin Katti. Dynacache: Dynamic cloud caching. In Proc. 7th Workshop on Hot Topics in Cloud Computing (HotCloud'15), 2015.

[23]

Juncheng Yang, Yao Yue, and KV Rashmi. A large scale analysis of hundreds of in-memory cache clusters at Twitter. In Proc. 14th Symp. on Operating Systems Design and Implementation (OSDI'20), pages 191--208, 2020.

[24]

Richard L. Mattson, Jan Gecsei, Donald R. Slutz, and Irving L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems journal, 9(2):78--117, 1970.

Digital Library

[25]

Frank Olken. Efficient methods for calculating the success function of fixed-space replacement policies. Master's thesis, University of California, Berkeley), 1981.

[26]

Weiming Zhao, Xinxin Jin, Zhenlin Wang, Xiaolin Wang, Yingwei Luo, and Xiaoming Li. Efficient LRU-based working set size tracking. Michigan Technological University Computer Science Technical Report, 2011.

[27]

Qingpeng Niu, James Dinan, Qingda Lu, and P. Sadayappan. PARDA: A fast parallel reuse distance analysis algorithm. In Proc. 26th Intl. Parallel and Distributed Processing Symp. (IPDPS'12), pages 1284--1294. IEEE, 2012.

Digital Library

[28]

Jake Wires, Stephen Ingram, Zachary Drudi, Nicholas JA Harvey, and Andrew Warfield. Characterizing storage workloads with counter stacks. In Proc. 11th Symp. on Operating Systems Design and Implementation (OSDI'14), pages 335--349, 2014.

[29]

Carl A Waldspurger, Nohhyun Park, Alexander Garthwaite, and Irfan Ahmad. Efficient MRC construction with SHARDS. In Proc. 13th Conf. on File and Storage Technologies (FAST'15), pages 95--110, 2015.

Digital Library

[30]

Nathan Beckmann and Daniel Sanchez. Talus: A simple way to remove cliffs in cache performance. In Proc. 21st Intl. Symp. on High Performance Computer Architecture (HPCA'15), pages 64--75. IEEE, 2015.

[31]

Xiameng Hu, Xiaolin Wang, Lan Zhou, Yingwei Luo, Chen Ding, and Zhenlin Wang. Kinetic modeling of data eviction in cache. In Proc. USENIX Annual Technical Conf. (ATC'16), pages 351--364, 2016.

[32]

Carl Waldspurger, Trausti Saemundsson, Irfan Ahmad, and Nohhyun Park. Cache modeling and optimization using miniature simulations. In Proc. USENIX Annual Technical Conf. (ATC'17), pages 487--498, 2017.

[33]

Xiameng Hu, Xiaolin Wang, Lan Zhou, Yingwei Luo, Zhenlin Wang, Chen Ding, and Chencheng Ye. Fast miss ratio curve modeling for storage cache. ACM Trans. on Storage (TOS'18), 14(2):1--34, 2018.

[34]

Cheng Pan, Xiameng Hu, Lan Zhou, Yingwei Luo, Xiaolin Wang, and Zhenlin Wang. Pace: Penalty aware cache modeling with enhanced AET. In Proc. 9th Asia-Pacific Workshop on Systems, pages 1--8, 2018.

Digital Library

[35]

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 Proc. USENIX Annual Technical Conf. (ATC'20), pages 785--798, 2020.

[36]

Jiangwei Zhang and YC Tay. PG2S+: Stack distance construction using popularity, gap and machine learning. In Proc. The Web Conf. (WWW'20), pages 973--983, 2020.

Digital Library

[37]

Damiano Carra and Giovanni Neglia. Efficient miss ratio curve computation for heterogeneous content popularity. In Proc. USENIX Annual Technical Conf. (ATC'20), pages 741--751, 2020.

[38]

Zhang Liu, Hee Won Lee, Yu Xiang, Dirk Grunwald, and Sangtae Ha. eMRC: Efficient miss ratio approximation for multi-tier caching. In Proc. 19th Conf. on File and Storage Technologies (FAST'21), pages 293--306, 2021.

[39]

Zhilu Lian, Yangzi Li, Zhixiang Chen, Shiwen Shan, Baoxin Han, and Yuxin Su. eBPF-based working set size estimation in memory management. In Proc. 2022 intl. conf. on Service Science (ICSS'22), pages 188--195, 2022.

[40]

Juncheng Yang, Yao Yue, and KV Rashmi. A large-scale analysis of hundreds of in-memory key-value cache clusters at Twitter. ACM Transactions on Storage (TOS'21), 17(3):1--35, 2021.

[41]

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

[42]

Alexander Fuerst and Prateek Sharma. Faascache: Keeping serverless computing alive with greedy-dual caching. In Proc. the 26th ACM Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS'21), pages 386--400, 2021.

Digital Library

[43]

Gerhard Hasslinger, Mahshid Okhovatzadeh, Konstantinos Ntougias, Frank Hasslinger, and Oliver Hohlfeld. An overview of analysis methods and evaluation results for caching strategies. Computer Networks, 228:109583, 2023.

Digital Library

[44]

Dushyanth Narayanan, Austin Donnelly, and Antony Rowstron. Write off-loading: Practical power management for enterprise storage. ACM Trans. Storage (TOS'08, pages 10:1 - 10:23, 10 2008.

[45]

Vlad Nitu, Aram Kocharyan, Hannas Yaya, Alain Tchana, Daniel Hagimont, and Hrachya Astsatryan. Working set size estimation techniques in virtualized environments: One size does not fit all. In Proc. the ACM on Measurement and Analysis of Computing Systems, pages 1--22, 2018.

Digital Library

[46]

Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31(2):182--209, 1985.

Digital Library

[47]

Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137--147, 1999.

Digital Library

[48]

Ziv Bar-Yossef, TS Jayram, Ravi Kumar, D Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In Proc. Intl. Workshop on Randomization and Approximation Techniques in Computer Science, pages 1--10, 2002.

[49]

Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities. In Proc. European Symp. on Algorithms, pages 605--617, 2003.

[50]

Frédéric Giroire. Order statistics and estimating cardinalities of massive data sets. Discrete Applied Mathematics, 157(2):406--427, 2009.

Digital Library

[51]

Kevin Beyer, Peter J Haas, Berthold Reinwald, Yannis Sismanis, and Rainer Gemulla. On synopses for distinct-value estimation under multiset operations. In Proc. Intl. Conf. on Management of Data (SIGMOD'07), pages 199--210, 2007.

Digital Library

[52]

Kyu-Young Whang, Brad T Vander-Zanden, and Howard M Taylor. A linear-time probabilistic counting algorithm for database applications. ACM Trans. on Database Systems (TODS'90), 15(2):208--229, 1990.

[53]

Odysseas Papapetrou, Wolf Siberski, and Wolfgang Nejdl. Cardinality estimation and dynamic length adaptation for Bloom filters. Distributed and Parallel Databases, 28(2):119--156, 2010.

Digital Library

[54]

Hazar Harmouch and Felix Naumann. Cardinality estimation: An experimental survey. Proc. of the VLDB Endowment, 11(4):499--512, 2017.

Digital Library

[55]

Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In Proc. Discrete Mathematics and Theoretical Computer Science, pages 137--156, 2007.

[56]

Stefan Heule, Marc Nunkesser, and Alexander Hall. Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm. In Proc. 16th Intl. Conf. on Extending Database Technology, pages 683--692, 2013.

Digital Library

[57]

Internet Engineering Task Force (IETF). Domain name system (DNS) IANA considerations. https://aws.amazon.com/elasticache/. [Online; 2023].

[58]

Jaeyeon Jung, Arthur W Berger, and Hari Balakrishnan. Modeling TTL-based internet caches. In Proc. 22nd Annual Joint Conf. of the IEEE Computer and Communications Societies, volume 1, pages 417--426, 2003.

[59]

Nicaise Choungmo Fofack, Philippe Nain, Giovanni Neglia, and Don Towsley. Performance evaluation of hierarchical TTL-based cache networks. Computer Networks, 65:212--231, 2014.

[60]

Daniel S Berger, Philipp Gland, Sahil Singla, and Florin Ciucu. Exact analysis of TTL cache networks. Performance Evaluation, 79:2--23, 2014.

[61]

Ningwei Dai, Yunpeng Chai, Yushi Liang, and Chunling Wang. ETD-cache: An expiration-time driven cache scheme to make SSD-based read cache endurable and cost-efficient. In Proc. 12th ACM Intl. Conf. on Computing Frontiers, pages 1--8, 2015.

[62]

Soumya Basu, Aditya Sundarrajan, Javad Ghaderi, Sanjay Shakkottai, and Ramesh Sitaraman. Adaptive TTL-based caching for content delivery. Transactions on Networking, 26(3):1063--1077, 2018.

Digital Library

[63]

Damiano Carra, Giovanni Neglia, and Pietro Michiardi. TTL-based cloud caches. In Proc. Conf. on Computer Communications, pages 685--693, 2019.

Digital Library

[64]

Aashaka Shah, Vinay Banakar, Supreeth Shastri, Melissa Wasserman, and Vijay Chidambaram. Analyzing the impact of GDPR on storage systems. In Proc. 11th Workshop on Hot Topics in Storage and File Systems (HotStorage'19), 2019.

[65]

Damiano Carra, Giovanni Neglia, and Pietro Michiardi. Elastic provisioning of cloud caches: A cost-aware TTL approach. Transactions on Networking, 28(3):1283--1296, 2020.

Digital Library

[66]

Twitter. Anonymized cache request traces from Twitter production. https://github.com/twitter/cache-trace. [Online; 2023].

[67]

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

[68]

U.S. Securities and Exchange Commission (SEC). Electronic data gathering, analysis, and retrieval system (EDGAR) log file dataset. https://www.sec.gov/dera/data/edgar-log-file-data-set.html. [Online].

[69]

James Ryans. Using the EDGAR log file data set. Available at SSRN 2913612, 2017.

[70]

Saguiitay. Cardinality estimation. https://github.com/microsoft/CardinalityEstimation/. [Online; 2023].

[71]

Pin Zhou, Vivek Pandey, Jagadeesan Sundaresan, Anand Raghuraman, Yuanyuan Zhou, and Sanjeev Kumar. Dynamic tracking of page miss ratio curve for memory management. In Proc. 11th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS'04), pages 177--188, 2004.

Digital Library

[72]

Rong Gu, Simian Li, Haipeng Dai, Hancheng Wang, Yili Luo, Bin Fan, Ran Ben Basat, Ke Wang, Zhenyu Song, Shouwei Chen, Beinan Wang, Yihua Huang, and Guihai Chen. Adaptive online cache capacity optimization via lightweight working set size estimation at scale. In Proc. USENIX Annual Technical Conference (ATC'23), pages 467--484, 2023.

[73]

Guido Urdaneta, Guillaume Pierre, and Maarten Van Steen. Wikipedia workload analysis for decentralized hosting. Computer Networks, 53(11):1830--1845, 2009.

Digital Library

[74]

David K Tam, Reza Azimi, Livio B Soares, and Michael Stumm. RapidMRC: Approximating L2 miss rate curves on commodity systems for online optimizations. In Proc. Intl. Conf. on Architectural Support for Program ming Languages & Operating Systems (ASPLOS'09), pages 121--132, 2009.

[75]

Trausti Saemundsson, Hjortur Bjornsson, Gregory Chockler, and Ymir Vigfusson. Dynamic performance profiling of cloud caches. In Proc. Symp. on Cloud Computing (SoCC'14), pages 1--14, 2014.

Digital Library

[76]

BP Welford. Note on a method for calculating corrected sums of squares and products. Technometrics, 4(3):419--420, 1962.

[77]

Yazhuo Zhang, Juncheng Yang, Yao Yue, Ymir Vigfusson, and KV Rashmi. Sieve is simpler than LRU: an efficient turn-key eviction algorithm for web caches. In Proc. 21st USENIX Symp. on Networked Systems Design and Implementation (NSDI'24), 2024.

[78]

Redis. Redis eviction. https://redis.io/docs/reference/eviction/. [Online; 2024].

[79]

Benjamin Berg, Daniel S Berger, Sara McAllister, Isaac Grosof, Sathya Gunasekar, Jimmy Lu, Michael Uhlar, Jim Carrig, Nathan Beckmann, Mor Harchol-Balter, et al. The CacheLib caching engine: Design and experiences at scale. In Proc. 14th Symp. on Operating Systems Design and Implementation (OSDI'20), pages 753--768, 2020.

[80]

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 Proc. 28th Symp. on Operating Systems Principles (SOSP'21), pages 243--262, 2021.

[81]

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

[82]

Twitter. Improving key expiration in Redis. https://blog.twitter.com/engineering/en_us/topics/infrastructure/2019/improving-key-expiration-in-redis. [Online; 2024].

[83]

Redis. Diving into Redis 6.0. https://redis.com/blog/diving-into-redis-6/. [Online; 2024].

[84]

Redis. Discussion by the maintainers of Redis on Twitter's article [82]. https://news.ycombinator.com/item?id=19662501. [Online; 2024].

[85]

Bryan T Bennett and Vincent J. Kruskal. LRU stack processing. IBM Journal of Research and Development, 19(4):353--357, 1975.

Digital Library

[86]

James Gordon Thompson. Efficient analysis of caching systems. PhD thesis, University of California, Berkeley, 1987.

Digital Library

[87]

George Almási, Călin Caşcaval, and David A Padua. Calculating stack distances efficiently. In Proc. Workshop on Memory System Performance, pages 37--43, 2002.

Digital Library

[88]

Pin Zhou, Vivek Pandey, Jagadeesan Sundaresan, Anand Raghuraman, Yuanyuan Zhou, and Sanjeev Kumar. Dynamic tracking of page miss ratio curve for memory management. In Proc. the 11th Intl. Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'04), page 177--188, 2004.

Digital Library

[89]

David Eklov and Erik Hagersten. Statstack: Efficient modeling of LRU caches. In Proc. Intl. Symp. on Performance Analysis of Systems & Software (ISPASS'10), pages 55--65. IEEE, 2010.

[90]

Xiameng Hu, Xiaolin Wang, Yechen Li, Lan Zhou, Yingwei Luo, Chen Ding, Song Jiang, and Zhenlin Wang. LAMA: Optimized locality-aware memory allocation for key-value cache. In Proc. USENIX Annual Technical Conf. (ATC-15), pages 57--69, 2015.

[91]

Ailing Yu, Yujuan Tan, Congcong Xu, Zhulin Ma, Duo Liu, and Xianzhang Chen. DFShards: Effective construction of MRCs online for non-stack algorithms. In Proc. the 18th ACM intl. Conf. on Computing Frontiers 2021 (CF'2021), page 63 - 72, 2021.

[92]

Rongshang Li, Yingtian Tang, Qiquan Shi, Hui Mao, Lei Chen, Jikun Jin, Peng Lu, and Zhuo Cheng. Accurate probabilistic miss ratio curve approximation for adaptive cache allocation in block storage systems. In Proc. the 2022 Design, Automation and Test in Europe Conf. and Exhibition (DATE'22), page 1197 - 1202, 2022.

[93]

Yuchen Wang, Junyao Yang, and Zhenlin Wang. Multi-tenant in-memory key-value cache partitioning using efficient random sampling-based LRU model. IEEE Transactions on Cloud Computing, 11(4):3601--3618, 2023.

[94]

Jun Xiao, Yaocheng Xiang, Xiaolin Wang, Yingwei Luo, Andy Pimentel, and Zhenlin Wang. FLORIA: A fast and featherlight approach for predicting cache performance. In Proc. 37th intl. Conf. on Supercomputing, pages 25--36, 2023.

Digital Library

[95]

Mark D Hill and Alan Jay Smith. Evaluating associativity in CPU caches. IEEE Trans on Computers, 38(12):1612--1630, 1989.

Digital Library

[96]

Moinuddin K Qureshi and Yale N Patt. Utility-based cache partitioning: A low-overhead, high-performance, runtime mechanism to partition shared caches. In Proc. 39th intl. Symp. on Microarchitecture (MICRO'06), pages 423--432, 2006.

Digital Library

[97]

Weiming Zhao and Zhenlin Wang. Dynamic memory balancing for virtual machines. In Proc. 2009 ACM SIGPLAN/SIGOPS Intl. Conf. on Virtual Execution Environments (VEE'09), page 21--30, 2009.

Digital Library

[98]

Ioan Stefanovici, Eno Thereska, Greg O'Shea, Bianca Schroeder, Hitesh Ballani, Thomas Karagiannis, Antony Rowstron, and Tom Talpey. Software-defined caching: Managing caches in multi-tenant data centers. In Proc. Symp. on Cloud Computing (SoCC'15), pages 174--181, 2015.

[99]

Ricardo Koller, Ali José Mashtizadeh, and Raju Rangaswami. Centaur: Host-side SSD caching for storage performance control. In Proc. Intl. Conf. on Autonomic Computing (ICAC'15), pages 51--60, 2015.

Digital Library

[100]

Asaf Cidon, Assaf Eisenman, Mohammad Alizadeh, and Sachin Katti. Cliffhanger: Scaling performance cliffs in web memory caches. In Proc. 13th Symp. on Networked Systems Design and Implementation (NSDI'16), pages 379--392, 2016.

[101]

Daniel Byrne, Nilufer Onder, and Zhenlin Wang. mPart: Miss-ratio curve guided partitioning in key-value stores. In Proc. Intl. Symp. on Memory Management (ISMM'18), pages 84--95, 2018.

Digital Library

[102]

Song Liu, Chen Zhang, Shiqiang Nie, Keqiang Duan, and Weiguo Wu. PC-Allocation: Performance cliff-aware two-level cache resource allocation scheme for storage system. Applied Sciences, 13(6):3556, 2023.

[103]

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

Digital Library

[104]

Donald R. Slutz and Irving L. Traiger. A note on the calculation of average working set size. Communications of the ACM, 17(10):563--565, 1974.

Digital Library

[105]

M.C. Easton and B.T. Bennett. Transient-free working-set statistics. Communications of the ACM, 20(2):93 - 99, 1977.

Digital Library

[106]

P.J. Denning. Working sets past and present. IEEE Transactions on Software Engineering, SE-6(1):64--84, 1980.

Digital Library

[107]

Ashutosh S Dhodapkar and James E Smith. Managing multi-configuration hardware via dynamic working set analysis. In Proc. 29th Intl. Symp. on Computer Architecture (ISCA'02), pages 233--244, 2002.

[108]

Sameh Elnikety, Steven Dropsho, and Willy Zwaenepoel. Tashkent+: memory-aware load balancing and update filtering in replicated databases. In Proc. 2nd ACM SIGOPS/EuroSys European Conf. on Computer Systems 2007 (EuroSys'07), page 399--412, 2007.

Digital Library

[109]

Changwoo Min, Inhyuk Kim, Taehyoung Kim, and Young I.K. Eom. Hardware assisted dynamic memory balancing in virtual machines. IEICE Electronics Express, 8(10):748 - 754, 2011.

[110]

Xiaoya Xiang, Bin Bao, Chen Ding, and Yaoqing Gao. Linear-time modeling of program working set in shared cache. In Proc. 2011 Intl. Conf. on Parallel Architectures and Compilation Techniques (PACT'11), pages 350--360, 2011.

Digital Library

[111]

Lei Cui, Jianxin Li, Tianyu Wo, Bo Li, Renyu Yang, Yingjie Cao, and Jinpeng Huai. HotRestore: A fast restore system for virtual machine cluster. In Proc. 28th Large Installation System Administration Conf. (LISA'2014), pages 10--25, 2014.

[112]

Aparna Mandke Dani, Bharadwaj Amrutur, and Y.N. Srikant. Toward a scalable working set size estimation method and its application for chip multiprocessors. IEEE Trans. on Computers, 63(6):1567 - 1579, 2014.

Digital Library

[113]

Kishore Kumar Pusukuri. Working set model for multithreaded programs. In Proc. 2014 Conf. on Timely Results in Operating Systems (TRIOS'2014), 2014.

Digital Library

[114]

Jui-hao Chiang, Tzi-Cker Chiueh, and Han-Lin Li. Memory reclamation and compression using accurate working set size estimation. In Proc. 2015 IEEE 8th Intl. Conf. on Cloud Computing (CLOUD'15), pages 187--194, 2015.

[115]

Dulcardo Arteaga, Jorge Cabrera, Jing Xu, Swaminathan Sundararaman, and Ming Zhao. CloudCache: On-demand flash cache management for cloud computing. In Proc. 14th USENIX Conf. on File and Storage Technologies (FAST'16), pages 355--369, 2016.

[116]

Peter J Denning. Working set analytics. Computing Surveys, 53(6):1--36, 2021.

Digital Library

[117]

Weiming Zhao, Xinxin Jin, Zhenlin Wang, Xiaolin Wang, Yingwei Luo, and Xiaoming Li. Low cost working set size tracking. In Proc. 2011 USENIX Annual Technical Conf. (ATC'11), 2011.

Digital Library

[118]

Yousra Chabchoub and Georges Heébrail. Sliding hyperloglog: Estimating cardinality in a data stream over a sliding window. In Proc. Intl. Conf. on Data Mining, pages 1297--1303, 2010.

[119]

Nirav Atre, Justine Sherry, WeinaWang, and Daniel S Berger. Caching with delayed hits. In Proc. 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, 2020.

Digital Library

Cited By

Han HLee SSon Y(2024)ScaleOPT: A Scalable Optimal Page Replacement Policy SimulatorProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004268:3(1-25)Online publication date: 13-Dec-2024
https://dl.acm.org/doi/10.1145/3700426
Mao ZIyer RShenker SStoica I(2024)Revisiting Cache Freshness for Emerging Real-Time ApplicationsProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696858(335-342)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1145/3696348.3696858

Index Terms

TTLs Matter: Efficient Cache Sizing with TTL-Aware Miss Ratio Curves and Working Set Sizes
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation support systems
      1. Simulation tools
2. General and reference
  1. Cross-computing tools and techniques
    1. Performance

Recommendations

mPart: miss-ratio curve guided partitioning in key-value stores
ISMM 2018: Proceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management

Web applications employ key-value stores to cache the data that is most commonly accessed. The cache improves an web application's performance by serving its requests from memory, avoiding fetching them from the backend database. Since the memory space ...
mPart: miss-ratio curve guided partitioning in key-value stores
ISMM '18

Web applications employ key-value stores to cache the data that is most commonly accessed. The cache improves an web application's performance by serving its requests from memory, avoiding fetching them from the backend database. Since the memory space ...
Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer Architecture

On-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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '24: Proceedings of the Nineteenth European Conference on Computer Systems

April 2024

1245 pages

ISBN:9798400704376

DOI:10.1145/3627703

Copyright © 2024 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 the author(s) 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

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 April 2024

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

University of Toronto

Conference

EuroSys '24

Sponsor:

SIGOPS

EuroSys '24: Nineteenth European Conference on Computer Systems

April 22 - 25, 2024

Athens, Greece

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
449
Total Downloads

Downloads (Last 12 months)449
Downloads (Last 6 weeks)28

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han HLee SSon Y(2024)ScaleOPT: A Scalable Optimal Page Replacement Policy SimulatorProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/37004268:3(1-25)Online publication date: 13-Dec-2024
https://dl.acm.org/doi/10.1145/3700426
Mao ZIyer RShenker SStoica I(2024)Revisiting Cache Freshness for Emerging Real-Time ApplicationsProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696858(335-342)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1145/3696348.3696858

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