Cache-Strategie für URL-Redirects: L1 LRU und L2 Redis

Die Redirect-Ebene eines URL-Shorteners ist eines der wenigen Produktivsysteme, bei denen die Cache-Strategie die Architektur definiert. Auf dem Hot-Path findet keine andere relevante Arbeit statt – jeder Request löst einen Key (den Kurz-Slug) auf, liest eine Ziel-URL und sendet einen 301 oder 302. Alles andere ist Observability und Buchhaltung. Der Cache entscheidet darüber, ob ein Request im Median 800 Mikrosekunden oder 12 Millisekunden dauert.

Dieser Post dokumentiert die Cache-Strategie hinter dem Edge-Redirect-Service von Elido. Zwei Stufen, eine Eviction-Policy, die eher auf Tail-Latency als auf die Hit-Rate optimiert ist, eine Warming-Strategie, die langweiliger ist als sie klingt, und Fehlerszenarien, die wir in 18 Monaten Produktionsbetrieb tatsächlich erlebt haben. Der Redirect p95 < 15ms Cornerstone deckt das gesamte Latenz-Budget ab; dies hier ist der spezifische Deep-Dive in den Cache.

Warum zwei Stufen#

Die einfachste Cache-Architektur für einen Redirect-Service ist eine einzige Stufe: ein Redis-Cluster zwischen dem Redirect-Prozess und der Origin-Datenbank. Jeder Request, der nicht die Datenbank trifft, trifft Redis; jeder Request, der nicht Redis trifft, trifft die Datenbank. Der Redis-Hop fügt etwa 1ms hinzu, wenn sich Redis in der gleichen Region befindet.

Zweistufige Caches fügen eine In-Process-Ebene vor Redis hinzu. Die erste Stufe – nennen wir sie L1 – befindet sich direkt im Adressraum des Redirect-Prozesses. Ein Treffer in L1 liefert die Ziel-URL in wenigen hundert Nanosekunden zurück, ohne Netzwerk-Roundtrip. Ein Miss in L1 fällt auf Redis (L2) zurück, das mit Sub-Millisekunden-Latenz antwortet. Ein Miss in L2 fällt auf den gRPC-Aufruf gegen die kanonische Postgres-Datenbank zurück.

Die Wahl zwischen einer oder zwei Stufen ist im Grunde eine Frage davon, wie flach die Tail-Latency sein muss. Redis ist schnell, aber nicht kostenlos. Eine p50 von 1ms zu Redis wird unter Last zu einer p99 von 4-6ms, und die p99.9 kann 20ms überschreiten, wenn das Netzwerk überlastet ist. Bei einem SLO, das eine p95 < 15ms anvisiert, verbraucht jeder Redis-Treffer einen erheblichen Teil des Budgets. Für eine p99.9 < 50ms ist der Redis-Tail der dominante Faktor.

Ein In-Process-LRU absorbiert die Keys mit der höchsten Frequenz – diejenigen, die über 80 % des Traffics verursachen. Bei der Traffic-Verteilung von Elido machen die Top 1000 Kurz-Links nach Request-Volumen über 70 % der Redirect-Requests aus. Diese Keys lassen sich leicht In-Process bedienen; der Long-Tail kann auf Redis zurückgreifen, ohne die p95 zu verschlechtern.

L1: Ein LRU pro Prozess#

Der L1-Cache nutzt Ristretto, den gleichen LRU mit Admission-Policy, den auch Caddy und Dgraph verwenden. Wir haben ihn aus drei Gründen ausgewählt:

• Konkurrierende Lesezugriffe skalieren linear mit den CPU-Kernen. Ein einfacher sync.Map-Cache stößt bei etwa 4 Mio. Ops/Sek auf einer typischen Edge-POP-Maschine an seine Grenzen; Ristretto schafft in unseren Benchmarks über 30 Mio. Ops/Sek.
• Die TinyLFU Admission-Policy verhindert, dass One-Shot-Scan-Workloads "heiße" Keys verdrängen. Ein Bot-Crawl, der 10.000 eindeutige Slugs jeweils einmal aufruft, verdrängt nicht die wirklich populären Links aus dem Cache.
• Begrenzter Speicher statt begrenzter Key-Anzahl. Wir können festlegen "nutze bis zu 256MB" anstatt "speichere bis zu 100.000 Einträge", was für die Kapazitätsplanung entscheidend ist.

