Version JavaScript du modèle de mise en cache TwoQueues_Connaissances de base

Le modèle de mise en cache TwoQueues mentionné dans cet article fait référence au modèle de mise en cache des données en mémoire.

Quelle que soit la langue, vous devrez peut-être mettre certaines données en mémoire pour éviter des opérations et des lectures répétées. Le scénario le plus courant est le sélecteur JQuery. La sélection de certains éléments Dom prend beaucoup de temps. Nous espérons mettre en cache ces données sans avoir à parcourir à nouveau l'arborescence Dom à chaque appel.

Enregistrez-le simplement, mais il doit y avoir un montant ! Il est impossible de mettre toutes les données historiques en mémoire. Après tout, la capacité mémoire actuelle est encore assez pitoyable. Même si la mémoire est suffisamment grande, la mémoire allouée à chaque thread est théoriquement limitée.

La question est donc : comment pouvons-nous mettre en cache efficacement des données vraiment utiles ? Cela implique des algorithmes d’élimination, qui doivent éliminer les données indésirables afin de conserver les données utiles.

Les idées les plus couramment utilisées sont les suivantes :

FIFO : Il s'agit d'une file d'attente premier entré, premier sorti. Les premières données mises en cache sont les premières à être éliminées. Ce modèle est utilisé dans le célèbre framework JQuery.

LRU : Structure de liste chaînée double. Chaque fois que de nouvelles données sont stockées, elles sont placées directement en tête de la liste chaînée ; à chaque accès aux données, elles sont également transférées en tête de la liste chaînée ; . De cette façon, les données à la fin de la liste chaînée sont les plus récentes. Celles qui n'ont pas été utilisées seront éliminées.

TwoQueues : FIFO LRU, FIFO stocke principalement les données stockées pour la première fois et LRU stocke les données de hotspot qui ont été utilisées au moins deux fois. Cet algorithme a un taux de réussite élevé, une forte adaptabilité et une faible complexité.

Il existe de nombreux autres algorithmes d'élimination, mais ces deux-là sont les plus couramment utilisés. Parce que leurs algorithmes ne sont pas complexes, faciles à mettre en œuvre, ont une efficacité d'exécution élevée et le taux de réussite du cache est acceptable dans la plupart des situations. Après tout, l’algorithme de mise en cache consomme également du CPU s’il est trop compliqué, même si le taux de réussite sera amélioré, le gain ne vaudra pas la perte. Imaginez, si la récupération des données du cache prend plus de temps que leur récupération à partir de l'emplacement d'origine, à quoi sert la mise en cache ?

Je n'entrerai pas dans les détails de la théorie spécifique. Il y en a beaucoup sur Internet, mais je ne les comprends pas vraiment. Ce que je veux partager avec vous aujourd'hui, c'est la version JavaScript du modèle de mise en cache TwoQueues.

Parlons d’abord de la façon de l’utiliser, c’est très simple.

L'utilisation de base est la suivante :

[/code]
var tq = initTwoQueues(10);
tq.set("clé", "valeur");
tq.get("clé");
[/code]

Lors de l'initialisation, précisez simplement la capacité du cache. Il convient de noter qu'en raison de l'implémentation interne du FIFO LRU, la capacité réelle est le double de la capacité spécifiée. L'exemple ci-dessus spécifie 10 (paires clé-valeur), mais 20 peuvent en fait être stockées.

La taille de la capacité doit être déterminée en fonction du scénario d'application réel. Si elle est trop petite, le taux de réussite sera faible, si elle est trop grande, l'efficacité sera faible.

Pendant le processus de développement, afin de revoir l'effet cache, vous pouvez initialiser le pool de cache à la version de développement :

Copier le code Le code est le suivant :

var tq = initTwoQueues(10, true);
tq.hitRatio();

