EAI International Conference on Performance Evaluation Methodologies and Tools, December 12-13, 2024 Milan, Italy. BEST PAPER AWARD!
Ziyue Qiu, Juncheng Yang, Mor Harchol-Balter
Carnagie Mellon University
Software caches are an intrinsic component of almost every computer system. Consequently, caching algorithms, particularly eviction policies, are the topic of many papers. Almost all these prior papers evaluate the caching algorithm based on its hit ratio, namely the fraction of requests that are found in the cache, as opposed to disk. The “hit ratio" is viewed as a proxy for traditional performance metrics like system throughput or request latency. Intuitively it makes sense that higher hit ratio should lead to higher throughput (and lower request latency), since more requests are found in the cache (low access time) as opposed to the disk (high access time).
This paper challenges this intuition. We show that increasing the hit ratio can actually hurt the throughput (and request latency) for many caching algorithms. Our investigation follows a three-pronged approach involving (i) queueing modeling and analysis, (ii) simulation to validate the accuracy of the queueing model, and (iii) implementation and mea- surement. We also show that the phenomenon of decreasing throughput at higher hit ratios is likely to be more pronounced in future systems, where the trend is towards faster disks and more cores per CPU.
KEYWORDS: caches, hit ratio, performance evaluation, scalability, modification analysis, queueing theory, LRU, eviction policies
FULL PAPER: pdf