Die Konfiguration, die wir einsetzen:

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 10_000_000, // 10M counters → tracks ~1M items
    MaxCost:     256 << 20,   // 256MB
    BufferItems: 64,
    Metrics:     true,
})

NumCounters ist die Größe der TinyLFU-Frequenz-Tracking-Tabelle; die Faustregel in der Ristretto-Dokumentation besagt: 10× die erwartete Item-Anzahl. Bei einem Budget von 256MB und einem durchschnittlichen Link-Datensatz von 200 Bytes hält der Cache etwa 1,3 Mio. Einträge, wenn er voll ist.

Die TTL für L1-Einträge beträgt 60 Sekunden. Dies ist bewusst kurz gewählt. Das Ziel eines Redirects kann jederzeit im Dashboard geändert werden, und der L1-Cache ist die am schwierigsten zu invalidierende Ebene (Redis kann per Publish invalidiert werden; L1 existiert in jedem Prozess und benötigt einen koordinierten Invalidierungspfad).

Eine TTL von 60 Sekunden bedeutet, dass die maximale Veraltung nach einem Ziel-Update 60 Sekunden beträgt. Für die meisten Anwendungsfälle ist das akzeptabel; für Fälle, in denen dies nicht ausreicht (sofortige Zieländerungen während einer Live-Kampagne), sendet der Invalidierungs-Button im Dashboard einen Fanout, der alle L1-Caches in der gesamten Flotte leert. Der Fanout nutzt Redis Pub/Sub auf einem Channel, den jeder Edge-Prozess beim Start abonniert.

L2: Redis-Cluster mit Read-Replicas#

L2 ist ein Redis-Cluster, der in jeder Region (Frankfurt, Ashburn, Singapur) bereitgestellt wird. Lesezugriffe gehen an lokale Replicas; Schreibzugriffe gehen an das regionale Primary-System und werden innerhalb des asynchronen Standardmodells von Redis repliziert.

Das Datenformat ist kompakt. Ein Redirect-Datensatz in L2 sieht so aus:

KEY:   redirect:f.elido.me:abc123
VALUE: {"d":"https://shop.example.com/spring","f":0,"v":12}

Drei Felder: Ziel-URL, Flags (Bot-Filterung aktiviert, Passwort erforderlich usw., gepackt in einen uint16) und Version. Die Version ist die Zeilenversion aus Postgres; sie ermöglicht es uns, veraltete Cache-Einträge beim Lesen zu erkennen.

Die TTL in L2 beträgt 24 Stunden. Dies ist wesentlich länger als in L1, da L2 über einen funktionierenden Invalidierungspfad verfügt: Wenn ein Link in der Origin-Datenbank erstellt oder aktualisiert wird, veröffentlicht die API eine Redis Pub/Sub-Nachricht an den regionalen Invalidierungs-Channel, woraufhin die Redirect-Prozesse ihre L1-Einträge löschen; der L2-Eintrag wird direkt von der API-Ebene überschrieben.

Die Pub/Sub-Invalidierung hat eine subtile Eigenschaft: Sie ist verlustbehaftet. Wenn ein Redirect-Prozess gerade neu startet, während die Invalidierungsmeldung veröffentlicht wird, sieht er die Meldung nicht und sein L1-Cache liefert möglicherweise bis zu 60 Sekunden lang den veralteten Wert. Wir akzeptieren dies, da die TTL die Rückfallebene bildet – die Veraltung ist zeitlich begrenzt.

