cache-stampede-reference

Pure-reference catalog of cache-stampede (thundering-herd) phenomena and mitigations: parallel misses on key expiry trigger simultaneous recomputation (often congestion-collapse), countered by three families - locking, external recomputation near-expiry, and probabilistic early expiration via XFetch (`(time() - delta * beta * log(rand(0,1))) >= expiry`). Use when designing cache-refresh strategy or diagnosing a stampede incident. This is the single failure-mode pattern; for the broader multi-tier pattern catalog use cache-coherence-patterns-reference, for the stale-while-revalidate / stale-if-error extensions use stale-while-revalidate-reference; a reference consumed by redis-cache-tests, not a runnable test.

Install with skills.sh (any agent)

npx skills add testland/qa --skill cache-stampede-reference

View source

cache-stampede-reference

Overview

A cache stampede (also "dog-piling," "thundering herd at cache miss") occurs when a cached value expires under high load - many requesters simultaneously detect the miss, all recompute, all write back. Per en.wikipedia.org/wiki/Cache_stampede (opens in new window): "massively parallel computing systems with caching mechanisms come under a very high load" and "multiple threads of execution will all attempt to render the content of that page simultaneously." The pathological state: "congestion collapse, preventing the resource from being recached and maintaining zero cache hit rates."

This skill is a pure reference consumed by per-tier test skills.

When to use

Designing the refresh policy for a hot cache key.
Investigating a "site falls over at 3 PM" report (TTL aligned with traffic peak).
PR review of new cache-using code.
Auditing existing locking / probabilistic logic.

How to use

Flag candidate hot keys: any key whose recompute-cost-vs-traffic ratio exceeds 0.1, or whose TTL aligns with a traffic peak.
Confirm a live stampede against the Symptoms table - latency spikes at TTL boundaries, hit rate dropping near zero, or cron-synchronised spikes.
Choose a mitigation family from references/stampede-mitigations.md by key knowability: XFetch for unknown / user-specific keys, external recompute for known-hot keys, locking as a backstop.
For XFetch, measure delta (recompute cost) during refresh and store it beside value and expiry; keep beta=1 unless a load test says otherwise.
Layer the strategies per Combining strategies so each covers the others' gaps.
Add the tests in Testable behaviours - especially the N-concurrent-on-cold-key load test at production concurrency.
Alarm on the cache-miss-rate metric so a silent regression (a failed cron, an expired lock) resurfaces the stampede visibly.

Symptoms in production

Signal	Interpretation
DB or upstream service latency spikes at cache-key TTL boundaries	Stampede on key expiry
Cache hit rate drops near zero, recovers slowly	Stampede causing congestion collapse
Periodic load spikes synchronised with cron / scheduled jobs	Multiple processes invalidating + recomputing
Recompute-cost-vs-traffic ratio > 0.1	Hot key - stampede risk

The three mitigation families

Per Wikipedia's cache-stampede article, three families counter the herd. Full code, drawbacks, and the XFetch variable table are in references/stampede-mitigations.md.

Locking - on miss, one process acquires a per-key lock and recomputes; others wait, return "not found," or serve stale. Risk: lock holder crash leaves the cache empty for the lock TTL.
External recomputation - a separate cron / near-expiry job refreshes known-hot keys off the request path. Fits static keys; doesn't help unknown or user-specific hot keys.
Probabilistic early expiration (XFetch) - each reader independently refreshes early with rising probability as the value ages:

if (!value || (time() - delta * beta * log(rand(0,1))) >= expiry)
  recompute_and_cache(key)
else
  return value

Per Wikipedia, "setting beta=1 works well in practice."

Worked example

A homepage aggregate ("top-10 products") is cached under one key with ttl=300. Every afternoon at the traffic peak the key expires, ~1,200 concurrent requests all miss, all hit the database, and the hit rate collapses to near zero for ~40 s - the Symptoms table's "site falls over at 3 PM" row.

