Caching-Strategien und ihre Fallstricke

Warum cachen, und was es kostet

Ein Cache hält eine Kopie von Daten an einem schnelleren oder näheren Ort als ihrem ursprünglichen Zuhause, damit wiederholte Anfragen nicht jedes Mal den vollen Preis zahlen. Abschnitt 0.2 hat die Idee als Tausch von Speicherplatz gegen Zeit eingeführt. Im Architekturmaßstab ist der Tausch interessanter, weil ein Cache drei Qualitäten zugleich verändert. Er senkt die Latenz (ein Redis-Zugriff im selben Rechenzentrum dauert typischerweise deutlich unter einer Millisekunde; eine Datenbankabfrage, die fünf Tabellen verknüpft, kann Dutzende Millisekunden dauern). Er erhöht den Durchsatz und schützt die Datenbank, weil jeder Treffer eine Abfrage ist, die die Datenbank nie sieht. Und er kann die Verfügbarkeit verbessern, weil ein Cache, der leicht veraltete Daten ausliefern darf, weiterarbeitet, während die Quelle langsam oder ausgefallen ist.

Der Preis wird mit Korrektheit und Komplexität bezahlt. Ein Cache ist eine zweite Kopie der Daten, und zwei Kopien können sich widersprechen. Jeder Cache verkörpert daher eine Entscheidung darüber, wie veraltet eine Antwort sein darf, und für wen. Eine fünf Minuten alte Speisekarte ist akzeptabel; ein fünf Minuten alter Kontostand, der einem Kunden angezeigt wird, der entscheidet, ob er sich eine Zahlung leisten kann, ist es nicht. Caches fügen außerdem eine Komponente hinzu, die ausfallen kann, verbrauchen Speicher, der Geld kostet, und schaffen neue Fehlerarten wie Stampedes und Kaltstarts, die es ohne sie nicht gäbe. Die erste Frage lautet daher nicht Welcher Cache?, sondern Was darf veraltet sein, wie stark, und was passiert, wenn es das ist?

Die Wirksamkeit eines Cache wird an seiner Trefferquote gemessen: Treffer geteilt durch alle Zugriffe. Die Trefferquote hängt davon ab, wie ungleich das Zugriffsmuster verteilt ist. Der Lesetraffic der meisten Endkundensysteme ist stark ungleich verteilt (ein kleiner Teil der Restaurants, Produkte oder Konten erhält die meisten Lesezugriffe), sodass ein Cache, der wenige Prozent der Daten hält, oft die meisten Lesezugriffe beantworten kann. Gleichmäßig zufällige Zugriffe dagegen lassen sich schlecht cachen, was man auch tut.

Die fünf klassischen Muster

Caching-Muster unterscheiden sich darin, wer den Cache befüllt, wann Schreibvorgänge die Quelle erreichen und folglich wie veraltet und wie dauerhaft die Daten sein können. Die Tabelle vergleicht sie; die Absätze danach erklären, wo jedes passt.

Cache-Aside ist aus gutem Grund der Standard: Es ist leicht nachvollziehbar und fällt sicher aus, denn verschwindet der Cache, liest die Anwendung einfach die Datenbank (langsamer). Read-Through verlagert dieselbe Logik in eine Cache-Bibliothek oder ein Cache-Produkt, was aufgeräumt ist, sich im Verhalten aber nicht unterscheidet. Write-Through passt zu Daten, die kurz nach dem Schreiben gelesen werden, etwa der Sitzung oder dem Warenkorb eines Nutzers. Write-Behind ist das riskante Muster: Es macht den Cache vorübergehend zum System of Record und ist daher nur angebracht, wo der Verlust der letzten paar Sekunden an Schreibvorgängen akzeptabel ist (Aufrufzähler, Analytics-Ereignisse, Spielstände) oder wo der Cache selbst repliziert und dauerhaft ist. Verwenden Sie Write-Behind nie für Geld. Refresh-Ahead ist eine Optimierung für eine kleine Menge sehr heißer Schlüssel, etwa die Restaurantliste auf der Startseite in einer belebten Stadt.

import json, random

TTL = 300  # seconds

