{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T14:10:27Z","timestamp":1762956627616,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T00:00:00Z","timestamp":1622160000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018YFB1003505"],"award-info":[{"award-number":["2018YFB1003505"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["62032001, 61672053, U1611461, and 62032008"],"award-info":[{"award-number":["62032001, 61672053, U1611461, and 62032008"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["CSR1618384"],"award-info":[{"award-number":["CSR1618384"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2021,5,30]]},"abstract":"<jats:p>Due to large data volume and low latency requirements of modern web services, the use of an in-memory key-value (KV) cache often becomes an inevitable choice (e.g., Redis and Memcached). The in-memory cache holds hot data, reduces request latency, and alleviates the load on background databases. Inheriting from the traditional hardware cache design, many existing KV cache systems still use recency-based cache replacement algorithms, e.g., least recently used or its approximations. However, the diversity of miss penalty distinguishes a KV cache from a hardware cache. Inadequate consideration of penalty can substantially compromise space utilization and request service time. KV accesses also demonstrate locality, which needs to be coordinated with miss penalty to guide cache management.<\/jats:p>\n          <jats:p>\n            In this article, we first discuss how to enhance the existing cache model, the Average Eviction Time model, so that it can adapt to modeling a KV cache. After that, we apply the model to Redis and propose pRedis,\n            <jats:italic>Penalty- and Locality-aware Memory Allocation<\/jats:italic>\n            in Redis, which synthesizes data locality and miss penalty, in a quantitative manner, to guide memory allocation and replacement in Redis. At the same time, we also explore the diurnal behavior of a KV store and exploit long-term reuse. We replace the original passive eviction mechanism with an automatic dump\/load mechanism, to smooth the transition between access peaks and valleys. Our evaluation shows that pRedis effectively reduces the average and tail access latency with minimal time and space overhead. For both real-world and synthetic workloads, our approach delivers an average of 14.0%\u223c52.3% latency reduction over a state-of-the-art penalty-aware cache management scheme, Hyperbolic Caching (HC), and shows more quantitative predictability of performance. Moreover, we can obtain even lower average latency (1.1%\u223c5.5%) when dynamically switching policies between pRedis and HC.\n          <\/jats:p>","DOI":"10.1145\/3447573","type":"journal-article","created":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T17:51:05Z","timestamp":1622224265000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Penalty- and Locality-aware Memory Allocation in Redis Using Enhanced AET"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4995-8407","authenticated-orcid":false,"given":"Cheng","family":"Pan","sequence":"first","affiliation":[{"name":"Department of Computer Science, Peking University, China and Peng Cheng Laboratory, Shenzhen, Guangdong, China"}]},{"given":"Xiaolin","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Peking University, China and Peng Cheng Laboratory, Shenzhen, Guangdong, China"}]},{"given":"Yingwei","family":"Luo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Peking University, China and Peng Cheng Laboratory, Shenzhen, Guangdong, China"}]},{"given":"Zhenlin","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Michigan Technological University, Houghton, MI, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,5,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved on","author":"From","year":"2020","unstructured":"From web. Approximated LRU. Retrieved on 15 March , 2020 from https:\/\/redis.io\/topics\/lru-cache. From web. Approximated LRU. Retrieved on 15 March, 2020from https:\/\/redis.io\/topics\/lru-cache."},{"key":"e_1_2_1_2_1","volume-title":"IEEE Standard for Floating-Point Arithmetic","author":"From","year":"2020","unstructured":"From web. IEEE Standard for Floating-Point Arithmetic (IEEE 754). Retrieved on 15 March , 2020 from https:\/\/en.wikipedia.org\/wiki\/IEEE_754. From web. IEEE Standard for Floating-Point Arithmetic (IEEE 754). Retrieved on 15 March, 2020 from https:\/\/en.wikipedia.org\/wiki\/IEEE_754."},{"key":"e_1_2_1_3_1","volume-title":"Memcached Memory Management Blog. Retrieved on","author":"From","year":"2020","unstructured":"From web. Memcached Memory Management Blog. Retrieved on 15 March , 2020 from https:\/\/www.loginradius.com\/engineering\/memcach-memory-management. From web. Memcached Memory Management Blog. Retrieved on 15 March, 2020 from https:\/\/www.loginradius.com\/engineering\/memcach-memory-management."},{"key":"e_1_2_1_4_1","volume-title":"Retrieved on","author":"Memcached Website From","year":"2020","unstructured":"From web. Memcached Website . Retrieved on 15 March , 2020 from http:\/\/memcached.org. From web. Memcached Website. Retrieved on 15 March, 2020 from http:\/\/memcached.org."},{"key":"e_1_2_1_5_1","volume-title":"Retrieved on","author":"From","year":"2020","unstructured":"From web. Memtier_benchmark. Retrieved on 15 March , 2020 from https:\/\/github.com\/GarantiaData\/memtier_benchmark. From web. Memtier_benchmark. Retrieved on 15 March, 2020 from https:\/\/github.com\/GarantiaData\/memtier_benchmark."},{"key":"e_1_2_1_6_1","volume-title":"MSR Cambridge Traces. Retrieved on","author":"From","year":"2020","unstructured":"From web. MSR Cambridge Traces. Retrieved on 15 March , 2020 from http:\/\/iotta.snia.org\/traces\/388. From web. MSR Cambridge Traces. Retrieved on 15 March, 2020 from http:\/\/iotta.snia.org\/traces\/388."},{"key":"e_1_2_1_7_1","volume-title":"Retrieved on","author":"MurmurHash From","year":"2020","unstructured":"From web. MurmurHash . Retrieved on 15 March , 2020 from https:\/\/en.wikipedia.org\/wiki\/Murmur-Hash. From web. MurmurHash. Retrieved on 15 March, 2020 from https:\/\/en.wikipedia.org\/wiki\/Murmur-Hash."},{"key":"e_1_2_1_8_1","volume-title":"Retrieved on","author":"Website From","year":"2020","unstructured":"From web. MySQL Website . Retrieved on 15 March , 2020 from https:\/\/www.mysql.com. From web. MySQL Website. Retrieved on 15 March, 2020 from https:\/\/www.mysql.com."},{"key":"e_1_2_1_9_1","volume-title":"Retrieved on","author":"Lslap From","year":"2020","unstructured":"From web. MySQ Lslap . Retrieved on 15 March , 2020 from https:\/\/tosbourn.com\/mysqlslap-a-quickstart-guide\/. From web. MySQLslap. Retrieved on 15 March, 2020 from https:\/\/tosbourn.com\/mysqlslap-a-quickstart-guide\/."},{"key":"e_1_2_1_10_1","volume-title":"Retrieved on","author":"Website From","year":"2020","unstructured":"From web. PostgreSQL Website . Retrieved on 15 March , 2020 from https:\/\/www.postgresql.org\/. From web. PostgreSQL Website. Retrieved on 15 March, 2020 from https:\/\/www.postgresql.org\/."},{"key":"e_1_2_1_11_1","volume-title":"Redis as an LRU cache. Retrieved on","author":"From","year":"2020","unstructured":"From web. Redis as an LRU cache. Retrieved on 15 March , 2020 from http:\/\/oldblog.antirez.com\/post\/redis-as-LRU-cache.html. From web. Redis as an LRU cache. Retrieved on 15 March, 2020 from http:\/\/oldblog.antirez.com\/post\/redis-as-LRU-cache.html."},{"key":"e_1_2_1_12_1","volume-title":"Retrieved on","author":"Redis Website From","year":"2020","unstructured":"From web. Redis Website . Retrieved on 15 March , 2020 from https:\/\/redis.io. From web. Redis Website. Retrieved on 15 March, 2020 from https:\/\/redis.io."},{"key":"e_1_2_1_13_1","volume-title":"Retrieved on","author":"Cloud Serving From","year":"2020","unstructured":"From web. Yahoo! Cloud Serving Benchmark (YCSB). Retrieved on 15 March , 2020 from https:\/\/github.com\/brianfrankcooper\/YCSB. From web. Yahoo! Cloud Serving Benchmark (YCSB). Retrieved on 15 March, 2020 from https:\/\/github.com\/brianfrankcooper\/YCSB."},{"key":"e_1_2_1_14_1","volume-title":"Retrieved on","author":"Zipfian's Law From","year":"2020","unstructured":"From web. Zipfian's Law . Retrieved on 15 March , 2020 from https:\/\/en.wikipedia.org\/wiki\/Zipf%27s_law. From web. Zipfian's Law. Retrieved on 15 March, 2020 from https:\/\/en.wikipedia.org\/wiki\/Zipf%27s_law."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1224252.1224501"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254766"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3387514.3405883"},{"volume-title":"Proceedings of the IEEE 21st International Symposium on High Performance Computer Architecture (HPCA). 64\u201375","author":"Beckmann N.","key":"e_1_2_1_18_1","unstructured":"N. Beckmann and D. Sanchez . 2015. Talus: A simple way to remove cliffs in cache performance . In Proceedings of the IEEE 21st International Symposium on High Performance Computer Architecture (HPCA). 64\u201375 . N. Beckmann and D. Sanchez. 2015. Talus: A simple way to remove cliffs in cache performance. In Proceedings of the IEEE 21st International Symposium on High Performance Computer Architecture (HPCA). 64\u201375."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3154630.3154670"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3291168.3291183"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2527081"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154738"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2015.84"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299706.3210571"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1267279.1267297"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2005.32"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2827719.2827738"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2930611.2930636"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154722"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2964791.2901451"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2173351"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2813767.2813772"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2618920"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026959.3026992"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3185751"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/107972.107995"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741956"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.92.0078"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.117"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2015.62"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.17"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3265723.3265736"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.790804"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/377792.377797"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3143361.3143368"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154737"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/2750482.2750490"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807060.1807064"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2685048.2685075"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS). 190\u2013197","author":"Xie Z.","year":"2017","unstructured":"Z. Xie , W. Ding , H. Wang , Y. Xiao , and Z. Liu . 2017. D-Ary Cuckoo filter: A space efficient data structure for set membership lookup . In Proceedings of the IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS). 190\u2013197 . DOI:https:\/\/doi.org\/10.1109\/ICPADS. 2017 .00035 10.1109\/ICPADS.2017.00035 Z. Xie, W. Ding, H. Wang, Y. Xiao, and Z. Liu. 2017. D-Ary Cuckoo filter: A space efficient data structure for set membership lookup. In Proceedings of the IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS). 190\u2013197. DOI:https:\/\/doi.org\/10.1109\/ICPADS.2017.00035"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-015-0384-3"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201914)","author":"Yoon M. K.","year":"2014","unstructured":"M. K. Yoon , J. Son , and S. Shin . 2014. Bloom tree: A search tree based on Bloom filters for multiple-set membership testing . In Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201914) . 1429\u20131437. DOI:https:\/\/doi.org\/10.1109\/INFOCOM. 2014 .6848077 10.1109\/INFOCOM.2014.6848077 M. K. Yoon, J. Son, and S. Shin. 2014. Bloom tree: A search tree based on Bloom filters for multiple-set membership testing. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201914). 1429\u20131437. DOI:https:\/\/doi.org\/10.1109\/INFOCOM.2014.6848077"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519076"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1037949.1024415"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447573","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447573","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447573","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:37Z","timestamp":1750195717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447573"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,28]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,5,30]]}},"alternative-id":["10.1145\/3447573"],"URL":"https:\/\/doi.org\/10.1145\/3447573","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2021,5,28]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}