Source-linked AI summary
TinyLFU: A Highly Efficient Cache Admission Policy
Gil Einziger, Roy Friedman, Ben Manes
TL;DR
Caches need to exploit skewed, changing access patterns while keeping admission decisions and metadata efficient. The paper introduces TinyLFU, an approximate recent-frequency structure that decides whether a new item should replace a victim, and combines it with replacement policies including W-TinyLFU. Simulations on synthetic and real traces validate the approach, while the paper identifies sampling behavior and freshness-related mechanisms as scope boundaries.
Problem
Cache admission must handle changing access frequencies while keeping frequency metadata practical; exact frequency tracking can be prohibitively expensive.
Method
TinyLFU uses approximate frequency statistics over recent accesses to decide whether admitting a new item is preferable to retaining the eviction candidate.
Results
TinyLFU significantly improves caches with arbitrary eviction policies, and its performance is validated on synthetic and multiple real-world traces.
Takeaways & Limitations
Separating admission from eviction simplifies independent optimization, while W-TinyLFU extends the approach to a wider variety of workloads.
Takeaways & Limitations
Sampling-error reduction with larger samples applies to static distributions, whereas sample size for real workloads requires empirical trial and error.
Abstract
from arXiv · showhide
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.
1 Introduction
Caching exploits skewed and time-varying access patterns, but limited cache capacity makes efficient item selection difficult. The paper addresses these challenges with approximate frequency-based admission and evaluates its combination with replacement policies.
- Motivation: Skewed access distributions make caching effective because frequently accessed items are more likely to produce cache hits.Access patterns may also change over time, creating time locality.
- Motivation: Limited cache capacity forces designers to choose which items to retain and evict while controlling metadata time and space overhead.The cache metadata supports insertion and eviction decisions, but excessive overhead can outweigh caching benefits.
- Existing policies: LFU can maximize hit ratio under static distributions, but its implementations require large metadata and adapt poorly when popularity changes.LFU retains the n most frequently used items, while practical workloads may change radically over time.
- Existing policies: LRU adapts efficiently to temporal changes and bursts, but often needs larger caches than LFU to achieve the same hit ratio.LRU always admits the latest item and evicts the least recently accessed item when full.
- Paper contributions: TinyLFU augments caches with an approximate LFU admission policy that compares a new item with the replacement policy’s victim before admission.The paper also introduces W-TinyLFU for bursty workloads and studies enhanced policies against alternatives including LIRS and ARC.
2 Related Work
Prior cache policies trade off frequency, recency, adaptation, metadata cost, and object-specific factors. TinyLFU instead provides compact approximate statistics that can augment existing policies and improve LRU-based caching.
- Frequency-based policies: Perfect LFU is optimal for static distributions but has prohibitively high histogram cost and does not adapt to dynamic access distributions.In-Memory LFU reduces scope by tracking only cached items, while WLFU limits statistics to the last W requests.
- Recency-frequency hybrids: LRU-K, ARC, LIRS, SLRU, and 2Q combine recency and frequency through remembered accesses, multiple lists, reuse distance, segments, or queues.These policies differ in how they retain recent history and respond to repeated accesses or evictions.
- Object-aware policies: Web caching policies may additionally account for object size, retrieval cost, latency, or frequency when selecting victims.Examples include SIZE, LRU-SP, and GDSF.
- Admission-based alternatives: A Hot List gives popular items eviction priority but does not compare the cached item’s frequency with that of the newly accessed item.TinyLFU is described as an augmenting mechanism that uses approximate statistics over a large history with low metadata overhead.
- Approximate counting: Approximate counting methods offer fast updates and compact memory, but sampling, Counter Braids, compressed counters, and sketches have context-specific space, decoding, or accuracy trade-offs.TinyLFU uses short counters, while its description can also apply to CM-Sketch.
- Applications: Adding TinyLFU admission to an LRU eviction policy greatly boosts performance in caching services such as MemcacheD and cloud caches.The paper presents TinyLFU as compatible with the caching examples discussed.
3.1 TinyLFU Overview
TinyLFU separates admission from eviction: the cache policy selects a victim, while TinyLFU estimates whether admitting the new item should improve hit ratio. It maintains recent frequency statistics approximately to keep metadata practical.
- Architecture: TinyLFU decides whether replacing the cache victim with a newly accessed item is expected to increase the cache hit ratio.The eviction policy chooses the victim; TinyLFU supplies the admission decision.
- Architecture: TinyLFU approximates frequency statistics over a sizable recent history because storing exact statistics is prohibitively expensive.Its techniques combine approximate-counting adaptations with ideas tailored to caching.
- Design challenges: TinyLFU must maintain freshness by removing old events and substantially reduce memory overhead for practical cache management.These are identified as the two main design challenges.
- Architecture: Figure 1 depicts a general cache augmented with TinyLFU.The accompanying architecture assigns victim selection to the cache eviction policy and admission testing to TinyLFU.
3.2 Approximate Counting Overview
TinyLFU uses approximate counting structures to represent access frequencies compactly. Its Minimal Increment counting Bloom filter updates only minimum counters, while the design can also use CM-Sketch.
- Counting Bloom filters: A counting Bloom filter replaces each Bloom-filter bit with a counter that is incremented at hash-derived indexes.This supports approximate counting rather than simple membership representation.
- Minimal Increment CBF: A Minimal Increment CBF provides Add and Estimate operations using k hash-derived counters and the minimum counter value.Add increments only counters tied for the minimum, while Estimate returns the minimum read value.
- Minimal Increment CBF: Updating only minimum counters avoids unnecessary increments to large counters and empirically reduces error for high-frequency counts.The method does not support decrements.
- Alternative sketches: TinyLFU’s description is independent of choosing a Counting Bloom Filter or CM-Sketch, although CM-Sketch is described as faster but less accurate per space.The stated trade-off concerns approximate-counting accuracy and speed.
3.3 Freshness Mechanism
TinyLFU keeps its frequency sketch fresh with a reset operation that periodically halves all counters, using little extra space. The paper analyzes convergence and truncation error under constant access distributions while noting the reset’s infrequent scan cost.
- Reset method: The reset method halves every counter after W additions, using only a single Log(W)-bit counter as extra memory.It replaces the ordered list of m sketches, which requires reading multiple sketches and storing repeated counters.
- Reset method: The reset method yields a more accurate sketch for the same space by improving the accuracy of high-frequency items.The paper reports this property analytically and experimentally.
- Reset cost: The reset requires an infrequent scan over all counters, but its amortized complexity is constant.Hardware shift registers and software shift-and-mask operations can implement the division efficiently.
- Reset correctness: Under a constant distribution, TinyLFU eventually converges to the correct frequency regardless of its initial counter value.The expected histogram value is E(h_i) = f_i · W.
- Reset truncation error: Integer division removes the initial counter error after log2(σ) samples but introduces truncation error.The worst-case accumulated truncation error converges to at most one point below the accurate rate, with a recorded-rate effect of as much as 2 W immediately after reset.
3.4 Space Reduction
TinyLFU reduces frequency-histogram space by shrinking counters and allocating them selectively, while using a Doorkeeper Bloom filter for tail items. Its reset-based aging supports compact counters but introduces truncation error when the Doorkeeper is cleared.
- TinyLFU reduces space along two axes: smaller counters and fewer total counters.
- Counters can be capped at W/C because admission only needs to compare a replacement victim with the accessed item.
- Reset-based aging permits the counter optimization, whereas a sliding window can evict a frequently accessed item under alternating access patterns.
- When W/C = 8, counters require 3 bits, compared with 14 bits without the small-counters optimization for a 2K-cache, 16K-sample example.
- The Doorkeeper Bloom filter stores first-time and tail items with one-bit counters, while repeated items are counted in the main structure.
- Resetting clears the Doorkeeper and halves main counters, removing first-timer information but increasing truncation error by 1.
3.5 Test Case: TinyLFU vs. a Strawman
The test case compares TinyLFU with a sliding-window strawman using a 1K-item cache and a 9K-item frequency histogram under a Zipf 0.9 workload. TinyLFU uses fewer counters and less memory through its single sketch, small counters, and Doorkeeper.
- The experiment uses a 1K-item cache, a 9K-item frequency histogram, and a Zipf 0.9 access distribution.
- TinyLFU counts to 9 using 3-bit counters up to 8 plus the Doorkeeper’s one-bit contribution, while the strawman uses ten 10-bit sketches.
- TinyLFU stores approximately 10% fewer unique values than the strawman because it uses one large sketch instead of ten smaller sketches.
- Most items use one-bit Doorkeeper counters, while frequent items receive an additional 3-bit counter in the main structure.
3.6 Connecting TinyLFU to Caches
Connecting TinyLFU to caches requires coordinating its reset-based frequency aging with cache state. The LFU implementation was modified so cached-item frequencies reset alongside TinyLFU.
- TinyLFU can connect to LRU and Random caches as a black-box admission component.
- Integrating TinyLFU with LFU required synchronizing TinyLFU resets and resetting the frequencies of cached items.
4 The W-TinyLFU Optimization
W-TinyLFU combines a recency-oriented window with a TinyLFU-admission main cache to handle bursty workloads that TinyLFU alone can miss. In Caffeine, this design uses a small window and a larger main cache.
- Sparse bursts can cause TinyLFU to evict new-burst items before they build enough frequency, producing repeated misses.
- W-TinyLFU uses an LRU window without admission and an SLRU main cache with TinyLFU admission.
- The main cache statically allocates 80% to hot A2 items and selects victims from the 20% non-hot A1 region.
- Caffeine 2.0 allocates 1% of the cache to the window and 99% to the main cache.
- W-TinyLFU is intended to retain TinyLFU behavior on LFU workloads while exploiting LRU-friendly bursts, with added complexity justified for broader workload coverage.
- W-TinyLFU’s Caffeine integration has 8 bytes of overhead per cache entry, lower than ARC and LIRS.
5 Experimental Results
Experiments show that TinyLFU admission broadly improves cache performance across static, dynamic, and real-world workloads, while W-TinyLFU remains competitive with state-of-the-art policies. Benefits depend on workload dynamics and window sizing, with notable limitations on bursty or gradually changing traces.
- Constant skewed distributions: TinyLFU makes LRU, Random, and LFU perform similarly under constant skewed distributions, leaving only a marginal benefit for LFU eviction.The evaluation reports that TinyLFU-enhanced caches converge under static skewed workloads, where hit-ratio is theoretically bounded.
- Dynamic workloads: TinyLFU remains effective on dynamic YouTube workloads, but victim selection matters more than under static distributions.The benefit is greater when popularity distributions change more slowly, while augmented Random and LRU differ more from true LFU.
- Wikipedia and sampling: Very large samples can reduce hit-ratio on real workloads because they slow adaptation to gradually changing access patterns.Sampling error decreases with larger samples for static distributions, but real workloads require empirically chosen sample sizes.
- Comparative analysis: W-TinyLFU matches or outperforms state-of-the-art policies on database, SPC1-like, Windows, and most OLTP traces.It is at parity with LIRS on Glimpse, beats competing policies on DS1 and SPC1-like traces, and performs attractively on P8 and P12.
- Window sizing: For OLTP, F1, and F2 traces, window caches of 20–40% perform best, whereas the usual 1% window is insufficient.These workloads typically underperform with smaller windows, and larger window allocations improve hit-ratio.
- Approximation and overhead: TinyLFU’s approximate implementation matches the accurate version through ≈1.25 bytes per sample item, while Caffeine’s default uses 8 bytes per cached entry.Doubling Caffeine’s allocation to 16 bytes per entry increases hit-ratio by approximately ≈0.5% across the evaluated traces.
6 Conclusion
TinyLFU is an approximate frequency-based admission policy that can augment arbitrary eviction policies while using a low-memory representation of access statistics. Its performance was validated on synthetic and real-world traces, and its orthogonal design separates admission from eviction concerns.
- TinyLFU significantly improves the performance of caches using arbitrary eviction policies.The policy is designed to admit an accessed item only when replacing the cache victim is likely to improve the hit ratio.
- TinyLFU’s admission policy is orthogonal to the eviction policy, enabling the two components to be optimized independently.This separation simplifies cache design and implementation.
- Approximate sketching lets TinyLFU maintain statistics for a relatively large sample with little metadata.
- TinyLFU and W-TinyLFU were validated through simulations on synthetic traces and multiple real-world traces from different sources.TinyLFU is also available as open-source functionality in the Caffeine Java caching project.