Abstract
Cache is used to reduce performance differences between storage layers. It is widely used in databases, operating systems, network systems, and applications. Loop reference pattern where blocks are referenced repeatedly with regular intervals is a common phenomenon during data referencing. Good management of looping reference blocks can effectively help improve the performance of cache management. In this work, we propose a loop assistant cache replacement (LOACR) policy. We divide the cache into two parts, one part is used to store looping reference data, and the rest of the cache uses an ML-based algorithm to manage. We regularly identify the looping reference pattern and the specific information of the loop at the end of every window. At the same time, we will place the looping reference data that may appear in the next window into the cache in advance to improve the hit rate of the cache. The remaining space in the cache drives the LRU and LFU specialists to cache replacement through a parameter-free machine learning approach. Finally, we evaluated LOACR across a broad range of experiments using multiple sets of cache configurations across multiple data sets.
This work is supported by the Key R &D Program of Shandong Province under Grant 2021CXGC010104.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Association, S.N.I., et al.: The snia’s i/o traces, tools, and analysis (iotta) repository (2021)
Choi, H., Park, S.: Learning future reference patterns for efficient cache replacement decisions. IEEE Access 10, 25922–25934 (2022)
Choi, J., Noh, S.H., Sang, L.M., Cho, Y.: An adaptive block management scheme using on-line detection of block reference patterns. In: International Workshop on Multi-media Database Management Systems (1998)
Choi, J., Noh, S.H., Min, S.L., Cho, Y.: An implementation study of a detection-based adaptive block replacement scheme. In: USENIX Annual Technical Conference, General Track, pp. 239–252 (1999)
Cidon, A., Eisenman, A., Katti, S., Attar, M.A.: Cliffhanger: Scaling performance cliffs in web memory caches. In: Networked Systems Design and Implementation (2016)
Huang, S., Wei, Q., Feng, D., Chen, J., Chen, C.: Improving flash-based disk cache with lazy adaptive replacement. ACM Trans. Storage (TOS) 12(2), 1–24 (2016)
Kim, J.M., et al.: A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references. In: Proceedings of the 4th Conference on Symposium on Operating System Design & Implementation-Volume 4 (2000)
Li, C.: Dlirs: Improving low inter-reference recency set cache replacement policy with dynamics. In: Proceedings of the 11th ACM International Systems and Storage Conference, pp. 59–64 (2018)
Li, P., Gu, Y.: Learning forward reuse distance (2020)
Littlestone, N., Warmuth, M.K.: The weighted majority algorithm. Inf. Comput. 108(2), 212–261 (1994)
Loomes, G., Sugden, R.: Regret theory: an alternative theory of rational choice under uncertainty. Econ. J. 92(368), 805–824 (1982)
Manes, B.: Caffeine: A high performance caching library for java 8. https://github.com/ben-manes/caffeine (2016)
Megiddo, N.: Arc : A self-tuning, low overhead replacement cache. In: USENIX File and Storaqe Technologies Conference (FAST’03), San Francisco, CA (2003)
Robinson, J.T., Devarakonda, M.V.: Data cache management using frequency-based replacement. In: Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pp. 134–142 (1990)
Rodriguez, L.V., et al.: Learning cache replacement with cacheus. In: File and Storage Technologies (2021)
Santana, R., Lyons, S., Koller, R., Rangaswami, R., Liu, J.: To arc or not to arc. In: Proceedings of the 7th USENIX Conference on Hot Topics in Storage and File Systems, pp. 14–14 (2015)
Shi, Z., Huang, X., Jain, A., Lin, C.: Applying deep learning to the cache replacement problem. In: Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pp. 413–425 (2019)
Smith, W.L.: Regenerative stochastic processes. Proc. Royal Society of London. Series A. Math. Phys. Sci. 232(1188), 6–31 (1955)
Song, J., Zhang, X.: Lirs: An efficient low inter-reference recency set replacement to improve buffer cache performance. In: Proceedings of the International Conference on Measurements and Modeling of Computer Systems, SIGMETRICS 2002, June 15–19, 2002, Marina Del Rey, California, USA (2002)
Vietri, G., et al.: Driving cache replacement with ml-based lecar. In: USENIX Annual Technical Conference (2018)
Waldspurger, C.A., Saemundsson, T., Ahmad, I., Park, N.: Cache modeling and optimization using miniature simulations. In: USENIX Annual Technical Conference, pp. 487–498 (2017)
Wulf, W.A., Mckee, S.A.: Hitting the memory wall: Implications of the obvious. Acm Sigarch Computer Architecture News (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Li, T. et al. (2023). LOACR: A Cache Replacement Method Based on Loop Assist. In: Meng, X., et al. Spatial Data and Intelligence. SpatialDI 2023. Lecture Notes in Computer Science, vol 13887. Springer, Cham. https://doi.org/10.1007/978-3-031-32910-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-031-32910-4_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-32909-8
Online ISBN: 978-3-031-32910-4
eBook Packages: Computer ScienceComputer Science (R0)