The key is known and hot, so external recomputation fits: a cron job refreshes it every 240 s (inside the 300 s TTL), decoupled from requests. XFetch is added on read as a backstop for the seconds around a missed cron run - each reader's delta * beta * log(rand(0,1)) term nudges a few readers to refresh early instead of the whole herd. The load test in Testable behaviours (N=1000 on a cold key) then asserts the upstream sees <=5 recomputes, down from ~1,000.

Combining strategies

The strongest setups combine:

Layer	Strategy
Cache backend	TTL + stale-while-revalidate per `stale-while-revalidate-reference`
App logic	XFetch on read for hot keys
Operations	External recompute for known-hot keys
Safety net	Distributed lock (Redis SET NX EX) as a backstop

The point of layering: XFetch handles unknown hot keys gracefully; external recompute handles known hot keys; locks catch the few that slip through.

Testable behaviours

Behaviour	Test
Lock holds under contention	N concurrent gets on missing key → 1 recompute, N-1 waits/stale
XFetch probability rises near expiry	Statistical test: many runs, fraction refreshing before expiry within target band
External recompute fires before TTL	E2E: write source-of-truth → wait → assert cache reflects new value
Stampede absent under load	Load test: N=1000 concurrent on cold key → upstream sees ≤N recomputes (target: 1-5)
Refresh-cost (`delta`) updated on each refresh	Inspect cached metadata

Anti-patterns

Anti-pattern	Why it fails	Fix
No mitigation at all	Stampede inevitable under traffic	Pick at least one strategy
Lock without TTL	Lock holder crash → deadlock	TTL on locks; refresh while recomputing
XFetch with `beta` very high (10+)	All requesters refresh constantly	beta=1; tune via load test
External recompute without monitoring	Cron job fails silently; stampedes return	Alarm on cache-miss rate spike
Cache TTL = stale-while-revalidate window	RFC 5861 SWR window depends on `Cache-Control: stale-while-revalidate=N` being separate	See `stale-while-revalidate-reference`
Stampede-mitigation tested only under low load	Pass at 10 RPS; fail at 1000	Test at production-equivalent concurrency
Hot key with `must-revalidate`	Forced re-validation = forced stampede on TTL	Use SWR or grace mode
Logging the stampede instead of measuring it	Logs swamped during incident; no recovery signal	Metric on cache-miss rate; alarm
Trusting client-side retries to "thin" the herd	Retries can amplify	Server-side rate limit on the recompute path

Limitations

XFetch assumes exponential distribution is right. Some workloads have bimodal cost; tune delta measurement to use e.g., p95 not mean.
Locking blocks on lock acquisition. Higher latency than XFetch / SWR for clients that wait.
External recompute is brittle. A failed cron run leaves the cache cold; needs paired monitoring.
Cross-region replication. Mitigations work per cache node; geo-distributed setups need per-region coordination.
TTL skew. Multiple cache nodes with slightly different expiry → many node-local stampedes instead of one global.

References

Cache stampede definition + XFetch formula: en.wikipedia.org/wiki/Cache_stampede (opens in new window).
Mitigation implementations: references/stampede-mitigations.md.
Companion catalogs: cache-coherence-patterns-reference, stale-while-revalidate-reference.
Consumed by: redis-cache-tests, cdn-cache-purge-tests, varnish-test-vtc-syntax.

Cache-stampede mitigation families

View source

Cache-stampede mitigation families

The three families named in cache-stampede-reference, in full, per Wikipedia's cache-stampede article. The SKILL.md spine summarises each in one line and keeps the XFetch formula; this file carries the implementations, drawbacks, and the XFetch variable table.

1. Locking

Upon cache miss, processes attempt to acquire a lock for that key. Only the lock holder recomputes; others either wait, return "not found," or use a stale value.

