Comprehensive knowledge of caching principles, architectures, patterns, and operational practices used to improve latency, throughput, and scalability. Covers multi level caching across browser or client, edge content delivery networks, application in memory caches, dedicated distributed caches such as Redis and Memcached, and database or query caches. Includes cache design and selection of technologies, defining cache boundaries to match access patterns, and deciding when caching is appropriate such as read heavy workloads or expensive computations versus when it is harmful such as highly write heavy or rapidly changing data. Candidates should understand and compare cache patterns including cache aside, read through, write through, write behind, lazy loading, proactive refresh, and prepopulation. Invalidation and freshness strategies include time to live based expiration, explicit eviction and purge, versioned keys, event driven or messaging based invalidation, background refresh, and cache warming. Discuss consistency and correctness trade offs such as stale reads, race conditions, eventual consistency versus strong consistency, and tactics to maintain correctness including invalidate on write, versioning, conditional updates, and careful ordering of writes. Operational concerns include eviction policies such as least recently used and least frequently used, hot key mitigation, partitioning and sharding of cache data, replication, cache stampede prevention techniques such as request coalescing and locking, fallback to origin and graceful degradation, monitoring and metrics such as hit ratio, eviction rates, and tail latency, alerting and instrumentation, and failure and recovery strategies. At senior levels interviewers may probe distributed cache design, cross layer consistency trade offs, global versus regional content delivery choices, measuring end to end impact on user facing latency and backend load, incident handling, rollbacks and migrations, and operational runbooks.
MediumTechnical
77 practiced
Describe how you would implement cache warming (prepopulation) after a deployment or full cache flush to avoid cold-start penalties. Discuss strategies: (a) proactive list-based warm, (b) background on-demand warm, (c) traffic-driven gradual warm, and how to rate-limit warming to protect the origin. Include verification and rollback considerations.
Sample Answer
Goal: avoid cold-cache spikes after deploy/flush while protecting origin and being observable. I’d implement a hybrid approach combining (a) proactive list-based warm, (b) background on‑demand warm, and (c) traffic-driven gradual warm plus strict rate-limiting, verification and rollback hooks.a) Proactive list-based warm- Build a prioritized URL list from analytics (top N by traffic, critical pages, product pages, A/B test seeds).- Run a parallel warm job after deploy that fetches URLs via CDN’s cache-api or HEAD/GET through the CDN edge to populate edge caches.- Example: a Kubernetes job reading a CSV, issuing concurrent requests with configurable concurrency/pacing.- Use service-account credentials or internal IPs so warms count as cacheable traffic.b) Background on-demand warm- Edge or app layer intercepts cache-miss events and enqueues warms in a background queue (e.g., Kafka, SQS) to prefetch related resources (images, JSON).- This avoids synchronous latency for first user; instead, serve origin response while warming adjacent keys.c) Traffic-driven gradual warm- Use real production traffic to warm less-critical items by sampling requests (e.g., 1%→10%→100%). Route sampled users to a warmed path or trigger prefetches for similar items (user’s frequently accessed items).- This reduces thundering‑herd by increasing load gradually.Rate-limiting to protect origin- Global and per-origin token buckets limiting warm RPS (e.g., 5 RPS per origin for heavy items).- Circuit breaker: if origin latency or error rate exceeds threshold, pause warms.- Backoff policy on 5xx/429s and exponential backoff for retries.- Limit concurrency per origin/IP and introduce jitter to avoid synchronized bursts.Verification and observability- Emit metrics: warm requests issued, success/failure, cache hit ratio, origin RPS, latency, error rates.- Smoke test: after warm run, sample HEADs to confirm cached TTL and X-Cache headers on edge.- Dashboards & alerts for abnormal origin load or low cache hit ratio.Rollback / safety- If origin metrics breach thresholds, automatic rollback: stop warm jobs, increase sampling interval, and disable proactive warms.- Feature flag the warm job and use gradual rollout (canary) so you can toggle off quickly.- Post-mortem: record which warm keys caused issues, tune lists and rate-limits.Trade-offs and notes- Proactive warms best for predictable hot items; traffic-driven warms handle long tails. Background on‑demand balances latency vs load.- Always include monitoring and conservative defaults; prefer incremental warming to avoid thundering‑herd.
MediumTechnical
77 practiced
Implement an LRU (Least Recently Used) cache class in Python that supports get(key) and put(key, value) with O(1) average time. The cache should have a fixed capacity and evict the least recently used item when full. You may use built-in data structures but explain their roles; show class signature and core methods.
Sample Answer
Approach: Use a hashmap (dict) for O(1) lookup mapping keys → nodes, and a doubly-linked list to maintain recency order (head = most recent, tail = least recent). On get/put we move accessed node to head. When capacity exceeded, remove tail node and delete from dict.
python
class LRUCache:
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None
def __init__(self, capacity: int):
self.capacity = capacity
self.map = {} # key -> Node
# dummy head & tail to avoid edge-case checks
self.head = self.Node(0, 0)
self.tail = self.Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
# helper: add node right after head (most recent)
def _add_node(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
# helper: remove node from list
def _remove_node(self, node):
prev, nxt = node.prev, node.next
prev.next = nxt
nxt.prev = prev
# helper: move existing node to head
def _move_to_head(self, node):
self._remove_node(node)
self._add_node(node)
# helper: pop tail (least recent)
def _pop_tail(self):
node = self.tail.prev
self._remove_node(node)
return node
def get(self, key: int) -> int:
node = self.map.get(key)
if not node:
return -1
self._move_to_head(node)
return node.val
def put(self, key: int, value: int) -> None:
node = self.map.get(key)
if node:
node.val = value
self._move_to_head(node)
else:
new_node = self.Node(key, value)
self.map[key] = new_node
self._add_node(new_node)
self.size += 1
if self.size > self.capacity:
tail = self._pop_tail()
del self.map[tail.key]
self.size -= 1
Key points:- dict gives O(1) key → node lookup.- doubly-linked list supports O(1) insertion/removal for recency updates.Time: O(1) average per get/put. Space: O(capacity).Edge cases: capacity <= 0 (should be handled by caller or raise), updating existing keys, repeated gets, and integer/immutable key types. Alternative: collections.OrderedDict simplifies implementation (move_to_end).
MediumTechnical
136 practiced
You plan an A/B test to add a distributed cache in front of a read path. Design the experiment/canary to measure end-to-end impact on user-facing latency, backend DB load, error rates, and cost. Describe traffic selection, duration, metrics to capture (including percentiles), significance considerations, and safety guards to stop the experiment if something goes wrong.
Sample Answer
Situation: We want to add a distributed cache in front of a read path and measure real user impact before full rollout.Plan / traffic selection:- Start with a randomized traffic-split canary: 1% users -> treatment (cache), 99% -> control. Gradually ramp to 5%, 25%, 50% after validating safety gates.- Randomization keyed by user-id or request-hash to keep sessions consistent.Duration:- Minimum two weeks or at least enough time to capture weekly usage patterns and rare errors; each ramp stage runs at least 24–72 hours once traffic is stable.Metrics to capture (control + treatment, with percentiles):- User-facing latency: p50, p90, p95, p99, and max; also tail duration over time buckets.- Backend DB load: QPS, CPU, active connections, read IOPS, average and p95 DB latency.- Error rates: 4xx/5xx for API, cache miss/eviction rates, DB errors, and SLO breach counts.- Cost: cache instance-hours, network egress, DB cost delta per hour.- Business metrics: request success rate & key product KPIs.Analysis & significance:- Use pre-defined primary metric (e.g., user p95 latency). Run statistical tests (bootstrap or t-test on logged response times) per-treatment per-stage. Require p < 0.01 for rollout decisions; check practical significance thresholds (e.g., p95 decrease > 5%).Safety guards / automated stops:- Hard stops: if error rate increases > 0.5 percentage points absolute or > 2x relative; DB errors increase > predefined threshold; CPU > 85% on any core; cache miss spike leading to DB QPS > X% of baseline.- Soft stops: if p95 latency worsens by >5% for 30 minutes, pause ramp and alert.- Automation: alerting + automated rollback to previous splitter on hitting hard stop. Run canary isolation so treatment runs on separate infra where possible.Notes:- Monitor correlation between cache miss rate and backend load; instrument cache headers in responses for debugging.- Validate correctness (stale data risks): include consistency checks comparing control and treatment payloads for a sample before full roll.
HardTechnical
85 practiced
You are building an online ticketing reservation system where seat reservations must be strongly consistent. Discuss why naive caching is dangerous here and propose a caching-safe architecture (for example: cache-aside with immediate invalidation, authoritative origin locking, conditional updates, or combining cache reads with origin verification). Analyze performance vs correctness trade-offs and mitigation strategies.
Sample Answer
Naive caching is dangerous for seat reservations because stale reads can lead to double-booking: a cache can return a “free” seat while another concurrent reservation already committed to the database, violating strong consistency and user expectations. Caches also complicate failure modes (partial invalidation, race windows) and make correctness dependent on timing.A caching-safe architecture- Authoritative origin: Make the database (or a single reservation service) the source of truth for writes. All reservations must be validated and committed at the origin.- Read path (low-latency): Use cache-aside for reads, but never treat cache as authoritative for writes. On a read: check cache; if miss, read origin and populate cache.- Write path (strong consistency): Acquire a short-lived per-seat lock or use optimistic conditional updates (version/ticket CAS) at origin: - Optimistic: Include seat_version in read; on commit, do “UPDATE seats SET owner=..., version=version+1 WHERE id=? AND version=?”. If 0 rows affected, retry read/refresh—this avoids global locks. - Pessimistic: For high contention, acquire a distributed lock (e.g., Redis Redlock or DB row lock) for the seat during reservation.- Immediate invalidation: After a successful commit, immediately invalidate or update cache for that seat (or publish an invalidation event). Invalidate-before-respond pattern (commit -> invalidate -> respond) reduces stale-read windows.- Origin verification for reads: For critical flows (checkout), re-verify seat availability at origin immediately before final commit even if cache showed free.Performance vs correctness trade-offs- Correctness-first: Pessimistic locks guarantee single-writer semantics but add latency and reduce throughput under contention.- Optimistic CAS: Higher throughput and lower latency in common low-contention cases; requires retries under conflicts.- Immediate invalidation: Minimizes stale windows but adds latency (synchronous invalidation) or complexity (eventual invalidation via pub/sub).- Read amplification: Origin re-checks increase origin load; mitigate with read replicas for non-critical reads but always verify on commit.Mitigations to balance both- Partition seats to reduce lock scope; use sharded services for reservation ownership.- Use per-seat optimistic updates with exponential backoff and bounded retries to handle transient conflicts.- Cache patterns: short TTLs, write-through for quick updates, or skip caching highly contended seats entirely.- Instrument: monitor conflict rate, cache hit/miss, latency; adapt strategy (switch to pessimistic under high contention).- Use transactional DB features (serializable isolation or SELECT ... FOR UPDATE) when absolute atomicity is required.Recommendation: Default to optimistic conditional updates with immediate cache invalidation and origin verification at commit. Add per-seat locks for hot seats or during peak windows, and tune caching (short TTLs, avoid caching hot items) while monitoring conflict metrics to adapt. This yields strong correctness with acceptable latency in typical loads, and predictable degradation paths under contention.
MediumSystem Design
85 practiced
Design a multi-level caching strategy for an e-commerce product detail page serving 50k RPS globally, with 1M SKUs. Specify what to cache at each layer (browser, CDN, edge, app memory, distributed Redis), cache key design, invalidation approach for price and inventory changes, and how to maximize hit rate while meeting freshness requirements for price/availability.
Sample Answer
Requirements & constraints clarified:- 50k RPS global traffic, 1M SKUs, strict freshness for price/inventory (near real-time for inventory; price tolerance maybe <1s–5s depending on business).- Goal: max hit rate while keeping price/availability fresh.High-level multi-layer strategy (what to cache & why)- Browser (client): cache static assets (CSS/JS/images), HTML with short cache-control and stale-while-revalidate for UX. Use ETag/If-None-Match for conditional GETs.- CDN (global edge): cache full product page HTML and images for high hit-rate; set short TTLs for dynamic fragments (price/inventory). Support cache-key variants by cookie/query. Use stale-while-revalidate and serve stale on error.- Edge compute / edge workers: cache rendered page fragments (product description, reviews snapshot) and assemble dynamic fragments fetched from origin or Redis. This reduces origin load and allows per-request personalization at edge.- App memory (local per-instance): tiny LRU in-memory cache for hottest SKUs (top 1–5% by traffic) for microsecond reads and to reduce Redis/DB calls.- Distributed Redis (regional clusters): authoritative fast cache for product state (price, inventory, promo tags, flags). Use sharded Redis with TTL and pub/sub invalidation channels.Cache key design- CDN/edge HTML key: product:{sku}:v{page_version}:region:{region}:lang:{lang}:device:{device_type}- Fragment keys: product:{sku}:static:v{static_ver}, product:{sku}:price:v{price_version}, product:{sku}:inventory:v{inventory_version}- App memory key: same as Redis key for consistency.Invalidation approach (price and inventory)- Versioned keys + event-driven invalidation: - Maintain version numbers for mutable fields in Redis: price_version and inventory_version per SKU. - On price/inventory update (from pricing service or inventory system), increment corresponding version and publish event on Redis pub/sub / Kafka topic. - Edge/CDN invalidation: for critical updates, send targeted cache purge for CDN key product:{sku}:* or use surrogate-keys tagging to purge quickly (avoid full CDN purge). - For non-critical/expected frequent inventory changes, rely on short TTLs + stale-while-revalidate and use edge workers to fetch latest inventory from Redis on assemble.- Conditional GET / ETag: backend returns ETag for assembled page so CDNs and browsers can revalidate.Maximizing hit rate while meeting freshness- Hot/cold split: aggressive caching and longer TTLs for static/hot fragments; short TTLs for inventory/price fragments.- Stale-while-revalidate and serve-stale-on-error reduce missed hits during origin spikes.- Pre-warm caches for anticipated promotions using analytics (prime top N SKUs regional caches before traffic).- Use surrogate-keys / tag-based invalidation for efficient CDN purges instead of full-key purges.- Read-through caching in Redis with write-through/async-write-back patterns for consistency trade-offs: price updates use synchronous write-through + immediate version bump; inventory can use eventual consistency with optimistic decrement and background reconciliation if business allows.- Monitoring & autoscaling: track hit-rate, latency, and invalidation lag; scale Redis read replicas and CDN edge rules per region.Trade-offs- Frequent invalidations lower hit rate; versioning + fragmenting isolates churn to small fragments.- Strong consistency for price requires immediate invalidation (slightly more origin/CDN traffic); inventory can often tolerate milliseconds of staleness if handled by business logic (hold items at checkout).This design balances high global hit rates (CDN + edge + app memory + Redis) with low-latency freshness for price/inventory via versioned fragments, targeted invalidation, and event-driven propagation.
Unlock Full Question Bank
Get access to hundreds of Caching Strategies and Patterns interview questions and detailed answers.
