How Do You Prevent a Cache Stampede When a Hot Key Expires?

Prompt and scope

A hot product-configuration key receives 50,000 reads per second. The source database is safe up to 200 queries per second, and rebuilding the cache takes 800 ms at p95. Cached data is fresh for 10 minutes, and the business tolerates at most 30 seconds of staleness. The service runs on 100 stateless application instances that share a remote cache and the same source database.

Design the complete read and refresh path. Cover soft expiry, hard expiry, the first cold load, a refresher crash, a cache outage, and source data changing during a refresh. Explain how you would prove that the design does not merely move concurrent load to the database. The throughput, latency, and expiry values are interview inputs, not performance claims about a product.

This is a backend reliability question. A current public set of 2026 SRE interview questions explicitly presents a cache stampede caused by a critical key expiring under 100,000 requests per second; this version turns that scenario into measurable engineering constraints. It is distinct from implementing an in-process LRU eviction policy because its core problem is cross-instance concurrency and failure semantics.

What the interviewer evaluates

First, the candidate should quantify the expiry event. If every arrival bypasses the cache during an 800 ms rebuild, approximately 50,000 × 0.8 = 40,000 requests may try to reach the origin. That is far beyond a safe rate of 200 queries per second. Adding a cache has not solved synchronized load when the cache entry disappears.

Second, a strong answer separates three protection layers. Local request coalescing constrains one process only; if each of 100 instances elects a refresher, the system may still issue 100 concurrent rebuilds. A distributed lease normally reduces cross-instance refreshes to one, but lease expiry, process pauses, and partitions can still create overlapping refreshes. An origin concurrency bulkhead or rate limit must therefore remain an independent final defense.

Third, expiry semantics must be explicit. Fresh data returns immediately. After soft expiry, data may be returned within the 30-second stale window while a refresh is attempted in the background. After hard expiry, the system cannot serve stale data forever: requests that do not own the refresh must wait for a bounded period, degrade, or fail rather than all reaching the origin.

Finally, the interviewer should hear how the design prevents an old refresher from overwriting a newer value. A lease provides exclusion only during its validity window; it is not an exactly-once guarantee. Cache entries need a source version or generation, and writes must compare versions before replacing data.

Questions to clarify

• Is stale data actually safe? This scenario allows at most 30 seconds. Balances, authorization, and inventory deductions may require stricter behavior.
• What does the origin limit measure? Treat 200 queries per second as the database-wide safe limit, while also asking for the per-key concurrency and timeout limits.
• Can a cold load return a default? By default no stale value exists, so only one refresher reaches the origin and followers wait for a bounded time. A static default is an explicit product degradation if available.
• How are entries invalidated? Use logical freshness and hard-expiry timestamps instead of physically deleting every copy at the same second. Source change events may refresh or invalidate entries early.
• Is this multi-region? Start with 100 instances in one region. Multiple regions need allocated origin budgets; a cross-region lock should not be assumed to solve every failure mode.
• Should callers know that data is stale? Internal responses and telemetry should at least record stale_age and the degradation reason. Product requirements decide whether end users see it.
• What happens if the cache fails? Define degradation and origin budgets in advance. A cache error cannot mean that every request queries the database.

30-second answer

“I would cache fresh_until, stale_until, and the source version with the value. Fresh hits return directly. During the 30-second stale window, return the old value and elect a refresher using per-process singleflight plus a distributed lease with an ownership token and TTL. On a cold or hard miss, followers only wait for a bounded time and reread with jitter. Refresh writes compare source versions, and lease release checks the token. Because lease expiry can still allow overlap, the database also needs per-key and global bulkheads. I would validate origin QPS, concurrency, and maximum stale age with expiry load tests, refresher crashes, lease overruns, and cache-outage drills.”

Step-by-step deep dive

Start by defining a cache entry rather than storing only the business value:

CacheEntry {
  value
  source_version
  generated_at
  fresh_until
  stale_until
}

fresh_until ends the 10-minute freshness period, and stale_until extends it by no more than 30 seconds. The remote key's physical TTL must cover stale_until plus a small cleanup margin; otherwise the cache will delete a value that is still safe to serve during soft expiry. The stale window is a business budget and must not be extended silently after repeated refresh failures.

The read path can be expressed as pseudocode:

entry = cache.get(key)
now = clock.now()

if entry exists and now < entry.fresh_until:
  return entry.value

if entry exists and now < entry.stale_until:
  try_refresh_async(key)
  return entry.value

