Hierarchical Sketch: An Efficient, Scalable and Latency-aware Content Caching Design for Content Delivery Networks

Content Delivery Networks (CDNs) are designed to reduce user-perceived waiting times and alleviate backbone bandwidth pressure. Since CDN cache servers have limited storage capacity, effective cache replacement policies are needed. However, existing CDN cache replacement policies mainly focus on improving content hit rates. As a result, some content with long origin fetch latency may not be cached, resulting in the long tail latency and degrading user experience. In this paper, we present Hierarchical Sketch, an efficient, scalable, and latency-aware cache replacement algorithm. Our approach leverages hierarchical slicing and voting mechanisms on a modified sketch to optimize content caching, reducing sorting complexity from O(log n) to O(1) with minimal loss of hit rate. Extensive simulations on synthetic and real-life industry CDN traces demonstrate that Hierarchical Sketch outperforms other algorithms in four different scenarios, with up to a 15% improvement.