Cache Eviction: Managing Finite Resources

RAM is fast, but it's also expensive and limited. You cannot cache everything forever. When your cache reaches its capacity, it must decide which data to delete to make room for new items. This process is called Eviction.

An eviction policy is the algorithm that determines which items are removed.

Common Eviction Policies

1. LRU (Least Recently Used): Discards the least recently used items first. This is the most popular policy as it assumes that data you haven't used in a long time is less likely to be needed again soon.
2. LFU (Least Frequently Used): Tracks how often an item is requested. The items with the lowest hit count are evicted first.
3. FIFO (First-In, First-Out): The cache acts like a queue; it evicts the oldest items regardless of how often or recently they were accessed.
4. RR (Random Replacement): Randomly selects an item to evict. Simple and low overhead, but often less effective than LRU.
5. TTL-Based: Items are evicted when their pre-defined time-to-live expires.

When to Use Which?

• LRU is great for general web traffic where there is a clear "working set" of popular data.
• LFU is useful when certain items are consistently popular over long periods (e.g., a top-10 products list), even if they haven't been accessed in the last few seconds.
• FIFO is simple but can evict very popular "old" items, leading to poor cache performance.

Modern Variations

• Segmented LRU (SLRU): Divides the cache into a "probationary" and a "protected" segment to prevent a one-time "scan" of data from wiping out the whole cache.
• W-TinyLFU: A highly sophisticated policy used in modern libraries (like Caffeine for Java) that combines the benefits of LRU and LFU while using very little memory for tracking.

Common Mistakes

• Incorrect Capacity Planning: Setting the cache size too small, leading to constant "thrashing" (where items are evicted and then immediately re-cached).
• Ignoring LFU Overhead: Tracking hit counts for every single key in LFU can consume a significant amount of memory if not implemented efficiently.
• Uniform TTLs: Setting the same TTL for every type of data. Sensitive data might need a 1-minute TTL, while static configuration might last 24 hours.

Recap

• Eviction is necessary because cache memory is limited.
• LRU is the industry standard for most workloads.
• LFU handles long-term popularity better but is more complex.
• Thrashing occurs when your eviction policy or cache size is poorly matched to your access patterns.