DIV CSS 佈局教程網

JavaScript版TwoQueues緩存模型實作全解析
編輯:關於JavaScript     

本文所說的TwoQueues緩存模型,指的是資料在記憶體中的快取策略。無論使用哪種語言,我們都可能需要把一部分資料暫存在記憶體裡,以避免重複的運算與讀取。最典型的場景莫過於jQuery選擇器——某些DOM元素的查詢相當耗時,我們自然希望能把結果快取起來,不必每次呼叫都重新遍歷整棵DOM樹。

可是快取歸快取,總得設個上限。我們不可能把全部歷史資料一股腦兒塞進記憶體,畢竟記憶體容量寶貴,而且理論上每個執行緒能分到的記憶體也是有限的。

於是問題就來了:怎樣才能高效地把真正有用的資料快取起來?這就牽涉到「淘汰演算法」——只有把垃圾資料清出去,才能保住真正有價值的資料。常見的思路主要有以下幾種:

FIFO(先進先出):最先進入的資料最早被淘汰,它就像一個普通的佇列。著名的jQuery框架內部採用的正是這種模型。

LRU(最近最少使用):採用雙向鏈表結構。每次有新資料存入就放到鏈表頭部;每次被存取的資料也移到鏈表頭部。這樣一來,鏈表尾部的資料就是最近沒被使用過的,淘汰它們即可。

TwoQueues:由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));

最後要再次提醒:快取演算法必須與實際應用場景相結合,世界上沒有萬能的演算法,只有適合與否——合適的才是最好的。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved