Q20 — How do cache eviction policies work — LRU, LFU — and why does the choice matter?
Why does eviction exist at all?
A cache lives in memory. Memory is finite. Your dataset is (usually) not.
As the cache fills up, incoming data that needs to be cached has nowhere to go unless something already in the cache is removed first. Eviction is the process of deciding which existing cache entry to remove to make room for the new one.
The goal is to remove the entry that is least valuable to keep — the one least likely to be requested again in the near future. If you knew the future, you'd always evict the item whose next access is furthest away (this optimal strategy is called Bélády's algorithm). Since you don't know the future, every eviction policy is a heuristic — a bet about what future access patterns look like based on past behavior.
Getting this bet right matters. Evict the wrong thing and the next request for it becomes a cache miss — triggering a database fetch, adding latency, and potentially evicting something else to make room for the re-fetched data. A bad eviction policy can cause a cascade of misses that makes the cache perform worse than having no cache at all.
LRU — Least Recently Used
LRU evicts whichever item was accessed least recently. The intuition: if you haven't looked at something in a while, you probably won't look at it soon.
How it works: Maintain a conceptual ordering of all cache entries by last access time. When a new entry needs to be inserted and the cache is full, evict the entry at the "least recently used" end of the ordering. When any entry is accessed (hit or miss+insert), move it to the "most recently used" end.
In implementation, this is typically a doubly-linked list + hash map combination: the hash map gives O(1) lookup, and the doubly-linked list maintains the recency ordering, with O(1) moves to the front on access and O(1) removal from the tail on eviction.
When LRU works well: Workloads with temporal locality — if you accessed something recently, you're likely to access it again soon. User sessions, hot product pages, recently trending content. These access patterns match LRU's assumption almost perfectly.
When LRU fails — the scan problem: Imagine a workload where every request reads through a large dataset sequentially — a nightly analytics job scanning 1 million rows, or a search that touches many records. These items are accessed once each and never again. But LRU treats each newly scanned item as "most recently used" and bumps it to the front of the queue, evicting items that are genuinely hot (frequently accessed user records) to make room for cold scan data.
This is called cache pollution. A single sequential scan can wipe out your entire warm working set. After the scan completes, all the actually hot data has been evicted, and the next real user requests all miss, causing a flood of database queries to repopulate the cache. This is a well-known failure mode of pure LRU in database systems — MySQL InnoDB has a specific mitigation called the "LRU list heat zone" to protect hot pages from being evicted by scans.
LFU — Least Frequently Used
LFU evicts whichever item has been accessed the fewest times overall. The intuition: items that have been accessed many times in the past are likely to be accessed again; items accessed rarely are not.
How it works: Maintain an access counter for each cache entry. When eviction is needed, remove the entry with the lowest counter. On access, increment the entry's counter and re-sort or re-bucket it into the appropriate frequency tier.
When LFU works well: Stable workloads with a persistent hot set. Some items are permanently popular (a homepage, a featured product, a celebrity's profile) and should never be evicted. LFU naturally protects these — they accumulate very high counts and are last to be evicted. Cold scan data that's accessed once never accumulates counts and is first to go.
When LFU fails — the frequency bias problem: LFU has no concept of time. A news article that was the most-read article in the world three months ago has a very high counter — but nobody has touched it in weeks. Under LFU, this dead article is protected while a fresh breaking news story that's been accessed 50 times in the last hour is considered less valuable (50 < 10,000) and gets evicted.
This is frequency bias — old, stale-but-popular items crowd out new, emerging-hot items. LFU doesn't know that access patterns have shifted; it only knows what happened historically.
The fix — decay: Many LFU implementations add frequency decay. Counters slowly decrease over time (halved every minute, for example), so historical accesses gradually become less influential. An item accessed 10,000 times three months ago and nothing since will decay toward zero, while an item accessed 50 times in the last hour maintains a higher effective count. This is sometimes called LFU with aging, or Window-TinyLFU.
Redis's approach — approximated LRU and LFU
Maintaining a perfect LRU ordering requires updating a doubly-linked list on every single cache hit. At millions of requests per second, this becomes a significant overhead. Redis doesn't maintain a perfect LRU list.
Instead, Redis uses sampled approximation: when eviction is needed, Redis randomly samples a small number of keys from the cache (default 5 samples, configurable), examines their last-access timestamps, and evicts the oldest among the sample. This is approximate — it doesn't guarantee the globally least-recently-used item is evicted, but in practice it approximates LRU closely at a fraction of the overhead.
Redis also supports an LFU mode (since version 4.0), where each key maintains a logarithmic approximation of access frequency with decay. The logarithm means frequent items converge quickly to a high value without requiring arbitrarily large counters.
You configure eviction behavior in Redis via maxmemory-policy:
allkeys-lru— evict any key using approximate LRUvolatile-lru— evict only keys with an expiry set, using LRUallkeys-lfu— evict any key using approximate LFUallkeys-random— evict a random key (surprisingly effective for uniform access patterns)noeviction— return an error when memory is full (default — dangerous for production caches)
FIFO and Clock — simpler alternatives
FIFO (First In, First Out) evicts the item that was inserted earliest, regardless of access. Simple to implement (a queue), but makes no use of access information. Items inserted long ago that are still heavily used get evicted; recently-inserted cold items stay. Generally worse than LRU/LFU.
Clock algorithm (Second-Chance): A practical approximation of LRU that avoids the doubly-linked list overhead. Items are arranged in a circular list with a reference bit. On access, the bit is set to 1. When eviction is needed, a "clock hand" sweeps through the list: if a bit is 1, clear it (giving the item a second chance) and advance the hand; if a bit is 0, evict that item. Items recently accessed will have their bit set to 1 and survive the sweep. Items not recently accessed get evicted. The clock algorithm is used in operating system page replacement and approximates LRU in O(1) time without maintaining a sorted list.
Why the eviction policy matters for your application
The choice of eviction policy should be driven by your access pattern:
If your hot set is temporally driven (what's popular now is what was accessed recently) — LRU is the right bet.
If your hot set is stable (the same items are always popular, but new items occasionally rise to prominence) — LFU with decay is better.
If your workload includes large sequential scans alongside regular traffic — pure LRU will fail you. Consider LFU, or a segmented LRU (where scan data is kept in a separate "probationary" segment and only promoted to the main cache after being accessed multiple times).
If you're uncertain — measure. Redis's INFO stats and redis-cli --hotkeys give you eviction rates and access distributions. High eviction rates with many cache misses on hot keys usually signal the wrong eviction policy or undersized cache.
The mental model
Why eviction: memory is finite, cache must make room for new data
Goal: evict the item least likely to be accessed again
LRU (Least Recently Used):
Bet: recent access predicts future access
Win: workloads with temporal locality (sessions, trending content)
Lose: sequential scans evict the warm working set (cache pollution)
LFU (Least Frequently Used):
Bet: high historical access count predicts future access
Win: stable hot sets (homepages, featured items)
Lose: old popular items crowd out new emerging-hot items (frequency bias)
Fix: add decay so historical counts fade over time
Redis: approximated LRU/LFU (random sample, evict worst of sample)
— good enough accuracy at much lower overhead
Clock algorithm: bit-per-entry approximation of LRU, O(1), used in OS page replacement
Choose based on access pattern:
Temporal → LRU
Stable hot set → LFU with decay
Mixed / uncertain → measure eviction rate and miss rate, adjust accordingly
Eviction is where your cache's assumptions about the future are made explicit. Every policy is a bet — understanding what each policy bets on lets you pick the one whose assumption matches your actual workload.