Eviction Policies: LRU, LFU and TTL

What you'll learn: By the end of this lesson you will be able to tell eviction apart from expiry and invalidation, describe what FIFO, LRU, LFU, random and TTL-ordered eviction each bet on, replay a trace through them, explain why a scan ruins plain LRU and a shift in popularity ruins plain LFU, name the designs that repair those weaknesses, and configure and monitor Redis eviction.

A fridge is full and a shopping bag is arriving. Something has to go. You could throw out whatever has been there longest, whatever you have not touched for the longest time, whatever you eat least often, or whatever is closest to its use-by date. Each rule is reasonable, and each is wrong in some week: the longest-resident item is the butter you use daily, the least recently touched is the Christmas turkey you bought on purpose, and the least often eaten is the new yoghurt you have only just started to like.

A cache faces this choice thousands of times a second. Caching Basics introduced LRU and LFU in a paragraph, and ShopStream Stage 2 replays one short trace by hand. This lesson is the dedicated treatment: what a policy is for, how each family works and fails, what real caches do (they approximate), and how to configure and watch it. Building an LRU cache from scratch is the subject of Build an LRU Cache in Java.

Verified against the Redis documentation, the MySQL 8.4 InnoDB buffer pool page, the Caffeine wiki and the TinyLFU abstract, all read on 2026-11-08. Check the page for the version you run.

The core idea

Eviction is a capacity decision: when a cache is full and something new must go in, which entry leaves? It is not a correctness mechanism. An entry can leave a cache in three different ways, and they solve three different problems:

Only eviction is a guess. Expiry and invalidation remove entries for a known reason; eviction removes an entry that may be needed in a second, on the bet that another is needed less. A bad policy makes the cache a slower, more expensive way of reading the database.

