Unifying Caching Objectives with Learning Relaxed Belady

Abstract

Caching is crucial to the end-to-end performance of distributed systems. By temporarily storing content that is commonly requested so that it can be served more quickly, this technique improves request latency and reduces load on backend servers. There are three objectives in caching: reducing object miss ratio, byte miss ratio, and miss ratio for unit-sized objects, with different objectives being important to different systems. Learning Relaxed Belady (LRB) is an existing machine learning (ML) caching algorithm that achieves substantially better byte miss ratios than other state-of-the-art approaches.

In this thesis, we adapt LRB for the other two objectives: object miss ratio and caching for unit-sized objects. Object miss ratio is a crucial metric to a wide range of caches, including CDN in-memory caches and key-value caches for large storage systems. Decreasing object miss ratio translates directly into improved application performance. We apply a novel technique, byte sampling, to LRB that allows it to outperform other methods for object miss ratio. LRB also performs better than other policies for unit-sized traces, demonstrating the broad applicability of this algorithm. We evaluate LRB on 5 production traces and demonstrate its robustness in performance on varying workloads. LRB, enhanced with byte sampling, is the only algorithm we know of that can consistently outperform other state-of-the-art policies for all three caching objectives. We unify these objectives with this algorithm and simplify the method through which further advancements can be made.