Cache Eviction: What to Forget When It's Full

In the caching piece we met a cache: a fast copy of an answer kept close by. We also met its catch. A cache is small, so it is almost always full, and to make room it has to forget something. We used LRU there as the default. Now we put all three eviction policies side by side, each in full, because each is really its own idea.

Think of a small bag you carry every day. It holds four things, and it is always full. The moment you want to add a fifth, you have to take one out. Which one do you drop? You could drop the thing you have not touched in the longest time. Or the thing you reach for the least overall. Or the thing that has simply gone off, like a snack past its date. Those are three genuinely different rules, and each is a real eviction policy. There is no single right answer, only a right answer for a given pattern of use.

That is the whole of eviction: a full cache, and one question, "which one goes?" Everything below is three ways to answer it.

LRU: drop the least recently used

Picture a small desk that holds four things. Every time you touch one, you slide it to the front. When you reach for a fifth and the desk is full, the thing at the very back, the one you have ignored the longest, goes back on the shelf. That is LRU, least recently used. Its bet is simple: what you touched recently, you will probably touch again soon, so keep the recent stuff and drop the stale stuff.

Worked example. The desk holds [A, B, C, D], most recent at the front. You use A, so it slides to the front: [A, B, C, D] becomes [A, ...] with the rest shifting back. Now a new item E arrives and the desk is full. The item at the back, D, has gone untouched the longest, so D is evicted and E takes the front. Recency won: D left not because it was unpopular overall, but because it had been quiet lately.

LRU is the workhorse, the sensible default, and the one most systems reach for first. It matches how a lot of real traffic behaves: a burst of interest in something, then silence.

LFU: drop the least frequently used

Now change the rule. Picture a small bestseller shelf in a bookshop. What earns a spot is not when a book last sold, but how many copies it has sold in total. A steady favorite that sells every week keeps its place for months. A book that had one lucky day and then nothing gets pulled, even though that one day was recent. That is LFU, least frequently used: every item keeps a running count of how often it has been asked for, and when the cache fills, the item with the lowest count leaves.

The difference from LRU is the whole point. LRU asks "when did you last use this?" LFU asks "how often do you use this, ever?" So an item touched long ago but very often survives, while a fresh newcomer with a count of one is the first to go.

Worked example. The cache holds four items with these use-counts: A used 2 times, B used 50 times, C used 3 times, D used 8 times. A new item E arrives and the cache is full. LFU drops the lowest count, which is A at 2, even though A might have been used a moment ago. B, used 50 times, stays easily, even if its last use was hours back. Frequency won.

LFU shines when popularity is lopsided and durable: a small set of items is genuinely hot for a long time (think a handful of viral videos, or the top search queries). It has one well-known weakness, called cache pollution or aging: an item that was popular last month can build up a huge count and then linger long after interest has died, because its old score keeps it safe. Real systems fix this by letting counts decay over time, which we will see in a moment.

TTL: expire on a timer

Now a completely different rule, one that does not care about use at all. Picture the milk in your fridge. It has a date stamped on it. When that date passes, out it goes, whether you drank a glass this morning or have not touched it in a week. That is TTL, time to live: each item is stored with a countdown, and when the timer reaches zero the item expires and is evicted, regardless of how recently or how often it was used.

TTL answers a different worry from LRU and LFU. Those two are about space, "we are full, make room." TTL is about freshness, "this answer is only trustworthy for so long." A stock price, a weather reading, a login session, a rendered feed: each is fine to reuse for a few seconds or minutes, then it should be thrown out and fetched again so nobody sees a stale value.

Worked example. You cache a currency rate with a TTL of 30 seconds. For 30 seconds every request gets the cached rate, fast and cheap. At the 30-second mark it expires and is evicted, even if a thousand people are reading it right then. The next request misses, fetches a fresh rate, and caches it again with a new 30-second timer. The item left on age, not on pressure for space.

Because TTL is about age rather than space, it is not really a competitor to LRU and LFU; it sits alongside them. A real cache often runs both: a TTL so nothing is ever too stale, and LRU or LFU to decide what to drop early when memory runs out before the timers do.

The same cache, three different victims

Here is the cleanest way to feel the difference. Take one cache, in one exact state, and ask all three policies which item to evict. They disagree, because they are measuring three different things.

Same four items, same instant, three answers. LRU evicts D (quiet the longest). LFU evicts A (used the fewest times overall). TTL evicts C (its timer runs out first). None of them is wrong. They are tuned to different questions, and picking a policy means picking which question matches your traffic.

Which one to use when

A short guide, and then what real systems actually do.

The honest summary: reach for LRU unless you have a reason not to. Add LFU when a small set of items stays hot for a long time and you want to protect it. Add TTL almost always, on top of either, because most cached data has a shelf life and you would rather it expire on a timer than be served stale.

What production actually runs

Two things are worth knowing, because they come up the moment you configure a real cache.

First, real caches do not track perfect order. Keeping an exact, globally sorted "least recently used" list for millions of keys would cost more memory and time than the cache saves. So systems approximate. Redis, for example, does not scan every key to find the true LRU or LFU victim; it samples a small handful of random keys and evicts the worst one among them. You control how many with maxmemory-samples (default 5); raising it to 10 gets closer to true LRU at a little more CPU. It is a deliberate trade of a touch of accuracy for a lot of speed.

Second, the policy is a setting, not a rewrite. In Redis you pick one with maxmemory-policy, and the names map straight onto this article: allkeys-lru and allkeys-lfu apply the rule to every key, volatile-lru and volatile-lfu only to keys that have a TTL set, and volatile-ttl evicts the key whose TTL is nearest first. Redis LFU is the approximate kind: it stores frequency in a small probabilistic counter (a Morris counter) that increments slowly and, importantly, decays over time, which is the built-in fix for the aging problem we saw earlier. Memcached, the other classic, runs LRU. The concepts are exactly the three above; the products just wrap them in config flags.

Next: eviction handles a cache that is too full. The harder problem is a cache that is wrong, serving an answer that is no longer true. That is cache invalidation, and its nasty cousin, the stampede that hits when a hot key expires and every request rushes the database at once. That is the next piece.

Sources: Redis, Key eviction.