Cache Stampede verhindern: Locking und probabilistisches Refresh

1. Was ein Cache Stampede ist und warum er gefaehrlich wird

Ein Cache Stampede, auch Thundering Herd genannt, entsteht, wenn ein stark nachgefragter Redis-Schlüssel abläuft und im selben Moment viele gleichzeitige Anfragen auf diesen abgelaufenen Schlüssel treffen. Ohne Schutzmechanismus behandelt jede dieser Anfragen den Cache Miss unabhängig voneinander: Jede lädt aus der Datenbank neu, jede schreibt anschließend denselben Wert zurück in Redis. Was als einzelne Datenbankabfrage genügt hätte, wird zu hundert oder tausend parallelen Abfragen in Millisekundenbruchteilen.

Die Gefahr eines Cache Stampede liegt in seiner Verstärkungswirkung: Gerade die beliebtesten, am häufigsten gelesenen Datensätze sind am stärksten betroffen, weil sie die meisten gleichzeitigen Zugriffe erhalten. Eine Datenbank, die für die normale Last problemlos ausgelegt ist, kann durch einen einzelnen Cache Stampede kurzzeitig in die Knie gezwungen werden, mit Kaskadeneffekten auf andere Anfragen, die dieselbe Datenbank teilen. Bei stark frequentierten Systemen ist der Cache Stampede damit eines der unterschätztesten Risiken im Caching-Design.

2. Wie Thundering Herd beim TTL-Ablauf entsteht

Der Mechanismus hinter einem Cache Stampede ist einfach nachzuvollziehen. Ein Schlüssel wie product:bestseller:4711 hat eine TTL von 60 Sekunden und wird in dieser Zeit tausendfach gelesen. In der Sekunde, in der die TTL abläuft, kommt die nächste Anfrage an und findet GET mit (nil) vor. Ohne Koordination beginnt diese Anfrage sofort mit dem Nachladen aus der Datenbank. Da zwischen dem Ablauf und dem erneuten Befüllen des Caches typischerweise einige Millisekunden vergehen, sehen alle Anfragen, die in diesem Zeitfenster eintreffen, denselben leeren Cache und lösen jeweils eine eigene Datenbankabfrage aus.

Besonders kritisch wird es bei rechenintensiven Cache-Werten, etwa aggregierten Statistiken oder komplexen Joins, bei denen eine einzelne Datenbankabfrage bereits mehrere hundert Millisekunden dauert. In diesem Fall vergrößert sich das kritische Zeitfenster entsprechend, und die Zahl der parallel eintreffenden Anfragen während dieses Fensters wächst proportional zur Nachfrage. Ein Cache Stampede auf einen solchen Schlüssel kann eine Datenbank für mehrere Sekunden überlasten, selbst wenn der Schlüssel im Normalbetrieb kaum spürbare Last erzeugt.

# Ablauf eines beliebten Schluessels simulieren
redis-cli SET product:bestseller:4711 '{"views":18420}' EX 5
redis-cli TTL product:bestseller:4711
# (integer) 5

# Nach Ablauf: viele parallele Clients sehen gleichzeitig (nil)
redis-cli GET product:bestseller:4711
# (nil)

# Ohne Schutz: jeder Client startet unabhaengig einen DB-Reload
# --> N gleichzeitige Datenbankabfragen statt einer einzigen

3. Mutex-Locking als erste Verteidigungslinie

Die klassische Lösung gegen Cache Stampede ist ein verteiltes Mutex-Lock, das sicherstellt, dass nur eine einzige Anfrage tatsächlich die Datenbank abfragt, während alle anderen entweder kurz warten oder mit dem zuletzt bekannten Wert bedient werden. In Redis lässt sich ein solches Lock atomar mit SET lock:key value NX PX 5000 erzeugen: NX setzt den Wert nur, wenn der Schlüssel noch nicht existiert, PX definiert eine Ablaufzeit in Millisekunden, die verhindert, dass ein abgestürzter Prozess das Lock dauerhaft blockiert.

Der Ablauf mit Mutex-Lock: Bei einem Cache Miss versucht die Anwendung zuerst, das Lock zu erwerben. Gelingt das, lädt sie aus der Datenbank, befüllt den Cache und gibt das Lock frei. Gelingt das Erwerben nicht, weil eine andere Anfrage das Lock bereits hält, wartet die Anwendung kurz und prüft den Cache erneut, oder sie liefert einen leicht veralteten Wert aus einem Fallback-Schlüssel ohne TTL zurück. Diese zweite Variante, oft als "Stale-While-Revalidate" bezeichnet, vermeidet Wartezeiten für den Nutzer vollständig.

# Lock atomar erwerben, nur wenn noch nicht vorhanden
redis-cli SET lock:product:4711 "worker-1" NX PX 5000
# OK

# Zweiter Versuch waehrend das Lock aktiv ist: schlaegt fehl
redis-cli SET lock:product:4711 "worker-2" NX PX 5000
# (nil)

# Lock nach erfolgreichem Refresh wieder freigeben
redis-cli DEL lock:product:4711

