CMU-CS-16-120
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-16-120

Achieving High Cache Hit Ratios for CDN Memory Caches with Size-aware Admission

Daniel S. Berger, Ramesh K. Sitaraman, Mor Harchol-Balter

July 2016

CMU-CS-16-120.pdf


Keywords: Web caching, cache admission control, content delivery networks, cache hit ratio, object hit ratio, cache tuning

Content delivery networks (CDNs) allow billions of users to expediently access content with higher reliability and performance from proximal "edge" caches deployed around the world. Each edge cache typically uses an in-memory Hot Object Cache (HOC) and a disk-based cache. While the HOC provides very fast response times, it is also very small. Maximizing the object hit ratio (OHR) of the HOCs is a major goal of a CDN.

Almost all prior work on caching policies has focused on improving the OHR via highly complex eviction policies. In contrast, this work investigates the superiority of size-aware admission policies, where the emphasis is on simplicity. Specifically, we propose two policies that either admit an object with some probability proportional to its size, or as a simple size threshold. Our results are based on two expansive production HOC traces from 2015 captured in the Akamai CDN. Unlike older traces, we find that object sizes in these traces span ten orders of magnitude, and that highly popular objects have an order of magnitude smaller size on average. Our simple policies efficiently exploit this property and achieve a 23-92% OHR improvement over state-of-the-art research-based and commercial caching systems.

The superior performance of our policies stems from a new statistical cache tuning method, which automatically adapts the parameters of our admission policies to the request traffic. We find that our statistical tuning method is significantly superior to state-of-the-art cache tuning methods such as hill climbing. Our method consistently achieves 80% of the OHR of offline parameter tuning. To demonstrate feasibility in a production setting, we show that our tuning method can be incorporated into a high-performance caching system with low processing and memory overheads and negligible impact on cache server throughput.

31 pages

*University of Kaiserslautern
*University of Massachusetts at Amherst / Akamai Technologies


Return to: SCS Technical Report Collection
School of Computer Science