Stratégie de cache pour les redirections URL : L1 LRU et L2 Redis

Le niveau de redirection d'un raccourcisseur d'URL est l'un des rares systèmes de production où la stratégie de cache est l'architecture. Il n'y a pas d'autre travail significatif sur le hot path — chaque requête résout une clé (le slug court), lit une URL de destination et émet un 301 ou 302. Tout le reste n'est qu'observabilité et tenue de registres. C'est le cache qui détermine si la requête médiane prend 800 microsecondes ou 12 millisecondes.

Ce post documente la stratégie de cache derrière le service edge-redirect de Elido. Deux niveaux, une politique d'éviction choisie pour optimiser la latence de queue plutôt que le taux de réussite, une stratégie de warming plus banale qu'il n'y paraît, et les modes de défaillance que nous avons réellement rencontrés en 18 mois de production. Le pilier p95 de redirection < 15ms couvre l'ensemble du budget de latence ; ceci est un zoom spécifique sur le cache.

Pourquoi deux niveaux#

L'architecture de cache la plus simple pour un service de redirection est à un seul niveau : un cluster Redis entre le processus de redirection et la base de données d'origine. Chaque requête qui ne touche pas la base de données touche Redis ; chaque requête qui ne touche pas Redis touche la base de données. Le saut Redis ajoute environ 1ms lorsque Redis se trouve dans la même région.

Les caches à deux niveaux ajoutent une couche in-process devant Redis. Le premier niveau — appelons-le L1 — réside dans l'espace d'adressage du processus de redirection. Un succès (hit) au niveau L1 renvoie l'URL de destination en quelques centaines de nanosecondes, sans aucun aller-retour réseau. Un échec (miss) au niveau L1 retombe sur Redis (L2), qui sert avec une latence inférieure à la milliseconde. Un échec au niveau L2 retombe sur l'appel gRPC d'origine vers la base de données Postgres canonique.

Le choix entre un niveau ou deux est essentiellement une question de stabilité de votre latence de queue (tail latency). Redis est rapide, mais il n'est pas gratuit. Un p50 de 1ms vers Redis devient un p99 de 4-6ms sous charge, et le p99.9 peut dépasser 20ms en cas de congestion réseau. Pour un SLO qui cible un p95 < 15ms, chaque accès à Redis consomme une fraction significative du budget. Pour un p99.9 < 50ms, la queue de Redis est le contributeur dominant.

Un LRU in-process absorbe les clés à plus haute fréquence — celles qui génèrent plus de 80 % du trafic. Avec la distribution de trafic de Elido, les 1000 liens courts les plus populaires représentent plus de 70 % des requêtes de redirection. Ces clés sont faciles à servir in-process ; la longue traîne peut retomber sur Redis sans dégrader le p95.

L1 : un LRU par processus#

Le cache L1 utilise Ristretto, le même LRU à politique d'admission utilisé par Caddy et Dgraph. Nous l'avons choisi pour trois raisons :

• Les lectures concurrentes scalent linéairement avec les cœurs CPU. Un simple cache sync.Map plafonne à environ 4M ops/sec sur une machine POP edge typique ; Ristretto soutient plus de 30M dans nos benchmarks.
• La politique d'admission TinyLFU empêche les charges de scan ponctuel d'évincer les clés chaudes. Un crawl de bot qui touche une seule fois 10 000 slugs uniques ne déplace pas les liens réellement populaires du cache.
• Mémoire bornée plutôt que nombre de clés borné. Nous pouvons définir "utiliser jusqu'à 256MB" plutôt que "stocker jusqu'à 100 000 entrées", ce qui est la configuration cruciale pour la planification de capacité.

La configuration que nous déployons est la suivante :

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 10_000_000, // 10M compteurs → suit ~1M d'éléments
    MaxCost:     256 << 20,   // 256MB
    BufferItems: 64,
    Metrics:     true,
})

NumCounters est la taille de la table de suivi de fréquence TinyLFU ; la règle de base dans la doc de Ristretto est de 10× le nombre d'éléments attendus. Avec un budget de 256MB et un enregistrement de lien moyen de 200 octets, le cache contient environ 1,3M d'entrées lorsqu'il est plein.