4. Mutex-Lock in PHP implementieren

In PHP lässt sich das Mutex-Lock-Muster mit wenigen Zeilen um eine bestehende Cache-Aside-Implementierung ergänzen. Wichtig ist, das Lock mit einer eindeutigen Kennung zu versehen, damit ein Prozess nicht versehentlich das Lock eines anderen Prozesses freigibt, und das Lock stets in einem finally-Block freizugeben, damit auch bei einer Exception keine dauerhafte Sperre entsteht.

Die folgende Implementierung zeigt das vollständige Muster, inklusive kurzer Wartezeit mit begrenzter Anzahl an Wiederholungsversuchen, um Endlosschleifen bei einem dauerhaft blockierten Lock zu vermeiden.

<?php

declare(strict_types=1);

final class StampedeProtectedRepository
{
    public function __construct(
        private readonly \Predis\Client $redis,
        private readonly ProductDatabaseRepository $database,
        private readonly int $ttlSeconds = 60
    ) {
    }

    /**
     * Cache read protected against cache stampede via a distributed mutex lock.
     */
    public function find(int $productId): ?array
    {
        $key = "product:{$productId}";
        $cached = $this->redis->get($key);

        if ($cached !== null) {
            return json_decode($cached, true);
        }

        $lockKey = "lock:{$key}";
        $lockId = bin2hex(random_bytes(8));
        $acquired = $this->redis->set($lockKey, $lockId, 'NX', 'PX', 5000);

        if (!$acquired) {
            // Another process is already refreshing: wait briefly and retry
            for ($i = 0; $i < 20; $i++) {
                usleep(50_000); // 50ms
                $cached = $this->redis->get($key);
                if ($cached !== null) {
                    return json_decode($cached, true);
                }
            }
            // Fallback: still nothing, load directly to avoid an empty response
            return $this->database->find($productId);
        }

        try {
            $product = $this->database->find($productId);
            if ($product !== null) {
                $this->redis->setex($key, $this->ttlSeconds, json_encode($product));
            }
            return $product;
        } finally {
            // Only release the lock if we still own it
            $current = $this->redis->get($lockKey);
            if ($current === $lockId) {
                $this->redis->del([$lockKey]);
            }
        }
    }
}

5. Probabilistisches Early Expiration im Detail

Mutex-Locking löst das Problem reaktiv, nachdem der Schlüssel bereits abgelaufen ist. Eine proaktivere Strategie ist probabilistisches Early Expiration, bei der einzelne Anfragen den Cache schon vor dem tatsächlichen Ablauf der TTL erneuern, mit einer Wahrscheinlichkeit, die mit der Nähe zum Ablaufzeitpunkt steigt. Das bekannteste Verfahren dafür ist der XFetch-Algorithmus, veröffentlicht von Vattani, Chierichetti und Lowenstein bei Google.

Die Grundidee: Bei jedem Cache-Zugriff wird nicht nur der Wert gelesen, sondern auch geprüft, wie lange der letzte Refresh gedauert hat und wie nah die verbleibende TTL am Ablauf liegt. Die Formel (jetzt - delta * beta * log(random())) >= ablaufzeit berechnet daraus eine probabilistische Entscheidung, ob dieser konkrete Zugriff den Cache proaktiv erneuern soll. Der Parameter beta steuert die Aggressivität: Größere Werte lösen frühere, häufigere Refreshes aus. Das Ergebnis ist eine gleichmäßige Verteilung der Refresh-Last über die Zeit, statt einer konzentrierten Spitze exakt beim TTL-Ablauf.

6. Der XFetch-Algorithmus in PHP

Die Implementierung von XFetch erfordert zwei zusätzliche gespeicherte Werte neben dem eigentlichen Cache-Wert: den Zeitpunkt, an dem der Wert zuletzt neu berechnet wurde, und die Dauer, die diese Neuberechnung gedauert hat. Beide Werte lassen sich zusammen mit dem eigentlichen Wert in einer JSON-Struktur speichern und benötigen keine separate Redis-Operation.

In der Praxis wird XFetch häufig für Cache-Werte eingesetzt, deren Neuberechnung teuer ist und deren TTL bewusst großzügig gewählt wird, etwa aggregierte Reports oder rechenintensive Empfehlungslisten. Die probabilistische Vorab-Erneuerung verteilt die teure Neuberechnung über viele einzelne Zugriffe, statt sie exakt beim Ablauf zu konzentrieren.

<?php

declare(strict_types=1);

final class XFetchCache
{
    public function __construct(
        private readonly \Predis\Client $redis,
        private readonly float $beta = 1.0
    ) {
    }

