Cache Eviction Policies

Analogy categoryAnalogies

A cache has finite capacity, so once it's full, adding a new entry requires deciding what to remove — this decision is the eviction policy, and it directly determines the cache's hit ratio in practice. A poorly chosen policy can evict data that was about to be reused, while a well-matched policy keeps the genuinely 'hot' working set resident even under memory pressure. There's no universally best policy; the right choice depends on the access pattern of the workload, which is why production caches (Redis, CDNs, CPU caches) typically offer several policies to choose from.

🏏

Cricket analogy: A team's 15-player World Cup squad has a hard cap, so adding a uncapped young allrounder means dropping someone — drop the wrong veteran and you lose a player who was about to be needed for the next match.

Recency-Based: LRU

Least Recently Used evicts the entry that hasn't been accessed for the longest time, on the theory that data used recently is likely to be used again soon (temporal locality) — a pattern that holds for a large share of real workloads, from web sessions to database query results. LRU is typically implemented with a doubly linked list plus a hash map: the hash map gives O(1) lookup, and the linked list is reordered on every access so the least-recently-used item is always at the tail, giving O(1) eviction. LRU's weakness is that a single large sequential scan (e.g. a batch export job) can flush the entire cache of genuinely hot items, since every scanned item becomes 'most recent' even though it won't be accessed again soon. Least Frequently Used (LFU) takes a different approach, evicting the entry with the lowest access count instead, which handles the sequential-scan problem better than LRU since one-time scanned items never accumulate a high frequency count. But LFU has its own weakness: an item that was extremely popular in the past but is no longer relevant can retain a high frequency count and resist eviction long after it stopped being useful (this is sometimes mitigated with decayed/aging frequency counts). LFU is also more expensive to maintain, since every access requires updating and potentially reordering a frequency structure rather than a simple linked-list move.

🏏

Cricket analogy: LRU is like a captain rotating fielders based on who's been most active in the last few overs — usually right, but a bowler having one long spell of dot balls (a scan) can push a genuinely key fielder out of position.

Simpler Policies: FIFO and TTL

FIFO evicts the oldest-inserted entry regardless of access pattern — simple to implement but generally worse than LRU/LFU because insertion order has no necessary relationship to future usefulness. TTL (time-to-live) isn't strictly an eviction policy for capacity pressure but a complementary mechanism: entries expire automatically after a fixed duration regardless of access pattern, which bounds staleness and is essential whenever correctness requires that cached data not live forever, independent of memory pressure. Most production systems combine a capacity-driven policy (LRU or LFU) with TTLs for correctness.

🏏

Cricket analogy: FIFO drops the player who joined the squad earliest regardless of current form — simple but arbitrary, unlike TTL, which is more like an automatic fitness re-test after a fixed number of weeks that anyone must pass, hot form or not.

python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = OrderedDict()  # preserves insertion/access order

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

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)  # evict least recently used

Redis supports multiple eviction policies configurable via maxmemory-policy, including allkeys-lru, allkeys-lfu, volatile-ttl (evict the entry closest to expiring among those with a TTL set), and noeviction (reject writes once full). Choosing volatile-ttl versus allkeys-lru is a real production decision depending on whether TTL proximity or access recency better reflects which data is safe to drop.

A common mistake is assuming LRU is always the right default. Workloads with large sequential scans (batch jobs, full-table exports) can trigger 'cache pollution' under plain LRU, flushing genuinely hot data purely because the scan touched more recent items. Some systems mitigate this with a scan-resistant variant (e.g. LRU-K or splitting the cache into probationary and protected segments) rather than assuming plain LRU handles every access pattern well.

Eviction policies decide what to remove from a full cache, and the choice directly affects hit ratio.
LRU evicts the least-recently-accessed item, exploiting temporal locality, implemented efficiently with a hash map plus linked list.
LFU evicts the least-frequently-accessed item, resisting one-time scans better but costing more to maintain and risking stale popularity.
FIFO is simple but ignores access patterns entirely, generally underperforming LRU/LFU.
TTL expires entries after a fixed duration for correctness, independent of memory pressure, and is often combined with a capacity-based policy.
Large sequential scans can pollute an LRU cache; scan-resistant variants or segmented caches mitigate this.

Practice what you learned

1. What principle does LRU eviction rely on?

2. What data structures are typically combined to implement LRU with O(1) get and put?

3. Why can a large sequential scan hurt a plain LRU cache?

4. What weakness does LFU have that LRU does not share?

5. What is the purpose of a TTL (time-to-live) on a cache entry?

Was this page helpful?

Why Caching Matters

Cache Invalidation Strategies

Related Study Notes in Software Engineering

Browse all study notes

Software Engineering

Microservices Study Notes

Software Architecture · 30 topics

Software Engineering

Testing & TDD Study Notes

Software Testing · 30 topics

Software Engineering

Design Patterns Study Notes

Software Design · 30 topics

Software Engineering

Software Engineering Study Notes

Python · 40 topics

Software Engineering

Git & Version Control Study Notes

Bash · 40 topics

Topics covered

#Architecture#SystemDesignStudyNotes#SoftwareEngineering#CacheEvictionPolicies#Cache#Eviction#Policies#Recency#StudyNotes#SkillVeris

Cache Eviction Policies