Recap — Cache Patterns, Invalidation, Eviction

# Cache Patterns, Invalidation, Eviction Caching is the most impactful performance lever in system design. A 99% cache hit ratio means your origin sees 1% of the load. "There are only two hard things in computer science: cache invalidation and naming things." — Phil Karlton ## Cache layers (from client to origin) ``` [Browser cache] → [CDN] → [LB cache] → [App cache] → [DB cache] → [Origin DB] 1ms 5ms 1ms 1ms 1ms 50ms ``` Each layer absorbs load. The earlier (closer to user), the better. | Layer | What's cached | TTL | |---|---|---| | Browser | Static assets, API responses | minutes to days | | CDN | Static files, sometimes API | minutes to hours | | App-level (Redis, Memcached) | Computed objects, sessions | seconds to days | | DB query cache | Recently-run queries | minutes | | OS / disk cache | Filesystem reads | automatic | ## Three caching patterns ### Pattern 1: Cache-aside (lazy loading) App checks cache first; on miss, fetches from DB and stores in cache. ```python def get_user(user_id): user = cache.get(f"user:{user_id}") if user is None: user = db.query("SELECT * FROM users WHERE id = ?", user_id) cache.set(f"user:{user_id}", user, ttl=300) return user ``` Pros: simple; only caches what's actually requested. Cons: cache miss = full DB hit; stale data if not updated on writes. ### Pattern 2: Write-through Writes go to cache AND DB simultaneously. ```python def update_user(user_id, data): db.update(user_id, data) cache.set(f"user:{user_id}", data, ttl=300) ``` Pros: cache always consistent. Cons: extra latency on writes; cache may hold rarely-read data. ### Pattern 3: Write-behind (write-back) Writes go to cache immediately; flushed to DB asynchronously. ```python def update_user(user_id, data): cache.set(f"user:{user_id}", data) queue.enqueue(("update_db", user_id, data)) ``` Pros: fast writes. Cons: data loss if cache dies before flush; complexity. **In practice**: cache-aside is the default for most apps. Write-through where consistency matters. Write-behind for write-heavy systems where some data loss is tolerable. ## Eviction policies When cache is full, what to remove? ### LRU (Least Recently Used) Evict the item not accessed for longest. Most common default; works for general workloads. ### LFU (Least Frequently Used) Evict the least-accessed item. Better when access patterns have a long tail. ### TTL (Time To Live) Item expires after N seconds. Combined with LRU/LFU; first expired-by-TTL, then LRU among the rest. ### FIFO Evict oldest by insertion time. Rarely optimal; sometimes used for size-bounded caches. ### Random Evict a random item. Surprisingly OK for some workloads; cheap to implement. Redis defaults to LRU-with-TTL hybrid. Configurable. ## The hard problem: cache invalidation How do you ensure cached data isn't stale? ### Strategy 1: TTL (expire after time) Set TTL; data refreshes when TTL expires. Pros: simple; eventually consistent. Cons: stale data until TTL; tunable trade-off (short TTL = fresher but more DB hits). ### Strategy 2: Explicit invalidation (write-through or pub/sub) When data changes, invalidate or update the cache. ```python def update_user(user_id, data): db.update(user_id, data) cache.delete(f"user:{user_id}") # next read will refetch ``` Pros: cache is fresh. Cons: harder to track all cache keys for a piece of data; bugs lurk here. ### Strategy 3: Versioning Embed a version in the key. ```python cache_key = f"user:{user_id}:v{version}" ``` When schema changes or you want a hard reset, bump version. Old keys age out naturally. ### Race conditions Two writers update the DB; one's cache invalidation arrives at a different time. Cache ends up stale. Solutions: - Use a single cache per data item (no replication issues). - Use distributed locks (rare; complex). - Accept eventual consistency (most common). ## Cache stampede (thundering herd) Cache miss → many concurrent requests all try to populate cache simultaneously → DB overwhelmed. ``` Cache miss at 10:00:00 1000 concurrent requests all hit DB DB has 1000 identical queries to handle ``` Mitigations: - **Probabilistic early refresh**: re-fetch before TTL expires (some fraction of requests trigger refresh). - **Locking**: only one request refreshes; others wait. - **Stale-while-revalidate**: serve stale data while refreshing in background. ## What to cache Best candidates: - **Expensive to compute** (joins, aggregations). - **Read frequently** (high traffic). - **Tolerates slight staleness**. Bad candidates: - **Strict consistency required** (financial transactions; cache makes this hard). - **Rarely read** (caching cost > benefit). - **Cheap to recompute** (sub-ms operations). ## Common caching mistakes 1. **Caching without invalidation strategy.** Stale data; hard-to-debug bugs. 2. **No TTL.** Cache fills with cold data; eventually evictions thrash. 3. **C