Le modèle de cache TwoQueues mentionné dans cet article fait référence au modèle de cache des données en mémoire.
Quelle que soit la langue, vous devrez peut-être mettre des données en mémoire pour éviter les opérations et la lecture 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 ces données en cache sans avoir à rediffuser l'arbre Dom à chaque fois que nous appelons.
Enregistrez-le, mais il doit y avoir une quantité! Vous ne pouvez pas mettre toutes les données historiques en mémoire. Après tout, la capacité de mémoire actuelle est encore assez pitoyable. Même si la mémoire est suffisamment grande, la mémoire allouée par chaque thread en théorie est toujours limitée.
La question est donc de savoir comment pouvons-nous cacher efficacement les données vraiment utiles? Cela implique des algorithmes d'élimination et les données indésirables doivent être éliminées afin de préserver les données utiles.
Il y a plusieurs idées courantes:
FIFO: Il s'agit d'une file d'attente de premier ordre, les premières données mises en cache, et a été éliminée en premier. Ce modèle est utilisé dans le célèbre cadre JQuery.
LRU: Structure de liste à double liaison, chaque fois que de nouvelles données sont stockées, elles sont placées directement dans l'en-tête de la liste liée; Les données accessibles à chaque fois sont également transférées à l'en-tête de la liste liée. De cette façon, les données à la fin de la liste liée sont quelque chose qui n'a pas été utilisée récemment et sera éliminée.
Twoqueues: FIFO + LRU. FIFO stocke principalement les données stockées pour la première fois, et le LRU stocke les données de points chauds qui ont été utilisés 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 il n'y a que deux types d'entre eux qui sont plus utilisés dans la pratique. Parce que leurs algorithmes ne sont pas complexes, faciles à mettre en œuvre, une efficacité d'exécution élevée et le taux de succès du cache est acceptable dans la plupart des occasions. Après tout, l'algorithme de cache nécessite également une consommation de processeur. S'il est trop complexe, bien que le taux de réussite ait été amélioré, cela ne vaut pas la perte. Imaginez simplement, si vous récupérez les données du cache, cela prend plus de temps que de récupérer à partir de l'emplacement d'origine. À quoi sert le cache?
Je ne parlerai pas des théories spécifiques. Il y en a en ligne, mais je ne les comprends pas beaucoup. Aujourd'hui, je vais partager avec vous la version JavaScript du modèle de cache TwoQueues.
Parlons de la façon de l'utiliser en premier, c'est très simple.
La méthode d'utilisation de base est la suivante:
[/code]
var tq = inittwoqueues (10);
tq.set ("key", "valeur");
tq.get ("key");
[/code]
Lors de l'initialisation, spécifiez simplement la capacité de cache. Il convient de noter que puisque FIFO + LRU est implémenté en interne, la capacité réelle est le double de la capacité spécifiée. L'exemple ci-dessus spécifie 10 (paires de valeurs clés), qui peuvent en fait stocker 20.
La taille de la capacité doit être déterminée en fonction du scénario d'application réel. S'il est trop petit, le taux de succès est faible, l'efficacité est faible et l'extrême est l'opposé, et vous devez le mesurer vous-même.
Pendant le processus de développement, afin de revoir l'effet de cache, le pool de cache peut être initialisé dans la version de développement:
La copie de code est la suivante:
var tq = inittwoqueues (10, true);
tq.hitratio ();
Ajoutez simplement un paramètre à la fin et tout simplement vrai. Le pool de cache initialisé de cette manière comptera automatiquement le taux de réussite, et le taux de succès peut être obtenu via la méthode Hitratio. Si ce paramètre n'est pas ajouté, le taux de hit obtenu par la méthode HitRatio est toujours 0.
Le taux de réussite statistique consommera certainement des ressources, il n'est donc pas recommandé de s'activer dans les environnements de production.
Il est temps de partager le code:
La copie de code est la suivante:
(fonction (exportations) {
/ **
* Classe pure pour l'héritage
* @constructor
* /
fonction fn () {}
Fn.prototype = élimination.prototype;
/ **
* Classe parent d'algorithme d'élimination du cache basé sur la liste liée
* Capacité de cache @param maxlength
* @constructor
* /
Élimination de la fonction (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 (key) {
lancer une nouvelle erreur ("Cette méthode doit être remplacée!");
};
Elimination.prototype.set = fonction (clé, valeur) {
lancer une nouvelle erreur ("Cette méthode doit être remplacée!");
};
/ **
* Créer des nœuds dans la liste liée
* @param data les données contenues dans le nœud, c'est-à-dire la valeur de données mise en cache
* @param clé l'identifiant unique du nœud, c'est-à-dire la clé mise en cache
* @returns {{}}
* /
Elimination.prototype.buildNode = fonction (data, key) {
var node = {};
Node.data = données;
node.key = key;
node.use = 0;
Node de retour;
};
/ **
* Un nœud apparaît de l'en-tête de la liste liée
* @returns {*}
* /
Elimination.prototype.shift = function () {
var node = 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];
this.length--;
}
Node de retour;
};
/ **
* Insérez un nœud à partir de l'en-tête de la liste liée
* objet de nœud de nœud @param
* @returns {*}
* /
Elimination.prototype.unshift = fonction (noeud) {
node.next = this.linkhead.next;
this.linkhead.next.prev = node;
this.linkhead.next = node;
node.prev = this.linkhead;
this.Container [node.key] = node;
this.length ++;
Node de retour;
};
/ **
* Insérez un nœud à partir de la fin de la liste liée
* objet de nœud de nœud @param
* @returns {*}
* /
Elimination.prototype.append = fonction (node) {
this.linktail.prev.next = nœud;
node.prev = this.linktail.prev;
node.next = this.linktail;
this.linktail.prev = nœud;
this.Container [node.key] = node;
this.length ++;
Node de retour;
};
/ **
* Un nœud apparaît à partir de la fin de la liste liée
* @returns {*}
* /
Elimination.prototype.pop = function () {
var node = 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];
this.length--;
}
Node de retour;
};
/ **
* Supprimez le nœud spécifié de la liste liée
* objet de nœud de nœud @param
* @returns {*}
* /
Elimination.prototype.remove = fonction (noeud) {
node.prev.next = node.next;
node.next.prev = node.prev;
Supprimer this.Container [Node.Key];
this.length--;
Node de retour;
};
/ **
* Le traitement qui doit être effectué lorsqu'un nœud est accessible doit déplacer le nœud vers l'en-tête de la liste liée
* nœud @param
* /
Elimination.prototype.use = fonction (node) {
this.remove (nœud);
this.unshift (nœud);
};
/ **
* Implémentation de l'algorithme d'élimination du cache LRU
* @constructor
* /
fonction lru () {
Elimination.Apply (ceci, arguments);
}
Lru.prototype = new fn ();
Lru.prototype.get = fonction (key) {
var nœud = non défini;
Node = this.Container [key];
if (node) {
this.use (nœud);
}
Node de retour;
};
Lru.prototype.set = fonction (key, valeur) {
var node = this.buildNode (valeur, key);
if (this.length === this.maxLength) {
this.pop ();
}
this.unshift (nœud);
};
/ **
* Implémentation de l'algorithme d'élimination du cache FIFO
* @constructor
* /
fonction FIFO () {
Elimination.Apply (ceci, arguments);
}
Fifo.prototype = new fn ();
Fifo.prototype.get = fonction (key) {
var nœud = non défini;
Node = this.Container [key];
Node de retour;
};
Fifo.prototype.set = fonction (clé, valeur) {
var node = this.buildNode (valeur, key);
if (this.length === this.maxLength) {
this.shift ();
}
this.append (nœud);
};
/ **
* L'algorithme LRU et FIFO
* @param maxLength
* @constructor
* /
Agent de fonction (maxLength) {
this.getCount = 0;
this.hitCount = 0;
this.lir = new FIFO (maxLength);
this.hir = new LRU (maxLength);
}
Agent.prototype.get = fonction (key) {
var nœud = non défini;
node = this.lir.get (key);
if (node) {
node.use ++;
if (node.use> = 2) {
this.lir.remove (nœud);
this.hir.set (node.key, node.data);
}
}autre{
node = this.hir.get (key);
}
Node de retour;
};
Agent.prototype.getx = fonction (key) {
var nœud = non défini;
this.getCount ++;
Node = this.get (key);
if (node) {
this.hitCount ++;
}
Node de retour;
};
Agent.prototype.set = fonction (clé, valeur) {
var node = null;
node = this.lir.connainer [key] || this.hir.Container [clé];
if (node) {
Node.data = valeur;
}autre{
this.lir.set (clé, valeur);
}
};
/ **
* Obtenez le taux de réussite
* @returns {*}
* /
Agent.prototype.hitratio = fonction () {
var ret = this.getCount;
if (ret) {
ret = this.hitCount / this.getCount;
}
retour retour;
};
/ **
* Interface externe
* Capacité de cache @param maxlength
* @param dev que c'est un environnement de développement, l'environnement de développement comptera le taux de réussite, sinon il ne sera pas
* @returns {{get, set: function, hitratio: function}}
* /
exportS.Inittwoqueues = fonction (maxLength, dev) {
var api = nouvel agent (maxLength);
retour {
get: (function () {
if (dev) {
return function (key) {
var ret = api.getx (key);
return ret && ret.data;
};
}autre{
return function (key) {
var ret = api.get (key);
return ret && ret.data;
};
}
} ()),
set: function () {
api.set.apply (API, arguments);
},
hitRatio: function () {
return api.hitratio.apply (API, arguments);
}
};
};
}(ce));
Enfin, je voudrais vous rappeler à nouveau que l'algorithme de cache doit être combiné avec des scénarios d'application réels. Sans un algorithme universel, le meilleur est le meilleur!