Eviction & Invalidation

1. ADD     → Data is written to cache (on miss or on write)
2. USE     → Data is read from cache (cache hit)
3. UPDATE  → Data is refreshed (invalidation + re-fetch)
4. EVICT   → Data is removed (memory full, TTL expired, or invalidated)

                ┌──────────────────────────────┐
                │         CACHE MEMORY         │
                │                              │
   ADD ──────→  │  key:value  (TTL: 300s)      │  ──────→ EVICT
                │  key:value  (TTL: 60s)       │    (LRU / LFU / TTL)
   USE ←──────  │  key:value  (TTL: 600s)      │
                │                              │
                └──────────────────────────────┘
                         ↑
                    INVALIDATE
                  (data changed in DB)

Cache capacity: 4 items

Access sequence: A, B, C, D, E, A, F

State after each access:
  A → [A]
  B → [B, A]
  C → [C, B, A]
  D → [D, C, B, A]        ← cache full
  E → [E, D, C, B]        ← A evicted (least recently used)
  A → [A, E, D, C]        ← B evicted, A moves to front
  F → [F, A, E, D]        ← C evicted

Key insight: recently accessed items stay, old items go.
Redis uses an approximated LRU (samples random keys, evicts the oldest).

Cache capacity: 3 items

Access sequence: A, A, A, B, B, C, D

State (item: access count):
  A(1) → A(2) → A(3) → A(3),B(1) → A(3),B(2) → A(3),B(2),C(1)  ← full
  D arrives → evict C (count=1, lowest) → A(3),B(2),D(1)

Key insight: frequently accessed items stay, rarely used items go.
Problem: a once-popular item that's no longer relevant stays forever
  (high count but no recent accesses).
Fix: decay counters over time, or use a hybrid LRU-LFU approach.

SET user:42 = {name: "Alice"} TTL 300  (expires in 5 minutes)

T=0s:    GET user:42 → {name: "Alice"}  ✅ (fresh)
T=200s:  GET user:42 → {name: "Alice"}  ✅ (still valid)
T=301s:  GET user:42 → null             ❌ (expired, cache miss)
         → Fetch from DB, re-cache with new TTL

TTL is a safety net:
  Even if invalidation fails, data won't be stale for more than TTL seconds.
  Short TTL (10s) = fresher data, more DB hits
  Long TTL (1hr) = staler data, fewer DB hits

User updates profile name:

1. App writes to DB:  UPDATE users SET name='Alicia' WHERE id=42
2. App writes to cache: SET user:42 = {name: "Alicia"}
   (or: DELETE user:42 to force re-fetch on next read)

Result: cache is always in sync with DB
Trade-off: every write is slower (must update both)
Risk: if step 2 fails, cache has stale data
  → Use "delete" instead of "update" — safer (forces re-fetch)

function updateUser(userId, data) {
  // 1. Write to database
  db.query("UPDATE users SET name = ? WHERE id = ?", data.name, userId);

  // 2. Delete from cache (NOT update)
  cache.delete("user:" + userId);

  // Next read will miss → fetch fresh data from DB → re-cache
}

Why DELETE instead of UPDATE?
  → If the DB write succeeds but cache update fails, cache has stale data
  → If you DELETE and it fails, worst case: cache still has old data (TTL safety net)
  → DELETE is idempotent and safer than UPDATE

Architecture:
  App Server A writes to DB
  App Server A publishes event: "user:42:updated"
  Redis Pub/Sub (or Kafka) broadcasts to all app servers
  All app servers delete "user:42" from their local cache

Flow:
  DB write → publish event → all caches invalidated

Benefits:
  ✅ Works across multiple app servers / cache instances
  ✅ Near real-time invalidation
  ✅ Decoupled — writers don't need to know about caches

Trade-offs:
  ⚠️ More infrastructure (message broker)
  ⚠️ Events can be delayed or lost
  ⚠️ TTL still needed as a safety net

Popular cache key: "homepage:trending" (TTL: 60 seconds)
Traffic: 10,000 requests/second for this key

Normal operation:
  9,999 requests → cache HIT (1ms)
  1 request → cache MISS → fetch from DB → re-cache

At TTL expiration (T=60s):
  Cache key expires
  Next 100 requests (within 50ms) ALL miss the cache
  All 100 hit the database simultaneously
  DB query takes 200ms (expensive aggregation)
  DB is now handling 100 identical queries at once
  DB CPU spikes to 100%, other queries slow down
  Cascading failure: more timeouts → more retries → more load

  ┌─────────┐
  │  Cache   │  key expired!
  └────┬─────┘
       │ MISS × 100
       ▼
  ┌─────────┐
  │ Database │  💥 100 identical queries at once
  └─────────┘

Approach 1: Startup Warming
  On server start, before accepting traffic:
    → Fetch top 1000 products from DB → cache them
    → Fetch homepage data → cache it
    → Fetch user session data for active users → cache it
  Then: start accepting traffic (cache is warm)

Approach 2: Scheduled Warming
  Every 5 minutes, a background job:
    → Queries DB for most-accessed keys (from access logs)
    → Preloads them into cache
    → Refreshes keys that are about to expire

Approach 3: Peer Warming
  New server joins the cluster:
    → Copies hot keys from an existing server's cache
    → No DB queries needed
    → Fastest approach but requires cache-to-cache transfer

Redis Cluster (128 GB, LRU eviction):
  ├── feed:{userId}        → user's feed (TTL 5min, invalidate on new post)
  ├── trending:posts       → top posts (early refresh, never expires)
  ├── user:{userId}:profile → user profile (TTL 10min, delete on update)
  └── post:{postId}        → post content (TTL 30min)

Invalidation:
  New post → delete feed:{followerId} for all followers
  Profile update → delete user:{userId}:profile
  Safety net: TTL on every key

Stampede prevention:
  All keys: request coalescing (singleflight)
  Top 100 trending: early refresh (background job)
  All TTLs: jitter ±10% (staggered expiration)

Warming:
  On startup: preload trending + top 100K user feeds
  Every minute: refresh trending, refresh expiring hot keys