Cache Stampede Prevention Between Services: Jitter, Early Refresh, Locks

What a cache stampede is and the three shapes it takes

A cache stampede, or thundering herd, happens when many callers miss the cache for the same data at the same moment and all try to recompute it. The cache stops shielding the backing store at exactly the moment demand peaks. It shows up in three distinct shapes, and the differences determine which defense works.

Jitter does nothing for a single hot key, because spreading one expiry still leaves one expiry. Locks do not help a cold cache either. When every key is missing, per-key coordination still lets one recompute per key through, and that is the full load.

Between services, the problem compounds. Dozens of instances across several services share the cache, and each one detects the miss independently, so in-process deduplication only collapses requests within one instance. Each recompute often fans out into its own downstream calls, so one miss becomes several queries. Callers with short timeouts give up on slow recomputes and retry, which adds load to a dependency that is already saturated.

Teams running multiple services against a shared cache with expensive or hot keys need defenses at several layers. No single technique covers all three shapes.

Copy   Service A             Service B             Service C
+-------------+       +-------------+       +-------------+
| inst a1..a4 |       | inst b1..b6 |       | inst c1..c3 |
| local dedup |       | local dedup |       | local dedup |
+-------------+       +-------------+       +-------------+
      |                     |                     |      ^
      | GET key             | GET key             |      | retry after
      v                     v                     v      | short timeout
+---------------------------------------------------+    |
|  Shared cache: key expired -> MISS seen by every  |    |
|  instance independently (no cross-service dedup)  |    |
+---------------------------------------------------+    |
      |                     |                     |      |
      v                     v                     v      |
+-------------+       +-------------+       +-------------+
| recompute   |       | recompute   |       | recompute   |
+-------------+       +-------------+       +-------------+
   |   |   |             |   |   |             |   |   |
   v   v   v             v   v   v             v   v   v
+---------------------------------------------------------+
| Downstream: DB, search, other services (fan-out)        |
| load ~ instances x missed keys x calls/recompute x tries|
+---------------------------------------------------------+

 Hot key:      1 key expires, N callers     -> early refresh / lock
 Synchronized: many keys share one TTL      -> TTL jitter
 Cold cache:   flush, failover, deploy      -> warm-up / admission

Each instance of each service detects the same miss on its own, recomputes with downstream fan-out, and retries on short timeouts, so load on dependencies multiplies; the legend maps the three stampede shapes to the mitigation each one needs.

When should stampede prevention be used?

Use these defenses when a cache miss is expensive enough, or concurrent enough, that duplicated recomputation can hurt the backing store or user-facing latency. Typical signals:

• Downstream load spikes line up with TTL boundaries. Database or service QPS jumps at regular intervals that match a key's TTL, or shortly after a backfill or deploy that wrote many keys at once.
• Latency spikes cluster on a few hot keys. Most requests are fast, but p99 jumps when a heavily read key expires and readers wait on recompute.
• Recompute is slow or fans out. A value built from several queries, a search call or another service's response turns one miss into many downstream requests.
• Many instances share the cache. Horizontal scaling multiplies the number of independent callers that see the same miss.
• Bulk writes stamp identical TTLs. Import jobs, cache warmers and backfills all create synchronized expiry.
• Cache flushes or failovers are part of normal operations. Replica promotion, region launches or key-format changes produce cold caches.

Some cases call for less or none of this. If recompute is cheap and traffic per key is low, the cost of an occasional duplicate miss is smaller than the cost of maintaining locks and refresh logic. Stale-while-revalidate is the wrong choice for data where a stale read is a correctness bug, such as balances, permissions and inventory. There, per-key coordination with fail-fast or short waits is safer. The decision table in the section on combining layers maps recompute cost and request rate to the layers worth applying.

How does stampede prevention work?

Every technique in this article acts on one of three things: when keys expire, who recomputes and when they do it, and how many callers recompute at once. A fourth group handles the cases where there is nothing usable to cache yet.

