Le cache et le problème de la mémoire limitée

Un cache est une mémoire rapide mais petite — tôt ou tard, elle se remplit. La politique d'éviction décide quoi jeter.

Un cache accélère l'accès aux données en les gardant près du consommateur — en mémoire vive, dans un service dédié comme Redis, ou dans un nœud CDN. Le problème : la mémoire est chère et limitée. Tu ne peux pas tout garder. Tôt ou tard, le cache est plein et tu dois décider quoi jeter.

Les trois familles

Dans la pratique, les systèmes combinent ces familles. Redis supporte 8 politiques qui croisent famille et périmètre (toutes les clés, ou seulement les clés avec TTL). On les découvrira section 05.

Mesurer l'efficacité : hit rate

La métrique clé d'un cache est son taux de succès (hit rate) :

hit rate = hits / (hits + misses)

// Un hit rate de 95% signifie :
// 95 requêtes sur 100 trouvent la donnée en cache
// seulement 5 vont en base

Simule ci-dessous un cache LRU de capacité 4 — ajoute des entrées, observe les évictions :

LRU — Least Recently Used

Jeter ce qui n'a pas été utilisé depuis le plus longtemps — l'intuition derrière LRU et son implémentation O(1).

LRU (Least Recently Used) repose sur un pari : si tu n'as pas utilisé une donnée depuis longtemps, tu ne l'utiliseras probablement pas bientôt. C'est la logique du bureau : les dossiers que tu n'as pas touchés depuis des semaines vont dans un tiroir, les dossiers récents restent à portée de main.

Implémentation O(1)

L'implémentation naïve (liste triée par date d'accès) est O(n) sur les accès. L'implémentation standard est O(1) pour les deux opérations get et put :

// Structure interne du cache LRU
class LRUCache {
    private head: Node; // sentinel MRU (le plus récent est après)
    private tail: Node; // sentinel LRU (le plus ancien est avant)
    private map: Map<string, Node>;
    private capacity: number;

    get(key: string): any | undefined {
        const node = this.map.get(key);
        if (!node) return undefined; // miss
        this.moveToFront(node); // hit → MRU
        return node.value;
    }

    put(key: string, value: any): void {
        if (this.map.has(key)) {
            this.moveToFront(this.map.get(key)!);
            return;
        }
        if (this.map.size >= this.capacity) {
            this.evict(); // supprimer le nœud avant tail (LRU)
        }
        const node = new Node(key, value);
        this.map.set(key, node);
        this.insertAfterHead(node);
    }
}

Cas d'usage réels

Variante CLOCK (Second Chance)

LRU exact requiert des pointeurs par nœud. L'algorithme CLOCK est une approximation O(1) en espace plus compacte : un tableau circulaire avec un bit "récemment utilisé" par case. En cas d'éviction, on tourne l'horloge ; si le bit est à 1, on le met à 0 et on continue ; si le bit est à 0, on évince cette case.

C'est l'algorithme utilisé par le noyau Linux pour la gestion des pages (swap).

LFU — Least Frequently Used

Jeter ce qui est le moins souvent demandé — LFU est plus précis que LRU, mais son vieillissement pose problème.

LFU (Least Frequently Used) parie que les données les plus souvent demandées dans le passé seront les plus souvent demandées dans le futur. Contrairement à LRU qui regarde quand tu as accédé à une donnée, LFU regarde combien de fois.

Implémentation O(1) — la structure de O'Neil

L'implémentation naïve (tri par compteur) est O(n log n). L'implémentation O(1) de O'Neil utilise :

// get : O(1)
get(key):
  node = map[key]           // O(1)
  freq[key]++               // O(1)
  déplacer node vers bucket freq[key]  // O(1) — pointeurs
  if (minFreq bucket vide) minFreq++
  return node.value

// put : O(1)
put(key, value):
  if (cache plein) évince minFreq bucket.LRU  // O(1)
  insérer key dans bucket freq=1
  minFreq = 1             // le nouveau nœud a fréquence 1

Le problème du vieillissement (aging)

LFU souffre du cache pollution par les anciens accès : une clé très populaire le mois dernier mais plus du tout accédée aujourd'hui gardera un compteur élevé et ne sera jamais évincée, même si de nouvelles clés chaudes ont besoin de cette place.

LRU vs LFU — quand choisir lequel

TTL — l'expiration temporelle

Le TTL ajoute une dimension temps au cache — une entrée périme non pas parce qu'elle est déplacée, mais parce qu'elle est trop vieille.

Le TTL (Time To Live) répond à un besoin différent de LRU/LFU : une donnée peut être "fraîche" du point de vue des accès récents, mais périmée du point de vue métier. Le prix d'un produit mis en cache il y a 24 heures n'est plus fiable, même s'il a été accédé il y a 2 secondes.

Deux mécanismes d'expiration

Redis — l'algorithme d'expiration active

