Cache Eviction Algorithms

Introduction: The “Full Suitcase” Problem

Memory is expensive. You can’t store everything in your cache (Redis, Memcached, or local RAM). When your “suitcase” is full and a new item arrives, you must decide which old item to throw away.

Cache Eviction is the algorithm that makes this decision. A good algorithm keeps the “Hot Data” (what you’ll need soon) and discards the “Cold Data.”

Core Algorithms

1. LRU (Least Recently Used)

• Logic: Throw away the item that hasn’t been used for the longest time.
• How it works: A Hash Map combined with a Doubly Linked List. Every time an item is accessed, move it to the front. The item at the tail is the victim.
• Pros: Very simple, works well for most “recency-based” workloads.
• Cons: Vulnerable to “Sparse Scans.” If a script reads 1 million old items once, it will flush out all your frequent hot data.

2. LFU (Least Frequently Used)

• Logic: Throw away the item with the lowest access count.
• How it works: Keeps a counter for every item.
• Pros: Good for “frequency-based” workloads (e.g., a static homepage that is always popular).
• Cons: Hard to implement efficiently ($O(1)$ requires complex bucketing). Also, items that were popular 1 hour ago but are dead now might stay in the cache forever (Stale Data).

3. W-TinyLFU (Window TinyLFU)

• Logic: A hybrid approach using a tiny “Admission Window” and a Bloom-Filter-like sketch to track frequency.
• The Hero: This is the algorithm used by Caffeine (Java) and Ristretto (Go). It provides near-perfect hit rates and is resistant to sparse scans.

Typical Business Scenarios

• ✅ Session Store: Use LRU. If a user hasn’t touched their session in 30 minutes, it’s safe to evict.
• ✅ Product Catalog: Use W-TinyLFU. Some products are always popular (frequency), others are trending right now (recency).
• ✅ Database Buffer Pool: MySQL and Postgres use modified versions of LRU (like LRU-2) to prevent full-table scans from ruining the cache.

Performance & Complexity

• LRU: $O(1)$ for both get and put.
• W-TinyLFU: $O(1)$ but requires more complex logic and a frequency sketch (Count-Min Sketch).

Summary

"LRU is the industry default because it's simple and fast. But if your system faces unpredictable traffic spikes or large scans, upgrade to W-TinyLFU to keep your cache hit rate high."