Why increasing the hit ratio can hurt cache throughput

Abstract Software caches are an intrinsic component of almost every computer system. Consequently, caching algorithms, particularly eviction policies, are the topic of many papers. Most of 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 response time. Intuitively, it makes sense that a higher hit ratio should lead to higher throughput (and lower response time), since more requests are found in the cache (low access time) as opposed to the backend storage (high access time). This paper challenges this intuition. We show that increasing the hit ratio can actually hurt the throughput (and response time) for many caching algorithms. Specifically, higher hit ratios can lead to contention on the hit path, resulting in lower throughput. This is relevant in light of recent caching systems papers that have noticed that many LRU-based eviction policies can suffer from high contention and thus have aimed at developing solutions that reduce lock contention. Our paper provides a methodological framework to precisely determine where the contention is and how the hit ratio affects this. In particular, we are able to pinpoint the exact hit ratio beyond which throughput degrades, across a wide variety of eviction 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 measurement. 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 toward faster disks and more cores per CPU.