Die Größe des Redis-Clusters an jedem POP ist gering. Frankfurt betreibt drei Primary-Nodes plus drei Replicas; der gesamte Datensatz passt in etwa 4GB. Bei unserer Cache-Hit-Rate (98 % L1, 1,8 % L2, 0,2 % Origin unter normaler Last) ist die Durchsatzanforderung an Redis moderat – üblicherweise 5-15k Ops/Sek in der Spitze pro POP, was weit innerhalb der Kapazität eines einzelnen Primary-Nodes läge, müssten wir konsolidieren.

Die Wahl der Eviction-Policy#

Ristrettos TinyLFU Admission-Policy ist die Entscheidung, die für die Tail-Latency am wichtigsten ist.

Ein naiver LRU verwirft den am längsten nicht genutzten Key, wann immer Platz geschaffen werden muss. Das ist in Ordnung, wenn das Zugriffsmuster einigermaßen gleichmäßig ist – die Keys, die zuletzt benutzt wurden, werden am wahrscheinlichsten wieder benutzt. Bei zwei spezifischen Mustern versagt dies jedoch:

• Scan-Workloads. Ein Bot-Crawl, der 50.000 eindeutige Slugs in schneller Folge aufruft, wird bei einem naiven LRU jeden heißen Key verdrängen und durch Crawl-Keys ersetzen, auf die nie wieder zugegriffen wird. Die Cache-Hit-Rate sinkt, die Origin-Datenbank sieht eine Lastspitze und die p95 springt nach oben, da die meisten Requests nun den langsamen Pfad nehmen.
• Kurzzeitige Lastspitzen bei "heißen" Keys. Ein Link, der normalerweise kaum aufgerufen wird, aber plötzlich 100.000 Requests in 30 Sekunden erhält (ein viraler Social-Post, eine TV-Kampagne), muss schnell gecached werden. Bei einem naiven LRU würde er einen der existierenden heißen Keys verdrängen.

TinyLFU bewältigt beides. Die Admission-Policy verfolgt die Frequenzen der Keys und lässt einen neuen Key nur dann in den Cache, wenn er häufiger aufgerufen wird als der Kandidat für die Verdrängung. Ein One-Shot-Bot-Crawl verdrängt die heißen Keys nicht, da die Crawl-Keys einen Frequenzzähler von 1 haben. Ein kurzzeitig extrem gefragter Key gelangt in den Cache, aber erst, wenn seine Frequenz die des Verdrängungskandidaten übersteigt – was innerhalb weniger hundert Requests geschieht.

Der Preis dafür ist, dass die ersten 100-500 Requests für einen neu populär gewordenen Link langsam sind (sie fallen auf L2 oder die Origin zurück), bis die Admission-Policy entscheidet, ihn zu cachen. Für die meisten Anwendungsfälle ist dies der richtige Kompromiss; für Kampagnen, bei denen wir im Voraus wissen, dass ein Link Spitzenwerte erreichen wird, haben wir den unten beschriebenen Pre-Warm-Endpunkt.

Cache-Warming#

Der L2-Cache startet "kalt", wenn ein neuer Redis-Cluster online geht. Wir wärmen ihn nicht über einen Snapshot auf; in den ersten 5 Minuten nach einem Cluster-Neustart ist der Origin-Traffic erhöht, bis sich der Cache natürlich füllt.

Der L1-Cache startet kalt, wenn ein Redirect-Prozess neu startet (Deploys, OOM-Kills, Scale-up). In den ersten 30 Sekunden nach einem Prozess-Neustart fallen die meisten Requests auf L2 zurück; in den nächsten 60 Sekunden füllt sich L1 mit seinem Working-Set an heißen Keys. Der Gesamtbeitrag der Kaltstarts zur Origin-Last ist gering (die meisten Edge-Prozesse starten viel seltener neu als die Cache-TTL).

