Formations — 1 037 leçons en français

Accueil › Node.js › Un cache à durée de vie et taille bornée

Un cache à durée de vie et taille bornée

Exercice de la série « Performance et montée en charge »intermediaire

Le besoin. Vous ajoutez un cache en mémoire devant une requête coûteuse. Deux réglages sont obligatoires : une durée de vie, pour borner l'incohérence, et une taille maximale, pour que le cache ne devienne pas une fuite de mémoire. La taille maximale impose une politique d'éviction.

Ce qu'on vous demande. Écrivez simuler(operations, config) où operations est une liste de lectures { t, cle } données dans l'ordre chronologique, et config vaut { ttlMs, taille }. Renvoyez { coups, echecs, evictions, politique, cles }.

Les règles, dans cet ordre, pour chaque lecture au temps t :

  1. si la clé est présente et que t - dateEcriture < ttlMs, c'est un coup au but ; la clé devient la plus récemment utilisée ;
  2. sinon c'est un échec : la valeur est recalculée, écrite avec dateEcriture = t, et la clé devient la plus récemment utilisée ;
  3. si l'écriture a fait passer le nombre de clés au-dessus de taille, la clé la moins récemment utilisée est retirée et evictions augmente de un.

Réécrire une clé périmée n'est pas une éviction. politique vaut toujours "lru". cles liste les clés encore présentes à la fin, de la moins récemment utilisée à la plus récemment utilisée.

Appel Résultat attendu
simuler([{t:0,cle:"a"},{t:1,cle:"a"}], {ttlMs:1000,taille:2}) { coups: 1, echecs: 1, evictions: 0, politique: "lru", cles: ["a"] }
simuler([{t:0,cle:"a"},{t:1000,cle:"a"}], {ttlMs:1000,taille:2}) { coups: 0, echecs: 2, evictions: 0, politique: "lru", cles: ["a"] }

Le piège. Un coup au but doit rafraîchir la récence. Si on se contente de lire la valeur sans réordonner la clé, l'ordre d'insertion de la Map fait de l'éviction une politique « premier entré, premier sorti » — et la clé la plus demandée du service, étant aussi la plus ancienne, est évincée en premier. Le taux de coups au but s'effondre sans qu'aucune erreur n'apparaisse.

Cas de test

Écrire le code et le faire exécuter →

Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.

La leçon qui prépare cet exercice

Les autres exercices de « Performance et montée en charge »