Stratégies de mise en cache et leurs pièges

Pourquoi mettre en cache, et ce que cela coûte

Un cache conserve une copie des données dans un endroit plus rapide ou plus proche que leur emplacement d’origine, afin que les requêtes répétées ne paient pas le prix fort à chaque fois. La section 0.2 a présenté l’idée comme un échange d’espace contre du temps. À l’échelle de l’architecture, l’échange est plus intéressant, car un cache modifie trois qualités à la fois. Il réduit la latence (une consultation de Redis dans le même centre de données prend généralement bien moins d’une milliseconde ; une requête qui joint cinq tables peut prendre des dizaines de millisecondes). Il augmente le débit et protège la base de données, car chaque succès (hit) est une requête que la base de données ne voit jamais. Et il peut améliorer la disponibilité, car un cache capable de servir des données légèrement anciennes continue de fonctionner pendant que la source est lente ou indisponible.

Le prix se paie en exactitude et en complexité. Un cache est une seconde copie des données, et deux copies peuvent diverger. Chaque cache incarne donc une décision sur le degré de péremption autorisé pour une réponse, et pour qui. Une carte de restaurant vieille de cinq minutes est acceptable ; un solde bancaire vieux de cinq minutes, montré à un client qui se demande s’il peut se permettre un paiement, ne l’est pas. Les caches ajoutent aussi un composant qui peut tomber en panne, consomment de la mémoire qui coûte de l’argent et créent de nouveaux modes de défaillance, comme les ruées et les démarrages à froid, qui n’existeraient pas sans eux. La première question n’est donc pas quel cache ? mais qu’est-ce qui peut être périmé, dans quelle mesure, et que se passe-t-il si c’est le cas ?

L’efficacité d’un cache se mesure par son taux de succès : le nombre de succès divisé par le nombre total de consultations. Le taux de succès dépend de l’asymétrie du profil d’accès. Dans la plupart des systèmes grand public, le trafic de lecture est très asymétrique (une petite fraction des restaurants, des produits ou des comptes reçoit l’essentiel des lectures), si bien qu’un cache contenant quelques pour cent des données peut souvent répondre à la plupart des lectures. Un accès aléatoire uniforme, en revanche, se met mal en cache quoi que vous fassiez.

Les cinq patrons classiques

Les patrons de mise en cache diffèrent par l’acteur qui charge le cache, par le moment où les écritures atteignent la source, et donc par le degré de péremption et de durabilité des données. Le tableau les compare ; les paragraphes qui le suivent expliquent où chacun trouve sa place.

Cache-aside est le choix par défaut pour de bonnes raisons : il est facile à comprendre et échoue sans danger, car si le cache disparaît, l’application lit simplement la base de données (plus lentement). Read-through déplace la même logique dans une bibliothèque ou un produit de cache, ce qui est plus net, mais ne change rien au comportement. Write-through convient aux données lues peu après leur écriture, comme la session d’un utilisateur ou son panier. Write-behind est le plus risqué : il fait du cache le système de référence temporaire, si bien qu’il ne convient que lorsque perdre les dernières secondes d’écritures est acceptable (compteurs de vues, événements analytiques, scores de jeu) ou lorsque le cache lui-même est répliqué et durable. N’utilisez jamais write-behind pour de l’argent. Refresh-ahead est une optimisation pour un petit ensemble de clés très demandées, comme la liste des restaurants de la page d’accueil dans une grande ville animée.

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

Durée de vie et invalidation

Il y a deux façons d’empêcher un cache de servir des données qui ont changé. La première est une durée de vie (TTL) : chaque entrée expire après une période fixe, ce qui borne la péremption sans aucune coordination. Un TTL de cinq minutes sur les cartes signifie qu’un changement de prix est visible partout en moins de cinq minutes. La seconde est l’invalidation explicite : quand la source change, quelque chose supprime ou met à jour la copie en cache. L’invalidation donne des données plus fraîches, mais exige que chaque chemin de code qui modifie les données connaisse chaque cache qui les contient, et c’est exactement ce qui se dérègle à mesure que les systèmes grandissent. Dans les systèmes distribués, l’invalidation est souvent pilotée par des événements : le service Carte publie MenuChanged, et chaque service qui en détient une copie supprime son entrée. La plupart des conceptions professionnelles combinent les deux : invalider lors des changements pour la fraîcheur, et garder un TTL comme filet de sécurité pour l’invalidation qui aura été manquée.