1. Change when keys expire (TTL jitter). Each write adds a bounded random offset to the TTL, so keys written together expire across a window instead of in the same second. This reduces the peak rate of recomputes without reducing their total number.
2. Move recompute ahead of expiry (probabilistic early expiration, stale-while-revalidate). A reader refreshes the value before it expires, or keeps serving the old value while one background refresh runs. Readers stop seeing a hard miss on hot keys, so recompute leaves the request's critical path.
3. Limit concurrent recomputes (single-flight, distributed locks). Within a process, single-flight makes one request the leader and has the rest wait for its result. Across processes, a per-key lock with a unique token lets one holder recompute while the others wait, serve stale data or fail fast.
4. Handle absent, failing and empty data (negative caching, error caching, warm-up, admission control). Sentinels stop repeated misses for keys that do not exist. Short-lived error entries stop callers from piling onto a failing backend. Pre-warming and concurrency caps keep a cold cache from sending the full load to the origin.

On a single read with all layers enabled, the path looks like this. The reader fetches the key. If the value is present and not near soft expiry, it is returned. If the early-refresh check fires, the reader tries a short lock and starts a background refresh if it wins, then returns the cached value either way. If the key is missing, the in-process single-flight collapses concurrent local misses into one call. That call takes the distributed lock, recomputes, and writes the result back with a jittered TTL. Losers follow the configured policy. The sections below cover each layer in detail.

Spreading expiry with TTL jitter

The cheapest layer is to stop keys from expiring together. Bulk writes such as a backfill job, a deploy that warms the cache, or a nightly import all stamp the same TTL at nearly the same moment. Those keys then expire together, and their recomputations hit the backing store at once. TTL jitter breaks that alignment by adding a bounded random offset to every TTL: base TTL plus or minus a percentage, drawn uniformly.

Choose the range from the write pattern, not by habit. The spread has to be wide compared with the window in which the keys were written, or they still expire in a clump. Illustrative estimate: a job writes 200,000 keys in 20 seconds with a one-hour TTL. With ±10% jitter, expiry spreads across 12 minutes, so the recompute rate drops by roughly 36× compared with the original 20-second burst. If the TTL is also a staleness guarantee, jitter only downward (base minus 0–15%) so no entry outlives its contract.

Apply the helper on every write, including refreshes and lock-holder recomputes. If any write path uses the fixed TTL, keys that were reloaded together line up again.

Know the limits. Jitter moves recomputations around in time but does not reduce how many there are. It makes expiry nondeterministic, so when debugging you should log or read the actual TTL on the key rather than infer it from config. It also does nothing for a single hot key, because one key has one expiry, and every concurrent reader still misses at that moment.

Copyimport random

import redis

BASE_TTL_S = 3600      # one-hour base TTL
JITTER_FRACTION = 0.10 # +/-10% -> expiry spread over ~12 minutes

r = redis.Redis(host="cache.internal", port=6379)


def jittered_ttl(base_s: int = BASE_TTL_S,
                 fraction: float = JITTER_FRACTION,
                 downward_only: bool = False) -> int:
    """Return base TTL plus a bounded, uniformly drawn offset.

    downward_only=True keeps every TTL <= base, for when the TTL
    is also a staleness guarantee and no entry may outlive it.
    """
    spread = base_s * fraction
    low = -spread
    high = 0.0 if downward_only else spread
    return max(1, int(base_s + random.uniform(low, high)))


def cache_write(key: str, value: bytes) -> None:
    # Single write path: backfills, warmers, refreshes and lock-holder
    # recomputes all go through here, so none of them reuse a fixed TTL
    # and line keys back up on the same expiry.
    r.set(key, value, ex=jittered_ttl())


def actual_ttl(key: str) -> int:
    # Expiry is nondeterministic, so when debugging read the real
    # remaining TTL from the key instead of inferring it from config.
    # Returns -2 if the key is missing, -1 if it has no expiry.
    return r.ttl(key)

A Python helper that adds a bounded random offset (optionally downward-only) to the base TTL on every cache write via redis-py, plus a way to read the key's actual remaining TTL when debugging.

