Maximizing Page-Level Cache Hit Ratios in LargeWeb Services

This is the authors' abstract. We don't add key points for this paper.

Large web services typically serve pages consisting of many individual objects. To improve the response times of page-requests, these services store a small set of popular objects in a fast caching layer. A page-request is not considered complete until all of its objects have either been found in the cache or retrieved from a backend system. Hence, caching only speeds up a page request if all of its objects are found in the cache. We seek caching policies that maximize the page-level hit ratio-the fraction of requests that find all of their objects in the cache. This work analyzes page requests served by a Microsoft production system.We find that in practice there is potential for improving the page-level hit ratio over existing caching strategies, but that analytically maximizing the page-level hit ratio is NP-hard.