Die Ausnahme: Wenn ein Campaign-Manager einen Link vorab veröffentlicht, von dem bekannt ist, dass er Spitzenwerte erreichen wird – eine TV-Werbe-URL, eine Pressemitteilungs-URL, eine Launch-Ankündigung –, bietet das Dashboard eine "Pre-warm"-Option an. Das Aktivieren sendet einen No-Op-Redirect gegen den Edge-Redirect-Service an jedem POP, wodurch L1 im Voraus gefüllt wird. Dies ist unspektakulär und selten notwendig; der Autoscaler bewältigt unvorhergesehene Traffic-Spitzen angemessen. Das Vorwärmen ist die Antwort auf erwartete Lastspitzen, bei denen die Kalt-Cache-Latenz der ersten 60 Sekunden sichtbar wäre.

Was bei Erreichen der L1-Kapazität passiert#

Ein 256MB L1-Cache füllt sich an einem typischen Edge-POP in weniger als einer Minute. Sobald er voll ist, muss die TinyLFU Admission-Policy bei jedem neuen Key entscheiden, ob er einen bestehenden Key verdrängen soll.

Die interessante Beobachtung: Bei unserer Verteilung stagniert die L1-Hit-Rate bei etwa 98 %, sobald er warm ist. Die 2 % Miss-Rate sind der Long-Tail – die ~30 % der Links, die weniger als 30 % des Traffics ausmachen und daher die TinyLFU-Frequenzschwelle nicht überschreiten. Diese verfehlen L1 und treffen L2, wo die Hit-Rate etwa 99 % beträgt. Die verbleibenden 0,2 % der Gesamtanfragen fallen auf die Origin zurück.

Wir haben diese Verteilung bei drei verschiedenen Workload-Formen gemessen – starker Bot-Traffic, virale Spitzen, Steady-State – und die L1-Hit-Rate schwankt zwischen 95 % und 99 %. Die L2-Hit-Rate ist mit 98-99,5 % stabiler. Die gesamte Origin-Last aus der Redirect-Ebene ist somit auf etwa 0,5 % des eingehenden Request-Volumens begrenzt, was die entscheidende Zahl für die Kapazitätsplanung der Origin-Systeme ist.

Cache-Invalidierung im Detail#

Der Invalidierungs-Flow ist der Teil, der von Außenstehenden am häufigsten missverstanden wird. Die Details:

Wenn die API einen PATCH /v1/links/{id} erhält, der die Ziel-URL ändert, passieren drei Dinge nacheinander:

1. Postgres committet die Änderung mit der neuen Zeilenversion (UPDATE links SET destination = ?, version = version + 1 WHERE id = ?).
2. Redis wird direkt beschrieben mit dem neuen Wert in jedem regionalen Redis-Cluster. Der Schreibvorgang wird von der API über eine Write-Through-Ebene an jedes regionale Redis verteilt.
3. Die Pub/Sub-Invalidierung wird veröffentlicht auf jedem regionalen invalidate:redirect-Channel. Edge-Redirect-Prozesse abonnieren diesen Channel beim Start und löschen den L1-Eintrag für den Key.

Die Reihenfolge ist entscheidend. Postgres-zuerst stellt sicher, dass der kanonische Speicher den neuen Wert hat. Redis-Write-Through vor der Veröffentlichung stellt sicher, dass jeder Prozess, der die Veröffentlichung verpasst, aber von Redis liest, den neuen Wert sieht. Das Veröffentlichen ist die Optimierung, die L1 synchron hält; die TTL ist die Rückfallebene, falls eine Veröffentlichung verpasst wird.

Die bekannte Race Condition: Ein Redirect-Prozess, der von Redis liest (wegen eines L1-Misses) und eine gleichzeitige Invalidierungs-Veröffentlichung. Der Lesezugriff kann den neuen Wert liefern (die Veröffentlichung geschah kurz vor dem Lesen) oder den alten (die Veröffentlichung geschah kurz danach). Wenn der alte Wert zurückgegeben und in L1 gecached wird, liefert dieser Prozess für die nächsten 60 Sekunden möglicherweise den alten Wert aus. Dies ist akzeptabel; die Alternative – ein synchrones Locking um das Read-Publish-Race herum – würde die Latenz bei jedem Request erhöhen, um einen Edge-Case zu vermeiden, der weniger als 0,01 % der Invalidierungen betrifft.

