Caching and Eviction for Google-Scale Services

What's being tested

Interviewers probe your ability to design and reason about high-throughput, low-latency caching systems: selecting eviction policies, ensuring correctness under concurrent updates, sizing and sharding caches, and preventing cache-related reliability incidents at scale. Google cares because caches are critical to reduce backend load, control tail latency (p99), and lower cost; the interviewer wants to see tradeoff-driven engineering, measurable SLAs, and safe operational practices.

Core knowledge

Cache hit rate and miss rate: define hit rate = hits / (hits + misses). Small improvements in hit rate can produce large backend load reductions; quantify expected backend QPS reduction given hit-rate delta.
Cache architectures: know cache-aside, write-through, and write-back semantics and failure modes; cache-aside is common for reads-heavy workloads, write-through simplifies durability at the cost of write latency.
Eviction policies: understand LRU, LFU, CLOCK, ARC, and TinyLFU; LRU is simple, LFU excels with skewed access, TinyLFU combines admission with eviction to avoid polluters.
Working set vs capacity: identify working-set size W relative to capacity C; if W >> C expect thrashing and low hit rates. Instrument to measure approximate W and tail-frequency distributions (e.g., Zipf).
Distributed caching & sharding: use consistent hashing for node membership churn; shard by key to avoid cross-node coordination. Account for rebalancing cost proportional to moved key bytes.
Replication & consistency: for read-replicas, choose between eventual consistency with TTL or synchronous invalidation; for strong consistency, prefer single-writer or versioned invalidation tokens (generation numbers).
Cache invalidation patterns: know time-based TTL, explicit invalidate-on-write, and hybrid approaches. Invalidation races lead to stale reads; using monotonically increasing version or compare-and-set reduces races.
Cache stampede & mitigation: mitigate thundering herd with request coalescing, singleflight, probabilistic early recompute, or client-side locking; use jittered TTL to avoid synchronized expirations.
Admission filtering & Bloom filters: reduce backend misses with Bloom filters to block requests for known-missing keys, but account for false positives and memory tradeoffs: false-positive rate ≈ (1 − e^(−k n / m))^k.
Eviction engineering at scale: track eviction rate, cold-start cost, and tail-latency impact; tune eviction in presence of hot keys via explicit pinning or hot-key bypass to single-tenant caches.
Instrumentation & SLOs: collect hit_rate, miss_lat, evictions/sec, and cache_fill_time; SLOs commonly target p99 read latency and a minimum hit-rate for backend protection.

Worked example — "Design a distributed cache for session data with eviction and strong consistency"

First 30s: ask workload questions — read/write ratio, session size, TTL expectations, consistency needs (strict read-after-write?), failure SLAs, and traffic patterns (burstiness, hot keys). Skeleton answer pillars: (1) data model: store session token → small JSON, keep version number for concurrency; (2) architecture: cache-aside with write-through for critical updates or cache-aside + synchronous invalidation if low write volume; (3) distribution: consistent-hash shards, optional replication for availability; (4) eviction: TTL per-session plus LRU within shard, pin authenticated sessions briefly to avoid premature eviction; (5) reliability: singleflight for refreshes, use compare-and-swap on writes to avoid stale overwrite. Tradeoff to flag: choosing write-through increases write latency and backend load consistency but simplifies correctness; cache-aside yields lower write latency but requires careful invalidation to avoid stale reads. Close by proposing measurable benchmarks (simulate 95th/99th percentile latency under production QPS), and if more time, implement load tests, heap/GC tuning on cache nodes, and an automated rebalancer that moves only cold keys.

A second angle — "Design a CDN-like cache for serving user avatars with TTL and global invalidation"

Same core concepts apply but constraints differ: traffic is extremely read-heavy, objects are larger, and eventual consistency is acceptable for most updates. Use long TTLs with Cache-Control headers, CDN edge caching, and origin invalidation API for user-initiated updates. Eviction becomes LRU within edge node capacity; apply range or object-size aware eviction to avoid evicting many small hot objects for a single large object. Use conditional GETs (ETag/If-Modified-Since) to reduce origin load. Mitigations: background cache-warming on expected changes, and a purge API that propagates invalidation asynchronously with versioning to prevent stale windows.

Common pitfalls

Pitfall: Treating eviction policy as the only knob.
Designers often focus on LRU/LFU but ignore admission filtering, working-set measurement, and hot-key handling; this leads to suboptimal hit rates and tail latency.

Pitfall: Not asking about read/write patterns and error budgets.
Failing to clarify whether strong consistency is needed causes wrong choices between write-through and cache-aside, exposing race conditions or unnecessary latency.

Pitfall: Over-optimizing per-node LRU without addressing rebalancing cost.
Ignoring consistent-hash churn or large-object movements during node scaling produces high network IO and transient misses; plan for incremental rebalancing and tooling.

Connections

Interviewers may pivot to load balancing and partitioning, database transaction isolation vs cache consistency, or rate limiting / backpressure to protect a backend when cache miss spikes occur. Be ready to tie caching decisions to capacity planning and SLO tradeoffs.