Taking recompute off the critical path: probabilistic early expiration and stale-while-revalidate

The fix for a single hot key is to stop treating expiry as a cliff. If one reader refreshes slightly before the value expires, nobody ever sees a miss.

Probabilistic early expiration

The XFetch approach stores two extra fields with the value: delta, the measured recompute time, and expiry, the absolute expiry timestamp. On each read, a reader refreshes early when:

now - delta * beta * ln(rand()) >= expiry

Here rand() is uniform in (0, 1], so ln(rand()) is zero or negative and the subtraction pushes now forward by a random amount. Most draws give a small push, and a few give a large one. As now approaches expiry, smaller pushes cross the line, so the refresh probability rises smoothly. Scaling by delta makes slow-to-compute keys start refreshing earlier, because they need more lead time.

beta controls how aggressive this is. A value of 1.0 is the usual default.

• Too high: cheap keys refresh long before they need to, which wastes backend capacity.
• Too low: the window shrinks toward zero, and you are back to a synchronized miss at expiry.

Stale-while-revalidate

Store a soft-expiry timestamp inside the payload, for example {value, soft_expiry, delta}, and set the cache's native TTL as the hard limit. After soft expiry, readers keep serving the stale value while a single background refresh runs. The hard TTL is the upper bound on staleness.

Avoid this pattern for balances, permissions and inventory, where a stale read is a correctness bug. Also watch for a broken refresher. If background refreshes keep failing, readers will serve stale data without any visible error until the hard TTL evicts it. Alert on refresh failures and on how stale the served values are.

Copyimport json, math, random, threading, time

BETA = 1.0       # 1.0 is the usual default; raise for earlier refreshes
SOFT_TTL = 300   # seconds until soft expiry (stored inside the payload)
HARD_TTL = 900   # cache-native TTL: hard upper bound on staleness

def write(r, key, compute):
    start = time.time()
    value = compute()
    delta = time.time() - start  # measured recompute duration
    payload = {"value": value, "soft_expiry": time.time() + SOFT_TTL, "delta": delta}
    r.set(key, json.dumps(payload), ex=HARD_TTL)
    return value

def should_refresh(payload, beta=BETA):
    u = 1.0 - random.random()  # uniform in (0, 1], so log(u) is never log(0)
    # -log(u) >= 0 pushes 'now' forward by a random amount scaled by delta*beta
    return time.time() - payload["delta"] * beta * math.log(u) >= payload["soft_expiry"]

def refresh(r, key, compute):
    try:
        write(r, key, compute)
    finally:
        r.delete(f"lock:{key}")  # failures should also be counted and alerted on

def read(r, key, compute):
    raw = r.get(key)
    if raw is None:  # hard TTL passed or cold cache: recompute inline
        return write(r, key, compute)
    payload = json.loads(raw)
    if should_refresh(payload):
        # Short NX lock so only one reader starts the background refresh
        if r.set(f"lock:{key}", "1", nx=True, ex=30):
            threading.Thread(target=refresh, args=(r, key, compute), daemon=True).start()
    return payload["value"]  # serve the cached (possibly stale) value meanwhile

A redis-py sketch that stores {value, soft_expiry, delta} in the payload, uses the XFetch formula against the soft expiry to trigger one locked background refresh while readers keep serving the cached value, and relies on the native TTL as the hard staleness limit.

Coordinating recomputation: single-flight and per-key distributed locks

The cheapest layer is in-process single-flight. When a hundred requests miss the same key on one instance, one becomes the leader and recomputes. The others wait on its result. Lock traffic then scales with the number of instances, not the number of requests. The catch is that waiters share the leader's fate. If the leader times out or gets a transient error, every waiter receives it too. To avoid this, return errors to the leader only and let waiters retry, or keep errors out of the shared result.

Across instances, use a per-key distributed lock. Acquire it with an atomic set-if-not-exists that carries an expiry, and store a unique token for each holder. Release it with a server-side script that deletes the key only if the token still matches. Without that check, a slow holder can delete a lock that now belongs to someone else.

