Distributed Caching with Delayed Hits

Caches serve as the cornerstone of latency-sensitive systems, yet a recently discovered phenomenon, so-called delayed hits, challenges conventional optimal caching algorithms, rendering them incapable of guaranteeing minimal latency. To fill this gap, in this paper, we pioneer a generic algorithmic analysis for distributed caching under delayed hits, making three contributions. Firstly, we analytically establish tight competitive ratio lower bounds for both deterministic and randomized online caching algorithms. Secondly, we develop a novel online caching optimization framework by generalizing the Least Recently Used (LRU) policy to distributed caching with delayed hits, encompassing both deterministic and randomized paradigms.

Our key technicality is a timer-based data fetching scheme that leverages query history to limit aggregate data retrieval latency. We prove that our deterministic and randomized algorithms are both asymptotically optimal. Thirdly, we conduct extensive experiments on a real-world dataset to demonstrate the effectiveness and superiority of our algorithms over state-of-the-art solutions.