shreyansh

Cache Patterns and Eviction

30-Second Glance

  • Cache-aside is the default: app owns the cache explicitly; all other patterns trade app simplicity for consistency or write-path guarantees.
  • Write-through = safe but slow writes; write-behind = fast writes that can lose seconds of data on crash. Pick by durability budget, not habit.
  • Hit ratio is the only metric that matters for capacity: 95% hit ratio turns 100k rps at the DB into 5k. Size and TTL exist to defend that ratio.
  • Thundering herd (one hot key expires → N threads stampede the DB) is prevented with request coalescing, probabilistic early refresh, or stale-while-revalidate — name at least two in an interview.
  • Redis = data structures + persistence + Lua; Memcached = pure LRU slab cache, multithreaded, simpler. Both serve p99 < 1 ms on cache hits.

Read and Write Patterns

Pattern Flow Pros Cons
Cache-aside (lazy) App: read cache → miss → read DB → populate cache. Writes: update DB, delete (not update) cache entry Only hot data cached; cache failure degrades, doesn't break; simplest to reason about First read always misses; delete-then-race windows on concurrent write+read
Read-through App reads cache; cache provider loads from DB on miss App code stays dumb; loader centralized Cache becomes critical path; cold-start identical to aside
Write-through App writes cache and DB synchronously Cache never stale; reads always fast after write Write latency = cache + DB; write-heavy workloads pay full DB cost anyway
Write-behind (write-back) App writes cache; cache flushes to DB async (batched, e.g. every 100 ms–1 s) Lowest write latency; absorbs bursts (10k writes/s → 1k batched DB writes) Data-loss window on cache crash; ordering/complexity in the flush path
Refresh-ahead Cache reloads hot keys before TTL expiry based on access stats No miss latency for predictable hot keys Wasted reloads on cooling keys; needs an access tracker (usually the cache itself)

Two rules interviewers listen for. First, on write in cache-aside, delete the key — don't update it: updating risks ordering inversions (slow DB write followed by fast cache write leaves stale data cached for the whole TTL). The delete-then-miss window is bounded and self-healing; a poisoned update is not. Second, double-delete (delete, update DB, delete again after ~100–500 ms) covers the race where a read repopulates between your delete and your commit — the standard answer for read-heavy MySQL+Redis stacks.

loading diagram…

TTL, Herds, and Stampede Prevention

TTL choice is a freshness-vs-load dial, not a constant: user profile ~minutes–hours, product catalog ~seconds–minutes with event invalidation, ML feature values ~pinned to training window. Always add TTL jitter (±10–20%) so mass-inserted keys don't expire in lockstep and re-stampede the DB.

The thundering herd scenario, stated precisely: hot key with 100k rps behind it expires; 100k concurrent requests all miss within the same millisecond and each opens a DB query. Defenses, pick two and be able to draw one:

  1. Request coalescing (singleflight): first misser takes a per-key lock (SET key:lock NX PX 3000); others wait on the lock and share the result. Go's singleflight, nginx proxy_cache_lock, and Varnish saint mode are all this.
  2. Probabilistic early refresh (xfetch): recompute TTL as ttl * (beta * log(rand) * ...) — refresh hot keys early with probability rising as expiry nears, spreading reloads over time.
  3. Stale-while-revalidate: serve the expired value instantly (bounded staleness, e.g. +30 s) while one background fetch refreshes. The availability-first answer; pairs naturally with edge caching semantics.
  4. Empty-result caching: cache misses/nulls with short TTL (30–60 s) to stop cache-penetration attacks and repeated queries for nonexistent rows.

Eviction Policies

Memory is finite; eviction decides who dies when it's full. maxmemory + policy is mandatory config — without it Redis OOM-errors writes.

Policy Evicts Fit
LRU (allkeys-lru / volatile-lru) Least-recently-used (approximated: sampled N=5 keys by default) General purpose; web workloads with recency locality
LFU (allkeys-lfu / volatile-lfu) Least-frequently-used with frequency decay Skewed popularity (few hot keys, long tail); Redis 4+; Memcached stays LRU-only
Random / volatile-random Random key (or random with TTL) Scan/periodic-batch workloads that would poison LRU
TTL-only (volatile-ttl) Shortest TTL first Session/mixed stores where persistent keys must never evict
noeviction Nothing — error on write You want backpressure instead of silent drops (risk: full outage if unmonitored)

