Google-Scale Caching and Cache Invalidation

What's being tested

Interviewers are checking your ability to design and reason about a low-latency, large-scale caching layer and its cache invalidation semantics: how you trade freshness, availability, and cost at Google scale. They want concrete choices (cache topology, invalidation protocol, eviction and sharding), quantitative tradeoffs (hit-rate vs origin-load), and engineering tactics for correctness under concurrency and failures. Demonstrate clear assumptions, failure-mode handling, and measurable SLAs (latency, stale-window, origin QPS).

Core knowledge

Caching patterns: know cache-aside, read-through, write-through, and write-back semantics, their origin-write amplification, and when each simplifies consistency or reduces origin load.
TTL vs explicit invalidation: TTL provides bounded staleness; explicit invalidation (versioning/publish) gives precise freshness but requires coordination and network fanout.
Multi-tier caches: differentiate edge/CDN (CDN), regional caches, and in-process caches (memcache, Redis, local LRU); understand s-t tradeoffs between propagation latency and hit-rate.
Cache hit-rate math: hit-rate H affects effective latency $L_{eff} = H·L_{cache} + (1−H)·L_{origin}$ and origin QPS = $(1−H)·request\_rate$ . Estimate required cache size from access distribution (Zipf/90-10).
Eviction policies: LRU/LFU trade memory and recency; approximate LFU (TinyLFU) works at high throughput; admission policies (probabilistic) prevent pollution from large one-off scans.
Sharding & consistent hashing: use consistent hashing to minimize re-shuffles when nodes join/leave; replicate hot keys for read-scaling but handle write fan-out/atomicity.
Cache stampede: mitigate with request coalescing/singleflight, mutex-per-key, or early recomputation; consider jittered TTLs to avoid synchronized expiry.
Invalidation protocols: push (fan-out via Pub/Sub) vs pull (clients check version); combine with versioned keys (key:v) so invalidation is an atomic key-swap.
Atomicity & races: enforce write ordering using monotonic version numbers, compare-and-swap, or single-writer sharding; avoid lost-invalidates by sequencing invalidation after origin commit.
Failure modes: network partitions can split-brain caches; prefer tolerant designs (serve stale with TTL+revalidate) over dropping to origin if availability SLA dominates.
Stale-while-revalidate and soft TTL: serve slightly stale data while background refresh reduces tail latency and origin spikes, with quantified stale windows.
Instrumentation & metrics: measure cache_hit_rate, origin_qps, stale_serves, p99_latency, and invalidation lag (time between origin commit and cache freshness).

Tip: wrap metric targets into SLOs (e.g., <50ms p95, stale-serve <1%) to drive tradeoffs.

Worked example

Design a caching strategy for a user-profile service where updates are rare but reads are high. First 30s: clarify SLAs — acceptable staleness (seconds vs minutes), read QPS, update QPS, and whether strong consistency is required for reads immediately after a write. Skeleton of answer: (1) choose topology: edge CDN for avatars + regional Redis for profile JSON; (2) population: cache-aside for reads, with write path performing origin commit then invalidation; (3) invalidation: publish a user-specific invalidation via Pub/Sub to regional caches and bump a versioned key (user:123:v42); (4) mitigate stampede: use singleflight on miss and jittered TTLs. Tradeoff to flag: eager push invalidation reduces staleness but costs O(number_of_caches) messages; versus TTLs cause bounded staleness but simpler. Close by saying you’d add metrics (invalidation lag histogram), run load tests to size Redis clusters, and, if more time, discuss replication strategy and failure-injection tests.

A second angle

Now assume the same service must support multi-region active-active writes with global user IDs and low write latency. Here the invalidation problem becomes global coherence: choose a single-writer-per-user routing to keep invalidation local, or use optimistic concurrency with monotonic timestamps and allow temporary divergent reads resolved by last-write-wins. Use versioned keys with global version vector / Lamport timestamps for monotonicity. Instead of pushing invalidations to every region synchronously, send an origin-of-truth write and then publish lightweight version-updates; regions compare versions and lazily pull authoritative data on mismatch. Emphasize the tradeoff: stronger cross-region freshness increases write latency and coupling; eventual consistency simplifies latency at the cost of temporary stale reads.

Common pitfalls

Pitfall: Designing for perfect freshness by synchronously invalidating every cache before acknowledging a write. This yields high write latency and brittle availability; interviewers prefer bounded staleness or async invalidation with well-measured windows.

Pitfall: Ignoring cache stampede and scaling only by adding memory. Large TTLs plus no coalescing causes sudden origin thundering when popular keys expire; propose singleflight, mutex per-key, or background refresh to prevent spikes.

Pitfall: Using naive key deletion across many shards without idempotency or ordering. If invalidation messages are lost or reordered, clients may read stale data; prefer versioned keys or sequence numbers and design idempotent invalidation handlers.

Connections

Interviewers may pivot to distributed consensus (e.g., when you need strong global invalidation ordering), consistency models (linearizability vs eventual consistency), or capacity planning (approximating cache size from access distribution and hit-rate targets). Be ready to discuss tradeoffs that touch on replication, partitioning, and operational runbooks.