Cache stampede prevention in HLD - Scalability & System Analysis

Scalability Analysis - Cache stampede prevention

Growth Table: Cache Stampede Prevention

Users / Traffic	Cache Hits	Cache Misses	Origin Server Load	Cache Stampede Risk	Latency Impact
100 users	High (95%+)	Low	Low	Negligible	Low
10,000 users	High (90%+)	Moderate	Moderate	Possible on hot keys	Moderate
1,000,000 users	High (85%+)	High	High	High risk on popular keys	High
100,000,000 users	High (80%+)	Very High	Very High	Severe risk, system overload	Very High

First Bottleneck

The first bottleneck is the origin server or database behind the cache. When many users request the same data that expires simultaneously, the cache misses spike. This causes a sudden surge of requests to the origin, overwhelming it. This is called a cache stampede. The origin server CPU, memory, or database connections become saturated first.

Scaling Solutions

• Mutex Locking: Use locks so only one request fetches data from origin while others wait for cache refill.
• Request Coalescing: Combine multiple requests for the same key into one origin fetch.
• Early Expiration: Refresh cache before expiry to avoid many misses at once.
• Randomized Expiry: Add random time to cache TTL to spread expirations.
• Backup Cache: Serve stale data temporarily while refreshing cache.
• Distributed Locks: Use Redis or similar for locks in multi-server setups.
• Cache Warming: Preload popular keys before traffic spikes.

Back-of-Envelope Cost Analysis

• At 1M users, assume 10% cache miss spike on a hot key: 100,000 origin requests in seconds.
• Origin server handles ~5,000 QPS; 100,000 QPS burst overloads it 20x.
• Network bandwidth: 1 Gbps (~125 MB/s) may saturate if responses are large.
• Memory for locks and cache metadata is minimal compared to data size.
• Implementing locks and randomized TTL adds negligible cost but prevents expensive origin overload.

Interview Tip

Start by explaining what a cache stampede is and why it happens. Then identify the origin server as the first bottleneck. Discuss simple solutions like locking and randomized TTL. Finally, mention distributed systems challenges and how to handle them. Keep answers structured: problem, bottleneck, solutions, trade-offs.

Self Check

Your database handles 1000 QPS. Traffic grows 10x with many users requesting the same cached key at once. What do you do first?

Answer: Implement cache stampede prevention by adding locking or request coalescing so only one request hits the database while others wait for cache refresh. This prevents overload and keeps latency low.

Key Result

Cache stampede causes origin server overload when many cache misses happen simultaneously. Prevent it by locking, request coalescing, and randomized cache expiry to spread load and keep the system stable.

Practice

1. What is the main goal of cache stampede prevention in system design?

easy

A. To prevent many requests from hitting the database simultaneously

B. To increase the size of the cache storage

C. To reduce the number of cache servers

D. To encrypt cached data for security

Solution

1. Step 1: Understand cache stampede problem

   Cache stampede happens when many requests try to fetch data from the database because the cache expired or missed.

2. Step 2: Identify the goal of prevention

   The goal is to stop all these requests from hitting the database at once to avoid overload.

3. Final Answer:

   To prevent many requests from hitting the database simultaneously -> Option A

4. Quick Check:

   Cache stampede prevention = prevent database overload [OK]

Hint: Focus on reducing database hits during cache misses [OK]

Common Mistakes:

• Confusing cache size with stampede prevention
• Thinking encryption is related to stampede
• Assuming reducing cache servers helps stampede

2. Which of the following is a common technique used to prevent cache stampede?

easy

A. Storing data only in the database

B. Increasing cache TTL to infinite

C. Disabling cache for all requests

D. Using distributed locks around cache refresh

Solution

1. Step 1: Review common stampede prevention methods

   Techniques include locking, early expiration, and request coalescing to control cache refresh.

2. Step 2: Match technique to options

   Distributed locks prevent multiple processes from refreshing cache simultaneously, stopping stampede.

3. Final Answer:

   Using distributed locks around cache refresh -> Option D

4. Quick Check:

   Locking = stampede prevention [OK]

Hint: Look for locking or coordination methods in options [OK]

Common Mistakes:

• Choosing infinite TTL which can cause stale data
• Disabling cache which increases load
• Ignoring locking as a prevention method

3. Consider this pseudo-code for cache stampede prevention:

if cache miss:
  acquire lock
  if cache still miss:
    data = fetch from DB
    update cache
  release lock
return cached data

What happens if the lock is not used here?

medium

A. Multiple requests fetch from DB simultaneously causing overload

B. Cache never updates and returns stale data

C. Requests wait indefinitely causing deadlock

D. Cache size increases exponentially

Solution

1. Step 1: Analyze the role of the lock

   The lock ensures only one request fetches data from DB and updates cache on miss.

2. Step 2: Consequence of missing lock

   Without lock, many requests detect cache miss and all fetch from DB, causing overload.

3. Final Answer:

   Multiple requests fetch from DB simultaneously causing overload -> Option A

4. Quick Check:

   No lock = DB overload [OK]

Hint: Lock prevents simultaneous DB fetch on cache miss [OK]

Common Mistakes:

• Thinking cache never updates without lock
• Confusing deadlock with missing lock
• Assuming cache size grows without lock

4. A system uses early expiration to prevent cache stampede by setting cache TTL shorter than data TTL. However, users report stale data sometimes. What is the likely cause?

medium

A. Cache TTL is longer than data TTL causing stale reads

B. Cache is not refreshed after early expiration due to missing lock

C. Database is down causing stale cache

D. Cache size is too small causing evictions

Solution

1. Step 1: Understand early expiration technique

   Early expiration refreshes cache before data TTL ends to avoid stampede.

2. Step 2: Identify cause of stale data

   If cache refresh is not coordinated (missing lock), cache may not update properly, causing stale data.

3. Final Answer:

   Cache is not refreshed after early expiration due to missing lock -> Option B

4. Quick Check:

   Missing lock = stale cache after early expiration [OK]

Hint: Check if locking coordinates cache refresh [OK]

Common Mistakes:

• Assuming TTL mismatch causes stale data
• Blaming database downtime without evidence
• Confusing cache size with freshness

5. You design a high-traffic API with cache stampede prevention. Which combination best prevents stampede while ensuring fresh data and minimal DB load?

hard

A. Disable cache and use database connection pooling

B. Use long cache TTL with no locking and rely on DB scaling

C. Use short cache TTL with distributed locking and request coalescing

D. Use infinite cache TTL and manual cache invalidation

Solution

1. Step 1: Evaluate each option for stampede prevention

   Use long cache TTL with no locking and rely on DB scaling risks DB overload without locking; C disables cache increasing DB load; D risks stale data.

2. Step 2: Identify best practice combination

   Short TTL triggers refresh often; distributed locking prevents multiple refreshes; request coalescing merges requests to reduce DB hits.

3. Final Answer:

   Use short cache TTL with distributed locking and request coalescing -> Option C

4. Quick Check:

   Locking + coalescing + short TTL = best stampede prevention [OK]

Hint: Combine locking and coalescing with short TTL for best results [OK]

Common Mistakes:

• Ignoring locking and causing DB overload
• Disabling cache increases latency and load
• Using infinite TTL causes stale data