Caching • Eviction PoliciesMedium⏱️ ~3 min

Admission Policies and W-TinyLFU: Filtering Cache Pollution

The Cache Pollution Problem
Standard eviction policies assume any fetched item is worth caching. This fails under two workloads. One hit wonders: items accessed exactly once (batch jobs, cold starts). Scan traffic: sequential access touching millions of keys once. Both evict hot data in favor of items never accessed again, collapsing hit rates from 80% to under 20%.
How Admission Works
An admission policy gates cache entry. When a candidate arrives, it competes against the eviction victim. If the candidate has higher historical frequency, it wins admission and the victim is evicted. If lower, the candidate is rejected. One hit wonders lose because they have zero prior accesses.
W-TinyLFU Architecture
W-TinyLFU combines three components. A Count Min Sketch (CMS) tracks frequencies using multiple hash functions mapping keys to counter arrays. Query all positions, take the minimum. Width 10,000 and depth 4 uses 40 KB with under 2% error. A window segment (1-2% capacity) absorbs bursts via LRU. Main cache splits into probation (20%) and protected (80%).
Sketch Aging
Counter aging halves all values every N accesses (typically 10x cache size). This bounds stale history so decisions reflect recent patterns.
Key Insight: W-TinyLFU improves hit rate by 10-30% over LRU. At 100,000 QPS, reducing miss rate from 20% to 14% saves 6,000 backend requests per second.

💡 Key Takeaways

✓Admission policies reject candidates unless hotter than the eviction victim. Without filtering, one hit wonders and scans collapse hit rates from 80% to under 20%.

✓Count Min Sketch uses multiple hash functions mapping keys to counters. Frequency estimate takes minimum across positions. Width 10,000 depth 4 uses 40 KB with under 2% error.

✓W-TinyLFU has three segments: window (1-2%) for bursts, probation (20%) for new items, protected (80%) for proven hot items.

✓Counter aging halves all values every N accesses to bound stale history.

✓Hit rate improves 10-30% over LRU. At 100,000 QPS, 6 point improvement saves 6,000 backend requests per second.

📌 Interview Tips

1Explain admission competition: candidates compete against victims using frequency. One hit wonders lose with zero prior accesses.

2For CMS, explain: multiple hash functions, counter arrays, minimum across positions for estimates.

3Know the three segments: window for bursts, probation tests new items, protected retains proven hot items.

← Back to Eviction Policies Overview