def get(key):
    val = cache.get(key)
    if val is not None and not val.stale:
        return val
    if cache.acquire_lock(key, ttl=30):
        try:
            val = recompute(key)
            cache.set(key, val, ttl=300)
            return val
        finally:
            cache.release_lock(key)
    else:
        # Another process is recomputing; serve stale or wait
        return val or wait_then_get(key)

Drawbacks per Wikipedia: "complex implementation handling edge cases like process failures and race conditions." Lock holder crashing → cache empty for the lock TTL.

Mitigation: short-TTL locks with periodic refresh while recomputing.

2. External recomputation

A separate process recomputes the cache periodically or near expiry, decoupled from the request path. Per Wikipedia: "triggered when values approach expiration, periodically, or on cache miss."

# Cron / scheduled job
def refresh_hot_keys():
    for key in HOT_KEYS:
        val = recompute(key)
        cache.set(key, val, ttl=600)

When it fits: static cache keys ("homepage data," "top-10 products"). Hot keys are knowable in advance. The recompute schedule overlaps the cache TTL.

Drawback: doesn't help with unknown / user-specific hot keys; needs separate infrastructure.

3. Probabilistic early expiration (XFetch)

Each requester independently decides - with rising probability as the value ages - to refresh before formal expiry. Per Wikipedia, the canonical formula:

if (!value || (time() - delta * beta * log(rand(0,1))) >= expiry)
  recompute_and_cache(key)
else
  return value

Where:

Variable	Meaning
`delta`	Time to recompute the value (scales the probability distribution)
`beta`	Tuning parameter (default 1; >1 favours earlier refresh)
`log(rand(0,1))`	Always negative; magnitude controls the early-refresh probability
`time()`	Wall-clock or monotonic time
`expiry`	Absolute expiry time stored alongside the value

The "exponential distribution" of refresh decisions means most requesters use the cached value; only a few do early refresh. Per Wikipedia: "setting beta=1 works well in practice."

Implementation:

import math, random, time

def get_xfetch(key):
    entry = cache.get(key)  # contains {value, expiry, delta}
    if not entry:
        val, delta = measure_recompute(key)
        expiry = time.time() + 300
        cache.set(key, {"value": val, "expiry": expiry, "delta": delta}, ttl=300)
        return val

    now = time.time()
    rand = max(random.random(), 1e-10)
    if now - entry["delta"] * 1.0 * math.log(rand) >= entry["expiry"]:
        # Early refresh
        val, delta = measure_recompute(key)
        expiry = now + 300
        cache.set(key, {"value": val, "expiry": expiry, "delta": delta}, ttl=300)
        return val
    return entry["value"]

The delta (recompute cost) is measured during refresh and stored. Expensive-to-recompute values get earlier refresh attempts.

Related skills

browser-cache-control-tests

Wraps browser-side Cache-Control testing with Playwright (Cypress for legacy stacks): asserting response Cache-Control headers from Network events, ETag round-trips (If-None-Match → 304), service-worker strategies (Workbox cacheFirst / networkFirst / staleWhileRevalidate), and reload semantics (normal vs hard). Covers MDN Cache-Control + RFC 9111. Use when auditing browser-tier caching in E2E tests. For CDN-edge purge use cdn-cache-purge-tests; for the reverse-proxy tier use varnish-test-vtc-syntax; for an app-tier store use redis-cache-tests; SWR directive semantics live in stale-while-revalidate-reference.

cache-coherence-patterns-reference

Pure-reference catalog of cache-coherence patterns across the request path. Defines the five-tier cache stack (browser → CDN → reverse-proxy → application → data store), the per-tier cache-writing patterns (cache-aside, write-through, write-back, write-around, refresh-ahead), and the canonical invalidation strategies (TTL-only, event-driven purge, surrogate keys, version-tagged URLs, soft purge), plus an anti-pattern table and a worked multi-tenant coherence-test example. Deep detail - the RFC 9111 Cache-Control / Vary / ETag directive tables and the cross-tier coherence + per-tier test surface - lives in references/. Use for pattern selection, Cache-Control header design, and coherence audits; use a cache-key-collision check when the question is whether two requests in an existing system collide on a concrete key scheme. Consumed by redis-cache-tests, cdn-cache-purge-tests, varnish-test-vtc-syntax, browser-cache-control-tests, and the cache-key-collision check.

