TinyLFU / W-TinyLFU (Admission + Eviction Design)

Goal

Improve hit rate under skewed and one-hit-wonder workloads by using frequency-based admission instead of admitting every miss.

Core Idea

TinyLFU is primarily an admission policy:

• Keep an approximate recent frequency sketch (usually Count-Min Sketch).
• On a miss, compare candidate frequency against a sampled victim.
• Admit only if the candidate appears “hotter” than the victim.

W-TinyLFU combines:

• Window cache (small recency-focused region, typically LRU)
• Main cache (segmented/protected region)
• TinyLFU admission gate between window and main

This keeps recent bursts responsive while avoiding long-tail pollution.

Core Data Structures (Typical)

• Hash index K -> Entry
• Window segment (e.g., LRU list or ring)
• Main segment (e.g., SLRU-style probation/protected)
• Frequency sketch (Count-Min Sketch)
• Optional reset/aging counter for sketch decay

Complexity & Overhead

• Access/update in sketch: O(1) with small constant factors
• Admission decision: O(1)
• Extra memory for sketch and segmented metadata
• Approximate counts can produce false positives, but usually good tradeoff

Notes For CacheKit

• Fits best as policy composition: storage + segmented eviction + admission.
• Keep hot-path updates allocation-free (pre-sized sketch, fixed segments).
• Make admission optional/configurable for apples-to-apples benchmarks.
• Benchmark against S3-FIFO, ARC/CAR, and Heap-LFU on:
  • Zipfian
  • scan + point lookup mixes
  • shifting hotspots

References

• Einziger et al. (2017): “TinyLFU: A Highly Efficient Cache Admission Policy”.
• Caffeine design notes (W-TinyLFU implementation details).
• Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies