System Design · Module 6 · Lesson 4 of 4 · 45 min

Stampedes Hot Keys and Cold Cache Recovery

Protect the origin when many requests miss together, distinguish hot keys from uneven key counts, and plan a bounded cache restart.

The cache failure path needs admission and concurrency limits so a missing copy cannot create unbounded origin work.

01 The idea

The problem this lesson solves

Five hundred requests arrive for a missing popular entry.

Prerequisite: earlier lessons introduce the vocabulary and shared examples used here. Follow the module order.

Single-flightCoalescing concurrent loads for one key into one shared rebuild.

Hot keyA key that receives enough traffic to dominate its serving owner.

TTL jitterVariation in lifetimes that spreads expiration events across different keys.

02 Worked example

Follow one worked example

Many misses: Same or distinct keys • Coalesce: One loader per key • Origin budget: Bound concurrent work • Recovery: Warm + observe.

Trace the example in order. Follow the same identities, units and state transitions through the diagram and the events below.

Expire one keyFive hundred requests arrive for a missing popular entry.

Coalesce duplicatesOne loader fetches while the other requests follow a bounded wait policy.

Bound the originA separate concurrency limit protects against many distinct missing keys.

Warm graduallyIncrease admitted traffic while observing origin latency, errors and saturation.

The cache failure path needs admission and concurrency limits so a missing copy cannot create unbounded origin work.

03 The method

Mechanisms decisions and a guided tutorial

Work through the explanation in order, then apply it in the tutorial. Each comparison names a cost as well as a benefit.

Choice or concept	Purpose	Boundary or cost
Single-flight	Duplicate work for one key	Waiters need bounds
TTL jitter	Synchronized expiry of different keys	Not a same-key lock
Origin concurrency limit	Total rebuild demand	Needs rejection or waiting policy
Hot-key local copy	Distributes eligible reads	More freshness coordination

Prevent duplicate rebuild work

If a popular entry expires while 1,000 requests arrive, naive cache-aside can issue 1,000 identical database reads. Request coalescing lets one request load while others wait. A distributed rebuild lock needs bounded waits, an expiry, unique ownership and safe release; a stale worker must not delete another worker's newer lock. TTL jitter spreads expiration times across different keys. It does not alone coalesce simultaneous misses for the same hot key.

A hot key is not fixed by moving unrelated keys

One viral short code can dominate a cache node. Adding shards redistributes many keys but a single key still has one owner under simple partitioning. A small short-lived local cache, read replicas with acceptable freshness, or a different serving strategy may spread those reads. Monitor per-key concentration carefully without exposing sensitive key values in logs. Guard the backing store with concurrency limits and admission control when the cache is unavailable.

Measure the hit and miss paths separately

Suppose a cache lookup takes 2 ms and a database read after a miss takes an additional 20 ms. At 90 percent hits, modeled mean lookup latency is 0.9 × 2 + 0.1 × 22 = 4 ms. This is a mean of assumed fixed costs, not a p99 prediction. When the hit rate drops, database demand increases and queueing can make the miss cost much worse than the assumed 20 ms. Observe hit rate, eviction, memory, miss latency and origin saturation together.

Make recovery part of the plan

A newly started cache is cold. Load likely hot data gradually, cap concurrent rebuilds, and watch the database before admitting full traffic. A cache outage should not trigger unlimited immediate fallbacks. Decide which requests can receive bounded stale data, which should be rejected, and which can wait. Keep durable business data in a store with the required persistence rather than assuming an evictable cache is a database replacement.

Count the duplicate work

One popular entry expires and five hundred callers miss together. Naive cache-aside can issue five hundred identical origin reads. Single-flight lets one loader perform the work while duplicate callers wait within a bounded policy. That reduces duplicate work for this key, not all demand on the database.

A distributed rebuild lock needs an owner token, expiry, safe release and a policy for slow or failed loaders. A worker whose lease expired must not delete a newer worker’s lock. Coordination mechanisms need failure semantics; a lock command name is not a complete stampede solution.

