Bird
Raised Fist0

Cache Stampede - Thundering Herd Problem and Prevention Strategies

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Cache Stampede - Thundering Herd Problem and Prevention Strategies
45 min · senior
senior

You are designing a caching layer for a 50 million daily active user (DAU) startup that serves personalized content with strict latency requirements. The system experiences frequent cache misses on hot keys, causing thundering herd problems that overload backend databases and increase tail latency. The business requires encrypted data at rest and in transit, offline delivery support for intermittent connectivity, and a P99 latency under 200ms for cache reads. You must design a system to prevent cache stampede while balancing consistency, freshness, and scalability.

Constraints
  • Data must be encrypted at rest and in transit using TLS and AES-256
  • Support offline delivery with eventual consistency guarantees
  • P99 cache read latency must be under 200ms
  • System must handle 50M DAU with peak QPS of 1M cache requests/sec
  • Cache misses on hot keys must not overwhelm backend databases
📋
Guided Steps
1/5
Step 1
Identify the root cause of cache stampede
What causes the thundering herd problem in caching systems at this scale, and why is it critical to address?
💡 Hint
Consider what happens when many clients simultaneously request a hot key that is missing or expired in cache.
Key Decision
Recognize that simultaneous cache misses on hot keys cause many backend DB queries, overwhelming the DB and increasing latency.
Interviewer Expectation
Mid: Explains cache misses cause DB overload. Senior: Details how concurrent cache miss spikes cause cascading failures and increased P99 latency.
⚠️Common Wrong Answer
Assuming cache misses are rare and ignoring the impact of simultaneous misses, leading to backend DB overload and latency spikes.
Step 2
Choose a cache invalidation and refresh strategy
Which cache refresh strategy prevents thundering herd while maintaining freshness and low latency?
💡 Hint
Think about locking or request coalescing mechanisms that allow only one backend fetch per hot key miss.
Key Decision
Use Redis with Redlock distributed locking to allow only one refresh per hot key miss, while others wait or serve stale data.
Interviewer Expectation
Mid: Names Redis with TTL. Senior: Explains Redlock distributed lock prevents multiple backend calls, reducing DB load and ensuring freshness.
⚠️Common Wrong Answer
Using simple TTL expiration without locking, causing multiple backend calls on cache expiry and thundering herd.
Step 3
Design the cache refresh coordination mechanism
How do you coordinate cache refresh requests across distributed cache nodes to avoid stampede?
💡 Hint
Consider a distributed lock or token that grants exclusive refresh rights per key across nodes.
Key Decision
Implement Redlock algorithm on Redis clusters to acquire distributed locks per key before backend fetch, ensuring single refresh owner.
Interviewer Expectation
Mid: Mentions distributed locking. Senior: Details Redlock's quorum-based locking guarantees and failure handling to avoid stale locks.
⚠️Common Wrong Answer
Using local in-memory locks per node, which fail to coordinate across distributed cache nodes, causing multiple backend hits.
Step 4
Handle stale data and offline delivery
How do you serve data during cache refresh delays or backend failures while supporting offline delivery?
💡 Hint
Think about serving stale data with a background refresh and client-side sync mechanisms.
Key Decision
Serve stale cache data with a stale-while-revalidate TTL policy and use client sync endpoints to update when fresh data arrives.
Interviewer Expectation
Mid: Suggests stale data serving. Senior: Explains stale-while-revalidate pattern with Redis TTL and client sync API to maintain consistency and offline support.
⚠️Common Wrong Answer
Failing to serve stale data causes client errors or high latency during backend delays, degrading user experience.
Step 5
Design APIs for client interaction with cache system
What are the 3 core API endpoints clients need to interact with the cache stampede prevention system?
💡 Hint
Consider endpoints for cache read, refresh trigger, and client acknowledgment or sync.
Key Decision
Design endpoints: (1) GET /cache/{key} for cache read with fallback, (2) POST /cache/refresh/{key} to trigger refresh with distributed lock, (3) POST /cache/sync/{key} for client to acknowledge updated data.
Interviewer Expectation
Mid: Names basic cache read and refresh APIs. Senior: Details API semantics, locking coordination, and offline sync support.
⚠️Common Wrong Answer
Only providing cache read API without refresh coordination or client sync, leading to uncontrolled stampede and stale data.
🔌
API Design Challenge
Sketch 3 core endpoints for the cache stampede prevention system that handle cache reads, cache refresh triggers, and client synchronization.
Hints
  • How does the client request cached data and handle cache misses?
  • How does the system coordinate cache refresh to prevent thundering herd?
  • How does the client acknowledge or sync updated cache data?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Explain root cause of thundering herd as simultaneous cache misses causing DB overload
  • Use Redis with Redlock distributed locking to coordinate cache refreshes
  • Design APIs for cache read, refresh trigger, and client sync
  • Serve stale data with stale-while-revalidate TTL to maintain low latency
  • Encrypt data in transit and at rest per constraints
