We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningFoundation · Caching Strategies
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).
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.
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.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Cache Eviction across a run of lessons, not one page. These 4 alone are about 95 minutes of step-by-step reading, every one with a quiz.
LFU beat LRU by 6 to 15 points, FIFO measured identical to random, and the scan that supposedly destroys LRU cost it 11 points for four hundred requests.
Windows defined by wall clock or event timestamps, the time semantics that determine correctness.
A batch job taking 30 percent of requests cost LRU 6.3 points of hit rate on the real requests, admission by approximate frequency 4.2, and exact counting 0.8, in 2,048 bytes.
Careful per-row invalidation served more than twice the stale reads of doing nothing, because it raised the hit rate on the entries it cannot see.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Cache Eviction Policiespay once,
yours for life
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
This page explains the idea. The "Cache Eviction Policies" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Cache Eviction Policies lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Cache Eviction in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
