Was ist ein Cache Stampede und wie verhindert man ihn?

Question

Accepted Answer

Ein **Cache Stampede** (oder Dogpile) tritt auf, wenn ein häufig genutzter gecachter Schlüssel abläuft und **viele gleichzeitige Anfragen ihn alle auf einmal verfehlen**, wobei alle zur Origin fallen, um denselben Wert gleichzeitig neu zu berechnen. Die Origin (DB oder Service) wird durch einen Burst bombardiert, den sie nicht verarbeiten kann, manchmal wird das System dadurch zum Absturz gebracht.

## Die Ursache

```text
t=0   hot key expires
t=0+  1000 requests arrive → all miss → all query the DB for the SAME value
      → DB overwhelmed; latency spikes; failures cascade
```

Der Auslöser ist das **gleichzeitige Ablaufen** eines beliebten Schlüssels. Die Lösung besteht darin, sicherzustellen, dass nur eine (oder wenige) Neuberechnung stattfindet, oder dass Anfragen nicht alle gleichzeitig ablaufen.

## Lösungen

- **Locking / Single-Flight** — der erste Cache-Miss nimmt einen Lock und berechnet neu; alle anderen warten auf dieses eine Ergebnis, anstatt alle die Origin zu treffen.
- **Stale-While-Revalidate** — serve den leicht veralteten Wert sofort, während ein Background-Task ihn aktualisiert. Keine Anfrage blockiert auf der Origin.
- **Early / Probabilistic Recomputation** — aktualisiere einen Schlüssel *vor* seinem Ablauf mit einer Wahrscheinlichkeit, die mit der Nähe des Ablaufs steigt, damit eine glückliche Anfrage ihn vor dem Stampede neu aufbaut.
- **Jittered TTLs** — füge Zufälligkeit zu TTLs hinzu, damit Schlüssel nicht alle zur gleichen Zeit ablaufen.
- **Request Coalescing** — reduziere identische gleichzeitige Anfragen auf einen Origin-Call.

## Single-Flight Pseudo-Code

```text
function get(key):
  val = cache.get(key)
  if val is present: return val            // fast path: a hit

if lock.acquire(key, ttl=5s):            // only ONE request wins the lock
    try:
      val = recompute()                    // hit the origin exactly once
      cache.set(key, val, ttl)
    finally:
      lock.release(key)
    return val
  else:
    wait_briefly(); return get(key)        // others wait, then read the filled cache
```

Der Lock stellt sicher, dass genau ein Origin-Call stattfindet; alle anderen gleichzeitigen Anfragen warten und lesen dann den neu gecachten Wert.

## Warum es wichtig ist

Ein Stampede verwandelt einen routinemäßigen Cache-Ablauf in einen Ausfall: der Cache, der deine DB schützte, funktioniert plötzlich nicht mehr, und der gesamte Traffic landet auf einmal auf der Origin. Die Ursache zu kennen (gleichzeitiges Ablaufen von häufig genutzten Schlüsseln) und die Lösungen (Single-Flight, Stale-While-Revalidate, Jitter) ist wichtig, um Caches zuverlässig unter echtem Traffic zu halten.