Für Anwendungsfälle, in denen das Zeitfenster der Veraltung inakzeptabel ist (eine Ziel-URL wird aus rechtlichen Gründen abgeschaltet, ein Ziel ist plötzlich bösartig), führt die Aktion "Cache leeren" im Dashboard eine aggressive Invalidierung durch: Sie pausiert alle L1-Lesezugriffe in der gesamten Flotte für 100ms, löscht den Key aus jedem L1 und nimmt den Betrieb dann wieder auf. Dies wird selten genutzt und ist durch ein Ratenlimit pro Sekunde geschützt.

Fehlerszenarien aus der Praxis#

Drei Fehler aus der 18-monatigen Produktionsgeschichte, die dokumentationswürdig sind, da sie die aktuelle Konfiguration geprägt haben.

Redis Primary-Failover mit veralteten Replicas. Im vierten Monat des Betriebs fiel ein Primary-Node im Frankfurter Cluster aus. Die Replica wurde innerhalb von 30 Sekunden befördert (Sentinel-gesteuerter Failover). Die Replicas waren im Moment des Ausfalls etwa 200ms hinter dem Primary, was bedeutete, dass die ersten paar hundert Invalidierungen, die kurz vor dem Failover veröffentlicht wurden, die beförderte Replica nicht erreichten. Ergebnis: Ein kurzes Zeitfenster, in dem etwa 0,3 % der Redirects veraltete Ziele auslieferten. Lösung: Wir betreiben Replicas nun mit min-replicas-to-write 1 und min-replicas-max-lag 10, was eine geringfügig schlechtere Schreibverfügbarkeit gegen eine engere Replikationsgarantie eintauscht.

L1-Cache-Thrashing während eines synthetischen Monitoring-Scans. Im neunten Monat war ein Drittanbieter-Uptime-Monitoring-Dienst so fehlkonfiguriert, dass er jeden Kurz-Link im Workspace eines Kunden einmal pro Minute prüfte. Der Kunde hatte 18.000 Kurz-Links. Das Probing-Muster war ein vollständiger Scan alle 60 Sekunden. Effekt: Die L1-Cache-Hit-Rate sank an drei Edge-POPs von 98 % auf 71 %, da das Scan-Muster jeden geprüften Key in den Cache aufnahm. Lösung: Wir haben eine User-Agent-basierte Filterung vor der Cache-Admission-Ebene hinzugefügt – bekannte Monitoring-User-Agents umgehen den Cache und werden direkt von L2 bedient. Dies war ein TinyLFU-Edge-Case: Die Scan-Keys sahen häufig genug aus, um wirklich heiße Keys zu verdrängen.

Pub/Sub-Verbindungsabbruch während eines langwierigen Deploys. Im 13. Monat führte ein Deploy, das länger dauerte als erwartet (etwa 4 Minuten), dazu, dass mehrere Edge-Prozesse mit dem alten Pub/Sub-Channel verbunden blieben, nachdem der Redis-Primary einen Failover durchgeführt hatte. Invalidierungen, die an den neuen Primary gesendet wurden, erreichten diese Prozesse nicht; ihre L1-Caches lieferten für die Dauer des Deploys veraltete Werte. Lösung: Pub/Sub-Verbindungs-Heartbeats mit automatischem Reconnect bei verpassten Heartbeats und ein L1-Flush zum Zeitpunkt des Deploys als Vorsichtsmaßnahme.

Was wir in Erwägung gezogen und verworfen haben#

Einige Alternativen, die evaluiert und nicht ausgewählt wurden:

Ein einziger In-Process-Cache ohne Redis. Getestet. Die Miss-to-Origin-Rate bei jedem einzelnen Prozess ist ohne L2 zu hoch; die Origin-Datenbank bräuchte die 3- bis 5-fache Kapazität. Die Grenzkosten für Redis sind gering im Vergleich zu den Einsparungen bei der Origin-Kapazität.

