Cache Invalidation & Eviction
You'll learn to
- -Explain LRU and LFU eviction
- -Explain the cache stampede problem
Eviction: What Happens When the Cache Is Full
A cache is finite memory, so once it's full, adding something new means evicting something old. Least Recently Used (LRU) evicts whatever hasn't been touched in the longest time (simple and usually a good default). Least Frequently Used (LFU) evicts whatever has been accessed the fewest times overall, which is better when "hot" items stay hot for a long time and you don't want a single recent-but-rare access to save something from eviction.
Invalidation: The Other Hard Problem
A cache is only useful if it's telling the truth. TTL-based invalidation (expire after N seconds) is simple but means you're always serving data that could be up to N seconds stale. Event-driven invalidation (bust the cache key the moment the underlying row changes) is accurate but adds real complexity: now every write path has to remember to also talk to the cache.
Cache Stampede
When a single hot key expires, every request that was previously served instantly from cache suddenly misses at the same moment, and all of them hit the database simultaneously, which can be enough load on its own to take the database down. Common fixes: a distributed lock so only one request repopulates the cache while others wait briefly, or jittering TTLs slightly per key so they don't all expire in the same instant.
A useful mental model: caching doesn't remove the hard problem of keeping data correct; it just relocates it from "how fast can I read" to "how do I know when to forget."
A celebrity's profile page just went viral and its cache entry is about to expire. What could go wrong?
"The next request will just miss and repopulate the cache, no big deal."
"That's the cache stampede scenario: the moment that one hot key expires, potentially thousands of concurrent requests all miss at the same instant and all hammer the database simultaneously to recompute the same value. I'd use a lock so only one request repopulates the cache while the rest wait briefly for it, or jitter that key's TTL slightly so it doesn't expire at the exact same moment traffic is highest."
A cache serves 950 requests directly and forwards 50 to the database out of 1,000 total. What is the hit ratio?
Level 3: URL Shortener is a caching-heavy, read-dominant system.