TinyLFU: A Highly Efficient Cache Admission Policy
Authors:
- Gil EinzigerGEGil Einziger
- Roy FriedmanRFRoy Friedman
- 1 February 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10666192,p. 146-153
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. Rather than deciding on which object to evict, TinyLFU decides, based on the recent access history, whether it is worth admitting an accessed object 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 recently accessed objects. TinyLFU is extremely compact and lightweight as it builds upon Bloom filter theory. The paper shows an analysis of the properties of TinyLFU including simulations of both synthetic workloads as well as YouTube and Wikipedia traces.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Probabilistic in-network caching for information-centric networks2012
- Wikipedia workload analysis for decentralized hostingComputer Networks, 2009
- Identifying High Cardinality Internet Hosts2009
- The eternal sunshine of the sketch data structureComputer Networks, 2008
- Statistics and Social Network of YouTube Videos2008
- Accurate and Efficient Traffic Monitoring Using Adaptive Non-Linear Sampling Method2008
- Building a better NetFlowACM SIGCOMM Computer Communication Review, 2004
- Replacement Policies for a Distributed Object Caching Service2002
- Adaptive random sampling for load change detectionACM SIGMETRICS Performance Evaluation Review, 2002
- The LRU-K page replacement algorithm for database disk bufferingACM SIGMOD Record, 1993