La difficulté est résumée par une boutade attribuée à Phil Karlton, de Netscape : Il n’y a que deux choses difficiles en informatique : l’invalidation de cache et le nommage des choses. C’est difficile parce que l’invalidation est un problème de systèmes distribués déguisé. L’écriture en base de données et la suppression dans le cache sont deux opérations sur deux systèmes sans transaction commune ; l’une peut donc réussir pendant que l’autre échoue, et des opérations issues de requêtes différentes peuvent s’entrelacer.

Deux règles évitent la plupart des problèmes. D’abord, lors d’une écriture, mettez à jour la base de données, puis supprimez l’entrée du cache ; n’écrivez pas la nouvelle valeur dans le cache. Deux écrivains concurrents qui mettent chacun le cache à jour peuvent terminer dans l’ordre inverse de leurs commits en base de données et laisser l’ancienne valeur en cache indéfiniment, alors qu’une suppression ne peut causer qu’un défaut supplémentaire. Ensuite, acceptez que même la suppression à l’écriture laisse une étroite situation de concurrence, illustrée ci-dessous, et bornez-la avec un TTL. L’article de Facebook de 2013 sur le passage à l’échelle de memcache décrit des baux (leases) pour ce cas : le cache remet un jeton au client qui a subi le défaut, et refuse l’écriture ultérieure de ce client si la clé a été supprimée entre-temps.

Ruées et effet de troupeau

Une ruée sur le cache (cache stampede) se produit quand une entrée populaire expire, ou qu’un nœud de cache redémarre vide, et que des centaines de requêtes concurrentes ratent toutes le cache au même instant. Chacune va à la base de données pour calculer la même valeur, et la base de données, dimensionnée pour le taux de défaut normal du cache, est submergée. Des réponses plus lentes font s’accumuler davantage de requêtes, et la surcharge peut se propager en cascade. Le phénomène voisin de l’effet de troupeau (thundering herd) désigne de nombreux clients en attente réveillés en même temps pour se disputer une seule ressource. Facebook a indiqué que, pour un ensemble de clés particulièrement sujettes à ce problème, les baux ont fait passer le pic de requêtes à la base de données de 17 000 à 1300 par seconde.

Les parades se combinent bien. Le regroupement des requêtes (request coalescing, aussi appelé single flight) ne laisse qu’une requête par clé aller chercher la valeur à la source, pendant que les autres attendent son résultat ; au sein d’un processus, c’est une table de futures en cours ; entre processus, un verrou court dans le cache, comme dans le code ci-dessus. L’expiration avec gigue aléatoire (jitter) ajoute une durée aléatoire à chaque TTL afin que des entrées écrites ensemble (après un déploiement ou un vidage du cache) n’expirent pas ensemble. Stale-while-revalidate sert la valeur expirée à tout le monde pendant qu’une requête en arrière-plan en récupère une nouvelle, ce qui supprime entièrement le pic de latence quand une légère péremption est acceptable. L’expiration anticipée probabiliste (Vattani, Chierichetti et Lowenstein, VLDB 2015) fait décider à chaque lecteur, au hasard et avec une probabilité qui augmente à l’approche de l’expiration, de rafraîchir l’entrée en avance, de sorte qu’une requête la rafraîchit généralement avant qu’elle n’expire réellement. Enfin, le préchauffage d’un nouveau cache à partir d’une liste de clés très demandées, avant qu’il ne reçoive du trafic, évite la ruée du démarrage à froid après un redémarrage.

Les niveaux de cache

Les caches existent à chaque niveau entre l’utilisateur et le disque, et une requête reçoit sa réponse du premier niveau qui dispose d’une copie utilisable. Le navigateur garde un cache privé contrôlé par des en-têtes HTTP. Un réseau de diffusion de contenu (CDN) garde des copies partagées dans des emplacements en périphérie (edge), près des utilisateurs, idéal pour les images, les scripts et les réponses d’API publiques comme les cartes. Un reverse proxy à l’origine (Nginx, Varnish) peut mettre en cache des réponses entières pendant quelques secondes, ce qu’on appelle le microcaching, qui peut absorber un pic soudain. L’application met en cache des objets calculés, soit dans le processus (le plus rapide, mais chaque instance a sa propre copie et elles divergent), soit dans un cache partagé comme Redis ou Memcached. La base de données met en cache des pages en mémoire (les shared buffers de PostgreSQL, le buffer pool d’InnoDB) et peut précalculer des résultats coûteux dans des vues matérialisées.