Good to Have - 30%
  • Discuss Redis Cluster for horizontal scalability
  • Explain failure modes of distributed locks and recovery
  • Include monitoring for cache stampede detection
  • Support offline delivery with client sync endpoints
Bonus - 10%
  • Propose fallback strategies if Redis lock acquisition fails
  • Suggest metrics to measure cache stampede impact and mitigation effectiveness
Anti-patterns to Avoid
Using local in-memory locks only, which do not coordinate across distributed cache nodes and cause multiple backend hits, resulting in backend overload and increased latency
Relying solely on TTL expiration without locking, leading to thundering herd on hot key expiry and cascading backend failures
Serving no stale data during backend delays, causing increased latency or client errors and degrading user experience
Omitting encryption, violating business security constraints and risking data breaches
Not providing client sync APIs, resulting in inconsistent offline data and poor user experience
Using HTTP polling for cache refresh coordination at 50M DAU causes 50 million reconnects per minute just to check for messages, collapsing under load and increasing latency
✅
Model Answer
▼ Reveal

The system uses Redis Cluster with Redlock distributed locking to coordinate cache refreshes and prevent thundering herd. It serves stale data with a stale-while-revalidate TTL policy to maintain low latency and supports offline delivery with client sync APIs. Data is encrypted in transit using TLS and at rest with AES-256. The design ensures only one backend fetch per hot key miss, protecting the database from overload and maintaining P99 cache read latency under 200ms.

Key Decisions
  • Use Redis Cluster to handle 1 million QPS cache requests with horizontal scalability
  • Implement Redlock distributed locking to ensure only one cache refresh per hot key miss, preventing thundering herd
  • Adopt stale-while-revalidate TTL policy to serve stale data during backend fetch delays, maintaining low latency
  • Encrypt all data in transit with TLS and at rest with AES-256 to meet security requirements
  • Provide client sync APIs to support offline delivery and eventual consistency
  • Trigger cache refresh asynchronously with fallback to stale data to maintain P99 latency under 200ms
  • Monitor lock acquisition and cache miss patterns to detect and mitigate stampede early
  • Redis with Redlock distributed locking to coordinate cache refreshes and prevent thundering herd
  • Stale-while-revalidate TTL policy in Redis to serve stale data during backend fetch delays
  • TLS encryption for all data in transit and AES-256 encryption at rest in Redis and backend stores
  • Client sync APIs to support offline delivery and eventual consistency
  • Use of Redis Cluster for horizontal scalability to handle 1M QPS cache requests
  • Backend database protected from overload by single refresh owner per key enforced by distributed lock
  • Cache refresh triggered asynchronously with fallback to stale data to maintain P99 < 200ms latency
  • Monitoring and alerting on lock acquisition failures and cache miss spikes to detect stampede early

Practice

(1/5)
1. In a Count-Min Sketch system, at step 3 the Update Worker hashes an incoming event key with the second hash function. What happens to the corresponding counter in the sketch at this step?
easy
A. The counter is reset to zero before incrementing
B. The counter at the hashed index is incremented by one
C. The counter is decremented to avoid overcounting
D. The counter is replaced with the maximum of current and new value

