2025/01/27 by Keerthana Gurushankar, Gurushankar, Keerthana, N. Singer +3
Computer Science · #Caching and Content Delivery #Advanced Data Storage Technologies #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2501.16535
In the classical caching problem, when a requested page is not present in the cache (i.e., a "miss"), it is assumed to travel from the backing store into the cache "before" the next request arrives. However, in many real-life applications, such as content delivery networks, this assumption is unrealistic. The "delayed-hits" model for caching, introduced by Atre, Sherry, Wang, and Berger, accounts for the latency between a missed cache request and the corresponding arrival from the backing store. This theoretical model has two parameters: the "delay" Z, representing the ratio between the retrieval delay and the inter-request delay in an application, and the "cache size" k, as in classical caching. Classical caching corresponds to Z=1, whereas larger values of Z model applications where retrieving missed requests is expensive. Despite the practical relevance of the delayed-hits model, its theoretical underpinnings are still poorly understood. We present the first tight theoretical guarantee for optimizing delayed-hits caching: The "Least Recently Used" algorithm, a natural, deterministic, online algorithm widely used in practice, is O(Zk)-competitive, meaning it incurs at most O(Zk) times more latency than the (offline) optimal schedule. Our result extends to any so-called "marking" algorithm.