    /**
     * Probabilistic early expiration (XFetch) to smooth out refresh load.
     */
    public function get(string $key, int $ttl, callable $recompute): mixed
    {
        $raw = $this->redis->get($key);
        $now = microtime(true);

        if ($raw !== null) {
            $entry = json_decode($raw, true);
            $delta = $entry['delta'];
            $expiry = $entry['expiry'];

            // XFetch formula: probabilistically trigger early refresh
            $rand = mt_rand() / mt_getrandmax();
            $shouldRefresh = ($now - $delta * $this->beta * log($rand)) >= $expiry;

            if (!$shouldRefresh) {
                return $entry['value'];
            }
        }

        $start = microtime(true);
        $value = $recompute();
        $delta = microtime(true) - $start;

        $this->redis->setex($key, $ttl * 2, json_encode([
            'value' => $value,
            'delta' => $delta,
            'expiry' => $now + $ttl,
        ]));

        return $value;
    }
}

7. Beide Strategien kombinieren

Mutex-Locking und probabilistisches Early Expiration schließen sich nicht aus, sondern ergänzen sich in der Praxis. XFetch reduziert die Wahrscheinlichkeit eines echten Cache Miss drastisch, indem es die meisten Refreshes bereits vor dem Ablauf verteilt. Für die verbleibenden Fälle, in denen trotzdem mehrere Anfragen gleichzeitig auf einen abgelaufenen Schlüssel treffen, etwa nach einem Cache-Flush oder Deployment, greift das Mutex-Lock als zusätzliches Sicherheitsnetz.

Diese Kombination ist besonders wertvoll bei Systemen mit stark schwankender Last, etwa Flash-Sale-Events im E-Commerce, bei denen ein einzelner Produktschlüssel innerhalb weniger Minuten von normaler auf extreme Nachfrage wechseln kann. Ein alleiniges Mutex-Lock würde in dieser Situation funktionieren, aber jeder TTL-Ablauf würde weiterhin kurze Wartezeiten für die ersten Anfragen erzeugen, während XFetch diese Wartezeiten durch proaktive Erneuerung meist vollständig vermeidet.

8. Cache Stampede im Monitoring erkennen

Ein Cache Stampede zeigt sich im Monitoring durch ein charakteristisches Muster: kurze, scharfe Spitzen in der Datenbank-Query-Rate, die zeitlich exakt mit dem TTL-Ablauf beliebter Cache-Schlüssel zusammenfallen. Das SLOWLOG von Redis selbst hilft dabei weniger, weil die einzelnen Redis-Operationen schnell bleiben, das Problem entsteht auf Datenbankebene. Wichtiger ist ein Query-Log oder APM-Tool, das gleichzeitige, identische Datenbankabfragen innerhalb desselben kurzen Zeitfensters erkennt.

Ein einfacher Indikator lässt sich auch direkt in Redis mitführen: ein Zähler, der bei jedem Cache Miss inkrementiert wird, kombiniert mit einem Zeitstempel des letzten Refreshs pro Schlüssel. Steigt dieser Zähler für einen einzelnen Schlüssel innerhalb weniger Millisekunden stark an, ist das ein klares Signal für einen aktiven Cache Stampede und ein Hinweis darauf, dass dieser Schlüssel von Mutex-Locking oder XFetch profitieren würde.

# Cache-Miss-Rate ueber Zeit beobachten
redis-cli INFO stats | grep keyspace_misses

# Anzahl aktiver Locks als Indikator fuer parallele Refreshes
redis-cli KEYS "lock:product:*" | wc -l

# Kommandos mit hoher Frequenz auf denselben Schluessel identifizieren
redis-cli MONITOR | grep "product:bestseller"

9. Mutex-Lock und probabilistisches Refresh im Vergleich

Beide Strategien haben unterschiedliche Staerken und lassen sich anhand der folgenden Kriterien einordnen, um die passende Wahl fuer den jeweiligen Anwendungsfall zu treffen.

In der Praxis empfiehlt sich für die meisten Systeme, mit Mutex-Locking zu beginnen, da es einfacher zu implementieren ist und sofortigen Schutz bietet. XFetch lohnt sich als Ergänzung für einzelne, besonders kritische Schlüssel mit teurer Neuberechnung, bei denen selbst kurze Wartezeiten während eines Locks spürbare Nutzerauswirkungen hätten.

10. Zusammenfassung

Ein Cache Stampede entsteht, wenn viele gleichzeitige Anfragen auf einen abgelaufenen Redis-Schlüssel treffen und jede davon unabhängig die Datenbank belastet. Mutex-Locking mit SET NX PX löst das Problem reaktiv, indem nur eine Anfrage die Datenbank abfragen darf, während andere kurz warten oder auf einen Fallback zurückgreifen. Probabilistisches Early Expiration nach dem XFetch-Algorithmus geht proaktiver vor und verteilt Refreshes bereits vor dem tatsächlichen Ablauf, wodurch echte Cache Misses seltener werden.

Beide Strategien lassen sich kombinieren: XFetch reduziert die Häufigkeit von Cache Misses drastisch, Mutex-Locking fängt die verbleibenden Fälle als Sicherheitsnetz ab. Wer beliebte, teure Cache-Schlüssel identifiziert und gezielt absichert, verhindert, dass ein einzelner TTL-Ablauf eine sonst gut dimensionierte Datenbank kurzzeitig überlastet.

11. FAQ: Cache Stampede verhindern