Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 65 ยท Caching

Cache Eviction Policies and LRU

Compare FIFO, LRU, LFU, random and TTL eviction, implement an O(1) LRU cache with a hash map and linked list, and measure hit rates on real access patterns.

A cache is small by design. When it is full and a new item must be stored, something has to go. The rule that decides what is removed is the eviction policy. A good policy keeps the items you will need soon and discards the ones you will not; a poor one throws away the hot items and fills memory with things nobody asks for again. Since the hit rate drives everything (caching fundamentals), the eviction policy is a direct lever on performance.

The perfect policy would evict the item that will be used furthest in the future (Belady's optimal algorithm), but nobody can see the future. Practical policies guess from the past.

The common policies

FIFO (first in, first out) evicts the oldest inserted item, regardless of use. It is trivial to implement but evicts popular items just because they were loaded long ago.

LRU (least recently used) evicts the item whose last access is oldest. It follows the idea of temporal locality: what you touched recently you will probably touch again. LRU is the default choice in most caches, and the policy behind the classic interview question.

LFU (least frequently used) evicts the item with the fewest accesses. It protects genuinely popular items and resists one-off scans, but it is slower to adapt: an item popular last week but not now can stay forever unless counts age or decay, and new items start with low counts and risk being evicted at once.

MRU (most recently used) evicts the newest access. It sounds odd but suits patterns like a large repeated scan, where the item just used will not be needed again for a long time.

Random evicts any item. It needs no bookkeeping, performs better than people expect and is used when tracking costs more than it gains (Redis offers sampled variants of LRU and LFU for exactly this reason).

TTL (time to live) is not about space but about time: each item expires after a set period. It is usually combined with one of the above (invalidation).

Eviction policies at a glance

FIFO Oldest inserted leaves first. Simple, ignores use.
LRU Longest unused leaves first. The common default.
LFU Least used overall leaves first. Favors popular items.
Random No bookkeeping. Surprisingly decent.

Match the policy to how your traffic behaves.

1 / 2

Building an LRU cache

An LRU cache must support two operations in O(1) time: get(key) (and mark it as most recently used) and put(key, value) (evicting the least recently used if full). The classic solution combines two structures:

  • A hash map from key to a node, for instant lookup.
  • A doubly linked list ordered by recency: the head is the most recently used, the tail the least recently used. Moving a node to the head, or removing the tail, takes constant time because each node knows its neighbors.
flowchart LR
  H["head<br/>most recent"] <--> A["key C"] <--> B["key A"] <--> C["key B"] <--> T["tail<br/>least recent"]
  M["hash map<br/>key to node"] -.-> A
  M -.-> B
  M -.-> C

Figure: the map finds the node, the list tracks the order; on access the node moves to the front, and the tail is evicted when full.

Python LRU cache from scratch: map plus doubly linked list

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.

After touching A, the least recently used key is B, so adding D evicts B, not A. Python's standard library gives you the same behavior in a few lines with collections.OrderedDict, which keeps insertion order and can move an item to the end in O(1):

Python LRU with OrderedDict

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.

Policies compared on real patterns

Which policy is best depends on the access pattern. The simulation below implements FIFO, LRU, LFU and random and runs each on three workloads: skewed popularity (a few hot keys), recency (a moving window of recent keys) and a scan (a long sequential pass over keys, which should not wipe out the hot set).

Python FIFO vs LRU vs LFU vs random

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.

Read the table by row. On skewed popularity, LFU is strongest because it protects the hot keys. On the sliding-recency workload, LRU and FIFO shine, while LFU struggles because old keys keep high counts. With scans, LRU gets flushed by the stream of one-time keys, while LFU keeps the hot set. No single policy wins everywhere, which is why production caches offer several and why measurement beats guessing.

Practical variants

  • LRU-K and 2Q: only promote an item after it has been seen more than once, so a one-time scan does not push out useful data.
  • ARC and LIRS: adaptive policies that balance recency and frequency automatically.
  • TinyLFU / W-TinyLFU: used by modern libraries (such as Caffeine): a compact frequency sketch decides whether a newcomer deserves to replace a victim. Excellent hit rates with low overhead.
  • Approximate LRU: Redis samples a few random keys and evicts the oldest of the sample, avoiding a full list.
  • Size-aware eviction: when objects differ greatly in size, account for bytes, not item count, or one huge object can evict hundreds of small ones.
  • TTL plus LRU: expired entries leave first; LRU decides among the rest.

Choosing a policy

  1. Start with LRU; it is a strong, simple default.
  2. If you have stable, heavily skewed popularity or large scans, try LFU or TinyLFU.
  3. If CPU for bookkeeping is the limit, use random or sampled eviction.
  4. Measure hit rate and eviction rate in production, and test with a replay of real traffic.
  5. Size the cache so the evicted entries are mostly ones nobody wants.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does LRU evict?

    LRU removes the least recently used item, assuming recent items will be used again.
  2. 2. Which two structures give an O(1) LRU cache?

    The map finds a node in O(1); the linked list reorders and removes in O(1).
  3. 3. Why can a large one-time scan hurt an LRU cache?

    Every scanned key becomes most recently used, evicting useful data that will not be reloaded soon.
  4. 4. What is a weakness of plain LFU?

    Without aging, old counts keep stale items in the cache and newcomers are evicted too quickly.
  5. 5. Why does Redis use sampled approximate LRU?

    Sampling a few keys gets close to true LRU at much lower bookkeeping cost.

Summary

  • Eviction decides what leaves a full cache; it directly affects the hit rate.
  • FIFO ignores use, LRU favors recency, LFU favors popularity, random needs no bookkeeping, TTL expires by time.
  • An O(1) LRU cache uses a hash map plus a doubly linked list (or an ordered dictionary).
  • No policy wins every workload: scans hurt LRU, drift hurts LFU; modern variants (2Q, ARC, TinyLFU) mix the two.
  • Start with LRU, then measure and tune using real traffic.

Next: Cache Invalidation and TTL