Cache Eviction, Invalidation, TTL & Cache Stampede
What to remove when the cache is full, when to remove stale data, and how to stop everything from crashing onto the DB at once: all covered here.
10.1 Why is it used?
- Cache RAM is limited, so some keys must be removed when it fills up; the eviction policy decides which ones.
- If data changed in the DB but the cache still holds the old value, the user sees a wrong price/stock; invalidation is needed.
- The moment a popular key expires, thousands of requests hit the DB together (cache stampede / thundering herd) and the DB goes down.
- A single hot key (like an IPL score) gets so much traffic that one cache node gets overloaded.
10.2 How it works
- LRU (Least Recently Used): remove the key that has not been used for the longest time. The most common.
- LFU (Least Frequently Used): remove the key that has been used the fewest times; popular data stays.
- FIFO / Random / TTL-based: simple policies; in Redis via maxmemory-policy values such as allkeys-lru, allkeys-lfu, volatile-ttl.
- TTL (Time To Live): an expiry for every key, e.g. 60 sec, after which it is deleted automatically. Add jitter (random +-10%) so that all keys do not expire together.
- Invalidation: on a DB update, delete the cache key (delete is better than update), or clear the cache using events (CDC/Kafka).
- Stampede fix 1, locking / request coalescing: on a miss only one request goes to the DB (Redis SETNX lock) and the rest wait.
- Stampede fix 2, stale-while-revalidate / early refresh: refresh in the background before expiry and serve the old data until then.
- Hot key fix: keep a copy in the local cache, replicate the key (key#1..key#N) across different nodes, use read replicas.
- Cache penetration: repeated requests for a key that does not exist in the DB all reach the DB; cache a null value with a short TTL or add a Bloom filter.
- 1.A popular key (match:score, TTL 2 sec) expires
- 2.Crores of requests MISS together -> all go to the DB (thundering herd)
- 3.DB CPU hits 100%, DB goes down
- 4.Fix: one worker takes the lock with SET lock:match NX EX 2
- 5.The remaining requests serve the 1-2 sec old (stale) score
- 6.The worker makes 1 query to the DB/score service and refreshes the cache
Result: the DB gets one query every 2 sec, not lakhs
- 1.App: UPDATE price in MySQL
- 2.Do not update the cache, DELETE: DEL price:12
- 3.Debezium reads the CDC binlog
- 4.The change event goes to Kafka
- 5.A consumer clears the cache key and the next read loads fresh data
- 6.TTL = 60s +- 10% jitter (54-66s), so all keys do not expire together
Varnish / Nginx do the same with proxy_cache_lock + stale-while-revalidate
10.3 Tools
| Tool | Type | How it is used |
|---|---|---|
| Redis | In-memory store | LRU/LFU eviction via maxmemory-policy, TTL via EXPIRE, stampede lock via SET NX. |
| Memcached | In-memory cache | Built-in LRU (segmented) eviction and TTL support. |
| Caffeine (Java) | Local cache | W-TinyLFU eviction, background refresh via refreshAfterWrite. |
| Varnish / Nginx proxy_cache | HTTP cache | They stop stampedes with options such as proxy_cache_lock and stale-while-revalidate. |
| Debezium + Kafka | CDC pipeline | Used to capture DB change events and invalidate the cache. |
| CloudFront / Akamai | CDN | Edge caches are cleared via TTL, Cache-Control headers and the invalidation API. |
10.4 Comparison: LRU vs LFU vs TTL-based eviction
| Point | LRU | LFU | TTL-based |
|---|---|---|---|
| What it removes | The least recently used item | The least frequently used item | The item whose expiry is nearest / already passed |
| Good when | Recent data is read the most | Some items are always popular (top products) | Data goes stale after some time |
| Weakness | One big scan pushes out all the hot data | Old popular items stick around and new ones get no room | RAM can fill up if the TTL is long |
| Complexity | Simple (hashmap + linked list) | Slightly higher (counters + decay) | Simple |
| Redis policy | allkeys-lru / volatile-lru | allkeys-lfu / volatile-lfu | volatile-ttl |
| Best for | General web cache, sessions | Product catalog, trending content | Price, OTP, rate limit counters |
10.5 When to choose which
- LRU: the default choice when you do not know the access pattern.
- LFU: when some items stay popular for a long time (top 100 products, famous videos).
- TTL + jitter: always apply it, whatever the eviction policy; it puts a fixed limit on staleness.
- Lock / request coalescing: when the DB query for one key is expensive and traffic is very high.
- Local cache + key replication: when a single hot key gets lakhs of QPS (live score, sale banner).
10.6 Real-world example
Hotstar IPL live score (an illustrative scenario)
- In the final, crores of users read the same key match:score: a classic hot key.
- The score key has a TTL of 2 sec; if everyone went to the DB the moment it expires, there would be a thundering herd.
- So on a miss only one worker takes the Redis lock with SET lock:match NX EX 2 and fetches the new score from the DB/score service.
- The remaining requests meanwhile serve the old score (1-2 sec stale): stale-while-revalidate.
- The hot key is also held in the app servers' local cache for 1 sec, so the load on the Redis node is lower.
- When the cache fills up, allkeys-lru removes old, rarely viewed keys (old match stats).
- Result: the DB gets one query every 2 sec, not lakhs.
10.7 Interview tips
- Giving all keys the same TTL is a mistake: they expire together and the DB gets a spike; add jitter.
- Updating the cache instead of deleting it after a DB update is a mistake: in a race condition a stale value stays.
- Not setting maxmemory is a mistake: Redis can fill the RAM and crash with an OOM.
- Interview tip: "There are only two hard things: cache invalidation and naming things"; state your invalidation strategy clearly. Number: TTL 60 sec + 10% jitter = 54-66 sec.