TinyLFU: A Highly Efficient Cache Admission Policy
Preprint
Abstract
This paper proposes to use a frequency based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate. Realizing this concept is enabled through a novel approximate LFU structure called TinyLFU, which maintains an approximate representation of the access frequency of a large sample of recently accessed items. TinyLFU is very compact and light-weight as it builds upon Bloom filter theory. We study the properties of TinyLFU through simulations of both synthetic workloads as well as multiple real traces from several sources. These simulations demonstrate the performance boost obtained by enhancing various replacement policies with the TinyLFU eviction policy. Also, a new combined replacement and eviction policy scheme nicknamed W-TinyLFU is presented. W-TinyLFU is demonstrated to obtain equal or better hit-ratios than other state of the art replacement policies on these traces. It is the only scheme to obtain such good results on all traces.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Estimators also need shared values to grow together2012
- On-demand time-decaying bloom filters for telemarketer detectionACM SIGCOMM Computer Communication Review, 2011
- Wikipedia workload analysis for decentralized hostingComputer Networks, 2009
- The eternal sunshine of the sketch data structureComputer Networks, 2008
- An Improved Data Stream Summary: The Count-Min Sketch and Its Applications2004
- Summary cache: a scalable wide-area Web cache sharing protocolIEEE/ACM Transactions on Networking, 2000
- Performance evaluation of Web proxy cache replacement policiesPerformance Evaluation, 2000
- Web caching and Zipf-like distributions: evidence and implications1999
- Caching Web objects using Zipf's law1998
- The LRU-K page replacement algorithm for database disk bufferingACM SIGMOD Record, 1993