Ajoutez simplement un paramètre à la fin, rendez-le vrai. Le pool de cache initialisé de cette manière comptera automatiquement le taux de réussite, et le taux de réussite peut être obtenu via la méthode hitRatio. Si ce paramètre n'est pas ajouté, le taux de réussite obtenu par la méthode hitRatio sera toujours 0.
Le taux de réussite statistique consommera certainement des ressources, il n'est donc pas recommandé de l'activer dans un environnement de production.
Il est temps de partager le code :

Copier le code Le code est le suivant :

 (fonction(exports){
     /**
* Classe pure pour l'héritage
* @constructeur
​​*/
     fonction Fn(){}
     Fn.prototype = Élimination.prototype;
     /**
* * Classe parent de l'algorithme d'élimination du cache basé sur une liste chaînée
* @param maxLength capacité du cache
* @constructeur
​​*/
     fonction Élimination(maxLength){
         this.container = {};
         this.length = 0;
         this.maxLength = maxLength || 30;
         this.linkHead = this.buildNode("", "");
         this.linkHead.head = true;
         this.linkTail = this.buildNode("", "");
         this.linkTail.tail = true;
         this.linkHead.next = this.linkTail;
         this.linkTail.prev = this.linkHead;
     >
     Elimination.prototype.get = fonction(clé){
         throw new Error("Cette méthode doit être remplacée !");
     };
     Elimination.prototype.set = function(clé, valeur){
         throw new Error("Cette méthode doit être remplacée !");
     };
     /**
*Créer des nœuds dans la liste chaînée
* @param data Les données contenues dans le nœud, c'est-à-dire la valeur des données mises en cache
* @param key L'identifiant unique du nœud, c'est-à-dire la clé mise en cache
* @returns {{}}
​​*/
     Elimination.prototype.buildNode = function(données, clé){
         var nœud = {};
         node.data = data;
         node.key = clé;
         node.use = 0;
         noeud de retour ;
     };
     /**
* Pop un nœud de la tête de la liste chaînée
* @returns {*}
​​*/
     Elimination.prototype.shift = function(){
         var noeud = null;
         if(!this.linkHead.next.tail){
             node = this.linkHead.next;
             this.linkHead.next = node.next;
             node.next.prev = this.linkHead;
             supprimer this.container[node.key];
             cette.longueur--;
         >
         noeud de retour ;
     };
     /**
* Insérez un nœud depuis la tête de la liste chaînée
* @param node objet nœud
* @returns {*}
​​*/
     Elimination.prototype.unshift = fonction (nœud){
         node.next = this.linkHead.next;
         this.linkHead.next.prev = node;
         this.linkHead.next = node;
         node.prev = this.linkHead;
         this.container[node.key] = node;
         cette.longueur ;
         noeud de retour ;
     };
     /**
      * 从链表尾插入一个节点
      * @param node 节点对象
      * @returns {*}
      */
     Elimination.prototype.append = fonction (nœud) {
         this.linkTail.prev.next = node;
         node.prev = this.linkTail.prev;
         node.next = this.linkTail;
         this.linkTail.prev = node;
         this.container[node.key] = node;
         cette.longueur ;
         noeud de retour ;
     };
     /**
* Pop un nœud à la fin de la liste chaînée
* @returns {*}
​​*/
     Elimination.prototype.pop = fonction(){
         var noeud = null;
         if(!this.linkTail.prev.head){
             node = this.linkTail.prev;
             node.prev.next = this.linkTail;
             this.linkTail.prev = node.prev;
             supprimer this.container[node.key];
             cette.longueur--;
         >
         noeud de retour ;
     };
     /**
*Supprimer le nœud spécifié de la liste chaînée
* @param node objet nœud
* @returns {*}
​​*/
     Elimination.prototype.remove = function(nœud){
         node.prev.next = node.next;
         node.next.prev = node.prev;
         supprimer this.container[node.key];
         cette.longueur--;
         noeud de retour ;
     };
     /**
* Le traitement qui doit être effectué lors de l'accès au nœud, notamment en déplaçant le nœud vers la tête de la liste chaînée
* @param node
​​*/
     Elimination.prototype.use = function(nœud){
         this.remove(noeud);
         this.unshift(noeud);
     };
 
     /**
* Implémentation de l'algorithme d'élimination du cache LRU
* @constructeur
​​*/
     fonction LRU(){
         Elimination.apply(ce, arguments);
     >
     LRU.prototype = nouveau Fn();
     LRU.prototype.get = fonction(clé){
         var node = non défini ;
         node = this.container[clé];
         if(nœud){
             this.use(noeud);
         >
         noeud de retour ;
     };
     LRU.prototype.set = fonction (clé, valeur){
         var node = this.buildNode(value, key);
         if(this.length === this.maxLength){
             this.pop();
         >
         this.unshift(noeud);
     };
 
     /**
* Implémentation de l'algorithme d'élimination du cache FIFO
* @constructeur
​​*/
     fonction FIFO(){
         Elimination.apply(ce, arguments);
     >
     FIFO.prototype = nouveau Fn();
     FIFO.prototype.get = fonction(clé){
         var node = non défini ;
         node = this.container[clé];
         noeud de retour ;
     };
     FIFO.prototype.set = fonction (clé, valeur){
         var node = this.buildNode(value, key);
         if(this.length === this.maxLength){
             this.shift();
         >
         this.append(noeud);
     };
 
     /**
* Encapsulation des algorithmes LRU et FIFO, devenant ainsi le nouvel algorithme d'élimination du cache à deux files d'attente
* @param maxLength
* @constructeur
​​*/
     fonction Agent(maxLength){
         this.getCount = 0;
         this.hitCount = 0;
         this.lir = new FIFO(maxLength);
         this.hir = nouveau LRU(maxLength);
     >
     Agent.prototype.get = fonction(clé){
         var node = non défini ;
         node = this.lir.get(key);
         if(nœud){
             node.use ;
             if(node.use >= 2){
                 this.lir.remove(node);
                 this.hir.set(node.key, node.data);
             >
         }autre{
             node = this.hir.get(key);
         >
         noeud de retour ;
     };
     Agent.prototype.getx = fonction (clé){
         var node = non défini ;
         this.getCount ;
         node = this.get(clé);
         if(nœud){
             this.hitCount ;
         >
         noeud de retour ;
     };
     Agent.prototype.set = fonction (clé, valeur){
         var noeud = null;
         node = this.lir.container[clé] || this.hir.container[clé];
         if(nœud){
             node.data = valeur;
         }autre{
             this.lir.set(clé, valeur);
         >
     };
     /**
* Obtenez un taux de réussite
* @returns {*}
​​*/
     Agent.prototype.hitRatio = fonction(){
         var ret = this.getCount;
         si(ret){
             ret = this.hitCount / this.getCount;
         >
         retour ret;
     };
     /**
      * 对外接口
* @param maxLength capacité du cache
* @param dev Qu'il s'agisse d'un environnement de développement, l'environnement de développement comptera le taux de réussite, sinon il ne le fera pas
* @returns {{get, set : Fonction, hitRatio : Fonction}}
*/
exports.initTwoQueues = function(maxLength, dev){
        var api = new Agent(maxLength);
          revenir {
                obtenir : (fonction(){
Si(dév){
Fonction de retour (clé){
                          var ret = api.getx(key);
                                           return ret && ret.data;
                      };
                     }autre{
Fonction de retour (clé){
                        var ret = api.get(key);
                                           return ret && ret.data;
                      };
                 }
              }()),
              set : function(){
api.set.apply(api, arguments);
             },
hitRatio : fonction(){
                          return api.hitRatio.apply(api, arguments);
            }
          };
};

}(ceci));

Enfin, je voudrais vous rappeler encore une fois que l'algorithme de mise en cache doit être combiné avec le scénario d'application réel. Il n'existe pas d'algorithme universel, et celui qui convient est le meilleur !