Learn AI Create the Future — with Pranay
Main site

Caching and Cost Control

Cache stampedes and single-flight

When a cached answer expires, many waiting requests can all rush to recompute it at the same moment. Single-flight makes only one of them actually do the work.

Read these first

On this page 8
  1. The short answer
  2. The analogy you have already lived
  3. Why it exists
  4. How it works
  5. A real example you have seen
  6. The honest part
  7. Remember this
  8. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

The short answer

A cache stampede is many requests rushing to recompute the same expired answer at once. Single-flight lets only one of them actually do it.

The analogy you have already lived

A ration shop opens its shutter at 8 a.m. sharp. Everyone who has been waiting outside pushes toward the counter at the exact same second. They were all waiting for the exact same thing to become available.

A well-run shop has one person open the shutter. One queue forms, and everyone else waits their turn calmly, served from that one opening event. A badly-run one has ten people trying to force the shutter open at once, each thinking they are the first.

A cache stampede is the badly-run version, happening inside a computer.

Why it exists

A popular cached answer eventually expires. The moment it does, a hundred requests for that same answer can arrive in the next second. A naive cache says "not here" to every single one of them. Every single one then asks the real, slow, expensive model to compute it again.

One expired entry should cost one recomputation. Without protection, it can cost a hundred, all landing on the model at the same instant. That is often exactly when it can least afford it.

How it works

   WITHOUT protection:

   10 requests arrive for the same expired key, all at once
              |
        all 10 see "not cached"
              |
   all 10 call the slow model AT THE SAME TIME
   (10x the load, for one real question)


   WITH single-flight:

   10 requests arrive for the same expired key, all at once
              |
   the FIRST one says "I'll compute it" and starts working
   the other 9 say "someone is already computing this, I'll wait"
              |
   the first one finishes, saves the answer
              |
   all 9 waiters get handed that SAME answer, instantly

Single-flight is the name for this pattern. Only one request per key is ever "in flight" — actively being computed — at a time. Everyone else waits for it instead of duplicating it.

A real example you have seen

A ticket-booking website at the exact moment a popular show goes on sale. Every user who refreshes at 10:00:00 a.m. is, in effect, asking the same question at the same instant: "is this seat available?" Sites survive that moment mostly by protecting themselves with something like single-flight.

The honest part

Single-flight fixes duplicate work. It does not fix a system that is too slow to answer even one request fast enough for everyone waiting. Say your single real computation takes ten seconds, and ten thousand people are waiting on it. They are all waiting ten seconds either way. This pattern makes the number of real computations 1 instead of 10,000 — not 1 instead of 10.

Remember this

  • A cache stampede happens when an expired entry causes many duplicate recomputations at once.
  • Single-flight ensures only the first request for a key does the real work; the rest wait for its result.
  • It removes duplicate work. It does not make one real computation any faster.

What to learn next

Developer — Code and libraries.

Setup

No installs needed — this uses only Python's standard library threading.

The problem, then the fix, measured

single_flight.py
import threading
import time

CALL_COUNT = 0
call_lock = threading.Lock()

def slow_model(x):
    global CALL_COUNT
    with call_lock:
        CALL_COUNT += 1
    time.sleep(0.2)  # pretend this is a real, expensive model call
    return x * x

# ---- Without protection: every thread that misses the cache calls the model ----
cache = {}

def get_naive(x):
    if x in cache:
        return cache[x]
    result = slow_model(x)
    cache[x] = result
    return result

CALL_COUNT = 0
threads = [threading.Thread(target=get_naive, args=(7,)) for _ in range(10)]
start = time.perf_counter()
for t in threads: t.start()
for t in threads: t.join()
print(f"naive:         {CALL_COUNT} real model calls, {(time.perf_counter()-start)*1000:.0f} ms")

# ---- With single-flight: only the first caller runs the model; the rest wait ----
cache.clear()
in_flight, in_flight_lock = {}, threading.Lock()

def get_single_flight(x):
    with in_flight_lock:
        if x in cache:
            return cache[x]
        if x in in_flight:
            event, wait_here = in_flight[x], True
        else:
            event = threading.Event()
            in_flight[x], wait_here = event, False

    if wait_here:
        event.wait()
        return cache[x]

    result = slow_model(x)
    cache[x] = result
    with in_flight_lock:
        del in_flight[x]
    event.set()
    return result