Redis ne peut pas se permettre de scanner toutes les clés (O(n)). Son algorithme actif est probabiliste :

// Toutes les 100ms, Redis fait :
repeat:
  sample = tirer 20 clés au hasard parmi les clés avec TTL
  supprimer toutes celles qui sont expirées
  if plus de 25% des clés sampléees étaient expirées:
      recommencer (il y en a probablement beaucoup d'autres)
  else:
      arrêter

Si le taux d'expiration est faible, l'algorithme s'arrête vite. Si beaucoup de clés expirent en même temps (par exemple, tout un batch mis en cache simultanément), Redis boucle jusqu'à nettoyer suffisamment.

TTL : défini à la création vs renouvelé à chaque accès

Stale-while-revalidate

La directive HTTP Cache-Control: max-age=60, stale-while-revalidate=30 est une application du TTL avec grâce : pendant 60 secondes, la réponse est fraîche. Entre 60 et 90 secondes, elle est périmée mais utilisable — le cache la sert immédiatement et relance la requête d'origine en arrière-plan. Après 90 secondes, elle est périmée et bloquante.

Write-through, write-behind, write-around

Écrire dans le cache est aussi complexe que lire — chaque stratégie fait un compromis différent entre latence, cohérence et durabilité.

Écrire dans le cache n'est pas symétrique à la lecture. Quand tu mets à jour une donnée, tu dois décider : est-ce que tu écris aussi en base immédiatement ? En différé ? Tu bypasses le cache ? Chaque réponse est une stratégie différente avec ses propres compromis.

Write-through — la sécurité

Write-behind (write-back) — la vitesse

… puis en arrière-plan : Cache → DB (flush asynchrone)

Write-around — les données éphémères

Refresh-ahead — l'anticipation

Le cache prédit les futures expirations et recharge proactivement les données avant qu'elles expirent. Au lieu d'attendre un miss, un agent surveille les TTL et déclenche une revalidation quand le TTL passe sous un seuil.

Compare les trois stratégies principales ci-dessous :

Redis — les 8 politiques d'éviction

Redis ne choisit pas ta politique d'éviction à ta place — tu la declares dans redis.conf et tu en assumes les conséquences.

Redis expose 8 politiques d'éviction, configurables via maxmemory-policy dans redis.conf ou CONFIG SET maxmemory-policy à chaud. Elles se croisent selon deux axes : le périmètre (toutes les clés, ou seulement celles avec un TTL) et le critère (LRU, LFU, random, TTL, rien).

Les 8 politiques

LRU approximatif de Redis

Redis n'implémente pas un LRU exact avec doubly linked list — ce serait trop coûteux en mémoire (2 pointeurs par clé). Il utilise un LRU probabiliste :

// Pour chaque éviction, Redis :
sample_size = maxmemory-samples  // défaut : 5
candidates = tirer sample_size clés au hasard dans le keyspace
evict = candidates.argmin(last_access_time)  // évince le moins récent du sample

Avec maxmemory-samples 10, l'approximation est très proche du LRU exact. Le coût : O(sample_size) par éviction au lieu de O(1) pour le LRU exact, mais sans overhead mémoire.

Configurer la limite mémoire

# redis.conf
maxmemory 2gb
maxmemory-policy allkeys-lru
maxmemory-samples 10  # augmenter pour une meilleure approximation LRU

# À chaud :
CONFIG SET maxmemory 2gb
CONFIG SET maxmemory-policy allkeys-lru

Cache stampede — le troupeau de requêtes

Quand une clé populaire expire, des centaines de requêtes foncent simultanément reconstruire le cache — c'est le stampede.

Imagine une clé très populaire — la page d'accueil de ton site, mise en cache avec un TTL de 5 minutes. Quand ce TTL expire, des centaines de requêtes arrivent simultanément. Chacune fait un miss, chacune pense qu'elle doit reconstruire le cache, toutes foncent sur la base de données en même temps. C'est le cache stampede.

Solution 1 — Mutex (verrou de reconstruction)

La première requête qui détecte le miss pose un verrou. Les autres requêtes attendent que le verrou soit libéré et lisent ensuite la valeur reconstruite depuis le cache.

function getWithMutex($key):
  value = cache.get($key)
  if value != null: return value    // hit

  // miss — essayer d'acquérir le verrou
  acquired = redis.set("lock:{$key}", 1, NX, EX 10)
  if acquired:
    value = db.fetch($key)           // seul à reconstruire
    cache.set($key, value, TTL)
    redis.del("lock:{$key}")
    return value
  else:
    sleep(50ms)                       // attendre que le verrou soit libéré
    return getWithMutex($key)        // retry

Solution 2 — Probabilistic Early Expiry (XFetch)

L'algorithme XFetch (Vattani, Chierichetti, Lowenstein, 2015) évite la saturation en déclenchant la revalidation avant l'expiration, de manière probabiliste :

// À chaque lecture :
now = time()
ttl_remaining = cache.ttl(key)
beta = 1.0  // paramètre d'agressivité (1.0 = standard)

// Probabilité de revalider AVANT l'expiration
if now - beta * delta * ln(rand()) > expiry:
  // "Je me comporte comme si c'était expiré"
  // delta = temps de reconstruction observé en secondes
  revalider(key)  // cette requête seule reconstruit
else:
  return cache.get(key)

Plus la reconstruction est longue (delta élevé), plus tôt la revalidation est déclenchée. Le résultat : une seule requête reconstruit, les autres continuent de servir la valeur périmée mais fonctionnelle, sans verrou.

Solution 3 — Stale-while-revalidate

Servir la valeur expirée pendant la reconstruction : le premier miss déclenche une revalidation asynchrone et sert l'ancienne valeur. La valeur "stale" est préférable à un timeout ou une erreur.

Cache warming et cold start

Un cache vide après un déploiement répercute tout le trafic sur la base de données — le cache warming évite ce gouffre.

Un cache vide après un déploiement, une mise à l'échelle, ou un flush d'urgence répercute l'intégralité du trafic sur la base de données. Le temps que le cache se remplisse organiquement (quelques minutes à quelques heures selon le TTL), la base agonise sous la charge. C'est le cold start.

Stratégies de warming

1. Warming depuis la base de données

Un script charge les données les plus populaires directement en cache avant que le serveur commence à servir des requêtes. Les données "top-N" peuvent être connues depuis les logs ou les statistiques d'accès.

// Warm les 1000 produits les plus consultés
$topProducts = $db->query(
    'SELECT * FROM products ORDER BY views DESC LIMIT 1000'
);
foreach ($topProducts as $product) {
    $redis->set("product:{$product['id']}", json_encode($product), 3600);
}

2. Warming depuis un snapshot

Avant le déploiement, exporter l'état du cache existant (RDB dump Redis) et le charger sur le nouveau serveur. Rapide, mais le snapshot peut être légèrement stale.

3. Shadow traffic / Replay

Dupliquer le trafic de production vers le nouveau serveur (en lecture seule, sans impacter les utilisateurs) pour laisser le cache se remplir organiquement avant le switch DNS.

4. Warming progressif (canary)

Router 1% du trafic vers le nouveau serveur pendant N minutes. Quand le hit rate monte à un niveau acceptable, augmenter progressivement le pourcentage.

Circuit breaker pendant le cold start

Même avec du warming, les premières secondes après un déploiement peuvent voir des pics de charge. Un circuit breaker protège la base :

if (db_error_rate > 50%):
    // Ouvrir le circuit — ne plus appeler la DB
    return serve_stale_or_default()
else if (db_error_rate > 20%):
    // Semi-open — laisser passer 10% des requêtes pour tester
    if (rand() > 0.9): return serve_stale()
    probe = db.fetch()
    if probe.ok: close_circuit()
    else: extend_open()

Cache distribué — consistent hashing et cohérence

Répartir un cache sur plusieurs nœuds introduit deux problèmes : où ranger chaque clé, et comment garder les copies cohérentes.

Quand un seul serveur Redis ne suffit plus (trop de données, besoin de HA, géographie), on distribue le cache sur plusieurs nœuds. Deux problèmes émergent : comment savoir sur quel nœud une clé est stockée, et comment garder les copies cohérentes.

Consistent Hashing

Le hachage simple (node = hash(key) % N) a un problème majeur : si N change (ajout ou retrait d'un nœud), presque toutes les clés changent de nœud — le cache entier est invalidé.

// Trouver le nœud pour une clé :
hash_value = hash(key)           // ex. 0x3A4F
nodes_sorted = [0x10, 0x40, 0x80, 0xF0]  // positions sur l'anneau
// Premier nœud >= hash_value :
node = nodes_sorted.find(n => n >= hash_value) ?? nodes_sorted[0]  // 0x40

Virtual nodes (vnodes)

Pour équilibrer la distribution, chaque nœud physique est représenté par N nœuds virtuels sur l'anneau (typiquement 150-200). Un serveur puissant peut avoir plus de vnodes.

Invalidation de cache — le problème le plus dur

"There are only two hard things in Computer Science: cache invalidation and naming things." — Phil Karlton

Dans un cache distribué, mettre à jour une clé sur un nœud ne met pas à jour les copies sur les autres. Trois stratégies d'invalidation :

Synthèse — le guide de choix

LRU, LFU ou TTL ? Write-through ou write-behind ? Mutex ou probabilistic expiry ? Voici comment choisir.

LRU, LFU, TTL, write-through, Redis — beaucoup d'outils pour un seul problème. Voici comment choisir selon la situation.

Quelle politique d'éviction ?

Quelle stratégie d'écriture ?

Comment protéger contre le stampede ?

Anti-patterns à éviter

Récapitulatif des métriques à surveiller