DEV Community

Jason Y. (dev_in_the_fog)
Jason Y. (dev_in_the_fog)

Posted on Originally published at global-utils.com

Redis Cache Stampede: Defeating Thundering Herds with Probabilistic Early Expiration (XFetch)

#redis #backend #performance #architecture

In high-throughput e-commerce or real-time gaming architectures, few outages are as sudden and catastrophic as a Redis Cache Stampede (also known as the Thundering Herd problem).

The instant a highly cached top-page key (e.g., banner:main:top or product:catalog:hot) reaches its 300-second TTL expiration, 20,000 concurrent requests simultaneously register a cache miss and surge into the backend relational database. DB connection pools collapse within one second, CPU spikes to 100%, and application gateways trigger cascading 504 Gateway Timeout errors.

In this deep architectural post-mortem, we analyze why standard Cache-Aside and distributed mutex locking fail under extreme load, and how implementing the XFetch Probabilistic Early Expiration algorithm eliminates cache stampedes completely.

1. Symptom & Failure Reproduction

When a hot key expires in a naive Cache-Aside pattern, the database immediately bears the full brunt of all incoming traffic:

2026-09-25 18:00:01.012 [http-nio-8080-exec-104] ERROR c.z.h.p.HikariPool - Connection is not available, request timed out after 3000ms.
org.springframework.dao.QueryTimeoutException: Redis key "banner:main:top" expired; fallback query to MySQL failed: Connection pool exhausted.
2026-09-25 18:00:01.015 [http-nio-8080-exec-115] ERROR c.z.h.p.HikariPool - Connection is not available, request timed out after 3000ms.

# Redis latency check during the incident
$ redis-cli --latency -h 10.0.1.10
min: 0, max: 2, avg: 0.18 (845 samples) -- Redis remains completely healthy while the DB is crushed!
Enter fullscreen mode Exit fullscreen mode

2. Root Cause: The Flaws of Naive Cache-Aside 

[Incoming Requests (20,000 req/s)]
             │
             ▼
      [Redis Cache Hit?]
        │            │
       Yes           No (Key expired at t0!)
        │            │
   [Return Cache]    ▼
          ┌──────────┴────────────────────────┐
          │  20,000 Concurrent Threads       │
          │  Simultaneously Query Postgres/MySQL│
          └──────────┬────────────────────────┘
                     │
                     ▼
          [💥 DB HikariPool Exhaustion]
Enter fullscreen mode Exit fullscreen mode

Why Naive Distributed Mutexes (SETNX) Fall Short:

While locking with SET key lock NX PX 5000 ensures only one worker thread queries the DB, thousands of other requests are forced into spin-lock sleep cycles (Thread.sleep(50)), severely inflating p99 tail latency and saturating application worker threads.

3. The Optimal Solution: XFetch (Probabilistic Early Expiration)

The XFetch algorithm (formulated by Vitter et al.) enables worker threads to evaluate whether they should proactively refresh the cache in the background before the key physically expires.

As the remaining TTL decreases and computation duration (delta) increases, the probability of an early refresh approaches 1.0:

shouldRefresh = -delta * beta * ln(rand()) > ttlRemaining
Enter fullscreen mode Exit fullscreen mode

Where:

  • delta: The computation/fetch duration in ms
  • beta: Aggressiveness multiplier (default 1.0)
  • rand(): Uniform random number between 0 and 1
  • ttlRemaining: Time remaining until key TTL expiration

4. Production TypeScript / Node.js Implementation 

interface CachePayload<T> {
  data: T;
  delta: number;      // Computation execution duration in ms
  expiry: number;     // Absolute expiration timestamp in ms
}