def get_menu(restaurant_id):
    key = f"menu:{restaurant_id}:v3"            # version the key with the data shape
    cached = cache.get(key)
    if cached is not None:
        return json.loads(cached)                # hit
    with cache.lock(f"lock:{key}", timeout=5):  # coalesce: one loader per key
        cached = cache.get(key)                  # someone may have filled it meanwhile
        if cached is not None:
            return json.loads(cached)
        menu = db.load_menu(restaurant_id)       # miss: go to the system of record
        jitter = random.randint(0, TTL // 10)    # spread expiry times out
        cache.set(key, json.dumps(menu), ex=TTL + jitter)
        return menu

def update_price(restaurant_id, item_id, price):
    db.update_price(item_id, price)              # 1. change the system of record
    cache.delete(f"menu:{restaurant_id}:v3")     # 2. invalidate, do not overwrite

Time to Live und Invalidierung

Es gibt zwei Wege, einen Cache daran zu hindern, geänderte Daten auszuliefern. Der erste ist eine Time to Live (TTL): Jeder Eintrag läuft nach einer festen Zeitspanne ab, was das Veralten ganz ohne Koordination begrenzt. Eine TTL von fünf Minuten für Speisekarten bedeutet, dass eine Preisänderung innerhalb von fünf Minuten überall sichtbar ist. Der zweite ist explizite Invalidierung: Ändert sich die Quelle, löscht oder aktualisiert etwas die Kopie im Cache. Invalidierung liefert frischere Daten, verlangt aber, dass jeder Codepfad, der die Daten ändert, jeden Cache kennt, der sie hält, und genau das geht schief, wenn Systeme wachsen. In verteilten Systemen wird Invalidierung oft durch Ereignisse ausgelöst: Der Speisekarten-Service veröffentlicht MenuChanged, und jeder Service, der eine Kopie hält, löscht seinen Eintrag. Die meisten professionellen Entwürfe kombinieren beides: Invalidierung bei Änderungen für Aktualität und eine TTL als Sicherheitsnetz für die Invalidierung, die verpasst wurde.

Die Schwierigkeit fasst ein Bonmot zusammen, das Phil Karlton von Netscape zugeschrieben wird: In der Informatik gibt es nur zwei schwierige Dinge: Cache-Invalidierung und das Benennen von Dingen. Es ist schwierig, weil Invalidierung ein verkapptes Problem verteilter Systeme ist. Der Schreibvorgang in der Datenbank und das Löschen im Cache sind zwei Operationen auf zwei Systemen ohne gemeinsame Transaktion; die eine kann gelingen, während die andere scheitert, und Operationen verschiedener Anfragen können sich überlappen.

Zwei Regeln vermeiden die meisten Probleme. Erstens: Aktualisieren Sie bei einem Schreibvorgang die Datenbank und löschen Sie dann den Cache-Eintrag; schreiben Sie nicht den neuen Wert in den Cache. Zwei gleichzeitige Schreiber, die jeweils den Cache setzen, können in umgekehrter Reihenfolge zu ihren Datenbank-Commits fertig werden und den älteren Wert auf unbestimmte Zeit im Cache hinterlassen, während ein Löschen höchstens einen zusätzlichen Fehltreffer verursacht. Zweitens: Akzeptieren Sie, dass selbst Löschen beim Schreiben eine schmale Race Condition übrig lässt, wie unten gezeigt, und begrenzen Sie sie mit einer TTL. Facebooks Paper von 2013 zur Skalierung von memcache beschreibt für diesen Fall Leases: Der Cache gibt dem Client, der einen Fehltreffer hatte, ein Token und lehnt dessen späteren Schreibvorgang ab, wenn der Schlüssel in der Zwischenzeit gelöscht wurde.

Stampedes und die Thundering Herd

Eine Cache Stampede entsteht, wenn ein beliebter Eintrag abläuft oder ein Cache-Knoten leer neu startet und Hunderte gleichzeitiger Anfragen im selben Augenblick einen Fehltreffer haben. Jede geht zur Datenbank, um denselben Wert zu berechnen, und die Datenbank, dimensioniert für die normale Fehltrefferrate des Cache, wird überlastet. Langsamere Antworten bedeuten, dass sich mehr Anfragen stauen, und die Überlast kann sich kaskadenartig ausbreiten. Die verwandte Thundering Herd beschreibt viele wartende Clients, die gleichzeitig geweckt werden und um eine Ressource konkurrieren. Facebook berichtete, dass Leases bei einer Gruppe besonders anfälliger Schlüssel die Spitzenrate der Datenbankabfragen von 17.000 auf 1300 pro Sekunde senkten.

Die Abwehrmaßnahmen lassen sich gut kombinieren. Request Coalescing (auch Single Flight genannt) lässt nur eine Anfrage pro Schlüssel bei der Quelle abrufen, während die anderen auf ihr Ergebnis warten; innerhalb eines Prozesses ist das eine Map laufender Futures, prozessübergreifend eine kurze Sperre im Cache, wie im Code oben. Gestreuter Ablauf (Jitter) addiert zu jeder TTL einen zufälligen Betrag, damit gemeinsam geschriebene Einträge (nach einem Deployment oder einem Leeren des Cache) nicht gemeinsam ablaufen. Stale-While-Revalidate liefert allen den abgelaufenen Wert aus, während eine Hintergrundanfrage einen frischen holt, was die Latenzspitze vollständig beseitigt, wenn leichtes Veralten akzeptabel ist. Probabilistischer vorzeitiger Ablauf (Vattani, Chierichetti und Lowenstein, VLDB 2015) lässt jeden Leser zufällig, mit einer Wahrscheinlichkeit, die mit nahendem Ablauf steigt, über eine vorzeitige Aktualisierung entscheiden, sodass meist eine Anfrage aktualisiert, bevor der Eintrag tatsächlich abläuft. Schließlich vermeidet das Aufwärmen eines neuen Cache anhand einer Liste heißer Schlüssel, bevor er Traffic annimmt, die Kaltstart-Stampede nach einem Neustart.

Caching-Ebenen

Caches gibt es auf jeder Ebene zwischen Nutzer und Festplatte, und eine Anfrage wird von der ersten Ebene beantwortet, die eine brauchbare Kopie hat. Der Browser führt einen privaten Cache, der über HTTP-Header gesteuert wird. Ein Content Delivery Network (CDN) hält geteilte Kopien an Edge-Standorten nahe bei den Nutzern, ideal für Bilder, Skripte und öffentliche API-Antworten wie Speisekarten. Ein Reverse Proxy am Origin (Nginx, Varnish) kann ganze Antworten für einige Sekunden cachen; das heißt Microcaching und kann eine plötzliche Lastspitze abfangen. Die Anwendung cacht berechnete Objekte, entweder prozessintern (am schnellsten, aber jede Instanz hält ihre eigene Kopie, und die Kopien widersprechen sich) oder in einem gemeinsamen Cache wie Redis oder Memcached. Die Datenbank cacht Seiten im Arbeitsspeicher (die Shared Buffers von PostgreSQL, der InnoDB-Buffer-Pool) und kann teure Ergebnisse in materialisierten Views vorberechnen.

Je weiter von den Daten entfernt, desto größer die Ersparnis pro Treffer und desto schwieriger die Invalidierung. Einen Schlüssel aus Redis können Sie in einer Millisekunde löschen; ein CDN können Sie leeren, langsamer; in den Browser eines Kunden können Sie gar nicht hineingreifen, also ist jedes max-age, das Sie senden, ein Versprechen, mit dem Sie leben müssen. Lange Browser-Lebensdauern werden daher für Dateien verwendet, deren URL sich ändert, wenn sich ihr Inhalt ändert (app.3f9a1c.js), und kurze, oder Revalidierung, für alles andere.

HTTP-Caching-Header

HTTP hat ein vollständiges Caching-Modell, definiert in RFC 9111 (Juni 2022), und wer es gut nutzt, kann Last abfangen, bevor sie Ihre Server erreicht. Cache-Control: max-age=60 erlaubt jedem Cache, eine Antwort 60 Sekunden lang wiederzuverwenden; s-maxage überschreibt das für geteilte Caches wie CDNs; private verbietet geteilten Caches, sie zu speichern (verwenden Sie es für alles Persönliche); no-cache bedeutet verwirrenderweise speichern, aber vor jeder Wiederverwendung beim Server nachfragen; und no-store bedeutet nie eine Kopie behalten, die richtige Einstellung für Kontostände und Kontoauszüge. Die Erweiterungen stale-while-revalidate und stale-if-error (RFC 5861, 2010) wenden die obigen Ideen zu Stampedes und Verfügbarkeit auf HTTP-Ebene an.

Ist eine Kopie im Cache veraltet, muss der Client sie nicht erneut herunterladen. Ein Validator lässt ihn fragen, ob sich etwas geändert hat: Der Server sendet mit der Antwort ein ETag (eine undurchsichtige Versionskennung) oder ein Last-Modified-Datum, und der Client sendet später If-None-Match oder If-Modified-Since. Hat sich nichts geändert, antwortet der Server mit 304 Not Modified ohne Body, was Bandbreite und oft den größten Teil der Serverarbeit spart. Diese bedingten Anfragen sind in RFC 9110 definiert. Der Header Vary teilt Caches mit, welche Anfrage-Header (etwa Accept-Language) unterschiedliche Antworten erzeugen, damit eine französische Speisekarte nie auf eine englische Anfrage ausgeliefert wird.

GET /restaurants/17/menu HTTP/1.1
Host: api.example-food.test

HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: public, max-age=60, s-maxage=300, stale-while-revalidate=30
ETag: "menu-17-v42"

... 18 KB of menu JSON ...

# 100 seconds later the copy is past max-age plus the stale-while-revalidate
# window, so the browser must revalidate before using it:
GET /restaurants/17/menu HTTP/1.1
If-None-Match: "menu-17-v42"

HTTP/1.1 304 Not Modified
Cache-Control: public, max-age=60, s-maxage=300, stale-while-revalidate=30
ETag: "menu-17-v42"

# A bank balance, by contrast, must never sit in any cache:
Cache-Control: no-store

Verdrängung, Dimensionierung und Konsistenzrisiken

Ein Cache ist kleiner als die Daten dahinter, also muss er etwas verdrängen, wenn er voll ist. Least Recently Used (LRU) verdrängt den Eintrag, der am längsten unberührt ist, und funktioniert gut, wenn jüngste Nutzung künftige Nutzung vorhersagt. Least Frequently Used (LFU) verdrängt den am seltensten genutzten Eintrag und widersteht einmaligen Scans (ein nächtlicher Bericht, der jedes Restaurant einmal berührt, würde einen LRU-Cache seiner wirklich heißen Einträge entleeren). Produktive Caches nähern beides an: Redis etwa zieht eine Stichprobe weniger Schlüssel, verdrängt den besten Kandidaten darunter und bietet Strategien wie allkeys-lru, allkeys-lfu und volatile-ttl. Seine Standardstrategie noeviction lehnt Schreibvorgänge ab, wenn der Speicher voll ist, was zu Redis als Datenspeicher passt, aber nicht als Cache; legen Sie die Strategie also bewusst fest.

Über das Veralten hinaus bringen Caches subtilere Konsistenzrisiken mit sich. Ein Nutzer, der seine Lieferadresse ändert und dann die alte sieht, weil der Lesezugriff aus einem Cache kam, den eine andere Instanz noch nicht invalidiert hatte, erlebt eine gebrochene Read-your-Writes-Garantie (Abschnitt 7.4); eine gängige Lösung ist, den Cache für die eigenen jüngsten Schreibvorgänge eines Nutzers zu umgehen. Prozessinterne Caches auf vielen Instanzen widersprechen einander, sodass aufeinanderfolgende Anfragen, die an verschiedene Instanzen gehen, einen Wert scheinbar rückwärts laufen lassen. Einen Fehler oder ein leeres Ergebnis ohne kurze TTL zu cachen, macht aus einem kurzen Ausfall einen langen. Daten zu cachen, die Nutzer vermischen (eine Seite mit dem Namen des Kunden, nur unter der URL gecacht), gibt personenbezogene Daten an den nächsten Besucher preis, eine bekannte Klasse von Sicherheitsvorfällen. Und Cache-Schlüssel müssen alles enthalten, was die Antwort verändert: Mandant, Sprache, Währung, Berechtigungen und die Version des Datenformats.