Home / Current Issue / Paper 1724912
A Simulation-Based Comparison of Cache Replacement Policies under Different Workloads and Cache Sizes
Subject area: Science,Engineering and Technology · Area of research: Computer Science
DOI: 10.64388/ire1724912
Abstract
The effectiveness of a cache replacement rule depends on the pattern of requests it receives and on how much space is available to retain previously requested items. This study used a deterministic simulator to compare least recently used (LRU), first-in-first-out (FIFO), and least frequently used (LFU) under three synthetic request patterns: uniform-random, Zipfian-skewed, and scan-heavy/mixed. For each workload, ten independently seeded traces of 50,000 requests were tested at capacities of 100, 250, 500, and 1,000 entries. The outcome was the proportion of requests served from the cache, reported as a mean and standard deviation across seeds. At capacity 500, LFU recorded the highest mean hit rate on the Zipfian workload (79.96% ± 0.22 percentage points), followed by LRU (75.88% ± 0.18) and FIFO (71.99% ± 0.19). On uniform-random requests, the three methods were almost indistinguishable, with hit rates of approximately 4.95% to 4.98%. In the specified scan-heavy/mixed workload, hit rates ranged from 4.12% to 4.56%. Larger caches generally improved hit rates, particularly under Zipfian access. These findings describe the behaviour of the stated simulator and input generators; they do not establish which policy will perform best in a production system. Tests using public application traces or a real storage workload are needed before making operational recommendations.
Keywords
cache replacement, FIFO, LFU, LRU, workload simulation
References
[1] Belady LA. A study of replacement algorithms for a virtual-storage computer. IBM Syst J. 1966;5(2):78–101. https://doi.org/10.1147/sj.52.0078
[2] Robinson JT, Devarakonda MV. Data cache management using frequency-based replacement. In: Proc. 1990 ACM SIGMETRICS Conf. Measurement and Modeling of Computer Systems; 1990. p. 134–142. https://doi.org/10.1145/98457.98523
[3] Ukibe JU, Atuorah N, Ike IF, Akawuku GI, Ezeumeanya CE, Amadiegwu EN. Storage techniques and the space-access time trade-off: A workload-aware review and decision framework. Int J Latest Technol Eng. 2026;15(9):2982–2997. https://doi.org/10.51583/IJLTEMAS.2026.150900150
[4] Cooper BF, Silberstein A, Tam E, Ramakrishnan R, Sears R. Benchmarking cloud serving systems with YCSB. In: Proc. 1st ACM Symp. Cloud Computing; 2010. p. 143–154. https://doi.org/10.1145/1807128.1807152
[5] Rodriguez LV, et al. Learning cache replacement with CACHEUS. In: Proc. 19th USENIX Conf. File and Storage Technologies (FAST 21); 2021. p. 341–354.
[6] Hosseini-Khayat S. Replacement algorithms for object caching. In: Proc. 1998 ACM Symp. Applied Computing; 1998. p. 90–97. https://doi.org/10.1145/330560.330653
[7] Jiang S, Zhang X. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. ACM SIGMETRICS Perform Eval Rev. 2002;30(1):31–42. https://doi.org/10.1145/511399.511340
[8] Megiddo N, Modha DS. ARC: A self-tuning, low overhead replacement cache. In: Proc. 2nd USENIX Conf. File and Storage Technologies (FAST ’03); 2003. p. 115–130.
[9] Park NE, Kim J, Jeong TS. Cache memory and replacement algorithm implementation and performance comparison. J Korea Soc Comput Inf. 2020;25(3):11–17. https://doi.org/10.9708/jksci.2020.25.03.011
[10] Zhou Y, Wang F, Shi Z, Feng D. An end-to-end automatic cache replacement policy using deep reinforcement learning. In: Proc. Int. Conf. Automated Planning and Scheduling; 2022. p. 537–545. https://doi.org/10.1609/icaps.v32i1.19840
[11] Zhou Y, Wang F, Shi Z, Feng D. An efficient deep reinforcement learning-based automatic cache replacement policy in cloud block storage systems. IEEE Trans Comput. 2024;73(1):164–177. https://doi.org/10.1109/TC.2023.3325625
How to cite this paper
@article{1724912,
author = {Joy Uchechukwu Ukibe, Chiagozie Excellence Ezeumeanya},
title = {A Simulation-Based Comparison of Cache Replacement Policies under Different Workloads and Cache Sizes},
journal = {Iconic Research And Engineering Journals},
year = {2026},
volume = {10},
number = {5},
pages = {2016-2025},
issn = {2456-8880},
url = {https://www.irejournals.com/formatedpaper/1724912.pdf},
abstract = {The effectiveness of a cache replacement rule depends on the pattern of requests it receives and on how much space is available to retain previously requested items. This study used a deterministic simulator to compare least recently used (LRU), first-in-first-out (FIFO), and least frequently used (LFU) under three synthetic request patterns: uniform-random, Zipfian-skewed, and scan-heavy/mixed. For each workload, ten independently seeded traces of 50,000 requests were tested at capacities of 100, 250, 500, and 1,000 entries. The outcome was the proportion of requests served from the cache, reported as a mean and standard deviation across seeds. At capacity 500, LFU recorded the highest mean hit rate on the Zipfian workload (79.96% ± 0.22 percentage points), followed by LRU (75.88% ± 0.18) and FIFO (71.99% ± 0.19). On uniform-random requests, the three methods were almost indistinguishable, with hit rates of approximately 4.95% to 4.98%. In the specified scan-heavy/mixed workload, hit rates ranged from 4.12% to 4.56%. Larger caches generally improved hit rates, particularly under Zipfian access. These findings describe the behaviour of the stated simulator and input generators; they do not establish which policy will perform best in a production system. Tests using public application traces or a real storage workload are needed before making operational recommendations.},
keywords = {cache replacement, FIFO, LFU, LRU, workload simulation},
month = {November},
doi = {https://doi.org/10.64388/ire1724912}
}