Cache eviction policies - LRU, LFU, and TTL explained
LRU eviction, LFU eviction, TTL expiry, FIFO, random eviction, cache size limits, eviction policy trade-offs
What Eviction Is
When a cache is full and a new item needs to be stored, the cache must evict something. The eviction policy determines what gets removed.
LRU - Least Recently Used
Evicts the item that hasn't been accessed for the longest time. Best for workloads with temporal locality - recently accessed items are likely to be accessed again soon.
# LRU in Python using OrderedDict
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key)
return self.cache[key]
return -1
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)LFU - Least Frequently Used
Evicts the item accessed fewest times total. Better for workloads with stable hot items (popular products, frequent queries). But new items are vulnerable - they start at frequency 1 and may be evicted before becoming popular.
TTL - Time To Live
Items expire after a fixed time regardless of access. Simple, predictable. Use for data with known staleness tolerance: weather data (TTL 10 min), session tokens (TTL 24h), product catalog (TTL 1h).