Cache Eviction Policies

Here’s a situation you’ll hit sooner or later:

• A cache is just a small, fast box of memory that holds copies of data you use a lot, so you can grab it quickly instead of going all the way back to the slow database.
• But that box is small on purpose. Fast memory is expensive, so you only get a little of it.
• So one day the box fills up. And now you want to put in something new.
• The thing is, there’s no empty space left, right? So before the new item can go in, something already inside has to be thrown out.

That “who gets thrown out?” decision is the whole topic of this lesson. The rule a cache uses to pick the loser is called an eviction policy, and we’ll go through the common ones one by one.

🎯 The Problem

Let’s name the pain first, because that’s what makes the rest make sense:

• Cache memory is limited. You can’t keep everything, only a small slice of your data fits.
• So the cache works fine right up until it’s full.
• Once it’s full, every new item you want to add runs into a wall. There’s simply no room.
• And you can’t just refuse the new item, because that new item might be exactly what people are asking for now.

So the cache is stuck with a choice. To make space for something new, it has to remove something old. The only question is: which old thing? Pick badly and you’ll keep throwing out stuff you needed two seconds later. Pick well and the cache stays useful.

🗑️ What is Eviction

Let’s pin down the word before we go further.

• Eviction means removing an item from a full cache to make room for a new one. That’s it.
• It only kicks in when the cache is out of space. If there’s still room, nothing gets evicted, the new item just goes in.
• The cache doesn’t pick randomly by accident. It follows a set rule, and that rule is the eviction policy.

So picture it like a small bookshelf that’s already packed. You buy a new book. To shelve it, you have to pull an old one off. The eviction policy is just your rule for deciding which book leaves.

That little diamond, “is the cache full?”, is the trigger. Everything below it is the eviction policy doing its job.

📋 The Common Policies

There are a handful of go-to rules, and each one answers “who leaves?” differently. Here they are side by side first, then we’ll talk through each.

Now let’s walk through what each one actually means.

• LRU, Least Recently Used. This one throws out the item that hasn’t been touched for the longest time. So the cache keeps track of when each item was last used. The one sitting idle the longest is the loser. The idea is simple: if you haven’t needed something in a while, you probably won’t need it right now either.
• LFU, Least Frequently Used. This one counts how many times each item gets used, and throws out the one with the lowest count. Notice the difference from LRU: LRU cares about when you last used it, LFU cares about how many times you’ve used it total. So a popular item that’s been hit a thousand times stays, even if nobody touched it in the last minute.
• FIFO, First In First Out. This one is the plainest. It throws out whatever was put in first, like a queue at a shop where the person who’s been waiting longest is served and leaves. It doesn’t care how often you used the item, only how long ago it arrived.
• Random. Exactly what it sounds like. When space is needed, the cache just grabs some item at random and removes it. It sounds careless, but it’s dead simple and surprisingly okay in some cases, because it needs no bookkeeping at all.
• TTL expiry. This is a bit different from the others, and we’ll come back to it. With TTL you stamp each item with an age limit. Once an item is older than that limit, it’s removed regardless of whether the cache is full. TTL removes by age, not by lack of space.

🏆 Why LRU Is So Popular

Out of all these, LRU shows up the most in real systems. Here’s why people reach for it first:

• Real-world access has a pattern: stuff you used recently, you tend to use again soon. This “recent things come back” behavior is sometimes called locality of reference, but you don’t need the fancy name to feel it.
• Think of the browser tabs you flip between, or the few files you keep reopening at work. The recent ones are the hot ones.
• So LRU bets on that pattern. By keeping recently used items and dropping the stale ones, it usually keeps the right things around.
• And it’s not too expensive to build. The cache just has to remember the order in which items were last touched, which is doable with simple data structures.

So when someone asks “what eviction policy should I start with?”, LRU is the honest default answer. It matches how people actually use data, and it rarely embarrasses you.

⏳ Eviction vs Expiry

This pair confuses a lot of people, so let’s separate them cleanly. They both remove items, but for completely different reasons.

• Eviction happens because the cache is out of space. The item might still be perfectly good and fresh, but it gets kicked out anyway to make room for something new.
• Expiry (TTL) happens because the item is too old. You decided ahead of time that this data is only trustworthy for, say, five minutes. After that it’s stale, so it gets removed even if the cache has tons of free space.

Here’s the way to remember it:

• Eviction is about room. “I need space, sorry, out you go.”
• Expiry is about freshness. “Your time’s up, you might be wrong now, out you go.”

A real cache often uses both at once. It expires data that’s gone stale by TTL, and it evicts data by LRU (or another policy) when it runs out of room. They’re two separate switches, not the same one.