Three illustrations run through the lesson: a minimal example (one 16-request trace on a four-entry cache, replayed through four policies), a realistic example (ShopStream's Redis, where a price-feed scan and shopper sessions share memory with product pages) and a failure example (scan pollution, where a one-off pass over the catalogue empties the cache of everything useful).

Figure 1. Expiry, invalidation and eviction all end in the same place. How to read this: from the cache's side the three exits look identical, because the next read misses. The difference is in cause and control: the first two are decisions you make, the third is the policy's guess.

What a policy bets on

Every policy answers the same question: which entry is least likely to be needed soon? They differ in the evidence they use.

LRU and LFU need bookkeeping that FIFO does not. A textbook LRU keeps a hash map from key to a node in a doubly linked list: every hit moves the node to the front and an eviction removes the node at the back, each in constant time. The cost is a write on every read (under many threads, a lock) and two pointers per entry. A textbook LFU keeps a count per entry; the cost is the counters and, as shown below, the need to age them.

Minimal example: one trace, four policies

A cache holds four entries. The requests are 16 keys in order: two staples, A and B, read three times each, then a one-off scan of six products that will never be read again (s1 to s6, say a nightly job walking the catalogue), then the staples again. Four policies replay it:

• FIFO and LRU as defined above, and LFU, evicting the lowest count and, on a tie, the entry that arrived first.
• Two-segment LRU, a small model of a design described later: a probation half and a protected half of two entries each. A new key enters probation; a hit in probation promotes it to protected; a protected entry pushed out falls back to probation; evictions come from probation.

The results (from a short replay script; exact for this trace, and nothing more than that for a real workload):

After request 12, when the scan has finished, FIFO and LRU both hold s3, s4, s5, s6: six one-off keys pushed out two entries that were read three times each, costing two extra misses at 13 and 14. LFU holds A, B (counts of 3 each) and s5, s6, and the two-segment cache holds A, B in protected and s5, s6 in probation: the scan keys only ever compete with each other for two slots.

LRU and FIFO tie here because the staples are not re-read between the scan's start and end. The point is the scan: recency alone cannot tell a one-off read from the start of a new hot streak.

Failure example: scan pollution, and the opposite failure of LFU

Scan pollution is what the example showed. A table scan, an export, a crawler or a full-catalogue refresh reads many entries once each; under LRU each becomes the most recently used entry and pushes out something useful. The hit ratio collapses and the database sees the load the cache was meant to absorb. The InnoDB buffer pool documentation describes exactly this: a "table scan, performed for a mysqldump operation or a SELECT statement with no WHERE clause" can bring a large amount of data into the pool and evict an equivalent amount of older data, "even if the new data is never used again".

The mirror-image failure belongs to frequency. In a second trace, a cache of three entries serves X Y Z ten times over (30 requests), after which traffic moves to three new products, P Q R, six rounds (18 requests):

LFU never adapts. X, Y and Z each hold a count of ten; each new key arrives with a count of one, so the next newcomer evicts it and the new hot set never gets in. Every real LFU has to forget: frequency counts must decay.

Figure 2. Each simple policy has a workload that breaks it. How to read this: the left branch is recency's blind spot, the right branch is frequency's. Real systems combine the two signals.

What real caches do

Production caches approximate the textbook versions, to save memory and locks, and add a defence against one or both failures above.

Protect proven entries: midpoint and segmented LRU

InnoDB manages its buffer pool as an LRU list with midpoint insertion. A page read into the pool enters the middle of the list, at the head of the "old" sublist (3/8 of the pool by default), and an access to a page in the old sublist makes it "young", moving it to the head of the young sublist. The manual is candid that the defaults do not fully solve the scan problem: by default, pages read by queries are moved into the young sublist at once, so a large scan can still push frequently used pages toward the old sublist, and it refers to a delay setting, innodb_old_blocks_time. The lesson for your own cache: scan resistance comes from making a new entry prove itself with a second access, and it only works if the first access does not count as proof. The two-segment model above makes that rule explicit.

Admit only what earns a place: TinyLFU and W-TinyLFU

Instead of changing what is evicted, change what is let in. The TinyLFU paper (Einziger, Friedman and Manes, 2015) proposes a frequency-based admission policy: use recent access history to decide whether a new item should replace the eviction candidate, with a compact approximate structure to hold the frequencies. The authors report simulations in which it improves various replacement policies, and present W-TinyLFU, a combined scheme. The Java library Caffeine implements it: a small admission LRU "window" evicts into a large segmented LRU if the TinyLFU filter accepts the entry. Its documentation says LRU "may have a poor hit rate in cases like full scans" and that the policy gives "a substantial improvement to LRU across a variety of workloads": the authors' own measurements, not a guarantee for your traffic.

Approximate it: sampling in Redis

Redis does not keep a true LRU list, because that costs more memory. Per its documentation, "it samples a small number of keys at random and then evicts the ones with the longest time since last access"; from Redis 3.0 it also keeps a pool of good eviction candidates, which brings it close to true LRU. The sample size is maxmemory-samples (the documented example shows 5); 10 approximates true LRU more closely at some extra CPU. For power-law access, the documentation reports little or no difference between true LRU and the approximation.

Redis LFU (from Redis 4.0) is approximate too: a probabilistic Morris counter in a few bits per object (range 0 to 255), sampled the same way and decayed so that old popularity fades. Two settings control it, shown with their documented example values:

lfu-log-factor 10
lfu-decay-time 1

lfu-decay-time is the number of minutes after which a sampled counter is decayed (0 means never). lfu-log-factor sets how many hits saturate the counter: with 10 it reaches 255 at about a million hits, with 100 about ten million; a lower factor gives finer resolution for low counts.

TTL and eviction together

TTL is a freshness rule that also frees memory, and the two mechanisms interact.

• Expired is not gone. Redis expires keys passively, when a client touches a timed-out key, and actively, by periodically testing a few random keys among those with an expiry. A key never read again may sit in memory past its expiry until sampling finds it.
• An expiry costs memory, so allkeys-lru is more memory efficient than a volatile-* policy, which needs the expiry to exist.
• Overwriting clears the TTL. In Redis, SET on a key with a TTL removes it (DEL, SET, GETSET and the *STORE commands clear it; INCR, LPUSH and HSET leave it). A cache-aside refresh that writes with a plain SET quietly turns an expiring entry into a permanent one that only eviction can remove.
• Short TTLs reduce eviction, because keys often expire before they need to be evicted.

Redis policies at a glance

maxmemory sets the limit (0 means no limit, the default on 64-bit systems) and maxmemory-policy chooses what happens at it.

The volatile-* policies behave like noeviction when no key has an expiry. The documentation's rule of thumb: allkeys-lru when a subset of keys is read far more than the rest (a good default if you have no reason to prefer another); allkeys-random when all keys are accessed about equally, such as a repeating cycle; volatile-ttl when your code can assign short TTLs to the good eviction candidates. It suggests two instances rather than one for cache keys plus persistent keys, if possible.

Choosing a policy

Figure 3. A starting point, not a verdict. How to read this: a cache that holds the only copy of something is a database, so answer the first question honestly, then ask about scans and stability. Measure whatever you choose against your own traffic.

Two practical points sit around the choice. First, keep scans out of the cache: a batch job that reads every product once should read the database without writing cache entries, which fixes the problem at the source whatever the policy. Second, size the cache for the hot working set: if it is smaller, no policy can save the hit ratio.

Trade-offs

In practice: one Redis for sessions, product pages and a nightly price feed

This is the realistic example, an educational scenario on the course's running example, ShopStream. It describes no real company, and every number is illustrative.

This is a realistic scenario, not a case history.

The situation

ShopStream runs one Redis (Stage 2) that holds shopper sessions, cached product pages for 100,000 products, and the results of a nightly price-feed job that walks every product once. The instance has a memory limit of 1 GB (illustrative) and the policy is allkeys-lru. After the feed started filling the cache, the morning hit ratio fell, database load rose, and a few shoppers were signed out.

Starting architecture

Figure 4. Three kinds of key under one eviction policy. How to read this: the feed writes one entry per product, each read once, into the same memory the product pages and sessions use. The policy cannot tell them apart, and sessions are not disposable.

Options considered

The decision

Option C. It follows the Redis documentation's advice to avoid mixing persistent and cache keys, and removes the scan at the source. The cache instance uses allkeys-lru with a larger sample size, since product traffic is skewed and shifts with promotions. Sessions go on a small instance with noeviction, so a full instance fails loudly instead of signing shoppers out, with an alarm well before the limit. The settings, as redis-cli commands (illustrative values):

> CONFIG SET maxmemory 1gb
> CONFIG SET maxmemory-policy allkeys-lru
> CONFIG SET maxmemory-samples 10

Rollout and verification

The rollout would move the feed first (it only stops writing to the cache), then the sessions, comparing three numbers against the previous week: the cache hit ratio, database queries per second, and unexpected sign-outs. Redis reports keyspace_hits and keyspace_misses in INFO stats; the documentation gives the hit ratio as keyspace_hits / (keyspace_hits + keyspace_misses) * 100. If it is lower than the hot set should deliver and evicted_keys is high, the wrong keys are being evicted too often; if evicted_keys is low and expired_keys is high, the TTLs are too short or the wrong keys are expiring. A replay of real traffic is the only honest test of a policy.

The 2 a.m. failure

The page reads: sessions are failing to write and shoppers cannot sign in. The sessions instance has reached maxmemory under noeviction, so commands that add data return errors, as designed. The checks: INFO memory, the session key count, and whether any keys lack a TTL (a SET without an expiry makes a permanent key). The mitigation is to raise the limit briefly and delete sessions that should have expired. The lasting fix is a TTL on every session write, an alarm at a fraction of maxmemory, and a capacity estimate of sessions per day times bytes per session.

Architect's notes

• State what each key is worth. Disposable cache entries, expiring sessions and durable data need different policies, usually different instances.
• Fix scans at the source. A job that reads everything once should not write the cache.
• Replay before you decide. A production trace beats any rule of thumb here; a test with uniform random keys is meaningless.
• Set a limit. Redis has no memory limit by default on 64-bit systems; set maxmemory before expecting eviction.
• Keep a TTL on everything, including entries written by a refresh path, and watch evictions and expirations separately.

Common mistakes

• Treating eviction as invalidation. An evicted entry left because of space; a wrong entry must be removed by your code.
• Never setting maxmemory, then wondering why nothing is evicted.
• Choosing LFU and forgetting decay. The cache fills with last month's favourites.
• Running scans through the cache, an expensive way to throw away your hot set.
• Mixing sessions or other must-keep keys with cache keys under an allkeys-* policy.
• Using a volatile-* policy when few keys have a TTL, or overwriting with SET and no expiry, which clears the TTL.

Key takeaways

• Eviction is about capacity; expiry is about freshness and invalidation is about correctness. Only eviction is a guess.
• FIFO ignores use, LRU bets on recency, LFU on stable popularity, random on nothing, TTL-ordered on near-expiry entries being cheapest to lose.
• LRU breaks on scans, LFU breaks when popularity shifts, so real caches add protection: segments or a midpoint, an admission filter, decayed counts.
• Redis approximates LRU and LFU by sampling, with a decaying probabilistic counter for LFU; maxmemory and maxmemory-policy are what enable eviction.
• Keep scans, sessions and other must-keep data out of an allkeys-lru cache, and watch keyspace_hits, keyspace_misses, evicted_keys and expired_keys.

Practice exercises

Exercise 1 (30 min). Replay the 16-request trace on paper for LRU and FIFO with a cache of five entries. Does the result change, and why does the scan of six keys still hurt?

Exercise 2 (45 min). Build a three-entry trace where LFU beats LRU and one where LRU beats LFU. Say in one sentence what each tests.

Exercise 3 (1 hour). For ShopStream, choose a policy, a TTL and an instance for each of five keys (session, product page, cart summary, rate-limit counter, price-feed result), and say what happens if the instance fills.

Exercise 4 (1 hour). A Redis cache runs volatile-lru and its keys are written with plain SET and no expiry. Predict what happens at maxmemory, and name two fixes.

Exercise 5 (2 hours). Write a script that replays a trace through FIFO, LRU, LFU and a two-segment LRU and prints hits per phase. Add LFU decay (halve every count every N requests) and find an N that repairs the second trace.

Related reading

• Caching Basics: why caches work, TTL and eviction in brief.
• Advanced Caching: write policies, invalidation, stampedes and hot keys.
• Cache Layers: where each layer sits and who controls it.
• ShopStream Stage 2: Scaling Reads: a three-entry LRU and LFU trace in context.

Official documentation

• Redis, Key eviction: maxmemory, the policies, the approximated LRU, LFU settings and the INFO guidance.
• Redis, EXPIRE: what clears a TTL, and how Redis expires keys (passive and active).
• MySQL 8.4 Reference Manual, The InnoDB Buffer Pool: midpoint insertion and scan behaviour.
• Einziger, Friedman and Manes, TinyLFU: A Highly Efficient Cache Admission Policy (2015).
• Caffeine, Efficiency: W-TinyLFU as implemented in the library, with the authors' own comparisons.