Un cache est le moyen le plus puissant d'accélérer un système — et la source la plus fréquente de bugs étranges. « Il n'y a que deux choses difficiles en informatique : l'invalidation de cache et nommer les choses. »
⏱️ Durée : environ 105 minutes · 🎓 Niveau : avancé · 🏅 Badge : Gardien de la mémoire rapide
🎬 L'histoire
HashBox met en cache la liste des cours pour soulager la base. Les temps de réponse passent de 120 ms à 4 ms. Mais le lendemain, une formatrice modifie un cours, et ses étudiants continuent de voir l'ancienne version pendant une heure. Une autre fois, à midi, le cache expire en même temps pour tout le monde : 2 000 requêtes identiques se ruent sur la base, qui s'effondre.
« Un cache, c'est une copie, dit Sam. Une copie peut devenir fausse. Il y a donc trois questions à se poser : que garde-t-on, jusqu'à quand, et comment sait-on que c'est périmé ? Et une quatrième : que se passe-t-il quand le cache est vide et que tout le monde arrive en même temps ? »
Tu apprends à implémenter des politiques d'éviction (LRU, LFU), à mesurer un taux de succès, à choisir une durée de vie et une stratégie d'invalidation, et à te protéger de la ruée (cache stampede).
🎯 Ta mission
À la fin, je serai capable de :
- calculer le temps d'accès moyen à partir du taux de succès (hit ratio)
- implémenter et comparer des politiques d'éviction (FIFO, LRU, LFU) sur une charge réaliste
- choisir entre durée de vie, invalidation explicite et clés versionnées
- empêcher la ruée sur la source avec un verrou par clé (single-flight)
- distinguer cache-aside, écriture immédiate (write-through) et différée (write-back)
🧩 Défi d'échauffement (5 XP)
Tu gardes dans ta poche les numéros de téléphone que tu composes souvent, plutôt que de chercher dans l'annuaire. Que se passe-t-il quand un ami change de numéro ? Que fais-tu quand ta poche est pleine et que tu veux ajouter un numéro ? Comment sais-tu quels numéros garder ?
💡 Le concept
Pourquoi un cache
Un cache garde une copie de données coûteuses à obtenir, dans un endroit plus rapide. Il est partout : registres et caches du processeur, cache de pages du système, navigateur, CDN, cache applicatif (Redis, Memcached), cache de requêtes de la base.
temps d'accès moyen = h × t_cache + (1 − h) × t_source (h = taux de succès)
Avec t_cache = 1 ms, t_source = 100 ms : à h = 50 %, 50,5 ms ; à 90 %, 10,9 ms ; à 99 %, 2 ms. Chaque point de taux de succès compte énormément quand la source est très lente.
Patrons d'utilisation
| Patron | Lecture | Écriture |
|---|---|---|
| Cache-aside (le plus courant) | l'application regarde le cache ; sinon va à la source et remplit le cache | l'application écrit la source, puis invalide (ou met à jour) le cache |
| Read-through | le cache lui-même charge depuis la source | idem |
| Write-through | — | écriture dans le cache et la source ensemble |
| Write-back | — | écriture dans le cache, source mise à jour plus tard (rapide, risque de perte) |
Éviction : que retirer quand c'est plein ?
| Politique | Retire | Bon pour |
|---|---|---|
| FIFO | le plus ancien arrivé | simple, souvent médiocre |
| LRU (Least Recently Used) | le moins récemment utilisé | localité temporelle : usage général |
| LFU (Least Frequently Used) | le moins fréquemment utilisé | popularité stable |
| TTL | ce qui a expiré | données qui vieillissent |
| Aléatoire | un au hasard | surprenamment correct, peu de coût |
Les accès réels suivent souvent une loi de type Zipf : quelques éléments très populaires, une longue traîne rare. Un petit cache (5 % des données) peut alors couvrir 70 à 90 % des accès.
Invalider : le vrai problème
| Stratégie | Principe | Risque |
|---|---|---|
| Durée de vie (TTL) | l'entrée expire après N secondes | données périmées jusqu'à N s |
| Invalidation explicite | on supprime l'entrée à chaque écriture | oublier un chemin d'écriture |
| Clés versionnées | la clé contient un numéro de version : cours:42:v7 ; changer la version rend l'ancienne entrée inatteignable | accumulation d'anciennes entrées (éviction) |
| Invalidation par étiquettes | à chaque entrée, des étiquettes (cours:42, categorie:algo) ; on invalide par étiquette | complexité |
| Événements | la source publie « changé » et les caches se mettent à jour | délai, perte de messages |
Combiner TTL + invalidation : le TTL est le filet de sécurité qui borne l'erreur si une invalidation est manquée.
Clés de cache
La clé doit contenir tout ce qui change le résultat : identifiant, langue, droits de l'utilisateur, version de l'API. Une clé trop petite mélange des résultats (fuite entre utilisateurs !) ; trop grande, elle ne réutilise rien.
La ruée (cache stampede)
Quand une entrée populaire expire, toutes les requêtes concurrentes la trouvent absente et vont toutes à la source. Remèdes :
- Un seul chargeur par clé (single-flight, verrou) : les autres attendent son résultat ;
- Expiration avec gigue : TTL = 300 s ± 10 % pour éviter l'expiration simultanée ;
- Rafraîchissement anticipé ou servir l'ancien pendant le rechargement (stale-while-revalidate) ;
- Mise en cache des absences (cache négatif) pour éviter de marteler la source avec des clés inexistantes.
Cohérence
Un cache fait renoncer à la cohérence parfaite : il y a une fenêtre où une lecture peut voir l'ancienne valeur. À décider consciemment : pour un solde bancaire, non ; pour la liste des cours, quelques secondes d'ancienneté sont acceptables.
Mesurer
Taux de succès, taux d'éviction, taille, latence avec et sans cache, âge des données servies. Un cache dont le taux de succès est de 5 % ne sert à rien et ajoute de la complexité.
🧠 Astuce : demande-toi, avant d'ajouter un cache : quelle est l'erreur acceptable (ancienneté) ? qui invalide ? que se passe-t-il à froid ? Si tu ne peux pas répondre, tu n'es pas prêt à le mettre en production.
🔍 Exemple pas à pas
Problème : implémenter FIFO, LRU et LFU, les comparer sur une charge Zipf, voir l'effet de la taille sur le taux de succès, la durée de vie (TTL) avec horloge simulée, et empêcher la ruée avec un verrou par clé.
import collections, random, threading, time
# ---------------- politiques d'éviction ----------------
class Cache:
def __init__(self, taille): self.taille, self.succes, self.echecs = taille, 0, 0
def acces(self, cle):
if self._present(cle):
self.succes += 1; self._toucher(cle); return True
self.echecs += 1; self._inserer(cle); return False
@property
def taux(self): return self.succes / (self.succes + self.echecs)
class FIFO(Cache):
def __init__(self, t): super().__init__(t); self.d = collections.OrderedDict()
def _present(self, c): return c .d
():
():
.d[c] =
(.d) > .taille: .d.popitem(last=)
():
(): ().__init__(t); .d = collections.OrderedDict()
(): c .d
(): .d.move_to_end(c)
():
.d[c] =
(.d) > .taille: .d.popitem(last=)
():
(): ().__init__(t); .d, .freq = {}, collections.Counter()
(): c .d
(): .freq[c] +=
():
(.d) >= .taille:
moins = (.d, key= k: .freq[k]); .d[moins]; .freq[moins]
.d[c] = ; .freq[c] =
():
rng = random.Random(graine)
poids = [ / (i + ) ** s i (n_cles)]
rng.choices((n_cles), weights=poids, k=n_acces)
ACCES = charge_zipf()
()
resultats = {}
taille (, , , ):
ligne = {}
nom, classe ((, FIFO), (, LRU), (, LFU)):
c = classe(taille)
k ACCES: c.acces(k)
ligne[nom] = c.taux
resultats[taille] = ligne
()
resultats[][] > resultats[][] resultats[][] >= resultats[][] -
resultats[][] >
(): h * t_cache + ( - h) * t_source
(, [(temps_moyen(h), ) h (, , )])
[(temps_moyen(h), ) h (, , )] == [, , ]
:
(): .ttl, .horloge, .d = ttl, horloge, {}
():
entree = .d.get(cle)
entree .horloge() < entree[]:
entree[],
valeur = charger(cle); .d[cle] = (valeur, .horloge() + .ttl)
valeur,
t = {: }; source = {: }
cache = CacheTTL(, : t[])
cache.lire(, source.get) == (, )
source[] =
t[] = ; cache.lire(, source.get) == (, )
t[] = ; cache.lire(, source.get) == (, )
():
appels, cache, verrous, g = [], {}, collections.defaultdict(threading.Lock), threading.Lock()
barriere = threading.Barrier(threads)
():
appels[] += ; time.sleep();
():
cle cache: cache[cle]
avec_verrou:
cache[cle] = charger(); cache[cle]
g: verrou = verrous[cle]
verrou:
cle cache: cache[cle] = charger()
cache[cle]
(): barriere.wait(); lire()
ts = [threading.Thread(target=tache) _ (threads)]
x ts: x.start()
x ts: x.join()
appels[]
sans, avec = ruee(), ruee()
()
avec == sans >=
Lecture :
- Sur une charge Zipf, un cache de seulement 2 % des données (200 clés sur 10 000) sert plus de la moitié des accès avec LRU ; LRU et LFU battent nettement FIFO. Plus on agrandit le cache, plus le gain diminue (rendements décroissants).
- Le temps moyen montre pourquoi chaque point de taux de succès compte : 50 ms à 50 %, 11 ms à 90 %, 2 ms à 99 %.
- Le TTL borne l'erreur : après un changement à la source, le cache peut servir l'ancienne valeur pendant au plus 60 secondes.
- Sans protection, la ruée envoie plusieurs appels simultanés à la source ; avec un verrou par clé, un seul chargeur travaille et les autres attendent son résultat.
✍️ À toi, avec aide (10 XP)
Un service a un temps de lecture à la source de 80 ms et un cache à 2 ms. Le trafic est de 500 requêtes/s.
- Calcule le temps moyen et la charge sur la source pour un taux de succès de 70 %, 90 % et 98 %.
- La source supporte au maximum 100 requêtes/s. Quel taux de succès minimal faut-il pour que la source tienne ?
- Après un redéploiement, le cache est vide et le taux de succès tombe à 0 % pendant quelques minutes. Que se passe-t-il, et quelle parade proposes-tu (au moins deux) ?
💡 Indice 1
Charge sur la source = trafic × (1 − h).
💡 Indice 2
Pour que la source tienne : 500 × (1 − h) ≤ 100.
💡 Indice 3
À froid, la source reçoit 500 requêtes/s alors qu'elle n'en supporte que 100.
✅ Réponse
for h in (0.70, 0.90, 0.98):
print(f"h = {h:.0%} : temps moyen {h * 2 + (1 - h) * 80:5.1f} ms | charge sur la source {500 * (1 - h):5.0f} req/s")
h_min = 1 - 100 / 500
print(f"taux de succès minimal : {h_min:.0%}")
assert round(h_min, 2) == 0.80
- 70 % : 25,4 ms, 150 req/s (la source est déjà dépassée) ; 90 % : 9,8 ms, 50 req/s ; 98 % : 3,6 ms, 10 req/s.
- Il faut au moins 80 % de succès pour que la source tienne ses 100 req/s.
- Au démarrage à froid, la source reçoit 500 req/s pour 100 supportables : files d'attente, timeouts, effondrement. Parades : préchauffer le cache avant de basculer le trafic ; monter en charge progressivement (canary, HEF-120) ; verrou par clé (single-flight) pour réduire les doublons ; limiter le débit vers la source avec dégradation (réponses de repli) ; (Redis) qui survit au redéploiement.
🚀 À toi, en solo (20 XP)
Cache à invalidation par étiquettes, avec lecture cohérente. Implémente CacheEtiquetes :
lire(cle, chargeur, etiquettes, ttl): cache-aside ; chaque entrée porte des étiquettes (cours:42,formateur:7) ;invalider(etiquette)supprime toutes les entrées associées ;- TTL avec gigue (±10 %) calculée par un générateur à graine fixée ;
- verrou par clé contre la ruée ;
- cache négatif : une clé absente de la source est mémorisée brièvement ;
- métriques : succès, échecs, invalidations, âge moyen des données servies ;
- test de cohérence : une écriture suivie d'une invalidation ne permet plus de lire l'ancienne valeur (sur un scénario de 1000 opérations aléatoires avec graine fixée, comparer avec un modèle sans cache) — il ne doit y avoir aucune lecture périmée, si les écritures invalident toujours.
✅ Pistes de correction
import collections, random, threading
class CacheEtiquettes:
def __init__(self, horloge, graine=1):
self.h, self.rng = horloge, random.Random(graine)
self.d, self.index, self.verrou = {}, collections.defaultdict(set), threading.RLock()
self.succes = self.echecs = self.invalidations = 0
self.ages = []
def lire(self, cle, chargeur, etiquettes=(), ttl=60.0, ttl_absent=5.0):
with self.verrou: # verrou global simple : un seul chargeur à la fois
e = self.d.get(cle)
if e and self.h() < e["expire"]:
self.succes += 1; self.ages.append(self.h() - e["cree"]); return e["valeur"]
self.echecs +=
valeur = chargeur(cle)
duree = (ttl valeur ttl_absent) * ( + .rng.uniform(-, ))
.d[cle] = {: valeur, : .h(), : .h() + duree, : (etiquettes)}
t etiquettes: .index[t].add(cle)
valeur
():
.verrou:
cle .index.pop(etiquette, ()):
.d.pop(cle, ) : .invalidations +=
t = {: }
source = {: i ()}
cache = CacheEtiquettes(: t[])
chargements = []
(): chargements.append(cle); source.get(cle)
rng = random.Random(); lectures_perimees =
op ():
t[] += rng.uniform(, )
i = rng.randrange()
cle =
rng.random() < cle source:
source[cle] =
cache.invalider(cle)
:
lu = cache.lire(cle, charger, etiquettes=(cle, ), ttl=)
lu != source.get(cle):
lectures_perimees +=
()
lectures_perimees ==
cache.succes > cache.echecs (chargements) == cache.echecs
cache.lire(, charger, (, )); cache.invalider()
n_avant = (chargements); cache.lire(, charger, (, ))
(chargements) == n_avant +
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Aucune stratégie d'invalidation | Données périmées sans limite | TTL + invalidation explicite |
| Clé de cache incomplète | Mélange de résultats entre utilisateurs ou langues | Inclure tout ce qui change le résultat |
| Expiration simultanée | Ruée vers la source | Gigue, single-flight, rafraîchissement anticipé |
| Cache dont le taux de succès est faible | Complexité sans gain | Mesurer ; supprimer s'il ne sert pas |
🐉 Mini-boss (40 XP)
Couche de cache pour le catalogue de HashBox. Conçois et teste une couche de cache pour le catalogue (cours, formateurs, prix) avec : 200 000 lectures/jour pour 5 000 cours (loi de Zipf), 50 modifications/jour, une source à 90 ms.
- choisis la politique d'éviction et la taille par simulation (taux de succès contre taille) ;
- conçois les clés (langue, devise, droits) et les étiquettes d'invalidation ;
- implémente TTL avec gigue, invalidation par étiquettes, single-flight, cache négatif ;
- simule une journée avec horloge virtuelle : taux de succès, charge sur la source, âge maximal servi ;
- simule un redéploiement à froid : mesure le pic sur la source avec et sans préchauffage ;
- écris les tests de cohérence contre un modèle sans cache ;
- définis les alertes (taux de succès, âge, taux d'éviction) et le budget d'ancienneté accepté.
✅ Pistes de correction
Un bon travail : simulation Zipf pour choisir LRU et une taille couvrant ~90 % des accès avec ~10 % des cours; invalidation par étiquettes à chaque écriture (cours:ID, formateur:ID, catalogue), TTL de 10 minutes ± 10 %, verrou par clé; tableau de la charge source avec et sans préchauffage (le préchauffage supprime le pic de démarrage); test aléatoire contre un modèle de référence prouvant l'absence de lecture périmée; alertes sur taux de succès < 80 %, âge servi > TTL, évictions anormales.
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Le temps d'accès moyen d'un cache dépend de :
- A. uniquement de sa taille
- B. de la couleur des données
- C. son taux de succès et des temps du cache et de la source
2. Une politique LRU retire :
- A. l'entrée la moins récemment utilisée
- B. l'entrée la plus grande
- C. une entrée au hasard uniquement
3. La ruée sur le cache (cache stampede) se prévient par :
- A. l'augmentation du nombre de requêtes
- B. un verrou par clé (un seul chargeur) et une expiration avec gigue
- C. la suppression du cache
4. 🔁 Révision mission 07 : Un SCAN dans un plan d'exécution signifie :
- A. une recherche par index
- B. une erreur de syntaxe
- C. un parcours complet de la table
5. 🔁 Révision mission 07 : Le problème N+1 correspond à :
- A. une requête pour la liste puis une requête par élément
- B. une table avec N+1 colonnes
- C. un index en trop
✅ Réponses
- C.
- A.
- B.
- C.
- A.
🪞 Je réfléchis (10 XP)
- Quelle donnée mise en cache dans ton système pourrait être périmée, et quelle ancienneté serait acceptable ?
- Que se passerait-il demain si ton cache était vidé d'un coup pendant l'heure de pointe ?
🎒 À retenir
- Temps moyen = h × t_cache + (1 − h) × t_source.
- LRU/LFU contre FIFO ; la charge réelle est de type Zipf.
- TTL + invalidation explicite (étiquettes, versions).
- Single-flight, gigue et préchauffage contre la ruée.
- Une clé contient tout ce qui change le résultat.
flowchart LR
T(["Cache et invalidation"])
T --> R1["1. Temps moyen = h × tcache + 1 − h × tsource."]
T --> R2["2. LRU/LFU contre FIFO ; la charge réelle est de type Zipf."]
T --> R3["3. TTL + invalidation explicite étiquettes, versions."]
T --> R4["4. Single-flight, gigue et préchauffage contre la ruée."]
T --> R5["5. Une clé contient tout ce qui change le résultat."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Gardien de la mémoire rapide
← Mission 07 — Bases de données et performance · Mission 09 — Concurrence et charge →
HEF-130 — Performance

