Cross-tier coherence problems and the per-tier test surface

Deep reference for cache-coherence-patterns-reference SKILL.md. Consult when auditing an existing multi-tier cache for coherence bugs and when deciding what to test at each tier.

Cross-tier coherence problems

A coherence bug at any tier surfaces at the user; the failure usually lives in the seam between two tiers, not inside one.

Testable behaviours by tier

Each tier needs its own coherence tests; the categories below map to the per-tier test skills that consume this reference.

RFC 9111 HTTP caching directives

Deep reference for cache-coherence-patterns-reference SKILL.md. Consult when designing the Cache-Control, Vary, and ETag contract that the browser and CDN tiers enforce.

Per www.rfc-editor.org/rfc/rfc9111.html (opens in new window):

Response directives (server → cache)

Per RFC 9111 §4.2.4: "A cache MUST NOT generate a stale response unless it is disconnected or doing so is explicitly permitted by the client or origin server." This is the formal basis for stale-while-revalidate per stale-while-revalidate.md (opens in new window).

Vary - the cache key

Per RFC 9111 §4.1: "When a cache receives a request that can be satisfied by a stored response and that stored response contains a Vary header field, the cache MUST NOT use that stored response without revalidation unless all the presented request header fields nominated by that Vary field value match those fields in the original request."

Practical: Vary: Accept-Encoding, Authorization means "separate cache entries per (Accept-Encoding, Authorization) combination." Missing Vary: Authorization is the canonical cross-tenant cache leak per cross-tenant-data-leak-tests Test 10.

ETag + If-None-Match revalidation

Per RFC 9111 §4.3.1: "Another validator is the entity tag given in an ETag field. One or more entity tags can be used in an If-None-Match header field for response validation."

Pattern: server returns ETag: "abc123"; client sends If-None-Match: "abc123"; server returns 304 Not Modified or 200 OK with new ETag. Bandwidth-efficient but doesn't help latency (still a round-trip).

Sources

• RFC 9111 HTTP Caching: www.rfc-editor.org/rfc/rfc9111.html (opens in new window).
• RFC 8246 immutable: www.rfc-editor.org/rfc/rfc8246.html (opens in new window).

stale-while-revalidate and stale-if-error (RFC 5861)

stale-while-revalidate (SWR) and stale-if-error (SIE) are Cache-Control extensions defined in RFC 5861 (opens in new window), widely implemented by browsers, CDNs (Cloudflare, Fastly, CloudFront), and reverse proxies (Varnish via grace).

stale-while-revalidate lifecycle

Per RFC 5861 §3 (opens in new window): "caches MAY serve the response in which it appears after it becomes stale, up to the indicated number of seconds." Syntax: Cache-Control: max-age=60, stale-while-revalidate=300.

1. t < max-age → fresh cache hit.
2. max-age < t < max-age + SWR → stale served and one async revalidation fires - this is the stampede-mitigation property: only the first request revalidates, the herd coasts on stale (stampede.md (opens in new window)).
3. Revalidation succeeds → cache refreshed.
4. t > max-age + SWR → truly stale; next request blocks on origin.

Failed-revalidation behaviour differs per vendor (Cloudflare keeps serving stale until the window expires; Fastly surfaces 5xx sooner; Varnish is VCL-configurable) - test the actual vendor.

stale-if-error

Per RFC 5861 §4 (opens in new window): a stale response "MAY be used to satisfy the request, regardless of other freshness information" on origin 500/502/503/504. Composition:

Cache-Control: max-age=60, stale-while-revalidate=300, stale-if-error=86400

1-minute freshness, 5-minute background-refresh grace, 1-day serve-stale grace if the origin is down.

Interaction with must-revalidate

Per RFC 9111, must-revalidate forbids serving stale after expiry. It and SWR are mutually exclusive in spirit; most caches honour the strictest (must-revalidate wins). For SWR / SIE to work, don't add must-revalidate.

Per-vendor support

Testable behaviours

Anti-patterns

Limitations

• Async revalidation is best-effort; the stale entry can be evicted under memory pressure → blocking fetch.
• Cold cache always blocks - SWR needs a previously cached response.
• no-store overrides everything.
• Staleness is invisible to users unless a Warning header survives (many CDNs strip it).

References

• RFC 5861: www.rfc-editor.org/rfc/rfc5861.html (opens in new window)
• Cloudflare Cache-Control docs: developers.cloudflare.com/cache/concepts/cache-control/ (opens in new window)
• nginx proxy_cache_use_stale: nginx.org/en/docs/http/ngx_http_proxy_module.html (opens in new window)

Cache-stampede mitigation families

The three families named in stampede.md (opens in new window), in full, per Wikipedia's cache-stampede article. That file 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:

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.

Cache stampede (thundering herd) - phenomena and mitigations

A cache stampede ("dog-piling") 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), the pathological state is "congestion collapse, preventing the resource from being recached and maintaining zero cache hit rates."

Symptoms in production

The three mitigation families

Per the Wikipedia article; full code, drawbacks, and the XFetch variable table are in stampede-mitigations.md (opens in new window).

1. 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.
2. External recomputation - a cron / near-expiry job refreshes known-hot keys off the request path. Doesn't help unknown or user-specific hot keys.
3. Probabilistic early expiration (XFetch) - each reader 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." Measure delta (recompute cost) during refresh and store it beside value and expiry.

Choosing and combining

Choose by key knowability: XFetch for unknown / user-specific keys, external recompute for known-hot keys, locking as a backstop. The strongest setups layer them:

Worked example

A homepage "top-10 products" aggregate under one key with ttl=300 expires at the traffic peak; ~1,200 concurrent misses hit the database and the hit rate collapses for ~40s. The key is known and hot, so external recomputation fits: a cron refreshes it every 240s, with XFetch on read as a backstop for a missed cron run. The load test below then asserts the upstream sees <=5 recomputes, down from ~1,000.

Testable behaviours

Anti-patterns

Limitations

• XFetch assumes exponentially distributed recompute cost; bimodal workloads should tune delta to p95, not mean.
• Mitigations work per cache node; geo-distributed setups need per-region coordination, and TTL skew across nodes yields many node-local stampedes.

References

• Cache stampede + XFetch formula: en.wikipedia.org/wiki/Cache_stampede (opens in new window)
• Mitigation implementations: stampede-mitigations.md (opens in new window)