Instances that lose the race need a policy:

The lock adds a round trip to every miss. If the lock TTL is shorter than the recompute time, it expires mid-work and two holders overlap. If it is too long, a crashed holder blocks refresh until the lock expires. Failover in the lock store can also grant the same lock twice. For all these reasons, the recomputation must be idempotent.

Copyimport threading, uuid
import redis

r = redis.Redis(host="cache.internal", port=6379)

RELEASE = r.register_script("""
if redis.call('get', KEYS[1]) == ARGV[1] then
  return redis.call('del', KEYS[1])
end
return 0
""")

def acquire(key, ttl_ms=30000):
    token = uuid.uuid4().hex  # unique per holder
    # SET NX PX: create-with-expiry in one step; falsy result means someone else holds it
    return token if r.set(f"lock:{key}", token, nx=True, px=ttl_ms) else None

def release(key, token):
    # Only deletes if our token still matches; a slow holder must not free a newer holder's lock
    return RELEASE(keys=[f"lock:{key}"], args=[token]) == 1

_inflight, _mu = {}, threading.Lock()

def single_flight(key, fn):
    with _mu:
        call = _inflight.get(key)
        leader = call is None
        if leader:
            call = _inflight[key] = {"done": threading.Event(), "ok": False, "val": None}
    if not leader:
        call["done"].wait(timeout=5)
        if call["ok"]:
            return call["val"]
        return fn()  # leader failed or timed out: retry instead of inheriting its error
    try:
        call["val"] = fn()
        call["ok"] = True  # only successes are shared; errors propagate to the leader alone
        return call["val"]
    finally:
        with _mu:
            _inflight.pop(key, None)
        call["done"].set()

A Redis per-key lock using SET NX PX with a unique token and a Lua check-and-delete release, plus an in-process single-flight wrapper that shares only successful results with waiters.

Negative caching, error caching and cold-start handling

Locks only bound concurrency for keys that exist. Two other cases need their own handling.

Negative caching. If a lookup finds nothing, such as a deleted user or an ID that was never valid, store a "not found" sentinel instead of storing nothing. Without the sentinel, every request for that key misses and goes to the backend. That matters when a client retries in a loop or a scanner enumerates IDs. The cost is that a sentinel can hide data created after it was written. Give negative entries a short TTL, and have the write path delete or overwrite the sentinel when it creates the item.

Error caching. When the backend times out or returns an error, record that failure for a few seconds. Callers then fail fast instead of piling onto a dependency that is already struggling. Keep error entries separate from not-found entries so callers can tell "absent" from "unknown". Keep their TTLs very short. A long error TTL keeps the outage going after the backend recovers. Where you have a stale value, serving it is usually better than serving a cached error.

Cold starts

Jitter and early refresh assume the cache already holds entries. After a flush, a failover to an empty replica, or a new-region launch, there is nothing to spread out or refresh early, so every request misses at once. Pre-warm before moving traffic: take the hot-key list from the serving region's access logs, populate the new cache, then ramp traffic in gradually. As a backstop, rate-limit admissions on the recompute path. Cap the number of concurrent backend fetches per instance. Requests over that cap wait on an in-flight fetch for the same key or get a degraded response. This keeps the backend's load within a known limit while the cache refills.

Combining the layers and choosing alternatives

Each layer handles a different failure, so they stack. Jitter costs almost nothing and applies to every write. Early refresh or stale-while-revalidate belongs on keys where a synchronous miss would hurt latency. Single-flight caps duplication inside each process. A distributed lock is worth adding only when the remaining fan-out, one fetch per instance, is still more than the origin can absorb.

Some alternatives replace layers entirely. A background job that writes keys ahead of expiry removes misses for a known, bounded key set, but it fails silently when the job stalls and does not cover long-tail keys. Pre-warming solves cold starts only. For cheap keys, accepting misses is often the correct design, not a shortcut.

Development cost is real. Every layer adds a branch that rarely runs in normal traffic, such as lock timeouts, stale serving and refresh failures. These branches are hard to exercise in tests and easy to leave without metrics, so their gaps tend to appear during incidents.