Ein CDN wie Cloudflare oder Fastly für Redirect-Caching. In Staging getestet. Die regionale Latenz eines CDNs bei einem Cache-Hit liegt mit 1-2ms in etwa im Bereich von Redis, aber die Invalidierung ist wesentlich schlechter (CDN-Purges haben Latenzen im Minutenbereich und verursachen Kosten pro URL-Purge). Das CDN fügte Komplexität hinzu, ohne die Latenz oder die Hit-Rate zu verbessern.

Ein größerer L1. Das 256MB-Budget ist auf den Speicherrahmen pro Prozess abgestimmt; eine Verdoppelung verdoppelt die Hit-Rate nicht, da das heiße Working-Set bereits hineinpasst. Der Grenznutzen sinkt bei unserer Verteilung ab etwa 128MB rapide; 256MB bieten Puffer für wachsenden Traffic.

Observability#

Die Metriken, die wir pro Edge-Prozess verfolgen:

• cache_l1_hit_total, cache_l1_miss_total – abgeleitete Hit-Rate pro Prozess.
• cache_l2_hit_total, cache_l2_miss_total – abgeleitete Hit-Rate pro Region.
• cache_origin_request_total – Origin-Request-Volumen; das SLO-Ziel ist < 1 % der Gesamtanfragen.
• cache_invalidation_total{source="pubsub|ttl|purge"} – Anzahl der Invalidierungen nach Mechanismus.
• cache_l1_memory_bytes – tatsächlich vom L1-Cache genutzter Speicher; Alarmierung bei 90 % des konfigurierten Budgets.

Alle Metriken werden von Prometheus erfasst und in den Dashboards des Observability-Guides visualisiert. Die Grafana-Dashboards auf regionaler Ebene zeigen die regionale Cache-Hit-Rate über die Zeit; die prozessbasierten Dashboards (für Incidents) zeigen die L1-Hit-Rate und den Speicherverbrauch pro Prozess.

Wann man diese Strategie nutzen sollte – und wann nicht#

Ein zweistufiger Cache ist sinnvoll, wenn:

• Der Workload read-heavy ist und eine Long-Tail-Key-Verteilung aufweist.
• Das heiße Working-Set in den Speicher pro Prozess passt (einige hundert Megabyte).
• Cache-Misses teuer genug sind, dass die zweite Stufe die Datenbanklast signifikant senkt.
• Das Budget für Veraltung so eng ist, dass die TTL von L1 allein nicht ausreicht.

Sie ist nicht sinnvoll, wenn:

• Das heiße Working-Set nicht in den Prozessspeicher passt. In diesem Fall fallen die L1-Misses so oft auf L2 zurück, dass L1 kaum einen Beitrag leistet.
• Schreibzugriffe im Verhältnis zu Lesezugriffen häufig sind. Die Invalidierungskosten dominieren dann.
• Die Daten pro Request eindeutig sind (kein Benefit durch Caching).

Für den URL-Shortener-Workload treffen alle vier "Ja"-Bedingungen zu, und die oben beschriebene Konfiguration hat sich über 18 Monate Produktionswachstum bewährt. Bei anderen Workloads müssen die Anzahl der Stufen und die Eviction-Policy neu bewertet werden.

Weiterführende Artikel#

• Redirect p95 < 15ms für FRA, ASH und SGP – der Cornerstone für den Engineering-Cluster; dieser Post ist der Cache-spezifische Deep-Dive.
• Warum wir ClickHouse für Click-Analytics nutzen (nicht Postgres) – angrenzende Engineering-Entscheidung in der gleichen Architektur.
• Fire-and-Forget Click-Ingestion mit Redpanda – die Pipeline für Click-Events, die parallel zum Redirect-Cache läuft.
• Short-Links als Terraform – der operative Walkthrough für die Konfiguration der Redirect-Ebene.
• Edge-Architektur: /docs/architecture/edge-redirect.
• Operativer Guide: /docs/guides/observability – das oben erwähnte Metriken-Dashboard.
• Produktübersicht: /solutions/developers und /solutions/analytics.
• Extern: Ristrettos Design-Paper und das TinyLFU-Paper zur Theorie der Admission-Policy.