Stratégies de Cache Distribué : Stale-While-Revalidate et Protection Anti-Stampede

1. Le risque du Cache Stampede (Thundering Herd)

Un cache stampede se produit quand une clé très sollicitée expire et qu’une rafale de requêtes concurrentes, arrivant dans les mêmes quelques millisecondes, ratent toutes le cache en même temps et retombent simultanément vers l’origine — votre base de données, ou un agrégat coûteux à calculer. Au lieu qu’une seule requête paie le coût du recalcul, ce sont N requêtes qui le paient en même temps, et N se compte souvent en centaines voire en milliers pour une clé réellement populaire sur un service à fort trafic.

La base de données ne perçoit pas cela comme N requêtes lentes indépendantes ; elle voit une rafale soudaine de charge identique et coûteuse arrivant d’un coup, exactement le motif qui sature les pools de connexions et pousse la latence P99 contre un mur. Sur un système déjà proche de sa capacité, un stampede sur une seule clé suffit à déclencher un épuisement du pool de connexions, qui se propage ensuite en cascade vers des requêtes sans rapport qui expirent, car elles se disputent le même pool fini de connexions base de données.

La solution naïve consistant à simplement baisser les TTL pour garder des données plus fraîches aggrave le problème au lieu de le résoudre, car elle augmente la fréquence des événements d’expiration et donc la fréquence des fenêtres de stampede. La vraie solution ne concerne pas du tout la valeur du TTL — il s’agit de garantir que lorsqu’une clé expire effectivement, une seule requête est responsable de son recalcul, tandis que toutes les autres requêtes concurrentes reçoivent une réponse raisonnable au lieu de frapper elles aussi l’origine.

2. Expiration probabiliste avec l’algorithme XFetch

XFetch (issu de l’article de 2015 de Vattani, Chierichetti et Lowenstein) attaque le stampede avant qu’il ne se produise en faisant recalculer les entrées de cache de façon probabiliste avant leur expiration réelle, étalant le recalcul dans le temps au lieu de le concentrer à l’instant précis de l’expiration. Chaque entrée en cache stocke non seulement sa valeur, mais aussi le temps réel qu’il a fallu pour la calculer (delta) et son heure d’expiration. À chaque lecture, plutôt qu’un test binaire is it expired, vous calculez un déclencheur probabiliste d’expiration anticipée.

La formule centrale est : recalculer par anticipation si `now - (delta * beta * ln(random()))` est supérieur ou égal à l’heure d’expiration, où beta est une constante ajustable (1.0 en général) et random() tire uniformément dans (0,1]. Comme ln(random()) est plus souvent proche de zéro que de grande magnitude, la plupart des lectures passent sans déclenchement, mais à mesure que la véritable expiration approche, la probabilité de déclencher un recalcul anticipé en arrière-plan augmente progressivement — le recalcul s’étale ainsi sur de nombreuses lectures antérieures au lieu d’éclater d’un coup au moment où le TTL atteint zéro.