O modelo de cache do BUIQUEUES mencionado neste artigo refere -se ao modelo de cache de dados na memória.
Independentemente do idioma, pode ser necessário colocar alguns dados na memória para evitar operações e leitura repetidas. O cenário mais comum é o seletor de jQuery. A seleção de alguns elementos DOM é muito demorada. Esperamos armazenar em cache esses dados sem ter que transferir novamente a árvore Dom toda vez que ligarmos.
Salve, mas deve haver uma quantidade! Você não pode colocar todos os dados históricos na memória. Afinal, a capacidade atual da memória ainda é muito lamentável. Mesmo que a memória seja grande o suficiente, a memória alocada por cada thread em teoria ainda é limitada.
Portanto, a questão é: como podemos cache com eficiência dados verdadeiramente úteis? Isso envolve algoritmos de eliminação, e os dados de lixo precisam ser eliminados para preservar dados úteis.
Existem várias idéias comuns:
FIFO: É a primeira fila da primeira saída, os primeiros dados em cache e foi eliminada primeiro. Este modelo é usado dentro da famosa estrutura jQuery.
LRU: estrutura de lista de ligações duplas, sempre que novos dados são armazenados, são colocados diretamente no cabeçalho da lista vinculada; Os dados acessados cada vez também são transferidos para o cabeçalho da lista vinculada. Dessa forma, os dados no final da lista vinculada são algo que não foi usado recentemente e será eliminado.
TwoQueues: FIFO+ LRU. O FIFO armazena principalmente dados armazenados pela primeira vez, e os dados do LRU armazenam dados que foram usados pelo menos duas vezes. Esse algoritmo tem uma alta taxa de acerto, forte adaptabilidade e baixa complexidade.
Existem muitos outros algoritmos de eliminação, mas existem apenas dois tipos deles que são mais usados na prática. Como seus algoritmos não são complexos, fáceis de implementar, alta eficiência de execução e a taxa de acerto de cache é aceitável na maioria das ocasiões. Afinal, o algoritmo de cache também requer consumo de CPU. Se for muito complexo, embora a taxa de acerto tenha sido melhorada, não vale a pena a perda. Imagine, se você buscar dados do cache, leva mais tempo do que buscar do local original. Qual é o uso do cache?
Não vou falar sobre as teorias específicas. Existem alguns online, mas eu não os entendo muito. Hoje vou compartilhar com você a versão JavaScript do modelo de cache TwoQueues.
Vamos falar sobre como usá -lo primeiro, é muito simples.
O método de uso básico é o seguinte:
[/código]
var tq = inittwoqueues (10);
tq.set ("key", "value");
tq.get ("key");
[/código]
Ao inicializar, basta especificar a capacidade do cache. Deve -se notar que, como o FIFO+LRU é implementado internamente, a capacidade real é o dobro da capacidade especificada. O exemplo acima especifica 10 (pares de valor-chave), que podem realmente armazenar 20.
O tamanho da capacidade precisa ser determinado de acordo com o cenário de aplicação real. Se for muito pequeno, a taxa de acertos é baixa, a eficiência é baixa e o extremo é o oposto, e você precisa medi -lo sozinho.
Durante o processo de desenvolvimento, para revisar o efeito do cache, o pool de cache pode ser inicializado na versão de desenvolvimento:
A cópia do código é a seguinte:
var tq = inittwoqueues (10, verdadeiro);
tq.hitratio ();
Basta adicionar um parâmetro ao fim e apenas verdadeiro. O pool de cache inicializado dessa maneira contará automaticamente a taxa de acerto, e a taxa de acerto pode ser obtida através do método Hitratio. Se este parâmetro não for adicionado, a taxa de acerto obtida pelo método Hitratio será sempre 0.
A taxa de acerto estatística definitivamente consumirá recursos, por isso não é recomendável ativar os ambientes de produção.
É hora de compartilhar o código:
A cópia do código é a seguinte:
(função (exportações) {
/**
* Classe pura para herança
* @Constructor
*/
função fn () {}
Fn.prototype = elimination.prototype;
/**
* Algoritmo de eliminação de cache da classe pai com base na lista vinculada
* @param maxlength cache capacidade
* @Constructor
*/
eliminação da função (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 = function (key) {
lançar um novo erro ("Este método deve ser substituído!");
};
Elimination.prototype.set = function (chave, valor) {
lançar um novo erro ("Este método deve ser substituído!");
};
/**
* Crie nós na lista vinculada
* @param dados Os dados contidos no nó, ou seja, o valor dos dados em cache
* @param chave O identificador exclusivo do nó, ou seja, a chave em cache
* @returns {{}}
*/
Elimination.prototype.buildNode = function (dados, chave) {
var node = {};
node.data = dados;
node.key = key;
node.use = 0;
Nó de retorno;
};
/**
* Um nó aparece do cabeçalho da lista vinculada
* @returns {*}
*/
Elimination.prototype.shift = function () {
var node = nulo;
if (! this.linkhead.next.tail) {
node = this.linkhead.next;
this.linkhead.next = node.next;
node.next.prev = this.linkhead;
exclua this.container [node.key];
this.length--;
}
Nó de retorno;
};
/**
* Insira um nó no cabeçalho da lista vinculada
* @param nó objeto
* @returns {*}
*/
Elimination.prototype.unshift = function (nó) {
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 ++;
Nó de retorno;
};
/**
* Insira um nó no final da lista vinculada
* @param nó objeto
* @returns {*}
*/
Elimination.prototype.append = function (nó) {
this.linktail.prev.next = node;
node.prev = this.linktail.prev;
node.next = this.linktail;
this.linktail.prev = nó;
this.container [node.key] = node;
this.length ++;
Nó de retorno;
};
/**
* Um nó aparece do final da lista vinculada
* @returns {*}
*/
Elimination.prototype.pop = function () {
var node = nulo;
if (! this.linktail.prev.head) {
node = this.linktail.prev;
node.prev.next = this.linktail;
this.linktail.prev = node.prev;
exclua this.container [node.key];
this.length--;
}
Nó de retorno;
};
/**
* Remova o nó especificado da lista vinculada
* @param nó objeto
* @returns {*}
*/
Elimination.prototype.remove = function (nó) {
node.prev.next = node.next;
node.next.prev = node.prev;
exclua this.container [node.key];
this.length--;
Nó de retorno;
};
/**
* O processamento deve ser feito quando um nó é acessado é mover o nó para o cabeçalho da lista vinculada
* Nó @param
*/
Elimination.prototype.use = function (nó) {
this.remove (nó);
this.UnShift (nó);
};
/**
* Implementação do algoritmo de eliminação do cache da LRU
* @Constructor
*/
função lru () {
Eliminação.Apply (isto, argumentos);
}
Lru.prototype = new fn ();
Lru.prototype.get = function (key) {
var node = indefinido;
nó = this.container [key];
if (nó) {
this.use (nó);
}
Nó de retorno;
};
Lru.prototype.set = function (chave, valor) {
var node = this.buildNode (valor, chave);
if (this.length === this.maxLength) {
this.pop ();
}
this.UnShift (nó);
};
/**
* Implementação do algoritmo de eliminação de cache do FIFO
* @Constructor
*/
function fifo () {
Eliminação.Apply (isto, argumentos);
}
FIFO.Prototype = new Fn ();
Fifo.prototype.get = function (key) {
var node = indefinido;
nó = this.container [key];
Nó de retorno;
};
Fifo.prototype.set = function (chave, valor) {
var node = this.buildNode (valor, chave);
if (this.length === this.maxLength) {
this.Shift ();
}
this.append (nó);
};
/**
* O encapsulamento do algoritmo LRU e FIFO tornou -se o novo algoritmo de eliminação de cache de dois cache
* @param maxlength
* @Constructor
*/
Agente de função (maxlength) {
this.getCount = 0;
this.hitCount = 0;
this.lir = novo FIFO (maxLength);
this.hir = new LRU (maxLength);
}
Agente.prototype.get = function (key) {
var node = indefinido;
node = this.lir.get (chave);
if (nó) {
node.use ++;
if (node.use> = 2) {
this.lir.remove (nó);
this.hir.set (node.key, node.data);
}
}outro{
node = this.hir.get (chave);
}
Nó de retorno;
};
Agente.prototype.getx = function (key) {
var node = indefinido;
this.getCount ++;
nó = this.get (chave);
if (nó) {
this.hitCount ++;
}
Nó de retorno;
};
Agente.prototype.set = function (chave, valor) {
var node = nulo;
node = this.lir.container [key] || this.hir.container [key];
if (nó) {
node.data = value;
}outro{
this.lir.set (chave, valor);
}
};
/**
* Obtenha uma taxa de atingimento
* @returns {*}
*/
Agente.prototype.hitratio = function () {
var ret = this.getCount;
if (ret) {
ret = this.hitcount / this.getCount;
}
retornar retorno;
};
/**
* Interface externa
* @param maxlength cache capacidade
* @param Dev, seja um ambiente de desenvolvimento, o ambiente de desenvolvimento contará a taxa de acerto, caso contrário, não será
* @returns {{get, set: function, hitratio: function}}
*/
exports.inittwoqueues = function (maxLength, dev) {
var api = novo agente (maxLength);
retornar {
Get: (function () {
if (dev) {
Função de retorno (chave) {
var ret = api.getx (chave);
return ret && ret.data;
};
}outro{
Função de retorno (chave) {
var ret = api.get (chave);
return ret && ret.data;
};
}
} ()),
SET: function () {
api.set.Apply (API, argumentos);
},
hitratio: function () {
retornar api.hitratio.apply (API, argumentos);
}
};
};
}(esse));
Por fim, gostaria de lembrá -lo novamente que o algoritmo de cache precisa ser combinado com os cenários reais de aplicação. Sem um algoritmo universal, o melhor é o melhor!