Jitter and hot-key spreading solve different problems

TTL jitter spreads expiration across different keys populated at similar times. It does not stop five hundred simultaneous misses for one already-expired key. A hot key also remains one ownership unit in simple sharding; moving unrelated keys to more nodes does not divide that key’s traffic.

An eligible short-lived local copy can spread hot reads across app instances, but introduces more copies and freshness work. Other designs use replicated reads or special serving for popular objects. Choose the mechanism from the freshness requirement and measured concentration, not a rule that every hot key needs a bigger cluster.

Recover gradually instead of stampeding all at once

A cold cache sends more demand to the origin. Bound total concurrent rebuilds as well as duplicate work per key. Warm likely popular entries at a controlled rate, admit traffic gradually and observe backing-store latency and saturation.

When limits are reached, choose bounded waits, eligible stale responses or a documented rejection. Unlimited fallback converts a cache outage into a database outage. The weighted mean latency calculation remains only a model: under overload, queueing changes the miss cost itself, which is why recovery testing must observe distributions and resource use.

Guided tutorial

1. Write the herd trace

Count origin reads with and without coalescing.

2. Separate controls

Assign jitter, per-key coalescing and total origin limits to their different problems.

3. Model a hot key

Explain why a single popular key still has one owner after adding unrelated shards.

4. Plan restart

Write warming rate, maximum rebuild concurrency, overload response and rollback signals.

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.

Choice or concept	Remember	Check
Single-flight	Duplicate work for one key	Waiters need bounds
TTL jitter	Synchronized expiry of different keys	Not a same-key lock
Origin concurrency limit	Total rebuild demand	Needs rejection or waiting policy
Hot-key local copy	Distributes eligible reads	More freshness coordination

Single-flightCoalescing concurrent loads for one key into one shared rebuild.

Hot keyA key that receives enough traffic to dominate its serving owner.

TTL jitterVariation in lifetimes that spreads expiration events across different keys.

05 Where & why

Check the primary references

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

Primary reference

Redis eviction policies

Read Redis eviction policies

Primary reference

Redis SET

Read Redis SET

Primary reference

Redis TTL

Read Redis TTL

Primary reference

HTTP stale-while-revalidate

Read HTTP stale-while-revalidate

State the implementation version and the workload assumptions when defending your own design.

06 Interview questions

Explain the reasoning out loud

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

What does Single-flight mean?

Coalescing concurrent loads for one key into one shared rebuild.

What does Hot key mean?

A key that receives enough traffic to dominate its serving owner.

What does TTL jitter mean?

Variation in lifetimes that spreads expiration events across different keys.

Why is single-flight not enough for every cold cache?

It coalesces duplicates for one key. Many distinct misses can still produce too much total origin work, requiring a separate concurrency and admission budget.

What does TTL jitter fail to solve?

It does not merge callers already missing the same key. It spreads expiry times across different entries.

Why not blindly delete a rebuild lock on completion?

The original lease may have expired and a new owner may hold the key. Release must verify ownership so an old worker cannot remove the new lock.

Does adding shards split a hot key’s reads?

1. Hit rate

18 / (18 + 6) = 0.75, or 75 percent.

2. Control matching

Jitter spreads different-key expiry; coalescing reduces duplicate same-key loads; a concurrency limit bounds total origin work.

3. Average latency

Mean = 0.8 × 1 + 0.2 × 31 = 7 ms under the fixed-cost model. It says nothing by itself about p99 or queueing under load.

4. Stampede defense

Use single-flight/coalescing for one rebuild and an origin concurrency limit or bounded wait to prevent overload. Jitter spreads different keys' expiry times, but these 500 requests already missed one key together.

5. Expired lease

A could delete B’s valid lock. Release must verify A still owns the responsibility, and stale fills need their own freshness checks.

6. Cold restart plan

Use controlled warming, per-key coalescing, a total rebuild budget and bounded admission. Serve eligible bounded stale data or reject according to the contract, while observing database saturation before increasing traffic.