CALL_COUNT = 0
threads = [threading.Thread(target=get_single_flight, args=(7,)) for _ in range(10)]
start = time.perf_counter()
for t in threads: t.start()
for t in threads: t.join()
print(f"single-flight: {CALL_COUNT} real model call(s), {(time.perf_counter()-start)*1000:.0f} ms")
Output
naive:         10 real model calls, 202 ms
single-flight: 1 real model call(s), 201 ms

A real run on this machine: ten simultaneous requests, ten wasted recomputations without protection, one with it. Both versions take about the same wall-clock time for these ten callers. Single-flight does not make the winner faster — it stops the other nine from doing needless work.

Line-by-line walkthrough

threading.Event(). A simple signal one thread can wait on and another can set. The first request creates it and stores it in in_flight. Later requests for the same key find it there, and wait on it instead of starting their own computation.

Two separate locks. call_lock protects the call counter, which exists only to measure the demo. in_flight_lock protects the decision of "am I first?" That decision has to be atomic, or two threads can both believe they are first at the same instant.

event.set() after saving to cache. The order matters. Every waiter wakes up only after the answer is already in cache, so return cache[x] is guaranteed to find it there.

Common mistakes

Checking the cache and starting the computation as two separate, unlocked steps. That gap between "check" and "start" is exactly where a stampede sneaks in. Two threads can both check, both see nothing, and both start — before either one has registered as "in flight."

Forgetting to remove the key from in_flight on error. Say slow_model raises an exception and the cleanup line is skipped. Every future request for that key then waits on an Event that never fires. Use a try/finally around the real computation in production code.

Applying this to a single Python process only. The pattern above only protects one process. If your service runs multiple worker processes or machines, a stampede can still happen across them. A shared lock in Redis (SET key value NX EX ttl, the standard "distributed single-flight" pattern) extends the same idea across machines.

Try it yourself

Change time.sleep(0.2) in slow_model to time.sleep(1.0) and rerun both versions. Watch how much bigger the gap in real model calls becomes as the slow work gets slower. Stampedes hurt more, the more expensive each duplicate call is.

What to learn next

Researcher — Mathematics and papers.

The dogpile effect and TTL jitter

Cache stampedes are also called the dogpile effect or cache avalanche in distributed-systems literature. A closely related failure mode occurs even with single-flight in place. If many different keys were all populated at the same time — a cold-start deploy, a bulk warm-up job — they all expire at the same time too. The backend then sees a coordinated spike across many keys simultaneously, rather than one.

The standard mitigation is TTL jitter: instead of setting every entry's time-to-live to exactly $T$, set it to $T \pm \delta$ for a random $\delta$ drawn per entry. This spreads expirations over a window instead of a single instant, converting a spike into a smoother, more manageable load curve.

Probabilistic early expiration

Vattani, Chierichetti and Lowenstein (2015, at Google) describe probabilistic early recomputation. Rather than waiting for an entry to expire and then racing to recompute it, each read of a soon-to-expire entry independently recomputes it with a rising probability as the true expiration approaches, weighted by how long the last recomputation took. This spreads the recomputation cost across the approach to expiry, rather than concentrating it at one instant. It needs no inter-process coordination — no lock, no shared state — at the cost of occasionally recomputing slightly early.

Locking granularity trade-offs

The demo above uses one global in_flight_lock guarding a dictionary of per-key events — correct, and adequate at moderate concurrency, but a single lock across all keys becomes a contention point at very high request rates. Production implementations — Redis's SETNX-based locks, memcached's add-based locks — shard this concern per key. They use the cache backend's own atomic operations rather than an in-process Python lock, so contention on one key never blocks progress on an unrelated key.

Failure mode when the leader dies

Single-flight introduces a new failure mode that a naive cache does not have. If the request computing the value crashes or hangs after registering as "in flight" but before setting the result, every waiter can block indefinitely. Correct implementations pair the lock with a timeout — either the lock itself expires (EX on a Redis key), or waiters give up and attempt to become the new leader after a bounded wait.

Papers

What to learn next