{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:31:48Z","timestamp":1755999108315,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T00:00:00Z","timestamp":1560902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,6,19]]},"abstract":"<jats:p>The Least Recently Used (LRU) caching and its variants are used in large-scale data systems in order to provide high-speed data access for a wide class of applications. Nonetheless, a fundamental question still remains open: in order to minimize miss probabilities, how should the cache space be organized to serve multiple data flows? Commonly used strategies can be categorized into two designs: pooled LRU (PLRU) caching and separated LRU (SLRU) caching. However, neither of these designs can satisfactorily solve this problem. PLRU caching is easy to implement and self-adaptive, but does not often achieve optimal or even efficient performance because its set of feasible solutions are limited. SLRU caching can be statically configured to achieve optimal performance for stationary workload, which nevertheless could suffer in a dynamically changing environment and from a cold-start problem. To this end, we propose a new insertion based pooled LRU paradigm, termed I-PLRU, where data flows can be inserted at different positions of a pooled cache. This new design can achieve the optimal performance of the static SLRU, and retains the adaptability of PLRU in virtue of resource sharing. Theoretically, we characterize the asymptotic miss probabilities of I-PLRU, and prove that, for any given SLRU design, there always exists an I-PLRU configuration that achieves the same asymptotic miss probability, and vice versa. We next design a policy to minimize the miss probabilities. However, the miss probability minimization problem turns out to be non-convex under the I-PLRU paradigm. Notably, we utilize an equivalence mapping between I-PLRU and SLRU to efficiently find the optimal I-PLRU configuration. We prove that I-PLRU outperforms PLRU and achieves the same miss probability as the optimal SLRU for stationary workload. Engineeringly, the flexibility of I-PLRU avoids separating the memory space, supports dynamic and refined configurations, and alleviates the cold-start problem, potentially yielding better performance than both SLRU and PLRU.<\/jats:p>","DOI":"10.1145\/3341617.3326154","type":"journal-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:18:56Z","timestamp":1561033136000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A New Flexible Multi-flow LRU Cache Management Paradigm for Minimizing Misses"],"prefix":"10.1145","volume":"3","author":[{"given":"Guocong","family":"Quan","sequence":"first","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Tan","sequence":"additional","affiliation":[{"name":"Alibaba Group &amp; The Ohio State University, Sunnyvale, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atilla","family":"Eryilmaz","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ness","family":"Shroff","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254766"},{"key":"e_1_2_1_2_1","volume-title":"Memory management: Challenges and techniques for traditional memory allocation algorithms in relation with today's real time needs. Advances in Computer Science: an International Journal","author":"Awais Muhammad Abdullah","year":"2016","unstructured":"Muhammad Abdullah Awais. 2016. Memory management: Challenges and techniques for traditional memory allocation algorithms in relation with today's real time needs. Advances in Computer Science: an International Journal, Vol. 5, 2 (2016), 22--27."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1096673.1096699"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3307441.3307475"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Daniel S Berger Ramesh K Sitaraman and Mor Harchol-Balter. 2017. AdaptSize: Orchestrating the hot object memory cache in a content delivery network.. In NSDI. 483--498.","DOI":"10.5555\/3154630.3154670"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2015.84"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2984356.2984371"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359634"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149371"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80014-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745850"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2017.09.002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0761"},{"key":"e_1_2_1_15_1","first-page":"430","article-title":"Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities","volume":"2","author":"Jelenkovi\u0107 Predrag R.","year":"1999","unstructured":"Predrag R. Jelenkovi\u0107. 1999. Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities. The Annals of Applied Probability 2 (1999), 430--464.","journal-title":"The Annals of Applied Probability"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791135.2791141"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8485860"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1247360.1247395"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/511399.511340"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/286860.286864"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741956"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1090694.1090708"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170081"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8485891"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737363"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/301453.301486"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3179408"},{"key":"e_1_2_1_28_1","volume-title":"Modern operating systems","author":"Tanenbaum Andrew S.","unstructured":"Andrew S. Tanenbaum. 2001. Modern operating systems 2rd ed.). Prentice Hall Press, Upper Saddle River, NJ, USA.","edition":"2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645647.664690"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908557"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326154","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341617.3326154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:29Z","timestamp":1750200089000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341617.3326154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,19]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,19]]}},"alternative-id":["10.1145\/3341617.3326154"],"URL":"https:\/\/doi.org\/10.1145\/3341617.3326154","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2019,6,19]]},"assertion":[{"value":"2019-06-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}