Le TTL sur les entrées L1 est de 60 secondes. C'est délibérément court. La destination d'une redirection peut être modifiée dans le tableau de bord à tout moment, et le cache L1 est la couche la plus lente à invalider (Redis peut être invalidé par publication ; L1 vit dans chaque processus et nécessite un chemin d'invalidation coordonné).

Un TTL de 60 secondes signifie que la vétusté maximale est de 60 secondes après une mise à jour de destination. Pour la plupart des cas d'utilisation, c'est acceptable ; pour les cas où cela ne l'est pas (changements immédiats pendant une campagne en direct), le bouton d'invalidation du tableau de bord émet un fanout qui purge tous les caches L1 de la flotte. Le fanout utilise le pub/sub de Redis sur un canal auquel chaque processus edge s'abonne au démarrage.

L2 : cluster Redis avec réplicas de lecture#

L2 est un cluster Redis, déployé dans chaque région (FRA, ASH, SGP). Les lectures vont vers les réplicas locaux ; les écritures vont au primaire régional et sont répliquées selon le modèle asynchrone standard de Redis.

Le format des données est compact. Un enregistrement de redirection au niveau L2 ressemble à ceci :

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

Trois champs : l'URL de destination, les drapeaux (filtrage de bots activé, mot de passe requis, etc., packagés dans un uint16) et la version. La version est la version de ligne de Postgres ; elle nous permet de détecter les entrées de cache obsolètes lors de la lecture.

Le TTL au niveau L2 est de 24 heures. C'est beaucoup plus long que pour L1 car L2 possède un chemin d'invalidation fonctionnel : lorsqu'un lien est créé ou mis à jour dans la base de données d'origine, l'API publie un message pub/sub Redis sur le canal d'invalidation régional, et les processus de redirection évincent leurs entrées L1 ; l'entrée L2 est directement écrasée par la couche API.

L'invalidation par pub/sub possède une propriété subtile : elle peut subir des pertes. Si un processus de redirection est en train de redémarrer au moment où le message d'invalidation est publié, il ne voit pas le message et son cache L1 peut servir la valeur obsolète pendant 60 secondes maximum. Nous acceptons cela car le TTL sert de garde-fou — la vétusté est bornée.

La taille du cluster Redis sur chaque POP est réduite. Francfort fait tourner trois nœuds primaires plus trois réplicas ; l'ensemble des données tient dans environ 4GB. Avec notre taux de réussite (98% L1, 1,8% L2, 0,2% origine sous charge normale), le besoin de débit sur Redis est modéré — généralement 5-15k ops/sec au pic par POP, ce qui reste largement dans la capacité d'un seul nœud primaire si nous devions consolider.

Le choix de la politique d'éviction#

La politique d'admission TinyLFU de Ristretto est le choix qui importe le plus pour la latence de queue.

Un LRU naïf évince la clé la moins récemment utilisée dès qu'il doit faire de la place. C'est correct lorsque le modèle d'accès est raisonnablement uniforme — les clés les plus récemment utilisées sont celles qui ont le plus de chances d'être réutilisées. Cela s'effondre sous deux modèles spécifiques :

• Charges de scan (Scan workloads). Un crawl de bot qui frappe 50 000 slugs uniques en succession rapide va, avec un LRU naïf, évincer chaque clé chaude et les remplacer par des clés de crawl qui ne seront plus jamais consultées. Le taux de réussite du cache chute, l'origine subit un pic de charge et le p95 bondit car la plupart des requêtes passent maintenant par le chemin lent.
• Clés chaudes par rafales (Bursty hot keys). Un lien normalement froid mais qui reçoit soudainement 100 000 requêtes en 30 secondes (un post social viral, une campagne TV) doit être mis en cache rapidement. Avec un LRU naïf, il déplacera l'une des clés chaudes existantes.

TinyLFU gère les deux. La politique d'admission suit les fréquences des clés et n'admet une nouvelle clé dans le cache que si elle est plus fréquente que la candidate à l'éviction. Un crawl de bot ponctuel ne déplace pas les clés chaudes car les clés de crawl ont un compte de fréquence de 1. Une clé chaude par rafale entre bien dans le cache, mais seulement après que sa fréquence a dépassé celle de la candidate à l'éviction — ce qui arrive en quelques centaines de requêtes.

Le coût est que les 100 à 500 premières requêtes pour un lien nouvellement populaire sont lentes (retombent sur L2 ou l'origine) jusqu'à ce que la politique d'admission décide de le mettre en cache. Pour la plupart des cas d'utilisation, c'est le bon compromis ; pour les campagnes où nous savons à l'avance qu'un lien va exploser, nous avons un endpoint de pré-warm décrit ci-dessous.

Warming du cache#

Le cache L2 subit un démarrage à froid (cold-start) lorsqu'un nouveau cluster Redis est mis en ligne. Nous ne le chauffons pas à partir d'un snapshot ; les 5 premières minutes après un redémarrage de cluster voient un trafic d'origine élevé jusqu'à ce que le cache se remplisse naturellement.

Le cache L1 subit un démarrage à froid lorsqu'un processus de redirection redémarre (déploiements, OOM kills, montée en charge). Les 30 premières secondes après un redémarrage de processus voient la plupart des requêtes retomber sur L2 ; les 60 secondes suivantes voient L1 se remplir de son ensemble de travail de clés chaudes. La contribution totale du démarrage à froid à la charge d'origine est faible (la plupart des processus edge redémarrent bien moins souvent que le TTL du cache).

L'exception : lorsqu'un gestionnaire de campagne pré-publie un lien qu'il sait devoir exploser — une URL de publicité TV, une URL de communiqué de presse, une annonce de lancement — le tableau de bord propose une option de "pré-warm". L'activer émet une redirection sans opération (no-op) contre le service edge-redirect sur chaque POP, ce qui peuple L1 à l'avance. C'est peu glamour et rarement nécessaire ; l'autoscaler gère adéquatement les pics de trafic imprévus. Le pré-warm est la réponse aux pics anticipés où les 60 premières secondes de latence avec cache froid seraient visibles.

Ce qu'il se passe à la capacité maximale de L1#

Un cache L1 de 256MB se remplit en moins d'une minute sur un POP edge typique. Une fois plein, chaque nouvelle clé oblige la politique d'admission TinyLFU à décider si elle doit évincer une clé existante.

Observation intéressante : avec notre distribution, le taux de réussite L1 plafonne autour de 98 % une fois chaud. Le taux d'échec de 2 % correspond à la longue traîne — les ~30 % de liens qui représentent moins de 30 % du trafic et qui ne passent donc pas le seuil de fréquence TinyLFU. Ceux-ci échouent au niveau L1 et réussissent au niveau L2, où le taux de réussite est d'environ 99 %. Les 0,2 % de requêtes totales restantes retombent sur l'origine.

Nous avons mesuré cette distribution sur trois types de charge — trafic intense de bots, pic viral, régime permanent — et le taux de réussite L1 fluctue entre 95 % et 99 %. Le taux de réussite L2 est plus stable, entre 98 % et 99,5 %. La charge totale sur l'origine provenant du niveau de redirection est donc bornée à environ 0,5 % du volume de requêtes entrantes, ce qui est le chiffre crucial pour la planification de la capacité d'origine.

L'invalidation du cache en détail#

Le flux d'invalidation est la partie la plus souvent mal comprise par ceux qui observent l'architecture de l'extérieur. Le détail :

Lorsque l'API reçoit un PATCH /v1/links/{id} qui modifie l'URL de destination, trois choses se produisent dans l'ordre :

1. Postgres valide la modification avec la nouvelle version de ligne (UPDATE links SET destination = ?, version = version + 1 WHERE id = ?).
2. Redis est écrit directement avec la nouvelle valeur dans chaque cluster Redis régional. L'écriture se diffuse de l'API vers le Redis de chaque région via une couche de write-through.
3. L'invalidation pub/sub est publiée sur chaque canal régional invalidate:redirect. Les processus de redirection edge s'abonnent à ce canal au démarrage et évincent l'entrée L1 pour la clé concernée.

L'ordre importe. Postgres en premier garantit que le stockage canonique possède la nouvelle valeur. Le write-through Redis avant la publication garantit que tout processus qui manque la publication mais lit depuis Redis verra la nouvelle valeur. La publication est l'optimisation qui maintient L1 synchronisé ; le TTL est le garde-fou si une publication est manquée.

La situation de concurrence (race condition) connue : un processus de redirection qui lit depuis Redis (à cause d'un échec L1) et une publication d'invalidation concurrente. La lecture peut renvoyer la nouvelle valeur (la publication a eu lieu juste avant la lecture) ou l'ancienne (la publication a eu lieu juste après). Si l'ancienne valeur est renvoyée et mise en cache dans L1, les 60 prochaines secondes pourraient servir l'ancienne valeur sur ce processus. C'est acceptable ; l'alternative — un verrou synchrone autour de la course lecture-publication — ajouterait de la latence à chaque requête pour éviter un cas limite qui affecte moins de 0,01 % des invalidations.

Pour les cas d'utilisation où la fenêtre de vétusté est inacceptable (une URL de destination est retirée pour des raisons légales, une destination est soudainement malveillante), l'action "purger le cache" du tableau de bord émet une invalidation agressive : elle suspend toutes les lectures L1 pendant 100ms sur toute la flotte, évince la clé de chaque L1, puis reprend. C'est rarement utilisé et limité par un rate limit par seconde.

Modes de défaillance réellement observés#

Trois échecs issus des 18 mois d'historique de production valent la peine d'être documentés car ils ont façonné la configuration actuelle.

Failover du primaire Redis avec réplicas obsolètes. Au 4ème mois de production, un nœud primaire du cluster de Francfort a échoué. Le réplica a été promu en moins de 30 secondes (failover piloté par Sentinel). Les réplicas avaient environ 200ms de retard sur le primaire au moment de la panne, ce qui signifie que les quelques centaines d'invalidations publiées juste avant le failover n'ont pas atteint le réplica promu. Résultat : une brève fenêtre où environ 0,3 % des redirections ont servi des destinations obsolètes. Résolution : nous faisons maintenant tourner les réplicas avec min-replicas-to-write 1 et min-replicas-max-lag 10, ce qui échange un léger impact sur la disponibilité en écriture contre une garantie de retard de réplication plus stricte.

Emballement du cache L1 pendant un scan de monitoring synthétique. Au 9ème mois, un service de monitoring tiers a été mal configuré pour tester chaque lien court d'un espace de travail client une fois par minute. Le client avait 18 000 liens courts. Le modèle de test était un scan complet toutes le 60 secondes. Effet : le taux de réussite du cache L1 est tombé de 98 % à 71 % sur trois POP edge car le modèle de scan admettait chaque clé testée dans le cache. Résolution : nous avons ajouté un filtrage basé sur le User-Agent avant la couche d'admission au cache — les User-Agents de monitoring connus contournent le cache et sont servis directement depuis L2. C'était un cas limite de TinyLFU : les clés de scan semblaient assez fréquentes pour déplacer des clés réellement chaudes.

Déconnexion pub/sub pendant un déploiement prolongé. Au 13ème mois, un déploiement qui a pris plus de temps que prévu (environ 4 minutes) a fait que plusieurs processus edge sont restés connectés à l'ancien canal pub/sub après le failover du primaire Redis. Les invalidations publiées sur le nouveau primaire n'ont pas atteint ces processus ; leurs caches L1 ont servi des valeurs obsolètes pendant toute la durée du déploiement. Résolution : battements de cœur (heartbeats) de connexion pub/sub avec reconnexion automatique en cas de battements manqués, et flush L1 au moment du déploiement par précaution.

Ce que nous avons envisagé et rejeté#

Quelques alternatives évaluées et non retenues :

Un seul cache in-process, pas de Redis. Testé. Le taux d'échec vers l'origine sur un processus unique est trop élevé sans L2 ; la base de données d'origine aurait besoin de 3 à 5 fois plus de capacité. Le coût marginal de Redis est faible par rapport aux économies de capacité d'origine.

Un CDN comme Cloudflare ou Fastly pour le cache des redirections. Testé en staging. La latence régionale de 1-2ms d'un CDN sur un hit de cache est à peu près la même que Redis, mais l'histoire de l'invalidation est matériellement pire (les purges de CDN ont une latence de l'ordre de la minute et des coûts de purge par URL). Le CDN ajoutait de la complexité sans améliorer la latence ni le taux de réussite.

Un L1 plus grand. Le budget de 256MB est dimensionné selon l'enveloppe mémoire par processus ; le doubler ne double pas le taux de réussite car l'ensemble de travail chaud tient déjà dedans. Les rendements décroissants commencent vers 128MB sur notre distribution ; 256MB offre une marge de manœuvre pour la croissance du trafic.

Observability#

Les métriques que nous suivons par processus edge :

• cache_l1_hit_total, cache_l1_miss_total — taux de réussite L1 dérivé par processus.
• cache_l2_hit_total, cache_l2_miss_total — taux de réussite L2 dérivé par région.
• cache_origin_request_total — volume de requêtes à l'origine ; la cible du SLO est < 1 % des requêtes totales.
• cache_invalidation_total{source="pubsub|ttl|purge"} — décomptes d'invalidation par mécanisme.
• cache_l1_memory_bytes — mémoire réellement utilisée par le cache L1 ; alerté à 90 % du budget configuré.

Toutes les métriques sont collectées par Prometheus et visualisées dans le tableau de bord du guide d'observabilité. Les tableaux de bord Grafana au niveau régional montrent le taux de réussite du cache régional au fil du temps ; les tableaux de bord par processus (utilisés lors d'incidents) montrent le taux de réussite L1 et l'utilisation de la mémoire par processus.

Quand utiliser cette stratégie (ou pas)#

Un cache à deux niveaux a du sens quand :

• La charge de travail est lourde en lecture avec une distribution de clés à longue traîne.
• L'ensemble de travail chaud tient dans la mémoire par processus (quelques centaines de mégaoctets).
• Les échecs de cache sont assez coûteux pour que le second niveau soulage réellement la base de données.
• Le budget de vétusté est assez serré pour que le TTL du L1 seul ne soit pas acceptable.

Cela n'a pas de sens quand :

• L'ensemble de travail chaud ne tient pas dans la mémoire du processus. Dans ce cas, les échecs L1 retombent si souvent sur L2 que L1 n'apporte que peu de chose.
• Les écritures sont fréquentes par rapport aux lectures. Le coût d'invalidation domine.
• Les données sont uniques par requête (aucun bénéfice du cache).

Pour la charge de travail d'un raccourcisseur d'URL, les quatre conditions "oui" sont remplies et la configuration ci-dessus a tenu bon face à 18 mois de croissance en production. Pour d'autres charges de travail, le nombre de niveaux et la politique d'éviction doivent être réévalués.

Lectures recommandées#

• Atteindre un p95 < 15ms pour les redirections depuis FRA, ASH et SGP — la pierre angulaire pour le cluster ingénierie ; ce post en est l'approfondissement spécifique au cache.
• Pourquoi nous utilisons ClickHouse pour l'analyse des clics (pas Postgres) — décision d'ingénierie adjacente dans la même architecture.
• Ingestion de clics en mode "fire-and-forget" avec Redpanda — le pipeline d'événements de clics qui tourne en parallèle du cache de redirection.
• Les liens courts en tant que Terraform — le guide opérationnel pour la configuration du niveau de redirection.
• Architecture Edge : /docs/architecture/edge-redirect.
• Guide opérationnel : /docs/guides/observability — le jeu de tableaux de bord de métriques référencé plus haut.
• Surface produit : /solutions/developers et /solutions/analytics.
• Externe : Le document de conception de Ristretto et le papier TinyLFU pour la théorie sur la politique d'admission.