🧩 Choosing a Policy

There’s no single winner. The right policy depends on how your data gets used, so think about your access pattern first.

• If recent items tend to come back soon, go with LRU. This is true for most everyday cases, which is why it’s the safe default.
• If a small set of items stays popular over a long time and you really want to protect them, lean toward LFU. Just know it can get stuck holding onto something that used to be popular but isn’t anymore.
• If you want something dirt simple and don’t want to track usage at all, FIFO or Random can be fine, especially when items are roughly equal in value.
• If your data goes stale after a while, add a TTL on top of whatever eviction policy you choose. Remember, TTL handles freshness; the eviction policy handles space. You usually want both.

If you’re unsure, start with LRU and a sensible TTL. Measure how often the cache actually helps, and only switch policies if the numbers tell you to.

⚠️ Common Mistakes and Misconceptions

A few ideas trip people up. Let’s clear them out.

• “Eviction and expiry are the same thing.” No. Eviction removes items because there’s no space. Expiry removes items because they’re too old. One is about room, the other about freshness.
• “LRU is always the best choice.” It’s the best default, not the best for every case. If your hot items get hit constantly over a long period, LFU might keep them better. The right answer depends on your access pattern.
• “A bigger cache always means fewer evictions, so make it huge.” Bigger does mean fewer evictions, but fast memory is expensive. The real point is to size it sensibly. Which brings us to the next one.
• “Undersizing the cache is harmless.” It isn’t. If the cache is too small for your working set, it fills up instantly and evicts items almost as fast as it stores them. That’s called thrashing, and a cache that thrashes barely helps at all, because the thing you need was just thrown out.
• “Random eviction is always a bad idea.” Not true. It needs zero bookkeeping, and when items are roughly equal in value, it performs close enough to fancier policies to be worth it.

🛠️ Design Challenge

Try this on your own to test yourself.

Imagine a cache that can hold only three items. Requests come in this order, and each letter is a key you read:

A, B, C, A, D, E, A

Walk through it using LRU. Each time the cache is full and a new key shows up, write down which item gets evicted and why. For example:

• After A, B, C the cache is full with A, B, C.
• The next A is already there, so it just becomes the most recently used. No eviction.
• Then D comes in. The cache is full, so LRU removes the least recently used one. Which is it? Work it out.

Do the same run with FIFO and compare. You’ll notice they evict different items, and that’s the whole point: the policy changes what survives.

🧩 What You’ve Learned

You can now explain how a full cache decides what to drop. Here’s what you’ve picked up.

• ✅ Eviction means removing an item from a full cache to make room for a new one, and it only triggers when space runs out.
• ✅ LRU removes the least recently used item, LFU removes the least frequently used, FIFO removes the oldest added, and Random removes any item.
• ✅ TTL expiry is separate: it removes items by age, not by lack of space.
• ✅ Eviction is about room; expiry is about freshness. Real caches often use both.
• ✅ LRU is the safe default because recently used data tends to be used again soon.
• ✅ Sizing the cache too small causes thrashing, where it evicts items almost as fast as it stores them.

🧠

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

1. 1

   When does cache eviction happen?

   Every time an item is read Only when the cache is full and needs room for a new item When the network is slow When the database is updated
   Check

   Why: Eviction only triggers when the cache is out of space, removing an item to make room for a new one.

2. 2

   What is the difference between LRU and LFU?

   LRU removes the oldest added item, LFU removes a random item They are exactly the same LRU removes the least recently used item, LFU removes the least frequently used item LRU is about freshness, LFU is about space
   Check

   Why: LRU cares about recency (when it was last used), while LFU cares about frequency (how many times it was used).

3. 3

   How is eviction different from TTL expiry?

   Eviction removes items due to lack of space, while TTL expiry removes items once they pass a set age They both only run at startup Eviction is about age, expiry is about space There is no difference
   Check

   Why: Eviction is about room while expiry is about freshness, and most real caches use both together.

4. 4

   What happens if your cache is too small for your working set?

   It runs faster It never evicts anything It thrashes, evicting items almost as fast as it stores them It becomes the source of truth
   Check

   Why: A too-small cache thrashes, so the data you need is often gone right when you want it and the cache barely helps.

Score: 0 / 4 Reset

🚀 What’s Next?

You now know how a cache makes room. Next, go deeper into the tools and the bigger picture.

• Introduction to Redis shows a real cache you can use, with its own eviction settings built in.
• Cache Hit vs Cache Miss explains how to measure whether your cache is actually helping, which is exactly how you’d know if your eviction policy is working.