javaScript实现TwoQueues缓存模型

本文所指TwoQueues缓存模型，是说数据在内存中的缓存模型。

无论何种语言，都可能需要把一部分数据放在内存中，避免重复运算、读取。最常见的场景就是JQuery选择器，有些Dom元素的选取是非常耗时的，我们希望能把这些数据缓存起来，不必每次调用都去重新遍历Dom树。

存就存吧，但总得有个量吧！总不能把所有的历史数据都放在内存中，毕竟目前内存的容量还是相当可怜的，就算内存够大，理论上每个线程分配的内存也是有限制的。

那么问题来了，如何才能高效的把真正有用的数据缓存起来呢？这就涉及到淘汰算法，需要把垃圾数据淘汰掉，才能保住有用的数据。

比较常用的思路有以下几种：

FIFO：就是一个先进先出的队列，最先缓存的数据，最早被淘汰，著名的JQuery框架内部就是用的这种模型。

LRU：双链表结构，每次有新数据存入，直接放在链表头；每次被访问的数据，也转移到链表头，这样一来，链表尾部的数据即是最近没被使用过的，淘汰之。

TwoQueues：FIFO+ LRU，FIFO主要存放初次存入的数据，LRU中存放至少使用过两次的热点数据，此算法命中率高，适应性强，复杂度低。

其他淘汰算法还有很多很多，但实际用的比较多的也就这两种。因为他们本身算法不复杂，容易实现，执行效率高，缓存的命中率在大多数场合也还可以接受。毕竟缓存算法也是需要消耗CPU的，如果太过复杂，虽然命中率有所提高，但得不偿失。试想一下，如果从缓存中取数据，比从原始位置取还消耗时间，要缓存何用？

具体理论就不多说了，网上有的是，我也不怎么懂，今天给大家分享的是Javascript版的TwoQueues缓存模型。

还是先说说使用方法，很简单。

基本使用方法如下：

1 var tq = initTwoQueues(10);2 tq.set("key", "value");3 tq.get("key");

初始化的时候，指定一下缓存容量即可。需要注意的是，由于内部采用FIFO+LRU实现，所以实际容量是指定容量的两倍，上例指定的是10个（键值对），实际上可以存放20个。

容量大小需要根据实际应用场景而定，太小命中率低，太大效率低，物极必反，需要自己衡量。

在开发过程中，为了审查缓存效果如何，可以将缓存池初始化成开发版：

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

就是在后边加一个参数，直接true就可以了。这样初始化的缓存池，会自动统计命中率，可以通过hitRatio方法获取命中率。如果不加这个参数，hitRatio方法获取的命中率永远为0。

统计命中率肯定要消耗资源，所以生产环境下不建议开启。

