Cache Eviction
The process of removing entries from a cache when it's full. Common policies: LRU (least recently used), LFU (least frequently used), FIFO (first in, first out).
What is Cache Eviction?
In short
Cache eviction is the process of deciding which entries to remove from a cache when it runs out of space, so new data can take their place. The policy that picks the victim entry (LRU, LFU, FIFO, or a time-based expiry) directly determines your cache hit rate and therefore how often you fall back to the slow backing store.
What cache eviction actually is
A cache is a small, fast store that holds copies of data so you do not have to fetch it from a slower source like a database or a remote API. The catch is that fast memory is limited. A Redis instance might have 16 GB of RAM, an L2 CPU cache is measured in megabytes, and a browser cache has a hard byte budget. Once the cache fills up, every new item you want to add forces an old item out. Choosing which item leaves is cache eviction.
The goal of an eviction policy is to keep the entries you are most likely to ask for next, and throw out the ones you probably will not need. A cache that keeps the right items has a high hit rate, meaning most reads are served from fast memory. A cache that keeps the wrong items has a low hit rate, so reads keep missing and hitting the slow backend, which defeats the point of having a cache at all.
Eviction is not the same as expiration. Expiration removes an entry because its time-to-live ran out and the data is considered stale. Eviction removes an entry because the cache is full and something has to go, even if the data is still perfectly valid. Most real systems use both at once.
How the common policies work under the hood
LRU (Least Recently Used) evicts the entry that has gone the longest without being read or written. The assumption is that recently used data will be used again soon, which holds for most workloads. A classic implementation pairs a hash map for O(1) lookups with a doubly linked list that tracks access order. On every access you move the node to the front of the list, and when you need space you drop the node at the back.
LFU (Least Frequently Used) evicts the entry with the lowest access count. It is better than LRU when some items are popular over a long window but accessed in bursts, because LRU would wrongly evict a popular-but-idle item. The downside is that a once-hot item can get stuck in the cache forever on stale count, so production LFU usually decays counts over time. Redis implements an approximate LFU using an 8-bit counter with logarithmic increment and periodic decay.
FIFO (First In, First Out) evicts the oldest inserted entry regardless of how often it was used, which is simple and cheap but often performs worse than LRU. Random eviction just picks a victim at random, which sounds bad but is surprisingly competitive and very cheap, which is why Redis offers allkeys-random. More advanced policies like W-TinyLFU, used by the Caffeine library, combine a frequency sketch with a small recency window and beat plain LRU on most real traces.
When to use which, and the trade-offs
Reach for LRU as the default. It is well understood, cheap to implement, and matches the access pattern of most web and application caches where recent data is hot. Use LFU when you have a stable set of popular keys and want to protect them from a flood of one-off requests, for example caching the top products in a catalog. Use TTL-based expiry alongside any of these when data goes stale on a clock, like a session token or a price quote.
The main trade-off is bookkeeping cost versus hit rate. Strict LRU and LFU need metadata updated on every access, which adds memory overhead and contention under high concurrency. That is why many systems use approximate versions: Redis samples a handful of keys rather than maintaining a perfectly ordered list, trading a tiny bit of accuracy for a lot of speed.
Watch out for cache thrashing, where the working set is larger than the cache, so every access evicts something you are about to need again. No policy fixes a cache that is simply too small. Also watch for scan resistance: a one-time bulk read, like a batch job scanning every row, can flush a naive LRU cache and evict everything genuinely hot. Policies like W-TinyLFU and segmented LRU are designed to survive exactly that.
A concrete real-world example
Say you run an e-commerce site and cache product pages in Redis with a 4 GB memory limit. You set maxmemory to 4gb and maxmemory-policy to allkeys-lru. Traffic is normal and your hit rate sits around 95 percent, so the database barely gets touched.
Then a marketing email goes out and 50,000 shoppers all hit the same 20 featured products in five minutes. Under LRU those 20 products stay hot and pinned in cache, your hit rate climbs, and the database stays calm. Now imagine a nightly job that reads all 2 million products once to rebuild a search index. That scan would push every featured product out of an LRU cache and tank your hit rate during the next morning's traffic.
The fix is either to point that job at a read replica that bypasses the cache, or to switch the hot path to a scan-resistant policy. This is the kind of decision the eviction policy forces you to make, and getting it wrong shows up immediately as database load and slower page loads.
Where it is used in production
Redis
Offers eight maxmemory policies including allkeys-lru, allkeys-lfu, volatile-ttl, and allkeys-random, using sampling-based approximations instead of exact ordering.
Memcached
Uses a segmented LRU with slab-based memory allocation, splitting items into hot, warm, and cold queues to reduce locking and improve scan resistance.
Caffeine (Java)
The default cache library in Spring and many JVM apps, built on the W-TinyLFU policy that consistently beats plain LRU on real-world access traces.
CDNs like Cloudflare
Evict cached assets at edge nodes under LRU-style pressure when storage fills, while also honoring Cache-Control TTLs for freshness.
Frequently asked questions
- What is the difference between cache eviction and cache expiration?
- Expiration removes an entry because its TTL elapsed and the data is now stale, regardless of how full the cache is. Eviction removes an entry because the cache hit its memory limit and needs room, even when the data is still valid. Most systems run both: TTL clears stale data on a clock, eviction frees space on demand.
- Which eviction policy should I use by default?
- LRU is the safe default for application and web caches because recently accessed data is usually accessed again soon, and it is cheap to implement. Switch to LFU when you have a stable set of popular keys you want to protect from one-off request floods, and add TTL expiry whenever data goes stale on a schedule.
- Why does LRU sometimes perform badly?
- LRU fails under scan-heavy workloads. A one-time bulk read, like a batch job scanning every record, fills the cache with data you will never request again and evicts your genuinely hot entries. Scan-resistant policies like W-TinyLFU or segmented LRU keep frequency information to avoid being flushed by a single large scan.
- Does Redis use true LRU?
- No. Exact LRU would require an ordered list updated on every access, which is too costly. Redis samples a small number of keys (configurable via maxmemory-samples, default 5) and evicts the least recently used among that sample. This approximation is far cheaper and almost as accurate as true LRU in practice.
- What is cache thrashing and how do I fix it?
- Thrashing happens when your working set is larger than the cache, so nearly every access evicts an entry you are about to need again, driving the hit rate toward zero. No eviction policy fixes it because the cache is simply too small. The remedies are increasing cache size, reducing what you cache, or splitting hot and cold data into separate tiers.
Learn Cache Eviction hands-on
This page explains the idea. The full lesson lets you step through the ring as servers join and leave, read the implementation, and check yourself with a quiz. It is one of 760+ lessons in the System Design Masterclass, from your first API call to distributed consensus. Eleven Foundation lessons are free, no signup. Lifetime access is ₹499 in India or $7.99 worldwide, one payment, no subscription.
Related lessons
Lessons that touch on Cache Eviction as part of a larger topic.
See also
Related glossary terms you might want to look up next.
Caching
Storing frequently accessed data in a faster storage layer so you don't have to fetch it from the original (slower) source every time.
Redis
An in-memory data store used as a cache, message broker, and database. Blazing fast because everything lives in RAM.
Memcached
A simple, high-performance distributed memory caching system. Stores key-value pairs in RAM. Simpler than Redis but less feature-rich.
CDN
A network of servers distributed globally that caches content close to users. Netflix uses CDNs to stream video from servers near you, not from one central location.
Cache-Aside
A caching pattern where the application checks the cache first; on a miss, it fetches from the database and populates the cache. Also called lazy loading.
Write-Through Cache
A caching pattern where every write goes to both the cache and the database simultaneously. Ensures consistency but adds write latency.