That cost is the reason to centralize the logic. A shared caching wrapper that applies layers based on a per-key policy means the edge cases are written and instrumented once. Teams then choose a policy instead of reimplementing locking, and expiry-driven outages stop recurring in each service separately.

How can stampede prevention save engineering time?

The main saving is incidents that never happen, followed by fewer repeated implementations across services.

• Fewer expiry-driven incidents to debug. Stampedes are hard to diagnose after the fact. The cache looks healthy most of the time, the database looks overloaded, and the trigger is a TTL that lapsed minutes earlier. Jitter and early refresh remove the most common triggers, so on-call engineers spend less time correlating load spikes with expiry times, backfills and deploys.
• Less capacity firefighting. Without coordination, the origin has to absorb the peak of duplicated recomputes, not the steady-state load. Teams often respond by scaling the database or adding replicas under pressure. Bounding concurrent recomputes lets capacity planning work from expected load instead of worst-case herd size.
• One implementation instead of many. With a shared caching wrapper, lock acquisition, token-checked release, stale serving, negative caching and metrics are written and reviewed once. Service teams choose a per-key policy from the decision table instead of each writing and debugging their own locking code. The rarely exercised branches, such as lock timeouts and refresh failures, get tested in one place.
• Faster, safer operational changes. Cache flushes, failovers, key-format changes and region launches become routine when warm-up and admission control exist. Without them, these changes need careful scheduling and someone watching the backend.
• Reproducible verification. The staging load test described below gives a repeatable check that the layers still work. Regressions surface during a test run rather than during an outage, which is cheaper to investigate and fix.

The saving depends on how often your services hit stampedes today. Your incident history is the best guide. If past outages or latency spikes trace back to cache expiry, flushes or bulk writes, those are the hours these layers recover. If recompute is cheap and no incidents trace back to expiry, the maintenance cost of extra layers can exceed the time saved. In that case jitter alone, or nothing, is the efficient choice.

Measuring it and reproducing a stampede in a load test

Every defense in this article can fail without anyone noticing. Background refresh, locks and stale serving all hide misses from users, so a broken one shows up only as stale data or a later outage. Instrument each layer separately, tagged by key class rather than raw key to keep cardinality bounded:

• Miss rate, split into true misses and early refreshes.
• Concurrent recomputations per key, a gauge that should stay near one when locks or single-flight work.
• Lock acquisition rate and wait time. Rising waits mean recompute is slower than the lock lease.
• Stale-serve rate and early-refresh rate.
• Downstream QPS during expiry windows, aligned to when hot keys expire.

Alerts for silent failures

Alert on the age of the stalest served value, not only on its rate. A stuck refresh worker keeps hit rates healthy while data ages indefinitely. Also alert when stale-serve rate climbs while early-refresh rate falls, which means refreshes are failing. Alert when concurrent recomputations for one key exceed a small threshold.

Reproducing a stampede

Force synchronized expiry in staging under steady load. Write a hot key set with identical short TTLs, or delete a hot key mid-test. Run once with all layers disabled, then enable jitter, early refresh and locking one at a time, and record peak downstream QPS for each run.

Illustrative estimate. Assume 50 instances each have 10 in-flight requests for one key when it expires. With no protection, that produces up to 500 recomputes. Per-process single-flight cuts this to about 50, and a distributed lock to about 1. If your measured peaks don't drop roughly this way, a layer is misconfigured.

How OneEnv can help

Disclosure: OneEnv is the product behind this blog.

OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.

Applied to cache stampede prevention, this is where it helps:

Saves time

• Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
• One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
• Reviewers see the exact diff and the list of affected services up front, so approval is a decision rather than an investigation.

Saves cost

• Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
• Less duplicated configuration to maintain: one shared definition inherited by many services.
• Per-service approve/reject means a bad shared value can be refused where it would break something, before it is live.
• OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.

These are qualitative benefits, not measured results — how much you save depends on how many services share the value.

Want to try it? Start at oneenv.io.