Cache Eviction Policies

Your cache has a problem: it's not infinite. Memory is expensive and finite. At some point, your cache will fill up, and when it does, it needs to decide what to throw out to make room for new data. That decision is your eviction policy.

Getting eviction wrong means your cache throws out the wrong things: popular data gets evicted and unpopular data stays, tanking your hit rate. Getting it right means your cache naturally gravitates toward keeping the most useful data.

Why Eviction Exists

Think of a cache like a whiteboard in a busy office. It's fast to read, but it only holds so much. When it fills up, someone has to erase something. The question is: which notes do you erase?

A bad strategy: erase the most recently written note. That's the newest information, probably the most useful. A good strategy: erase the note that nobody has looked at in the longest time. If it hasn't been needed for a week, it probably won't be needed tomorrow.

That instinct is LRU, and it's the most widely used eviction policy in production systems.

LRU — Least Recently Used

Evict the item that was accessed least recently.

LRU keeps a logical ordering of all cache entries by access time. Every time you read or write a key, it moves to the front of the list. When the cache is full and a new item needs to be stored, the item at the back of the list (least recently accessed) is evicted.

Why it works: Temporal locality — programs tend to access data they've recently accessed again. If a user just loaded their profile, they're likely to access it again soon. If a piece of data hasn't been touched in hours, it's probably cold.

Example: Imagine a cache holding 3 items: [A, B, C] (A is most recent). A new item D arrives:

1. Evict C (least recently used)
2. Add D → [D, A, B]

Real use: Redis's allkeys-lru and volatile-lru maxmemory policies. The LRU approximation Redis uses is probabilistic (it samples a few keys and evicts the least recently used among the sample) rather than exact, which is much faster to compute.

Cons: LRU can be tricked by a one-time scan. If you read a million cold keys sequentially, they'll all be marked as "recently used" and evict your actually-hot data. This is called cache pollution.

---

LFU — Least Frequently Used

Evict the item that has been accessed the least number of times.

Where LRU cares about when something was last used, LFU cares about how often it's been used. An item that's been accessed 1,000 times but not in the last minute is more valuable than an item accessed twice today.

Example: A news article published yesterday has been read 50,000 times. A trending article from an hour ago has been read 200 times. LRU might evict the older article (less recently accessed); LFU keeps it because it has a much higher frequency.

Why it works: Frequency is a better predictor of future demand than recency for workloads with stable "hotspot" data, like popular products, celebrity profiles, or viral content.

Cons:

• Frequency counters can become stale — a key that was popular 6 months ago still has a high count. LFU has no concept of "that was a long time ago." Modern implementations use a decay factor to solve this.
• New items are disadvantaged — a newly-added hot item starts with a frequency of 1 and is vulnerable to eviction before it builds up a count.

Redis added LFU support in version 4.0 with the allkeys-lfu and volatile-lfu policies, using a logarithmic counter with decay to handle the staleness problem.

---

FIFO — First In, First Out

Evict the item that has been in the cache the longest.

Simple queue semantics. The oldest entry gets evicted first, regardless of how often or recently it's been used.

Pros: Extremely simple to implement. Predictable behavior.

Cons: Terrible hit rate in most real scenarios. A hot item that was cached first will be evicted even if it's being accessed constantly, just because it's old.

When it makes sense: When your data has a natural time-based expiry, like a cache of daily reports or time-series snapshots. If old data genuinely becomes irrelevant over time, FIFO's behavior aligns with reality.

---

Random Eviction

Evict a randomly selected item.

Surprisingly, random eviction performs better than it sounds. In workloads with uniform access patterns (no clear hot or cold data), random eviction has similar hit rates to LRU but with zero bookkeeping overhead.

Pros: Zero overhead — no need to track access times or frequencies. Cons: No guarantee about which data is kept. Can evict hot data by bad luck.

Redis supports random eviction via allkeys-random and volatile-random.

---

TTL-Based Eviction

Evict items whose time-to-live has expired.

TTL isn't really an eviction strategy so much as a correctness mechanism. Every key in Redis can have an expiry time set. When the TTL expires, the key is eligible for deletion.

Redis handles TTL expiry lazily (check on access) and actively (periodic background sweep). The volatile-ttl policy evicts among TTL-bearing keys, prioritizing those whose TTL is closest to expiry.

TTL is almost always used in combination with an eviction policy. You set TTLs to enforce data freshness, and you set an eviction policy as the backstop when memory fills up before TTLs can clean up.

---

Redis's maxmemory-policy in Practice

Redis exposes these policies directly:

The most common production setup: allkeys-lru when you want the cache to manage itself, or volatile-lru when you have a mix of ephemeral and permanent keys and only want ephemeral ones evicted.

---

How to Choose

Summary

Cache eviction is the mechanism that keeps your cache from running out of memory by deciding what to discard. The policies range from the crude (FIFO, random) to the sophisticated (LFU with decay).

LRU is the workhorse. It works well for most workloads because recently-accessed data tends to be accessed again. LFU beats it when access patterns are stable and frequency is a better predictor than recency. TTL is not an alternative. It's a complement that enforces data freshness.

In practice, set your maxmemory limit in Redis, choose allkeys-lru as your default policy, add TTLs to keys where staleness matters, and monitor your hit rate. If your hit rate is low, your cache is too small or your access patterns don't have enough locality for your chosen policy to help.