4. Eviction policies and LRU

Description

The cache-aside pattern from the previous lesson has a consequence that must be faced head-on: the cache fills up nonstop. Each new link someone visits enters the cache on its first miss, and nobody takes it out. But RAM is finite —a Redis server has, say, 8 or 16 GB, not infinite—, so sooner or later the cache hits its limit. At that moment, to put in a new piece of data, you have to take out an old one. That expulsion is called eviction, and the rule that decides who gets evicted is the eviction policy. Choosing it well is what separates a cache with a 90% hit ratio from one with a 40% hit ratio, using exactly the same RAM.

This lesson runs through the policies —LRU, LFU, FIFO, random— and explains why LRU (Least Recently Used) is the sensible default for the vast majority of systems, including Enlace. You'll see LRU not as a definition, but in action: a small simulation, run in Python, that shows you step by step what enters, what gets evicted, and —most important— how many reads to the database it avoids compared to having nothing. By the end you'll know what Redis's maxmemory-policy options mean (allkeys-lru, volatile-lru…) and which one Enlace gets.

Connection to the module: lesson 3 filled the cache; this one decides what to throw out when it overflows. Lesson 5 will measure how the eviction policy translates into hit ratio, and from there into latency. Lesson 6 will compute how much RAM is needed so eviction almost never has to act (if the working set fits entirely, you don't evict anything hot). Eviction and size are two sides of the same coin: either you have RAM to spare, or you have to choose well whom you sacrifice.

The seasonal closet

Think of it this way. You have a fixed-size closet and more clothes than fit. You can't enlarge the closet (RAM is finite), so every time you buy a new item and it's already full, you have to take one out to make space. The question is: which one do you take out? On that decision depends whether your closet ends up full of the clothes you wear or full of the ones you never use.

There are several strategies. You could take out the one you haven't worn in the longest time —if you didn't use it in months, you probably won't miss it—: that's LRU. You could take out the one you wear least often in total —you keep count of how many times you used each item and take out the one with the lowest count—: that's LFU. You could take out the one you bought first, regardless of whether you use it or not —the oldest to come in—: that's FIFO. Or you could close your eyes and take out one at random: that's random. All four make space; only some make smart space, taking out what you really won't need.

LRU —"take out what you haven't used in the longest time"— is the one that works best for clothes and for almost everything else, and the reason has a name: temporal locality. What you used recently you tend to use again soon (this week's hoodie), and what you haven't touched in a while you probably no longer need (the coat from three seasons ago). In Enlace exactly the same thing happens: a link someone visited a second ago probably receives more visits in the next seconds (it's circulating now), while one no one has touched in hours has surely cooled off. LRU bets on that regularity, and that's why it's right so often.

When the cache fills up, you have to evict something to put in the new one. The eviction policy decides who. LRU —evict the least recently used— wins in most cases because it exploits temporal locality: what's recently used gets used again soon, what's cold no longer.

The policies, one by one

Before simulating, let's be clear on the four candidates, what they keep track of, and their weakness:

Policy	What it evicts	What it needs to remember	Weakness
LRU (Least Recently Used)	The entry used longest ago	The order of last access	A sweep of cold data (a bot going through rare links) can push the hot ones out
LFU (Least Frequently Used)	The entry with the fewest total accesses	A counter per entry	An old piece of data with many accumulated accesses stays even though no one requests it anymore ("polluted cache")
FIFO (First In, First Out)	The one that came in first, without looking at usage	The insertion order	It ignores whether an old piece of data is still popular; it can throw out something hot just for being old
Random	One at random	Nothing	It uses no information; simple and cheap, but wastes avoidable hits

Notice the tradeoff between LRU and LFU, which is the classic debate. LRU only remembers when each piece of data was last used; it's cheap and reacts quickly to changes in fashion (if a link stops circulating, it falls to the bottom and gets evicted soon). Its weak point is the sweep: if a process suddenly goes through a bunch of cold links (for example, a bot scanning codes), each one enters as "recently used" and pushes the hot ones toward the exit, even though the cold ones will never be requested again. LFU remembers how many times each piece of data was used, so it resists the sweep (a cold link with a single access doesn't evict a hot one with thousands). But LFU has its own trap: a piece of data that was very popular last month accumulated so many accesses that it stays stuck even though no one requests it anymore —the cache gets "polluted" with old glories—. That's why Redis offers LFU variants with decay, but that's already fine-tuning. For Enlace, whose traffic follows changing fashions (a link is viral this week and forgotten the next), LRU is the natural choice: it reacts quickly to what's hot now.

Simulating an LRU

The best way to understand LRU is to see it work. We're going to build a tiny LRU cache —capacity 3, so that eviction happens often and is visible— and feed it a sequence of short_codes where one, aX9, is viral and repeats. In Python, an LRU is cleanly implemented with an OrderedDict, which remembers the insertion order and allows moving a key to the end when it's used:

# lru_sim.py — an LRU cache of capacity 3, step by step
from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = OrderedDict()          # order: old (left) -> new (right)
        self.hits = 0
        self.misses = 0
        self.evictions = []

    def get(self, key):
        if key in self.store:
            self.store.move_to_end(key)     # using it makes it "recent"
            self.hits += 1
            return self.store[key]
        self.misses += 1
        return None

    def put(self, key, value):
        if key in self.store:
            self.store.move_to_end(key)
        self.store[key] = value
        if len(self.store) > self.capacity:
            evicted, _ = self.store.popitem(last=False)   # take out the oldest
            self.evictions.append(evicted)


# aX9 is viral: it repeats. Cache-aside: on each miss, it's populated from the DB.
sequence = ["aX9", "bK2", "cP7", "aX9", "dR4", "aX9", "bK2", "eT1", "aX9"]
cache = LRUCache(3)
db_reads = 0

for i, code in enumerate(sequence, 1):
    val = cache.get(code)
    if val is None:                          # MISS -> read DB and populate
        db_reads += 1
        cache.put(code, f"url_of_{code}")
        action = "MISS -> read DB + populate"
    else:                                    # HIT -> the DB is avoided
        action = "HIT  -> avoids the DB"
    contents = " ".join(cache.store.keys())
    print(f"{i} | {code} | {action:26} | cache: {contents}")

n = len(sequence)
print(f"\nrequests = {n} | hits = {cache.hits} | misses = {cache.misses}")
print(f"hit ratio  = {cache.hits/n:.1%}")
print(f"evictions  = {cache.evictions}")
print(f"reads to the DB: WITHOUT cache = {n}, WITH cache = {db_reads} "
      f"({n - db_reads} avoided)")

The LRUCache keeps its keys ordered from oldest (left) to most recent (right). Each get that hits moves the key to the recent end (move_to_end), so "recently used" is always on the right and "hasn't been used in the longest time" is always on the left. When a put overflows the capacity, popitem(last=False) takes out the leftmost one —the least recently used—. The sequence puts in aX9 as the viral link that repeats, and capacity 3 forces evictions so you see LRU decide.

What to expect. With python lru_sim.py:

1 | aX9 | MISS -> read DB + populate   | cache: aX9
2 | bK2 | MISS -> read DB + populate   | cache: aX9 bK2
3 | cP7 | MISS -> read DB + populate   | cache: aX9 bK2 cP7
4 | aX9 | HIT  -> avoids the DB         | cache: bK2 cP7 aX9
5 | dR4 | MISS -> read DB + populate   | cache: cP7 aX9 dR4
6 | aX9 | HIT  -> avoids the DB         | cache: cP7 dR4 aX9
7 | bK2 | MISS -> read DB + populate   | cache: dR4 aX9 bK2
8 | eT1 | MISS -> read DB + populate   | cache: aX9 bK2 eT1
9 | aX9 | HIT  -> avoids the DB         | cache: bK2 eT1 aX9

requests = 9 | hits = 3 | misses = 6
hit ratio  = 33.3%
evictions  = ['bK2', 'cP7', 'dR4']

Read it calmly, because each line tells a story. Look at step 4: aX9 is requested, it's a hit, and observe how aX9 jumps to the end of the cache (bK2 cP7 aX9) —using it made it the most recent, so now it's the last candidate to be evicted—. That's LRU's mechanics protecting the hot stuff. Now look at step 5: dR4 comes in, the cache was full, and who does it evict? bK2, which had gone the longest without being used —not aX9, which had just received a hit—. LRU sacrificed the cold one and protected the viral one. Notice also step 3→5: aX9 survived two evictions (those of bK2 and cP7) precisely because its hits kept it fresh. And in the end: of 9 requests, 3 reads to the database were avoided (the three hits). With a cache of only 3 slots and a viral piece of data, a third of the reads no longer bother the database.

Why the simulation's hit ratio is "only" 33%

Don't be scared by the 33.3%: it's an artifact of having made the cache deliberately tiny (capacity 3) so that eviction was visible. With such a small cache, only the viral one and two neighbors fit, so most distinct links enter cold and pay their miss. In Enlace the cache isn't 3 slots: it's hundreds of thousands of entries (lesson 6 computes ~666,667), enough for the whole hot working set to fit. When the working set fits entirely, eviction hardly acts on hot data —it only evicts the ones that have already cooled off—, and the hit ratio rises to 90% or more. The simulation doesn't say "LRU gives 33%"; it says "LRU protects the hot stuff even with almost no space, and avoids real reads". With real space, that same logic gives an excellent hit ratio. That relationship between size and hit ratio is exactly what you size in lesson 6.

Eviction in Redis: the maxmemory-policy

In the real world you don't implement the LRU by hand: Redis (our cache) brings it out of the box. You set a memory limit with maxmemory (for example, maxmemory 4gb) and tell it with maxmemory-policy what to do when it reaches it. The options that matter:

maxmemory-policy	What it does
noeviction	Doesn't evict anything: when full, it rejects new writes with an error. The source of truth isn't at risk, but the cache stops accepting new data.
allkeys-lru	Evicts with LRU among all the keys. The typical choice for a pure cache like Enlace's.
allkeys-lfu	Evicts with LFU (least frequent) among all the keys. Useful if the traffic is very stable.
volatile-lru	Evicts with LRU only among the keys that have a TTL (the ones marked to expire). Keys without a TTL stay.
allkeys-random	Evicts at random. Cheap, but wastes avoidable hits.

For Enlace, where the cache is a pure cache (all its content is reconstructible from the database and everything is a legitimate eviction candidate), the natural choice is allkeys-lru: it applies LRU over all the keys, which is exactly the seasonal-closet policy. volatile-lru makes sense when you mix in the same Redis "cacheable" data (with a TTL) and data you don't want to lose (without a TTL) —but in a pure cache you shouldn't have data you can't reconstruct, so allkeys-lru is simpler and safer—. And noeviction is what you do not want in a cache: it turns a performance problem (full cache) into an error (rejected writes). An honest note: Redis's LRU is approximate —it samples a few keys and evicts the oldest of the sample, instead of tracking the exact global order— because the perfect LRU would cost memory and CPU; the result is almost identical to the exact LRU you simulated, at a fraction of the cost.

Common mistakes

Leaving the cache in noeviction without realizing it. What happens: someone sets up Redis with the default configuration (which in some versions is noeviction), the cache fills up, and suddenly the writes to the cache start failing with "OOM command not allowed". The system doesn't go down —the database is still the truth—, but the cache stops populating and the hit ratio stalls. Why it happens: noeviction sounds safe ("it doesn't delete anything") but for a cache it's exactly the opposite of what you want. How to detect it: if you see OOM errors in Redis or the hit ratio stops rising when it fills up, check the policy. How to fix it: for a pure cache, set allkeys-lru (or allkeys-lfu). A cache must be able to throw out the old to put in the new; that's its nature.

Choosing LFU believing that "more frequent" always wins. What happens: someone reasons "I want to keep the most requested, so LFU" and configures allkeys-lfu. Months later, the cache is full of links that were viral a while ago and accumulated millions of accesses, but that no one visits anymore —they evict today's hot links, which are just starting to accumulate a count—. The hit ratio drops. Why it happens: LFU rewards historical frequency, and without decay, the old glories never let go of their spot. How to detect it: if your traffic follows changing fashions (like Enlace) and the hit ratio worsens with LFU, it's cache pollution. How to fix it: for traffic with changing fashions, LRU reacts better —what stopped circulating falls to the bottom and gets evicted soon—. LFU shines in very stable traffic; LRU, in changing traffic. Enlace is the latter.

Confusing "the cache filled up" with "the cache failed". What happens: someone sees the cache at 100% of its memory and panics, believing something broke. But a cache must be full: that's its normal working state. A half-empty cache is a wasted cache (RAM paid for and unused). Why it happens: "full" is associated with "problem", as with a disk. How to detect it: look at the hit ratio and the eviction rate, not the memory percentage. A full cache with a high hit ratio and moderate eviction is healthy. How to fix it: change the metric you look at. "Full" is normal; what matters is what the eviction is throwing out. If it's throwing out hot data (high eviction and the hit ratio dropping), it's that the cache is too small for the working set —and that's fixed with more RAM, which is what you size in lesson 6—, not by changing the policy.

Exercises

Exercise 1 — Trace the LRU by hand. With an LRU cache of capacity 2 (even smaller) and starting empty, trace this sequence of accesses: A, B, A, C, B. For each one say whether it's a hit or a miss, what's left in the cache (from oldest to most recent), and, when there's an eviction, who gets evicted.

See solution

Capacity 2, starting empty:

#	access	result	eviction	cache (old→new)
1	A	MISS	—	A
2	B	MISS	—	A B
3	A	HIT	—	B A (A jumps to recent)
4	C	MISS	B	A C (B was the oldest)
5	B	MISS	A	C B (A was the oldest)

Hits: 1. Misses: 4. Hit ratio = 1/5 = 20%.

The key moment is step 4. The cache was full with A and B, but in step 3 A was used, which made it the most recent and pushed B to the bottom. So when C comes in and something has to be evicted, B falls —the least recently used— and not A. LRU protected A because it had been used recently. If the policy had been FIFO (evict the one that came in first, without looking at usage), A would have fallen in step 4, even though it had just been used —and that would have been worse—. This is, in miniature, the advantage of LRU over FIFO: using a piece of data protects it.

Exercise 2 — The sweep that poisons LRU. LRU has a weak point: a "sweep" of cold data. Imagine an LRU cache of capacity 3 that has three hot links cached (H1, H2, H3, requested constantly). Suddenly, a bot requests five distinct cold links (F1, F2, F3, F4, F5) that will never be requested again. After that, what's left in the cache, and what happened to the hot links? Which policy would have resisted better?

See solution

The cache had H1 H2 H3. The bot requests five cold ones, each a miss that populates and evicts:

• F1 comes in → evicts H1 → H2 H3 F1
• F2 comes in → evicts H2 → H3 F1 F2
• F3 comes in → evicts H3 → F1 F2 F3
• F4 comes in → evicts F1 → F2 F3 F4
• F5 comes in → evicts F2 → F3 F4 F5

In the end the cache contains F3 F4 F5 —three cold links that will never be requested again— and the three hot ones H1, H2, H3 were evicted. The next time someone requests H1, it'll be a miss, even though H1 is very popular. The sweep "poisoned" the cache: LRU treated each cold link as "recently used" and let them push out the hot ones.

LFU would have resisted better: H1, H2, H3 have many accumulated accesses, and each cold one has only one, so LFU wouldn't have evicted the hot ones because of single-use cold ones. This is exactly the case where LFU wins. In practice, Redis mitigates this with variants and sampling, but the exercise shows why the policy choice depends on the access pattern: there's no policy that always wins. For Enlace, where bot sweeps exist but the hot working set is large and fits in RAM, LRU with enough memory holds up well —the sweep would have to be enormous to evict the whole working set—.

Exercise 3 — Choose the maxmemory-policy. For each Redis scenario, say which maxmemory-policy is best and why in one sentence. (a) Enlace's pure cache: all its content can be reconstructed from the database. (b) A Redis that mixes cacheable data (with a TTL) and a list of "active sessions" that you do NOT want to lose (without a TTL). (c) A system where you prefer the cache to reject new data rather than delete something it already has.

See solution

• (a) Enlace: allkeys-lru. All the content is reconstructible and everything is a legitimate eviction candidate, so applying LRU over all the keys is correct and simplest. It's the default choice for a pure cache.
• (b) Mix with data you don't want to lose: volatile-lru. This policy only evicts among the keys with a TTL (the cacheable ones), and leaves the ones without a TTL (the active sessions) intact. That way you protect the non-reconstructible data while letting the cacheable ones take turns. (Although, ideally, data you can't lose shouldn't live in a volatile cache, but in the database.)
• (c) Reject rather than delete: noeviction. This policy doesn't evict anything; when full, it rejects new writes with an error. It's rarely what you want in a cache, but it exists for cases where deleting an already-present piece of data would be worse than not accepting a new one. For a performance cache like Enlace's, it's exactly what you do not choose.

The mechanical rule: pure cache → allkeys-lru; cache mixed with precious data → volatile-lru (or, better, don't mix); never delete → noeviction (almost never desirable in a cache). Enlace lives in the first case, the cleanest.

Summary and next step

In this lesson you faced the consequence of RAM being finite: when the cache fills up, you have to evict something to put in the new one, and the eviction policy decides who. You ran through the candidates —LRU, LFU, FIFO, random— and saw why LRU is the sensible default: it exploits temporal locality (what's recently used gets used again soon), reacts quickly to changes in fashion, and is cheap to maintain. You saw it work in a capacity-3 simulation: LRU protected the viral link aX9 (its hits kept it fresh) and sacrificed the cold ones, avoiding 3 of 9 reads to the database even with almost no space.

You understood the LRU vs LFU tradeoff —LRU reacts to what's hot now, LFU rewards historical frequency and gets polluted with old glories— and why Enlace, with its changing fashions, prefers LRU. And you landed in Redis: maxmemory for the limit and allkeys-lru as the correct maxmemory-policy for a pure cache, with noeviction as what to avoid.

Before moving on you should be able to: explain what eviction is and why it's inevitable; define LRU and why it wins in most cases; describe LRU's weak point (the cold-data sweep) and when LFU resists it better; and choose allkeys-lru for Enlace justifying it.

What comes next is the number we've been circling all lesson: the hit ratio, and how it translates into the latency the user feels. In lesson 5 you'll run the module's central formula —L = h·L_cache + (1−h)·L_db— for hit ratios of 0.5, 0.8, 0.9, and 0.95, and you'll see why the jump from 0.9 to 0.95 nearly halves the latency, even though it only rises five points.

Resources

• Redis — Key eviction (maxmemory-policy) — the official documentation of all of Redis's eviction policies (allkeys-lru, volatile-lru, allkeys-lfu, noeviction…) and of how its approximate LRU by sampling works. The exact reference for configuring Enlace's cache.
• collections.OrderedDict — Python documentation — the structure with which we implemented the simulation's LRU. move_to_end and popitem(last=False) are the two operations that make an OrderedDict behave like an exact LRU cache.
• Designing Data-Intensive Applications, Kleppmann — on locality and access patterns — the theoretical foundation of why temporal locality (what's recently used gets used again) makes LRU right so often, and why the access pattern decides which policy wins. The "why" behind this lesson's choice.