return rebuild_or_wait(key, request_deadline)

The soft-expiry path protects request latency. The first request that notices soft expiry attempts a background refresh while the others keep using the old value. Per-process singleflight coalesces refresh calls by key; the public Go implementation defines this as one in-flight execution per key whose result is shared with duplicate callers. It does not cross process boundaries, so it is insufficient by itself across 100 instances.

Use a time-bounded lease for cross-instance refresh. A contender creates a random, non-reusable token and executes:

SET refresh:{key} {token} NX PX {lease_ms}

After acquiring the lease, reread the cache in case another refresher just completed, and query the origin only if a refresh is still needed. Release the lease only if its current value still equals the owner's token. A plain DEL is unsafe: an old refresher may pause until its lease expires, a successor may acquire a new lease, and the old process may resume and delete the successor's lease. Redis's distributed-lock guidance similarly requires a unique value and ownership check for safe release.

Set lease_ms above the measured refresh p99 plus network and scheduling margin, not mechanically to the 800 ms p95. A lease that is too short increases overlap; one that is too long delays takeover after a crash. Lease expiry only permits a new contender to try; it does not prove that the old operation stopped. Origin reads therefore still need a per-key singleflight service or database bulkhead, and cache writes must tolerate overlapping executions.

Read a monotonic source version with the data, such as a row version or event sequence. Replace the cache only when new.source_version >= cached.source_version. If the source has no reliable version, allocate refresh generations with an atomic increment in shared coordination storage and compare them atomically at the cache. The cache is still not the source of truth; a delayed refresh must not overwrite a newer version already installed by a change event.

A hard expiry or first load has no acceptable old value. The lease owner rebuilds only after entering the origin bulkhead. Followers reread the cache at short, jittered intervals within the request deadline instead of polling in lockstep. When that wait expires, return an explicit degraded response or error. A static default may be used if the product permits it, but apparent availability must not send all 50,000 requests to the origin.

The origin's final defense should include a per-key concurrency cap, a global refresh concurrency cap, and a query-rate budget. Under normal conditions only one rebuild runs for a key. During lease failures, the bulkhead still keeps total origin work inside a safe boundary. When capacity is exhausted, refreshes fail fast or enter a bounded queue; soft-expired requests continue to use values younger than 30 seconds, while hard misses follow the defined degradation policy.

When the cache is unavailable, applications must not shift the whole read rate to the database. A short-lived read-only near-cache may provide acceptable stale values, but all necessary origin reads still pass through the global bulkhead. Requests without a near-cache value must degrade or fail. Warm hot keys at a controlled rate during recovery instead of having every instance refill at once. Random TTL jitter helps when many different keys expire together, but it does not solve concurrent rebuilding of one hot key.

Related failure modes should remain separate. A cache stampede or hot-key breakdown is concurrent rebuilding after an existing hot key becomes unavailable. A cache avalanche is simultaneous expiry of many keys or a cache-wide outage. Cache penetration is repeated lookup of data that does not exist. TTL jitter primarily helps avalanches, while a short negative cache or Bloom filter helps penetration; neither replaces request coalescing for this scenario.

Predictably hot data can be refreshed before fresh_until. Cloudflare's published probabilistic early-revalidation approach increases refresh probability as expiry approaches, reducing lock contention under high request rates. A fixed statement such as “refresh 1% of requests” is unsafe because its behavior changes with traffic. The bounded stale window and background refresh also match the semantics of HTTP stale-while-revalidate: stale content is allowed only within an explicit interval while revalidation happens asynchronously.

For multiple regions, prefer regional caches and regional refreshers with allocated origin QPS and concurrency budgets. A single global lease adds cross-region latency and partition behavior to the read path. If every region shares one origin, a control plane can allocate refresh budgets or the origin can expose a centralized rebuild service. In either case, the sum of regional budgets must remain within 200 queries per second.

Observe fresh-hit, stale-served, and hard-miss rates; stale age; refresh attempts and failures; singleflight shared callers; lease contention and expiry; refresh latency; origin QPS, concurrency, and rejection; and cache latency and errors. Alert on exhausted origin budgets, values approaching stale_until, and sustained refresh failure rather than relying on cache hit rate alone.

Test the invariants directly. Expire the key under 50,000 requests per second and assert one origin rebuild per key in the normal case. Crash the refresher before its write and verify that stale data remains available and a successor takes over after lease expiry. Pause an old refresher beyond the lease and verify that it cannot replace a newer version. Disable the cache and verify that the origin remains within 200 queries per second and its concurrency bulkhead. Expire many keys together and verify TTL jitter plus the global budget.