Solution

  1. Step 1: Understand Update Worker hashing

    Each hash function maps the event key to an index in the sketch array.

  2. Step 2: Increment counter at hashed index

    The Count-Min Sketch increments the counter at that index to record the event occurrence.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Update increments counters at hash indices to track frequencies [check]
Hint: Update increments counters at hash indices, never resets or decrements [check]
Common Mistakes:
2. In the search ranking system request flow, at step 3 the Ranking Component calculates BM25 scores for candidate documents. What happens if the document frequency (DF) data is stale at this step?
easy
A. The query is rejected until fresh DF data is available
B. BM25 scores are recalculated later with fresh DF, so initial ranking is unaffected
C. The system falls back to TF-IDF scoring automatically to avoid stale data impact
D. Ranking Component uses stale DF, causing inaccurate relevance scores and suboptimal ranking

Solution

  1. Step 1: Understand BM25 reliance on DF

    BM25 scoring depends on accurate document frequency to weigh term rarity; stale DF skews scores.

  2. Step 2: Trace impact of stale DF at Ranking Component

    Ranking uses stale DF directly, leading to inaccurate relevance scores and suboptimal document ordering; no automatic fallback or query rejection occurs.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stale DF causes inaccurate BM25 scores and ranking errors [check]
Hint: BM25 depends on fresh DF; stale DF skews scores [check]
Common Mistakes:
3. A large-scale key-value store needs to quickly filter out non-existent keys before querying a slow backend database. Which component best handles this filtering to reduce backend load?
easy
A. Use a Bloom filter to probabilistically test key existence before backend query
B. Use a relational database index to speed up key lookups
C. Use a distributed cache like Redis to store all keys for exact lookup
D. Use a consistent hashing ring to route keys to backend shards

Solution

  1. Step 1: Identify the filtering requirement

    The system needs a fast, memory-efficient way to filter out keys that definitely do not exist before hitting the slow backend.

  2. Step 2: Evaluate component suitability

    Redis cache storing all keys (A) is expensive and not scalable for huge key sets. Relational DB indexes (C) still require backend queries. Consistent hashing (D) routes keys but does not filter non-existent keys. Bloom filters (B) provide fast probabilistic membership tests with low memory.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Bloom filters reduce backend queries by filtering non-existent keys [check]
Hint: Bloom filters quickly say no before expensive lookups [check]
Common Mistakes:
4. At 10x transaction volume, which component in the digital wallet system is most likely to become the first bottleneck, and why?
hard
A. The event log (Kafka), because partition count limits throughput and rebalancing partitions causes downtime
B. The reconciliation service, because it performs expensive cross-checks on all transactions synchronously
C. The API gateway, because it handles all client requests and cannot horizontally scale due to session affinity
D. The ledger database, because it requires strong consistency and cannot shard entries without breaking double-entry guarantees

Solution

  1. Step 1: Analyze ledger database constraints

    Ledger DB enforces strong consistency and atomic double-entry transactions, limiting sharding options.

  2. Step 2: Compare other components

    Reconciliation (A) can be scaled asynchronously; API gateway (C) can be scaled with stateless design; Kafka (D) scales with partitioning but ledger DB consistency is harder to scale.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Ledger DB consistency limits sharding -> first bottleneck [check]
Hint: Ledger DB consistency limits sharding -> first bottleneck [OK]
Common Mistakes:
5. At 10x scale, which component in a horizontally scaled chat system fails first and why?
hard
A. The chat servers because WebSocket connections are stateful and cannot be rebalanced across servers dynamically
B. The load balancer because it cannot distribute connections evenly at high scale
C. The database because it cannot handle the increased write volume without sharding
D. The message queue because it runs out of partitions to distribute messages

Solution

  1. Step 1: Identify stateful WebSocket connections on chat servers

    Each connection binds to server memory, limiting horizontal scaling flexibility.

  2. Step 2: Analyze scaling challenges

    Chat servers cannot easily move existing connections; adding servers doesn't reduce existing server load.

  3. Step 3: Compare other components

    Databases can shard; load balancers scale horizontally; message queues can add partitions.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Stateful WebSocket servers bottleneck scaling due to connection affinity [check]
Hint: Stateful WebSocket servers block horizontal scaling first [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard