Cache Eviction Policies
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.
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 usedRedis 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?
You May Also Like
Why Caching Matters
Explains the core motivation for caching in system design — reducing latency and load by storing frequently accessed data closer to where it's needed.
Cache Invalidation Strategies
Explores how systems keep cached data consistent with the source of truth, covering TTLs, write-through/write-behind patterns, and explicit invalidation on updates.
CDN Caching and Edge Computing
Covers how Content Delivery Networks cache content close to users to cut latency, and how edge computing extends this to running logic near the request origin.
Database Indexing at Scale
Explains how indexes accelerate queries via data structures like B-trees, and the tradeoffs of adding, maintaining, and choosing indexes on very large tables.
Related Reading
Related Study Notes in Software Engineering
Browse all study notesMicroservices Study Notes
Software Architecture · 30 topics
Software EngineeringTesting & TDD Study Notes
Software Testing · 30 topics
Software EngineeringDesign Patterns Study Notes
Software Design · 30 topics
Software EngineeringSoftware Engineering Study Notes
Python · 75 topics
Software EngineeringGit & Version Control Study Notes
Bash · 40 topics