JavaScript實(shí)現(xiàn)TwoQueues緩存模型
本文所指TwoQueues緩存模型，是說數(shù)據(jù)在內(nèi)存中的緩存模型。
無論何種語言，都可能需要把一部分?jǐn)?shù)據(jù)放在內(nèi)存中，避免重復(fù)運(yùn)算、讀取。最常見的場(chǎng)景就是JQuery選擇器，有些Dom元素的選取是非常耗時(shí)的，我們希望能把這些數(shù)據(jù)緩存起來，不必每次調(diào)用都去重新遍歷Dom樹。
存就存吧，但總得有個(gè)量吧！總不能把所有的歷史數(shù)據(jù)都放在內(nèi)存中，畢竟目前內(nèi)存的容量還是相當(dāng)可憐的，就算內(nèi)存夠大，理論上每個(gè)線程分配的內(nèi)存也是有限制的。
那么問題來了，如何才能高效的把真正有用的數(shù)據(jù)緩存起來呢？這就涉及到淘汰算法，需要把垃圾數(shù)據(jù)淘汰掉，才能保住有用的數(shù)據(jù)。
比較常用的思路有以下幾種：
FIFO：就是一個(gè)先進(jìn)先出的隊(duì)列，最先緩存的數(shù)據(jù)，最早被淘汰，著名的JQuery框架內(nèi)部就是用的這種模型。
LRU：雙鏈表結(jié)構(gòu)，每次有新數(shù)據(jù)存入，直接放在鏈表頭；每次被訪問的數(shù)據(jù)，也轉(zhuǎn)移到鏈表頭，這樣一來，鏈表尾部的數(shù)據(jù)即是最近沒被使用過的，淘汰之。
TwoQueues：FIFO+ LRU，F(xiàn)IFO主要存放初次存入的數(shù)據(jù)，LRU中存放至少使用過兩次的熱點(diǎn)數(shù)據(jù)，此算法命中率高，適應(yīng)性強(qiáng)，復(fù)雜度低。
其他淘汰算法還有很多很多，但實(shí)際用的比較多的也就這兩種。因?yàn)樗麄儽旧硭惴ú粡?fù)雜，容易實(shí)現(xiàn)，執(zhí)行效率高，緩存的命中率在大多數(shù)場(chǎng)合也還可以接受。畢竟緩存算法也是需要消耗CPU的，如果太過復(fù)雜，雖然命中率有所提高，但得不償失。試想一下，如果從緩存中取數(shù)據(jù)，比從原始位置取還消耗時(shí)間，要緩存何用？
具體理論就不多說了，網(wǎng)上有的是，我也不怎么懂，今天給大家分享的是JavaScript版的TwoQueues緩存模型。
還是先說說使用方法，很簡(jiǎn)單。
基本使用方法如下：
1 var tq = initTwoQueues(10); 2 tq.set("key", "value"); 3 tq.get("key");
初始化的時(shí)候，指定一下緩存容量即可。需要注意的是，由于內(nèi)部采用FIFO+LRU實(shí)現(xiàn)，所以實(shí)際容量是指定容量的兩倍，上例指定的是10個(gè)（鍵值對(duì)），實(shí)際上可以存放20個(gè)。
容量大小需要根據(jù)實(shí)際應(yīng)用場(chǎng)景而定，太小命中率低，太大效率低，物極必反，需要自己衡量。
在開發(fā)過程中，為了審查緩存效果如何，可以將緩存池初始化成開發(fā)版：
1 var tq = initTwoQueues(10, true); 2 tq.hitRatio();
就是在后邊加一個(gè)參數(shù)，直接true就可以了。這樣初始化的緩存池，會(huì)自動(dòng)統(tǒng)計(jì)命中率，可以通過hitRatio方法獲取命中率。如果不加這個(gè)參數(shù)，hitRatio方法獲取的命中率永遠(yuǎn)為0。
統(tǒng)計(jì)命中率肯定要消耗資源，所以生產(chǎn)環(huán)境下不建議開啟。
是時(shí)候分享代碼了：
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 * 創(chuàng)建鏈表中的節(jié)點(diǎn) 38 * @param data 節(jié)點(diǎn)包含的數(shù)據(jù)，即緩存數(shù)據(jù)值 39 * @param key 節(jié)點(diǎn)的唯一標(biāo)示符，即緩存的鍵 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 * 從鏈表頭彈出一個(gè)節(jié)點(diǎn) 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 * 從鏈表頭插入一個(gè)節(jié)點(diǎn) 71 * @param node 節(jié)點(diǎn)對(duì)象 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 * 從鏈表尾插入一個(gè)節(jié)點(diǎn) 89 * @param node 節(jié)點(diǎn)對(duì)象 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 * 從鏈表尾彈出一個(gè)節(jié)點(diǎn) 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 * 從鏈表中移除指定節(jié)點(diǎn) 127 * @param node 節(jié)點(diǎn)對(duì)象 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 * 節(jié)點(diǎn)被訪問需要做的處理，具體是把該節(jié)點(diǎn)移動(dòng)到鏈表頭 142 * @param node 143 */ 144 Elimination.prototype.use = function(node){ 145 this.remove(node); 146 this.unshift(node); 147 }; 148 149 150 /** 151 * LRU緩存淘汰算法實(shí)現(xiàn) 152 * @constructor 153 */ 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緩存淘汰算法實(shí)現(xiàn) 184 * @constructor 185 */ 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 maxLength 213 * @constructor 214 */ 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 * 對(duì)外接口 282 * @param maxLength 緩存容量 283 * @param dev 是否為開發(fā)環(huán)境，開發(fā)環(huán)境會(huì)統(tǒng)計(jì)命中率，反之不會(huì) 284 * @returns {{get, set: Function, hitRatio: Function}} 285 */ 286 exports.initTwoQueues = function(maxLength, dev){ 287 288 var api = new Agent(maxLength); 289 290 return { 291 get: (function(){ 292 if(dev){ 293 return function(key){ 294 var ret = api.getx(key); 295 return ret && ret.data; 296 }; 297 }else{ 298 return function(key){ 299 var ret = api.get(key); 300 return ret && ret.data; 301 }; 302 } 303 }()), 304 set: function(){ 305 api.set.apply(api, arguments); 306 }, 307 hitRatio: function(){ 308 return api.hitRatio.apply(api, arguments); 309 } 310 }; 311 312 }; 313 314 315 }(this));
最后，再次提醒，緩存算法需要和實(shí)際應(yīng)用場(chǎng)景相結(jié)合，沒有萬能算法，合適的才是最好的！
浙公網(wǎng)安備 33010602011771號(hào)