Stampedes Hot Keys and Cold Cache Recovery

01 The idea

The problem this lesson solves

A popular cache entry expires and five hundred requests miss together. If each performs the same expensive database query, the cache has converted one refresh into a burst of duplicate work. After a full restart, many different keys may miss instead. These are related but distinct recovery problems, and they need more than a longer TTL.

You should recognize the application, the database and the request path. Treat the database as the authority unless explicitly stated otherwise.

02 Worked example

Protect the origin during 500 simultaneous misses

03 The method

Understand the mechanism

Identify same-key stampedes and broad cold starts

A stampede occurs when many callers concurrently rebuild the same missing or expired value. The repeated origin work is largely redundant. A cold start across many distinct keys can overwhelm the origin even if every key has only one loader.

Suppose 500 callers request a7 during a 100-ms rebuild. Basic cache-aside can issue up to 500 origin loads if they all observe the miss before a fill becomes visible. A same-key coordination mechanism can reduce that to one active rebuild within its coordination scope.

Now suppose 500 callers request 500 different keys. One loader per key still means 500 origin loads. Protecting the origin therefore requires a global or appropriately partitioned concurrency/admission budget in addition to same-key deduplication.

Measure which pattern you have. Hot-key request concentration, synchronized expiry and a namespace-version rollout produce different miss distributions. The remedy should address the distribution instead of assuming every miss storm is identical.

Coalesce work with a bounded single-flight mechanism

Single-flight associates an in-progress load with a key. The first caller becomes the loader; later callers join its result rather than starting duplicate work. On completion, the result is delivered to waiters and eligible data is cached.

Bound the wait. If the loader hangs, hundreds of callers must not wait forever or retain unbounded memory. Use a deadline, cancellation policy and documented fallback. Remove or transition the in-progress record reliably when the loader fails.

An in-process single-flight map only coordinates callers within that process. With ten app instances, the origin may still receive ten simultaneous rebuilds for the same key. That can be acceptable under the budget, or it can motivate shared coordination.

Shared coordination adds failure questions. A lease can expire while a slow worker is still running, allowing another loader to begin. Ownership-aware release prevents an old worker from deleting a successor’s lock, but preventing stale side effects may require fencing or conditional version checks at the resource being written.

Protect against distinct-key overload

Use a bounded semaphore, queue or admission mechanism around origin rebuild work. If the origin can safely handle only a certain number of concurrent expensive loads, the cache layer should not exceed it merely because keys differ.

The budget should consider all callers and app instances. A local limit of twenty on each of fifty instances permits one thousand concurrent loads. If the origin’s safe budget is one hundred, those local limits do not establish the intended global protection.

Decide how callers behave when capacity is exhausted. They may wait in a bounded queue, receive a retryable error, or obtain an acceptable stale result. Each choice has latency, availability and freshness consequences. Dropping the limit under pressure defeats its purpose.

Propagate the remaining deadline. Loading a result after every waiting caller has timed out can waste scarce recovery capacity, although some deliberate background warmup may still be useful. Separate that warmup budget from interactive admission.

Spread expiry and rebuild ahead when appropriate

If many entries receive the same TTL during a bulk fill, they can expire together. Adding bounded random jitter to expiration can spread the rebuild load. Jitter changes the expiry distribution, so the resulting lifetime must still fit the freshness policy.

Refresh-ahead starts rebuilding before an entry becomes unusable. It can keep a hot value available, but it consumes origin work and needs coordination so every request does not trigger its own refresh. Refreshing cold entries wastes capacity.

Serving stale while one refresh runs can preserve availability for content that permits it. Apply a maximum stale policy and distinguish load failure from authoritative deletion or revocation. An old authorization result may be unacceptable even when an old article summary is fine.

None of these mechanisms removes the need to test a completely empty cache. A deployment, data loss or key-version change can bypass the steady-state expiry pattern. Recovery capacity needs its own plan.

Handle hot keys without confusing reads and writes

A hot read key can overload one shared-cache owner even when the database is protected by a high hit ratio. Local copies, replicated read serving or an edge cache can spread suitable read work, subject to the freshness contract.

Adding virtual nodes to a sharded cache balances key ranges more finely, but one key still belongs to one logical placement under a simple owner model. Equal key counts do not imply equal request demand.

Hot writes are harder to spread because updates may need a single ordered authority. Sharding a counter into partial counters can distribute increments, but exact reads and reset semantics become a different problem. Do not propose salting keys without explaining how the application combines or locates the resulting values.

Identify the unit of contention: one key’s lookup rate, one large value’s bandwidth, one loader’s compute cost or one ordered update stream. Different units justify different designs.

Make recovery a controlled operating mode

After cache loss, start with a known origin budget and gradually restore admitted load or selected warm keys. Prioritize data with demonstrated value rather than fetching every historical record. Measure whether warmup reduces misses enough to justify its origin cost.

Observe origin concurrency, queue time, timeout rate, rebuild duration, waiter count and cache hit ratio. A rising hit ratio can coexist with an overloaded origin if the remaining misses are expensive. Recovery is successful when user-visible behavior stabilizes within the defined target.

Test loader crashes, expired leases, stale fills and cancellation. The fill must still obey the freshness protocol from the prior lesson; single-flight reduces duplicate work but does not automatically make an old result current.

The final design combines independent protections: per-key coordination for duplicate work, bounded total origin work for broad misses, a deliberate stale-data policy and measured warmup. Each solves a specific part of the recovery problem.

on miss(key):
  join an existing bounded rebuild for key, if present
  otherwise acquire a safe rebuild responsibility
  enter the bounded origin-concurrency budget
  load and conditionally fill according to freshness policy
  release only the responsibility still owned by this worker

04 Cheat sheet

Review the decisions

Use this table to explain the mechanism and its limit without memorizing a product name.

05 Where & why

Check the primary references

Use official references for protocol and implementation details. The questions here are teaching prompts.

06 Interview questions

Explain the reasoning out loud

Answer before opening the explanation. The questions progress from vocabulary to decisions and failure behavior.

07 Practice problems

Practice a new case

Solve the new cases before revealing hints. Complete worked solutions follow the set.

Worked solutions