Eviction Algorithms for Large Web Caches

Abstract

Caching is ubiquitous in the modern-day internet, and is a vital part of ensuring low-latency content access for end-users as well as preventing overload on servers. As storage media continues to get cheaper, caches can become larger, but little work has been done on algorithms for caches that are large enough to serve almost all requested objects. In this thesis, we identify the challenges that differentiate large caches from other domains of web caching. We present a trace-driven analysis of the performance of both classic and modern caching algorithms on large caches, showing that LRU- based algorithms, especially SLRU, perform especially well in this domain. Finally, we describe SLRU+, a simple variant of SLRU, which approximates or outperforms it on several of the traces that were studied.