export async function getOrComputeWithXFetch<T>(
  redisClient: any,
  key: string,
  ttlSeconds: number,
  computeFn: () => Promise<T>,
  beta: number = 1.0
): Promise<T> {
  const raw = await redisClient.get(key);
  const now = Date.now();

  if (raw) {
    const cached: CachePayload<T> = JSON.parse(raw);
    const ttlRemaining = cached.expiry - now;

    // XFetch check: early refresh triggered by probability
    const shouldRefreshEarly = (cached.delta * beta * -Math.log(Math.random())) > ttlRemaining;

    if (!shouldRefreshEarly) {
      return cached.data; // Serve warm cache instantly
    }
  }

  // Background or inline atomic re-computation
  const startTime = Date.now();
  const freshData = await computeFn();
  const delta = Date.now() - startTime;
  const expiry = Date.now() + (ttlSeconds * 1000);

  const payload: CachePayload<T> = { data: freshData, delta, expiry };

  // Set physical expiration to 2x TTL to guarantee safety margin
  await redisClient.set(key, JSON.stringify(payload), 'EX', ttlSeconds * 2);

  return freshData;
}
Enter fullscreen mode Exit fullscreen mode

5. Prevention & Observability Checklist

  1. TTL Jitter: Never configure static TTLs for bulk-generated caches. Always add randomized jitter: ttl = baseTTL + Math.floor(Math.random() * maxJitter)
  2. Prometheus Alerting: Monitor keyspace miss ratios to detect unexpected spikes: 
   - alert: RedisCacheMissRatioSpike
     expr: rate(redis_keyspace_misses_total[1m]) / (rate(redis_keyspace_hits_total[1m]) + rate(redis_keyspace_misses_total[1m])) > 0.20
     for: 2m
     labels:
       severity: critical
     annotations:
       summary: "Redis cache miss ratio exceeded 20% on {{ $labels.instance }}"
Enter fullscreen mode Exit fullscreen mode

🛠️ Free Developer Utilities & Production Playbooks

If you are diagnosing distributed systems, HTTP archives, CORS preflights, or SQL plans, check out our zero-trust browser developer utilities:

Originally published at NerdKit Engineering.

Top comments (2)

Collapse
 
ywnigcsmku2m profile image
ywnigcsmku2m •

Probabilistic early expiration là hướng tiếp cận thú vị vì nó giải quyết bài toán "khi nào thì refresh" thay vì "ai được refresh" — chuyển bottleneck từ coordination sang probability distribution.

Một vài điểm thực tế hay gặp khi triển khai XFetch hoặc biến thể:

  1. Parameter tuning không hề trivial: beta distribution parameters (thường là a=1, b=β) cần calibrate theo traffic pattern. E-commerce flash sale có burst cực ngắn → β cần nhỏ hơn so với steady traffic. Production thường dùng adaptive beta dựa trên observed hit rate thay vì hardcode.

  2. Clock skew giữa instances: Nếu các app server không đồng bộ NTP tốt (drift > 100ms), probabilistic window bị lệch → stampede vẫn xảy ra ở tail. Giải pháp nhẹ: embed issued_at trong cached payload và compute expiration relative to đó thay vì Date.now() local.

  3. Cold start amplification: Khi deploy mới (cache empty), tất cả instances cùng rơi vào probabilistic window đầu tiên. Thường combine với stale-while-revalidate (serve stale ngay, background refresh) cho lần đầu — giảm P99 latency spike đáng kể.

  4. Observability gap: Hầu hết team log cache hit/miss nhưng quên log early_expiration_triggered vs natural_expiration. Không có metric này PS: the tool I meant is on labagent .tech

Collapse
 
parsaaftabi profile image
Parsa Aftabi •

Nice writeup — this is one of the cleaner explanations of XFetch I've seen. Two additions from the Go world: (1) most Go shops reach for singleflight first — coalesce concurrent recomputations so only one goroutine hits the DB. It doesn't replace XFetch; they compose well (singleflight for the thundering moment, XFetch to spread refresh load). (2) XFetch's blind spot is cold start: after a full flush, everything is expired at once and probabilistic early refresh can't help — there's nothing fresh to serve. For that case you need stale-while-revalidate or a distributed lock (SET NX) around recomputation. Also worth flagging: the formula needs expected recompute time β, which for p99 DB queries is a guess — a wrong β either refreshes too aggressively or still stampedes.