是时候分享代码了：

  1 (function(exports){  2   3     /**  4      * 继承用的纯净类  5      * @constructor  6      */  7     function Fn(){}  8     Fn.PRototype = Elimination.prototype;  9  10     /** 11      * 基于链表的缓存淘汰算法父类 12      * @param maxLength 缓存容量 13      * @constructor 14      */ 15     function Elimination(maxLength){ 16         this.container = {}; 17         this.length = 0; 18         this.maxLength = maxLength || 30; 19         this.linkHead = this.buildNode("", ""); 20         this.linkHead.head = true; 21         this.linkTail = this.buildNode("", ""); 22         this.linkTail.tail = true; 23  24         this.linkHead.next = this.linkTail; 25         this.linkTail.prev = this.linkHead; 26     } 27  28     Elimination.prototype.get = function(key){ 29         throw new Error("This method must be override!"); 30     }; 31  32     Elimination.prototype.set = function(key, value){ 33         throw new Error("This method must be override!"); 34     }; 35  36     /** 37      * 创建链表中的节点 38      * @param data 节点包含的数据，即缓存数据值 39      * @param key 节点的唯一标示符，即缓存的键 40      * @returns {{}} 41      */ 42     Elimination.prototype.buildNode = function(data, key){ 43         var node = {}; 44         node.data = data; 45         node.key = key; 46         node.use = 0; 47  48         return node; 49     }; 50  51     /** 52      * 从链表头弹出一个节点 53      * @returns {*} 54      */ 55     Elimination.prototype.shift = function(){ 56         var node = null; 57         if(!this.linkHead.next.tail){ 58             node = this.linkHead.next; 59             this.linkHead.next = node.next; 60             node.next.prev = this.linkHead; 61  62             delete this.container[node.key]; 63             this.length--; 64         } 65  66         return node; 67     }; 68  69     /** 70      * 从链表头插入一个节点 71      * @param node 节点对象 72      * @returns {*} 73      */ 74     Elimination.prototype.unshift = function(node){ 75         node.next = this.linkHead.next; 76         this.linkHead.next.prev = node; 77  78         this.linkHead.next = node; 79         node.prev = this.linkHead; 80  81         this.container[node.key] = node; 82         this.length++; 83  84         return node; 85     }; 86  87     /** 88      * 从链表尾插入一个节点 89      * @param node 节点对象 90      * @returns {*} 91      */ 92     Elimination.prototype.append = function(node){ 93  94         this.linkTail.prev.next = node; 95         node.prev = this.linkTail.prev; 96  97         node.next = this.linkTail; 98         this.linkTail.prev = node; 99 100         this.container[node.key] = node;101         this.length++;102 103         return node;104     };105 106     /**107      * 从链表尾弹出一个节点108      * @returns {*}109      */110     Elimination.prototype.pop = function(){111         var node = null;112 113         if(!this.linkTail.prev.head){114             node = this.linkTail.prev;115             node.prev.next = this.linkTail;116             this.linkTail.prev = node.prev;117 118             delete this.container[node.key];119             this.length--;120         }121 122         return node;123     };124 125     /**126      * 从链表中移除指定节点127      * @param node 节点对象128      * @returns {*}129      */130     Elimination.prototype.remove = function(node){131         node.prev.next = node.next;132         node.next.prev = node.prev;133 134         delete this.container[node.key];135         this.length--;136 137         return node;138     };139 140     /**141      * 节点被访问需要做的处理，具体是把该节点移动到链表头142      * @param node143      */144     Elimination.prototype.use = function(node){145         this.remove(node);146         this.unshift(node);147     };148 149 150     /**151      * LRU缓存淘汰算法实现152      * @constructor153      */154     function LRU(){155         Elimination.apply(this, arguments);156     }157     LRU.prototype = new Fn();158 159     LRU.prototype.get = function(key){160         var node = undefined;161 162         node = this.container[key];163 164         if(node){165             this.use(node);166         }167 168         return node;169     };170 171     LRU.prototype.set = function(key, value){172         var node = this.buildNode(value, key);173 174         if(this.length === this.maxLength){175             this.pop();176         }177 178         this.unshift(node);179     };180 181 182     /**183      * FIFO缓存淘汰算法实现184      * @constructor185      */186     function FIFO(){187         Elimination.apply(this, arguments);188     }189     FIFO.prototype = new Fn();190 191     FIFO.prototype.get = function(key){192         var node = undefined;193 194         node = this.container[key];195 196         return node;197     };198 199     FIFO.prototype.set = function(key, value){200         var node = this.buildNode(value, key);201 202         if(this.length === this.maxLength){203             this.shift();204         }205 206         this.append(node);207     };208 209 210     /**211      * LRU、FIFO算法封装，成为新的twoqueues缓存淘汰算法212      * @param maxLength213      * @constructor214      */215     function Agent(maxLength){216         this.getCount = 0;217         this.hitCount = 0;218         this.lir = new FIFO(maxLength);219         this.hir = new LRU(maxLength);220     }221 222     Agent.prototype.get = function(key){223         var node = undefined;224 225         node = this.lir.get(key);226 227         if(node){228             node.use++;229             if(node.use >= 2){230                 this.lir.remove(node);231                 this.hir.set(node.key, node.data);232             }233         }else{234             node = this.hir.get(key);235         }236 237         return node;238     };239 240     Agent.prototype.getx = function(key){241         var node = undefined;242 243         this.getCount++;244 245         node = this.get(key);246 247         if(node){248             this.hitCount++;249         }250 251         return node;252     };253 254     Agent.prototype.set = function(key, value){255         var node = null;256 257         node = this.lir.container[key] || this.hir.container[key];258 259         if(node){260             node.data = value;261         }else{262             this.lir.set(key, value);263         }264     };265 266     /**267      * 获取命中率268      * @returns {*}269      */270     Agent.prototype.hitRatio = function(){271         var ret = this.getCount;272 273         if(ret){274             ret = this.hitCount / this.getCount;275         }276 277         return ret;278     };279 280     /**281      * 对外接口282      * @param maxLength 缓存容量283      * @param dev 是否为开发环境，开发环境会统计命中率，反之不会284      * @returns {{get, set: Function, hitRatio: Function}}285      */286     exports.initTwoQueues = function(maxLength, dev){287 288         var api = new Agent(maxLength);