Eviction policies dictate what data is removed from the cache when memory reaches its limit (e.g., Redis maxmemory). As a lead developer, you must evaluate these algorithms based on your application’s read/write behavior to maximize your Hit Ratio while avoiding “Cache Pollution.”
1. LRU (Least Recently Used)
The most widely used policy (often default in Redis/Memcached).
- How it works: Assumes data accessed recently will be accessed again soon. Often implemented using a Doubly Linked List + Hash Map, moving accessed items to the “head” and evicting from the “tail.”
- Pros: fast access and eviction. Excellent for standard “Temporal Locality” workloads.
- Cons (The Pitfall): Vulnerable to Full Scan Pollution. If a background script reads 1 million cold records from the DB, LRU pushes them all to the head, evicting your active user data and destroying your hit ratio.
2. LFU (Least Frequently Used)
Looks at historical popularity instead of just recency.
- How it works: Maintains a counter for every item. Evicts items with the lowest counter.
- Pros: Immune to Full Scan Pollution (scanned items only get a score of
1and are instantly evicted). - Cons (The Pitfall): Suffers from Historical Baggage. A trending article gets 2 million hits over 3 days, then dies out. LFU refuses to evict it because its massive counter outweighs organic traffic for weeks. Also has high memory overhead for counters.
3. FIFO (First In, First Out)
- How it works: A simple queue. Evicts the oldest inserted item regardless of usage.
- Pros: Extremely fast, zero metadata overhead.
- Cons: Severe hit-ratio issues. Critical data loaded at startup is evicted purely due to age.
4. Random Replacement (RR)
- How it works: Randomly evicts a key.
- Use Case: In massive, planet-scale distributed datasets where access patterns are truly unpredictable, the CPU overhead of maintaining LRU linked-lists across a cluster outweighs the benefits. Random is mathematically “good enough” for zero CPU cost.
Modern / Advanced Eviction Policies
W-TinyLFU (The Modern standard for Local Caching)
Used by modern JVM caches like Caffeine. It combines the recency protection of LRU with the scanning protection of LFU.
- How it works:
- Tiny Memory Footprint: Uses a Count-Min Sketch to track frequency of millions of items using mere megabytes.
- Decay: Periodically halves all frequency counters, solving the LFU “Historical Baggage” problem.
- Admission Window: New items enter a tiny “LRU Window” first. They are only admitted to the main data store if their frequency proves they are worthy, preventing scan pollution.
- Pros: Near-optimal hit ratios (~99%+) for almost all workloads.
- Cons: High CPU overhead to maintain, making it better suited for local in-process caches where avoiding network/DB calls justifies the CPU cost.
Redis 4.0 Decaying LFU (Approximated LFU)
Why doesn’t Redis use W-TinyLFU? Because Redis is single-threaded and prioritizes blistering network throughput; it cannot afford the CPU cycles for exact W-TinyLFU structures.
However, Redis 4.0 introduced allkeys-lfu which behaves like a highly optimized hybrid:
- It uses a tiny 8-bit Logarithmic Counter (max 255) to track frequency, preventing memory bloat.
- It implements a Time-based Decay (e.g., halving the counter over time).
- Result: Because frequency decays over time, it naturally gains the fading effects of LRU. It effectively becomes a mix of LFU and LRU, heavily optimized for single-threaded speed via random key sampling.
Redis 8.6 LRM (Least Recently Modified)
A major addition that shifts the paradigm from focusing on Reads to focusing on Writes.
- The distinction: LRU updates a key’s timestamp on both reads and writes. LRM updates the timestamp only on writes.
- How it works: It evicts keys that haven’t been actively changed in the longest time (
allkeys-lrm,volatile-lrm). - The Architect’s Use-Case: Used to solve the tension between highly read static data (e.g., product catalogs) and highly active transactional data (e.g., shopping carts) sharing the same cache. With normal LRU, the heavily read static data pushes out the active shopping carts. With LRM, you guarantee that data experiencing active mutations is protected, while un-modified static data is evicted first under memory pressure.
How to Choose Between LRU and LFU
Insights derived from Redis engineering blog.
The decision between LFU and LRU isn’t always binary. You must map out your access patterns to choose the right strategy.
When to choose LFU
Choose LFU when popularity is a stronger predictor of future access than trendiness or recency.
- Skewed Data Access Patterns (80/20 Rule): When a small subset of items accounts for the vast majority of requests. For example, an e-commerce site caching “best-sellers”—they are accessed in nearly every session and remain popular over time.
- Static Hot Data: The “hot” data doesn’t change often. For example, if your application offers many APIs, but 3 of those APIs are called 90% of the time, LFU is best to ensure those responses stay cached.
- Systems with Popularity Rankings: Evergreen recommendation systems where historical user activity determines popularity, making raw frequency more important than recency.
When to choose LRU
Choose LRU when recent usage is the strongest signal of future usage.
- Rapidly Changing Access Patterns: When access trends shift on hourly or minute-by-minute timescales. For example, a social media news feed prioritizes recent updates. A real-time analytics dashboard prioritizes the metrics a user is currently scanning.
- Temporal Locality: When a user’s recent actions necessitate repeating those actions. For example, session/profile data while a user is actively online. Recency is paramount until they log off.
- Burst Patterns: When an unpredictable event drives a massive spike. For example, a flash sale on an otherwise rarely viewed item. LRU ensures that item stays cached during the burst, whereas LFU might evict it because its historical counter is too low to compete with evergreen items.
The Hybrid Reality
Many real-world environments require a Hybrid Approach. For instance, a financial application needs LRU for the latest volatile market data, but LFU for historically popular ticker symbols. Ensure your caching provider supports adaptable configurations, auto-tiering, or multi-tenancy (applying different eviction policies to different datasets within the same cluster) to avoid the pitfall of a rigid, one-size-fits-all policy.