Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 37 ยท Caching Concepts

Eviction Policies: LRU, LFU and FIFO

Compare cache eviction policies (FIFO, random, LRU, LFU), implement them in Python, run them on one request trace, and learn how Memcached's segmented LRU works.

Memory is finite. When Memcached is full and a new item arrives, it must throw something away to make room. The rule that decides what to throw away is the eviction policy. A good policy keeps items that will be asked for again and discards items that will not; since the future is unknown, every policy is a guess based on the past.

This lesson compares the classic policies, lets you run them on the same traffic, and then explains what Memcached actually does.

The classic policies

Policy Evicts Idea Weakness
FIFO The oldest inserted item Simple queue Ignores how often an item is used
Random A random item No bookkeeping Can evict a very hot item
LRU (least recently used) The item untouched for longest Recent use predicts future use A scan can flush the hot set
LFU (least frequently used) The item with the fewest accesses Popular items stay Old favourites linger; slow to adapt
TTL-aware Expired items first Free space costs nothing Only helps if items expire

Implementing four policies

The code below builds each policy as a small class with the same interface: access(key) returns True for a hit. LRU uses an OrderedDict; LFU keeps a counter per key.

Python FIFO, Random, LRU and LFU side by side

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On a steady, skewed workload like this one, LRU and LFU clearly beat FIFO and random. LFU is often best here because the popularity never changes. Now change the traffic.

Where LRU hurts: a scan

Add a one-time scan, say a batch job that reads 1,000 items once. LRU treats every scanned item as "recently used", so the hot items get pushed out.

Python A scan flushes LRU

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first 200 requests after the scan suffer because the hot items were evicted and must be reloaded from the database. Real caches defend against this with smarter policies.

What Memcached does: segmented LRU

Memcached does not run one big list. Since version 1.5 it uses a segmented LRU per slab class, with sub-queues:

  • HOT: newly stored items enter here. It is a short queue.
  • WARM: items that have been hit while cold move here and are protected from quick eviction.
  • COLD: the eviction candidates. Items fall into COLD from HOT or WARM; the tail of COLD is what actually gets evicted.
  • TEMP: very short TTL items (under about 60 seconds by default) that are never bumped.

A background LRU maintainer thread shuffles items between segments, so a read does not need to take a heavy lock to reorder a global list. The effect resembles the scan-resistant "2Q" family of algorithms: an item has to be used again to be promoted, so one-time scans stay in the cold segment and are evicted first.

Memcached also checks expired items before evicting live ones: if the tail item has already expired, it is reclaimed for free and the reclaimed counter rises. Only when no expired item is available does it evict a live one, and that increments evictions.

Two practical consequences follow. First, eviction is per slab class, not global, a point explored in Performance and Sizing. Second, you cannot choose LFU or tune the policy per key; you tune size, TTLs and item sizes.

Choosing a TTL helps eviction

Short TTLs make eviction cheaper: expired items disappear without displacing a live one. Long TTLs on cold data fill the cache with things nobody asks for. The next lesson covers expiry rules in detail.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does LRU evict?

    Least recently used: the item whose last access is oldest.
  2. 2. Why can a full scan hurt a plain LRU cache?

    Plain LRU promotes every touched key, even ones that will never be seen again.
  3. 3. Which Memcached segment holds the items that are evicted first?

    Items drift to COLD, and the tail of COLD is evicted. Items hit while cold are promoted to WARM.
  4. 4. What does Memcached do before evicting a live item?

    Expired items are free space. The reclaimed counter counts those; evictions counts live items thrown away.

Summary

  • An eviction policy decides what to discard when memory is full; every policy is a guess about the future.
  • FIFO and random are simple; LRU favours recency; LFU favours frequency.
  • Plain LRU is vulnerable to scans; segmented LRU (HOT/WARM/COLD) resists them.
  • Memcached reclaims expired items before evicting live ones, and evicts per slab class.
  • You cannot pick the algorithm, but TTLs and sizing influence it strongly.

Next: TTL and Expiration