Know the sampling caveat: Redis LRU/LFU are approximate (default 5-key sample; raise maxmemory-samples to 10 for better accuracy at slight CPU cost). Modern upgrades worth naming: TinyLFU / W-TinyLFU (admission filter so scans don't evict hot keys — used by Caffeine, Ristretto) and ARC/Clock (scan-resistant without tuning). If asked "LRU vs LFU": LRU wins when recency predicts reuse (feeds, sessions); LFU wins under stable Zipf popularity (video catalogs, package registries).

Redis vs Memcached

Redis Memcached
Model Data structures (strings, hashes, lists, sets, sorted sets, streams, HyperLogLog) + Lua scripting Opaque string/blob slab allocator
Threading Single-threaded event loop (I/O threads for network since 6.0); ~100k+ ops/s per node, p99 < 1 ms Multithreaded; scales linearly with cores for simple GET/SET
Persistence RDB snapshots + AOF log (required for write-behind-ish durability) None — pure cache; restart = cold
Clustering Redis Cluster (16384 slots, hash-tag colocation), Sentinel failover Client-side consistent hashing across a pool
Eviction LRU/LFU/Random/TTL/noeviction, per-policy LRU only (slab-class LRU)
Use when Leaderboards (ZSET), rate limiting (Lua + TTL), locks (SET NX), queues/streams, anything needing server-side compute Huge simple key-value fleet where multithreaded throughput and operational simplicity beat features (classic: Facebook's mcrouter tier)

Concrete numbers to quote: cache hit ~0.2–1 ms p99 intra-AZ vs 5–50 ms DB read; each 1% of hit ratio at 100k rps spares ~1k DB qps — which is why moving 90% → 99% hit ratio is worth more than most DB tuning. Size caches from hot_key_count × avg_value_size × overhead(≈1.5×) and verify with used_memory / eviction counters, not guesses.

Trade-offs

Approach Pros Cons Use when
Cache-aside + delete-on-write Simple; failure-safe; hot-only memory Miss storms; delete-race windows Default for DB-backed reads
Write-through Cache always consistent Write latency pays DB cost Read-heavy, stale-intolerant data (pricing, inventory counts)
Write-behind Minimal write latency; burst absorption Loss window; flush-path complexity Counters, analytics ingestion, bursty writes with replayable sources
Short TTL + jitter Self-healing staleness; no invalidation plumbing Extra DB load; worst-case stale = TTL Fast-moving data where "seconds stale" is acceptable
Event invalidation Near-zero staleness Invalidation bus to build (see Kafka vs RabbitMQ); ordering bugs Catalog/pricing where staleness costs money

Interview One-Liners

  • Q: Cache-aside: update or delete the key on write?
    A: Delete. Updating risks stale-wins races; a deleted key self-heals on next read, and double-delete covers the read-between-delete-and-commit race.
  • Q: One celebrity key expires and the DB falls over. Fix?
    A: Per-key lock with singleflight/coalescing so one request rebuilds; plus jittered TTLs and stale-while-revalidate so expiry never synchronizes a stampede.
  • Q: Redis or Memcached for a session store?
    A: Redis (persistence + TTL + data structures); Memcached if it's a giant fleet of opaque blobs and you want multithreaded simplicity.
  • Q: How do you size the cache tier?
    A: hot keys × avg size × 1.5 overhead, then confirm via hit ratio and evictions — target ≥95% hit ratio for DB-shielding tiers, scale shards before evictions climb.
  • Q: Write-behind lost 500 ms of writes on failover. Expected?
    A: Yes — that's the durability window you accepted for write latency. If unacceptable, use write-through or make the source replayable (see Stream Processing).
  • Q: LRU or LFU for a video catalog?
    A: LFU — popularity is Zipf-stable, and LRU would let one-off scans evict evergreen hits; add a TinyLFU-style admission filter if available.