The Role of Hysteresis in Caching Systems

• Published in: ACM transactions on modeling and performance evaluation of computing systems 2021-06, Vol.6 (1), p.1-38, Article 2
• Main Authors: Domingues, Guilherme, Mendonça, Gabriel, Silva, Edmundo De Souza E, Leão, Rosa M. M., Menasché, Daniel S., Rottenstreich, Ori, Dehghan, Mostafa, Towsley, Don
• Format: Article
• Language: English
• Subjects: Caching and paging algorithms; Design and analysis of algorithms; Network performance analysis; Network performance evaluation; Network performance modeling; Networks; Online algorithms; Theory of computation
• ISSN: 2376-3639; 2376-3647
• DOI: 10.1145/3450564

Caching is a fundamental element of networking systems since the early days of the Internet. By filtering requests toward custodians, caches reduce the bandwidth required by the latter and the delay experienced by clients. The requests that are not served by a cache, in turn, comprise its miss stream. We refer to the dependence of the cache state and miss stream on its history as hysteresis. Although hysteresis is at the core of caching systems, a dimension that has not been systematically studied in previous works relates to its impact on caching systems between misses, evictions, and insertions. In this article, we propose novel mechanisms and models to leverage hysteresis on cache evictions and insertions. The proposed solutions extend TTL-like mechanisms and rely on two knobs to tune the time between insertions and evictions given a target hit rate. We show the general benefits of hysteresis and the particular improvement of the two thresholds strategy in reducing download times, making the system more predictable and accounting for different costs associated with object retrieval.