Cache Design And Consistency

What's being tested

Candidates must demonstrate practical mastery of cache design and consistency tradeoffs in distributed backends: detecting stale reads, resolving concurrent updates, and choosing invalidation/refresh strategies that meet latency and correctness SLAs. Interviewers probe reasoning about cache–DB coherence, concurrency control (versioning / CAS), and operational patterns (distributed locks, idempotency, cache stampede mitigation) a backend engineer would implement.

Core knowledge

• Cache-aside vs read-through vs write-through: cache-aside gives explicit app-driven loads/evictions, read/write-through delegates to `Redis`/`Memcached`; choose based on write amplification and failure modes.

• Write strategies: write-through (synchronous write to cache + DB), write-back (lazy DB flush), write-around (write to DB, skip cache). Each trades latency, durability, and complexity; write-back risks lost writes on cache failure.

• Consistency models: strong (linearizability) vs eventual; strong requires synchronization (locks/consensus), eventual accepts bounded staleness — quantify SLA (e.g., staleness ≤ 5s).

• Invalidation patterns: explicit invalidation (publish invalidation events), time-based TTL, and version-based (compare object version or vector clock). Explicit invalidation plus short TTL reduces stale window.

• Versioning & CAS: store a monotonic version or `etag` in cache/DB. Use compare-and-swap (CAS) to ensure updates only apply if version matches; supports last-write-wins or application-defined resolution.

• Distributed coordination: use `etcd`/`ZooKeeper`/`Consul` or `Redis`-based locks for critical sections; prefer optimistic (CAS) over heavy locking for high read throughput; evaluate lock leader election cost and single-point bottlenecks.

• Cache stampede mitigation: techniques include request coalescing, probabilistic early refresh, mutex per-key, and SYNCHRONIZED reads; avoid naive all-clients-refresh bursts on miss.

• Eviction & admission: combine LRU/LFU eviction with admission filters (e.g., TinyLFU); for large item variance, use segmented caches or size-aware LRU.

• Topology & routing: consistent hashing for sharded caches to minimize reshuffle; for global user state use local caches + async invalidations or a distributed cache with cross-datacenter replication.

• Observability & SLOs: measure `cache hit rate`, `stale-read rate`, `write-success-after-invalidation`, and `p99` latencies for cache vs DB; instrument invalidation lag and version mismatches.

• Quantify staleness: if updates are Poisson with rate λ and TTL = T, stale-read probability ≈ $e^{-\lambda T}$. Use to pick TTL so stale probability ≤ target.

Tip: prefer idempotency keys for write APIs so retries/backfills don't double-apply when cache and DB sequences diverge.

Worked example — Handle cache-update conflicts in distributed services

First 30 seconds: ask which operations are reads vs writes, required consistency (strong vs eventual), QPS and write-rate, failure modes, and existing systems (`Redis`, `Postgres`) and if a pub/sub (e.g., `Kafka`) exists for invalidations. Skeleton answer pillars: (1) pick a consistency goal and SLA, (2) choose an update pattern (cache-aside with explicit invalidation vs write-through), (3) implement concurrency control (versioning + CAS or distributed lock), and (4) mitigate operational problems (stampede, split-brain, monitoring). For many e-commerce flows prefer “write to DB, publish invalidation event, update cache lazily” with a version token in both cache and DB; writers perform a DB write and publish an invalidation, readers check cache version and fall back to DB on mismatch. A concrete tradeoff to flag: using distributed locks (e.g., `Redis` `SETNX`) simplifies races but can add latency and failure surface — favor optimistic CAS when write contention is low. Close by noting tests: simulate partition, measure stale-read window, and say “if more time, add per-key request coalescing and a dead-letter for failed invalidations.”

A second angle — Solve Dependency, Prefix, and Cache Problems

When constraints shift toward algorithmic properties (low-memory prefix lookups or dependency graphs), caching choices change: use compact in-memory structures (e.g., trie for prefix) with TTLs for derived results, and maintain a dependency graph to track which keys must be invalidated when a source changes. For problems with many derived entries, implement reverse dependency edges and publish targeted invalidation messages rather than global flushes. If the working set is too big for single-node `Memcached`, prefer sharded caches with consistent hashing and use small TTLs plus versioned keys to coordinate dependent invalidations efficiently.

Common pitfalls

Pitfall: Choosing TTLs blindly — picking a long TTL reduces DB load but raises stale-read risk; quantify staleness using update rate and target stale probability rather than gut feel.

Pitfall: Relying on naive distributed locks — locks can exacerbate latency and create single-point bottlenecks; if you propose locks, describe lease expiry, clock skew, and failure handling.

Pitfall: Omitting idempotency or version checks — without versioning, concurrent retries or replayed invalidation messages can cause lost updates or cache inconsistency; always design for safe retries.

Connections

Interviewers may pivot to distributed transactions / two-phase commit when strong atomicity is required, or to change-data-capture (CDC) and eventing (`Kafka`) for invalidation propagation. They may also ask about capacity planning for cache clusters, or observability topics like tracing cache miss-to-db paths and `p99` degradation.

Further reading

• Designing Data-Intensive Applications — Martin Kleppmann — strong chapters on replication, consistency, and caches.

• Amazon Dynamo paper / All Things Distributed posts — practical tradeoffs for eventual consistency and versioning.

• Martin Fowler — Two Hard Things (Cache Invalidation & Naming Things) — concise discussion of why invalidation is difficult.