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.
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.
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:
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
Try this:
- Skewed: popularity here is stable, so LFU, which counts long-term popularity, clearly wins. LRU does no better than random on this trace.
- 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.
- Popularity shifts: now LFU struggles after the switch, clinging to yesterday's favorites, while LRU adapts.
- 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
| Option | Wins when | Loses 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
-
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.
-
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.
-
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.
-
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.
Next up
- Crack the system design round learning path