Optimal mixing of cache eviction policies reduces wasted memory switches
No-Regret Mixing of LRU and LFU with Optimal Switching Cost
Machine LearningNetworking and Internet Architecture
Summary
Caching is a way computers remember things quickly by keeping popular data close, but deciding what to forget can be tricky. Two common ways to do this are to forget the least recently used things or the least frequently used things, but each works better in different situations. The authors found that a recent method combining these two approaches sometimes performs badly in theory. They created a new method that mixes these two in a smart way, ensuring good overall performance while reducing unnecessary switches between strategies. This means the computer can keep more important data in memory efficiently without too much cost from changing how it decides.
cachingLRU (Least Recently Used)LFU (Least Frequently Used)eviction policiesonline learningregretHedge algorithmswitching costexperts problemadaptive algorithms
Authors
Younes Ben Mazziane, Xinying Zou
Abstract
Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge's selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.