Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Caching

System Design HLD-05.03

Eviction policies

When the cache is full, what goes? LRU, LFU, FIFO, random and TTLs compared on real access patterns, and how Redis approximates them.

Intermediate 10 min Last reviewed

The big idea

A cache is always smaller than the data behind it, so it fills up. When a new item arrives and there is no room, the cache must throw something out. The rule it uses is the eviction policyThe rule a full cache uses to choose which entry to remove to make room for a new one., and it quietly decides the hit ratio. Evict the wrong things and the cache keeps discarding data it will need again a moment later; evict the right ones and a small cache serves most requests.

Every policy is a bet about the future. LRU bets that what was used recently will be used again soon. LFU bets that what has been popular will stay popular. FIFO and random barely bet at all. Which bet wins depends on how your data is actually accessed.

Think of a small fridge. When it is full and you bring home groceries, you could throw out whatever you have not touched for longest (LRU), whatever you rarely use (LFU), whatever went in first (FIFO), or something at random.

How it works

Step 1: The policies

  • LRU (least recently used): evict the entry not accessed for the longest time. Great for most workloads with temporal locality. It is fooled by a single large scan, which pushes out everything hot.
  • LFU (least frequently used): evict the entry with the fewest accesses. Protects long-term favorites from one-off scans, but is slow to adapt when popularity shifts, because old favorites keep their high counts. Real implementations decay counts over time.
  • FIFO: evict the oldest inserted entry, regardless of use. Simple, but throws out hot items just because they are old.
  • Random: evict any entry. Surprisingly decent, and needs no bookkeeping.
  • TTL: entries expire after a fixed time whether or not the cache is full. TTL bounds staleness; it is used together with one of the above for capacity.
LRU cache slots ordered by recency Five cache slots ordered from most recently used on the left to least recently used on the right: E, A, D, B, C. A new item F arrives; C, the least recently used, is evicted and shown in red, and F enters on the left. F new E just used A 1 s ago D 4 s ago B 9 s ago C 30 s ago evicted most recent -> least recent Figure 1. An LRU cache keeps entries ordered by last use. Every hit moves an entry to the front; when a new item arrives at a full cache, the entry at the back (least recently used, red) is evicted.

Step 2: LRU in a few lines

LRU can be done in constant time per operation with a hash map plus a linked list ordered by recency. Python's OrderedDict is exactly that:

lru.pyruns with python3 (standard library)
from collections import OrderedDict

class LRUCache:
    """Evicts the least recently used key. Every operation is O(1)."""
    def __init__(self, capacity):
        self.capacity, self.data = capacity, OrderedDict()
        self.hits = self.misses = 0

    def get(self, key):
        if key not in self.data:
            self.misses += 1
            return None
        self.hits += 1
        self.data.move_to_end(key)            # mark as most recently used
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            evicted, _ = self.data.popitem(last=False)   # oldest use is at the front
            print(f"  evict {evicted}")

cache = LRUCache(capacity=3)
for key in ["A", "B", "C", "A", "D", "B", "E", "A"]:
    if cache.get(key) is None:
        print(f"miss {key}")
        cache.put(key, f"value-{key}")
    else:
        print(f"hit  {key}")
print("order (least to most recent):", list(cache.data), f"| hits {cache.hits}, misses {cache.misses}")

Output

miss A
miss B
miss C
hit  A
miss D
  evict B
miss B
  evict C
miss E
  evict A
miss A
  evict D
order (least to most recent): ['B', 'E', 'A'] | hits 1, misses 7

With three slots, the trace A B C A D B E A gets only one hit: each new key evicts something that is needed again a little later. A tiny cache facing a working set larger than itself performs badly under any policy.

Step 3: Approximations at scale

Exact LRU needs to update a shared list on every read, which is costly with many threads and millions of keys. Production caches approximate it. Redis, for example, samples a handful of keys at random when it needs to evict and removes the least recently used among the sample; with a sample of a few keys this behaves close to true LRU at a fraction of the cost. Redis also offers an LFU mode with counters that decay over time, and volatile-* modes that only evict keys with a TTL.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Skewed: popularity here is stable, so LFU, which counts long-term popularity, clearly wins. LRU does no better than random on this trace.
  2. Skewed + one-off scan: watch the red band in the middle of the strip for LRU: the scan flushes the hot items. LFU keeps them, because the scanned items are only used once.
  3. Popularity shifts: now LFU struggles after the switch, clinging to yesterday's favorites, while LRU adapts.
  4. Loop of 12 items with 10 slots: LRU gets almost nothing, always evicting the item needed next. Random does better. Then give the cache 12 slots.

Going deeper

The working set

The working setThe set of items a workload actively uses over a period of time. is the data actively in use over a period. If the cache can hold the working set, almost any policy works; if it cannot, the policy matters a lot, and adding memory may help more than tuning. Measure the hit ratio as you vary cache size: the curve usually rises steeply, then flattens once the working set fits.

Admission is the other half

Modern caches also decide whether to admit a new item at all. Policies such as TinyLFU keep a compact frequency sketch and only admit a newcomer if it is likely to be used more than the item it would replace, which defeats scans while still adapting to change.

Trade-offs

OptionWins whenLoses when
LRU General workloads with recency: sessions, feeds, recently viewed items Large one-off scans and loops slightly larger than the cache
LFU (with decay) Stable popularity with occasional scans: product catalogs, static content Fast-changing popularity, unless counts decay quickly
FIFO or random Very simple caches, or when bookkeeping cost matters more than hit ratio Hit ratio on skewed workloads
TTL Bounding staleness of data that changes Capacity management on its own; combine it with LRU or LFU

Common mistakes

  • Picking a policy without measuring the real access pattern and hit ratio.
  • Letting batch jobs or analytics scans read through the same cache as user traffic, flushing the hot set.
  • Relying on eviction alone for freshness. Eviction is about space; TTLs and invalidation are about correctness.
  • Running a cache with no memory limit, so the operating system kills it instead of it evicting.

Check yourself

  1. A nightly report reads every product once. Which policy is most hurt?

    Show answer

    B. LRU The scan makes every scanned item most recently used, pushing out the hot set under LRU; LFU keeps frequently used items.

  2. Trending topics change every hour. Which policy adapts poorly unless counts decay?

    Show answer

    B. LFU LFU keeps old favorites with high counts long after they stop being requested.

  3. Why does Redis approximate LRU instead of tracking it exactly?

    Show answer

    B. Maintaining exact recency order for millions of keys on every read is costly; sampling is close and cheap Evicting the least recent among a small random sample behaves close to LRU with far less bookkeeping.

  4. What is the role of a TTL compared with an eviction policy?

    Show answer

    B. TTL bounds how stale data can get; eviction decides what to drop when the cache is full One is about freshness, the other about capacity.

Recap

  • A full cache must evict; the policy is a bet about which data will be needed again.
  • LRU bets on recency and is beaten by scans; LFU bets on frequency and is slow to adapt.
  • FIFO and random are simple and weaker on skewed traffic.
  • Production caches approximate LRU and LFU by sampling and decaying counters.
  • If the working set fits, policy matters little; if not, measure and choose.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up