Strong sample answer

“I would start with the worst-case load. Fifty thousand requests per second multiplied by an 800 ms rebuild produces roughly 40,000 arrivals during the expiry window, while the database is safe for only 200 queries per second. No follower may fall through directly to the origin.

I would cache the value with its source version, fresh_until, and stale_until. Return it directly for 10 minutes, then serve it for up to 30 additional seconds while attempting a refresh. Each process first coalesces local work with singleflight, then contenders use SET lock token NX PX lease to elect a cross-instance refresher. The owner rechecks the cache before querying the database. Lease release compares the token, and cache writes compare source versions so an old refresher cannot delete a new lease or overwrite newer data.

On a cold load or after 30 seconds, there is no acceptable stale value. One request rebuilds while followers reread with jitter until their deadline, then use an explicit default degradation or return an error. The database also has per-key and global bulkheads because lease expiry may allow overlapping refreshers; a lock does not replace capacity protection.

I would load-test the exact expiry boundary and inject a refresher crash, a pause longer than the lease, cache failure, and a concurrent source update. Acceptance criteria include origin QPS no higher than 200, one normal rebuild per key, stale age no higher than 30 seconds, and no version regression from a delayed writer. That gives latency, freshness, and origin safety measurable bounds.”

Common mistakes

• Adding only random TTL jitter → This spreads expiry across different keys but does not stop concurrent rebuilding of one hot key → Coalesce work per key and retain an origin bulkhead.
• Using only in-process singleflight → One hundred instances may still create 100 refreshers → Combine local coalescing with a cross-instance lease.
• Reading the database before acquiring refresh rights → The concurrency spike has already reached the origin → Elect first, recheck the cache, and then enter the origin budget.
• Taking a SETNX lock without a TTL → A crashed refresher may block updates indefinitely → Use a bounded lease with takeover behavior.
• Releasing with a plain DEL → An old refresher may delete its successor's lease → Atomically release only when the unique token still matches.
• Treating a lease as exactly-once execution → A process paused past the TTL can overlap a successor → Use an origin bulkhead and versioned writes to tolerate overlap.
• Serving stale forever after failures → Data age loses its upper bound → Serve only before stale_until, then degrade or fail explicitly.
• Sending all traffic to origin during a cache outage → 50,000 reads per second will overwhelm an origin safe for 200 → Use near-cache values where allowed and route every origin read through the shared budget.
• Conflating stampede, avalanche, and penetration → The remedy no longer matches the failure → Use request coalescing, TTL jitter, and negative caching for their respective problems.
• Monitoring only hit rate → A high hit rate can hide failed refreshes and short origin spikes → Also monitor stale age, refresh concurrency, leases, and origin budgets.

Follow-ups

Follow-up 1: What if the business cannot serve stale data at all?

Remove stale responses and let followers wait only for a bounded period. Provision enough rebuild capacity and return explicit failures without sacrificing origin safety.

Follow-up 2: How long should the lease TTL be?

Start from measured refresh p99, network timeout, and scheduling pauses, then add margin and observe how often work outlives the lease. The 800 ms p95 is insufficient by itself.

Follow-up 3: What if source data changes during refresh?

Read and carry a source version, then conditionally update the cache. A newer version installed by a change event must not be replaced by a delayed refresh.

Follow-up 4: What if the whole cache cluster is unavailable?

Serve acceptable near-cache values, keep every necessary origin read behind the global bulkhead, degrade when no copy exists, and warm keys at a controlled rate during recovery.

Follow-up 5: How does negative caching fit?

Cache a confirmed “not found” result for a short TTL to prevent penetration. It is independent of coalescing refreshes for an existing hot key.

Follow-up 6: When is probabilistic early refresh useful?

For recomputable, stale-tolerant, high-rate data. The probability should depend on remaining freshness and observed traffic, with refresh failure and origin budgets still enforced.

Follow-up 7: Should regions share one lock?

Usually no. Refresh regionally and allocate origin budgets. Central coordination is justified only when global single refresh is required and cross-region latency and partitions are acceptable.

Follow-up 8: How do you prove the design works?

Drive 50,000 requests per second across soft and hard expiry while injecting crashes, pauses, cache failure, and version races. Assert one normal refresh per key, origin load within budget, staleness at most 30 seconds, and no version rollback.