JavaScript TwoQueues 缓存模型实现与使用

TwoQueues 缓存模型概述

TwoQueues 缓存模型指的是在内存中管理数据的一种机制。

在各类编程语言中，将部分数据驻留内存以避免重复计算或读取是常见做法。例如在 jQuery 选择器场景中，DOM 元素的选取往往耗时较长，若能将结果缓存，即可避免每次调用时重新遍历 DOM 树。

然而，内存容量有限，无法将所有历史数据保留在内存中。即便硬件内存充足，理论上每个线程分配的内存空间也是受限的，因此必须设定缓存容量的上限。

核心问题在于如何高效地保留有用数据并淘汰无效数据，这便涉及缓存淘汰算法的设计。

常见的缓存淘汰思路包括以下几种：

FIFO（先进先出）：这是一种基于队列的淘汰策略，最早进入缓存的数据最先被淘汰。著名的 jQuery 框架内部便采用了这种模型。

LRU（最近最少使用）：采用双链表结构，新数据存入时置于链表头部，被访问的数据也移至链表头部。因此，链表尾部的数据即为最近未被使用的，应优先淘汰。

TwoQueues：结合 FIFO 与 LRU 的优点。FIFO 队列主要存放初次存入的数据，而 LRU 队列存放至少被使用过两次的热点数据。该算法具有命中率较高、适应性强且复杂度低的特点。

尽管存在其他多种淘汰算法，但实际应用中以 FIFO 和 LRU 最为常见。原因在于它们算法逻辑简单、易于实现且执行效率高。虽然复杂算法可能略微提升命中率，但考虑到缓存算法本身也会消耗 CPU 资源，若从缓存读取数据比从原始位置读取更耗时，则缓存失去意义。因此，在大多数场景下，简单算法的命中率已足够接受。

此处不再赘述理论细节，网上相关资料丰富。本文将重点分享 JavaScript 版本的 TwoQueues 缓存模型实现。

基本使用方法与配置

首先介绍其使用方法，操作非常简便。

基本使用示例如下：

[/code] var tq = initTwoQueues(10); tq.set("key", "value"); tq.get("key"); [/code]

初始化时需指定缓存容量。需要注意的是，由于内部采用 FIFO 与 LRU 双队列实现，实际存储容量是指定容量的两倍。例如上例指定容量为 10 个键值对，实际上可存放 20 个。

容量大小需根据具体应用场景权衡。容量过小会导致命中率低，过大则可能影响效率，需根据实际情况自行衡量。

在开发过程中，为了评估缓存效果，可将缓存池初始化为开发模式：

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

只需在初始化时添加第二个参数为 true 即可。这样初始化的缓存池会自动统计命中率，通过 hitRatio 方法获取。若未添加该参数，hitRatio 方法返回的命中率始终为 0。由于统计命中率会消耗额外资源，生产环境中不建议开启此功能。

(function(exports){
     /**
* 继承用的纯净类
* @constructor
      */
function Fn(){}
Fn.prototype = Elimination.prototype;
     /**
* 基于链表的缓存淘汰算法父类
* @param maxLength 缓存容量
* @constructor
      */
function Elimination(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){
throw new Error("This method must be override!");
     };
Elimination.prototype.set = function(key, value){
throw new Error("This method must be override!");
     };
     /**
* 创建链表中的节点
* @param data 节点包含的数据，即缓存数据值
* @param key 节点的唯一标示符，即缓存的键
* @returns {{}}
      */
Elimination.prototype.buildNode = function(data, key){
var node = {};
node.data = data;
node.key = key;
node.use = 0;
return node;
     };
     /**
* 从链表头弹出一个节点
* @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;
delete this.container[node.key];
this.length--;
         }
return node;
     };
     /**
* 从链表头插入一个节点
* @param node 节点对象
* @returns {*}
      */
Elimination.prototype.unshift = function(node){
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++;
return node;
     };
     /**
* 从链表尾插入一个节点
* @param node 节点对象
* @returns {*}
      */
Elimination.prototype.append = function(node){
this.linkTail.prev.next = node;
node.prev = this.linkTail.prev;
node.next = this.linkTail;
this.linkTail.prev = node;
this.container[node.key] = node;
this.length++;
return node;
     };
     /**
* 从链表尾弹出一个节点
* @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;
delete this.container[node.key];
this.length--;
         }
return node;
     };
     /**
* 从链表中移除指定节点
* @param node 节点对象
* @returns {*}
      */
Elimination.prototype.remove = function(node){
node.prev.next = node.next;
node.next.prev = node.prev;
delete this.container[node.key];
this.length--;
return node;
     };
     /**
* 节点被访问需要做的处理，具体是把该节点移动到链表头
* @param node
      */
Elimination.prototype.use = function(node){
this.remove(node);
this.unshift(node);
     };
 
     /**
* LRU缓存淘汰算法实现
* @constructor
      */
function LRU(){
Elimination.apply(this, arguments);
     }
LRU.prototype = new Fn();
LRU.prototype.get = function(key){
var node = undefined;
node = this.container[key];
if(node){
this.use(node);
         }
return node;
     };
LRU.prototype.set = function(key, value){
var node = this.buildNode(value, key);
if(this.length === this.maxLength){
this.pop();
         }
this.unshift(node);
     };
 
     /**
* FIFO缓存淘汰算法实现
* @constructor
      */
function FIFO(){
Elimination.apply(this, arguments);
     }
FIFO.prototype = new Fn();
FIFO.prototype.get = function(key){
var node = undefined;
node = this.container[key];
return node;
     };
FIFO.prototype.set = function(key, value){
var node = this.buildNode(value, key);
if(this.length === this.maxLength){
this.shift();
         }
this.append(node);
     };
 
     /**
* LRU、FIFO算法封装，成为新的twoqueues缓存淘汰算法
* @param maxLength
* @constructor
      */
function Agent(maxLength){
this.getCount = 0;
this.hitCount = 0;
this.lir = new FIFO(maxLength);
this.hir = new LRU(maxLength);
     }
Agent.prototype.get = function(key){
var node = undefined;
node = this.lir.get(key);
if(node){
node.use++;
if(node.use >= 2){
this.lir.remove(node);
this.hir.set(node.key, node.data);
             }
}else{
node = this.hir.get(key);
         }
return node;
     };
Agent.prototype.getx = function(key){
var node = undefined;
this.getCount++;
node = this.get(key);
if(node){
this.hitCount++;
         }
return node;
     };
Agent.prototype.set = function(key, value){
var node = null;
node = this.lir.container[key] || this.hir.container[key];
if(node){
node.data = value;
}else{
this.lir.set(key, value);
         }
     };
     /**
* 获取命中率
* @returns {*}
      */
Agent.prototype.hitRatio = function(){
var ret = this.getCount;
if(ret){
ret = this.hitCount / this.getCount;
         }
return ret;
     };
     /**
* 对外接口
* @param maxLength 缓存容量
* @param dev 是否为开发环境，开发环境会统计命中率，反之不会
* @returns {{get, set: Function, hitRatio: Function}}
      */
exports.initTwoQueues = function(maxLength, dev){
var api = new Agent(maxLength);
return {
get: (function(){
if(dev){
return function(key){
var ret = api.getx(key);
return ret && ret.data;
                     };
}else{
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);
             }
         };
     };
 
}(this));

最后再次提醒，缓存算法必须结合实际应用场景选择，不存在万能算法，适合当前场景的才是最佳方案。