Plus on est loin des données, plus l’économie par succès est grande et plus l’invalidation est difficile. Vous pouvez supprimer une clé de Redis en une milliseconde ; vous pouvez purger un CDN, plus lentement ; vous ne pouvez pas du tout atteindre le navigateur d’un client, si bien que le max-age que vous envoyez est une promesse avec laquelle vous devrez vivre. Les longues durées de vie dans le navigateur sont donc réservées aux fichiers dont l’URL change quand leur contenu change (app.3f9a1c.js), et les courtes, ou la revalidation, à tout le reste.

En-têtes de cache HTTP

HTTP dispose d’un modèle de cache complet, défini dans la RFC 9111 (juin 2022), et bien l’utiliser peut supprimer de la charge avant même qu’elle n’atteigne vos serveurs. Cache-Control: max-age=60 permet à n’importe quel cache de réutiliser une réponse pendant 60 secondes ; s-maxage remplace cette valeur pour les caches partagés comme les CDN ; private interdit aux caches partagés de la stocker (utilisez-le pour tout ce qui est personnel) ; no-cache signifie, de façon déroutante, stocke-la, mais vérifie auprès du serveur avant chaque réutilisation ; et no-store signifie n’en garde jamais de copie, le bon réglage pour les soldes et les relevés bancaires. Les extensions stale-while-revalidate et stale-if-error (RFC 5861, 2010) appliquent au niveau HTTP les idées de ruée et de disponibilité vues plus haut.

Quand une copie en cache est périmée, le client n’a pas besoin de la télécharger à nouveau. Un validateur lui permet de demander si quelque chose a changé : le serveur envoie un ETag (un identifiant de version opaque) ou une date Last-Modified avec la réponse, et le client envoie plus tard If-None-Match ou If-Modified-Since. Si rien n’a changé, le serveur répond 304 Not Modified sans corps, ce qui économise de la bande passante et souvent l’essentiel du travail du serveur. Ces requêtes conditionnelles sont définies dans la RFC 9110. L’en-tête Vary indique aux caches quels en-têtes de requête (comme Accept-Language) produisent des réponses différentes, afin qu’une carte en français ne soit jamais servie à une requête en anglais.

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

Éviction, dimensionnement et risques de cohérence

Un cache est plus petit que les données qu’il couvre ; quand il est plein, il doit donc évincer quelque chose. La politique moins récemment utilisé (LRU) évince l’entrée restée inutilisée le plus longtemps et fonctionne bien quand l’usage récent prédit l’usage futur. La politique moins fréquemment utilisé (LFU) évince l’entrée la moins souvent utilisée et résiste aux parcours ponctuels (un rapport nocturne qui touche chaque restaurant une fois viderait un cache LRU de ses entrées réellement très demandées). Les caches de production approximent les deux : Redis, par exemple, échantillonne quelques clés et évince le meilleur candidat parmi elles, et propose des politiques comme allkeys-lru, allkeys-lfu et volatile-ttl. Sa politique par défaut, noeviction, rejette les écritures quand la mémoire est pleine, ce qui convient à Redis utilisé comme stockage, mais pas comme cache ; choisissez donc la politique délibérément.

Au-delà de la péremption, les caches introduisent des risques de cohérence plus subtils. Un utilisateur qui change son adresse de livraison puis voit l’ancienne, parce que la lecture provient d’un cache qu’une autre instance n’avait pas encore invalidé, subit une rupture de la garantie de lecture de ses propres écritures (section 7.4) ; une solution courante consiste à contourner le cache pour les écritures récentes de l’utilisateur lui-même. Les caches internes au processus de nombreuses instances divergent entre eux, si bien que des requêtes consécutives acheminées vers des instances différentes peuvent montrer une valeur qui revient en arrière. Mettre en cache une erreur ou un résultat vide sans TTL court transforme une brève panne en une longue. Mettre en cache des données qui mêlent plusieurs utilisateurs (une page portant le nom du client, mise en cache sous la seule URL) divulgue des données personnelles au visiteur suivant, une catégorie bien connue d’incidents de sécurité. Enfin, les clés de cache doivent inclure tout ce qui change la réponse : locataire (tenant), langue, devise, permissions et version du format des données.