Systems · intermediate
Caching and LRU eviction
A cache stores reusable results closer to demand; an LRU policy evicts the entry whose most recent access is oldest when bounded capacity needs space.
Why it matters
Caching can cut latency and backend load, but stale data, key mistakes, stampedes, and a mismatched eviction policy can make the system slower or incorrect.
Mental model
How to reason about caching and lru eviction
A lookup either hits reusable state or misses and pays to fetch or compute it. Capacity forces an eviction choice; LRU predicts that recently used entries are more likely to be used again.
Analogy
A small desk holds copies of frequently consulted archive files. When the desk fills, LRU discards the desk copy that has gone untouched longest; the archive remains the source of truth.
Examples
See the boundary, not just the happy path
Worked example · Cache-aside hit and miss
read cache; on miss read database and populate cacheThe application controls population, so a miss has a defined fallback and the cached value needs an expiration or invalidation policy.
Worked example · Expected O(1) LRU operations
hash map + doubly linked recency listA hash map gives expected constant-time lookup, while the list moves or evicts known nodes without scanning the cache.
Useful contrast · Poor fit for scans
read a one-time dataset larger than the cacheThe scan can evict the useful working set even though its entries are unlikely to be reused; LRU is a heuristic, not an oracle.
Common mistakes
Misconceptions to remove early
Caching without a freshness contract
Define acceptable staleness, expiration, invalidation, and behavior after writes. Otherwise a fast answer may be observably wrong.
Letting one miss become a stampede
Many callers can regenerate the same expired key simultaneously. Request coalescing, stale-while-revalidate, or randomized expiry can protect the origin.
Quick check
Can you predict the result?
1. Which entry does an LRU cache evict?
- • The entry whose most recent access is oldest
- • Always the largest entry
- • The entry inserted most recently
2. Why are a hash map and doubly linked list commonly paired for LRU?
Keep building