cache-key-discriminator-audit

Audits whether a cache key carries every discriminator the cached response actually depends on, so two requests that must not share a slot cannot collide. Ranks identity discriminators (tenant, user, authorization scope, plan tier) above presentation ones (locale, region, currency, feature flag), maps each missing discriminator to the data-exposure or wrong-content consequence it causes, classifies each key-and-value pair into a critical / high / medium severity band (including the Python lru_cache-on-an-instance-method trap), and writes the fix as a namespaced key builder plus the matching HTTP Vary header. Use when a cache key is being designed or changed, when a per-user or per-tenant response is about to be stored in a shared cache or CDN, or when investigating a report that one user or tenant saw another's data.

cdn-cache-purge-tests

Wraps CDN cache-purge testing patterns for Cloudflare (POST /zones/{zone_id}/purge_cache, single-file / everything / cache-tags / hostname / prefix), Fastly (POST purge-by-key / purge-all, surrogate-keys via Surrogate-Key header), and CloudFront (CreateInvalidation API + paths). Covers end-to-end test patterns (write origin → trigger purge → assert edge serves fresh), purge-propagation delay testing (typically 1-30s globally), surrogate-key + cache-tag patterns for group-purge, and Cache-Status header verification (cf-cache-status: HIT/MISS/BYPASS). Use when designing or auditing CDN cache-invalidation workflows.

memcached-tests

Wraps Memcached cache testing against a real container: an inline set/get/expire/no-persistence worked example, with the exhaustive protocol-command tests (set/get/add/cas/incr/decr, TTL 0=never-expire / 30-day Unix-timestamp boundary) and the LRU-eviction, consistent-hashing distribution, ElastiCache Auto Discovery, and CI-wiring deep-dives in references/. Use when writing tests for an application that uses Memcached as its primary cache, when verifying ElastiCache Memcached cluster behaviour, or when contrasting Memcached eviction and distribution semantics against Redis.

redis-cache-tests

Wraps Redis cache testing: EXPIRE / PEXPIRE / TTL verification (Redis 7+ NX/XX/GT/LT flags), cache-aside write-then-invalidate (write source → DEL key → assert fresh read), eviction under memory pressure (maxmemory + allkeys-lru), pub/sub invalidation across nodes, and tenant key-namespacing. Use when Redis is the app's primary cache. For a Memcached app-tier store use memcached-tests; for the browser/HTTP tier use browser-cache-control-tests; a runnable test, not the cache-stampede-reference or cache-coherence-patterns-reference catalogs.

stale-while-revalidate-reference

Pure-reference catalog of RFC 5861's stale-while-revalidate + stale-if-error Cache-Control extensions. Defines stale-while-revalidate=N (caches MAY serve a stale response while asynchronously revalidating, up to N seconds after expiry) and stale-if-error=N (caches MAY serve stale on 5xx upstream errors). Distinguishes from RFC 9111's must-revalidate (forbids serving stale) and from manual cache-aside refresh (synchronous). Covers the interaction with the freshness lifetime (max-age) and the cache-stampede-mitigation properties. Use when designing the cache-refresh boundary or auditing existing Cache-Control headers.

varnish-test-vtc-syntax

Wraps the varnishtest CLI + VTC (Varnish Test Case) syntax for testing VCL configurations. Covers the VTC test-file format (varnishtest scripts with server { ... } + client { ... } + varnish v1 -vcl+backend { ... } blocks), the grace-mode + saint-mode behaviours (stale-while-revalidate + stale-if-error equivalents in VCL), the PURGE method handler pattern (vcl_purge subroutine + ACL guards), and surrogate-key invalidation via xkey vmod. Use when authoring or testing Varnish-based caching layers.