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 :
- 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 ; - sinon c'est un échec : la valeur est recalculée, écrite avec
dateEcriture = t, et la clé devient la plus récemment utilisée ; - 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 etevictionsaugmente 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
[[{"t":0,"cle":"a"},{"t":1,"cle":"b"},{"t":2,"cle":"a"},{"t":3,"cle":"c"},{"t":4,"cle":"a"}],{"ttlMs":1000,"taille":2}][[{"t":0,"cle":"a"},{"t":999,"cle":"a"},{"t":1000,"cle":"a"},{"t":1500,"cle":"a"}],{"ttlMs":1000,"taille":5}][[{"t":0,"cle":"a"},{"t":10,"cle":"b"},{"t":20,"cle":"c"},{"t":30,"cle":"a"},{"t":40,"cle":"d"},{"t":50,"cle":"b"},{"t":60,"cle":"a"},{"t":600,"cle":"a"}],{"ttlMs":500,"taille":3}][[{"t":0,"cle":"a"},{"t":1,"cle":"b"},{"t":2,"cle":"a"},{"t":3,"cle":"b"}],{"ttlMs":10000,"taille":1}]
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.