JavaScript version of TwoQueues caching model_Basic knowledge

The TwoQueues caching model referred to in this article refers to the caching model of data in memory.

No matter what language, you may need to put some data in memory to avoid repeated operations and reading. The most common scenario is the JQuery selector. The selection of some Dom elements is very time-consuming. We hope to cache this data without having to re-traverse the Dom tree every time it is called.

Just save it, but there must be an amount! It is impossible to put all historical data in memory. After all, the current memory capacity is still quite pitiful. Even if the memory is large enough, the memory allocated to each thread is theoretically limited.

So the question is, how can we cache truly useful data efficiently? This involves elimination algorithms, which need to eliminate junk data in order to retain useful data.

The more commonly used ideas are as follows:

FIFO: It is a first-in, first-out queue. The first cached data is the first to be eliminated. This model is used within the famous JQuery framework.

LRU: Double linked list structure. Every time new data is stored, it is placed directly at the head of the linked list; each time the data is accessed, it is also transferred to the head of the linked list. In this way, the data at the end of the linked list is the most recent Those that have not been used will be eliminated.

TwoQueues: FIFO LRU, FIFO mainly stores the data stored for the first time, and LRU stores hotspot data that has been used at least twice. This algorithm has a high hit rate, strong adaptability, and low complexity.

There are many other elimination algorithms, but these two are the most commonly used. Because their algorithms are not complex, easy to implement, have high execution efficiency, and the cache hit rate is acceptable in most situations. After all, the caching algorithm also consumes CPU. If it is too complicated, although the hit rate will be improved, the gain will not be worth the loss. Just imagine, if retrieving data from the cache takes more time than retrieving it from the original location, what is the use of caching?

I won’t go into details about the specific theory. There are many on the Internet, but I don’t really understand them. What I want to share with you today is the JavaScript version of the TwoQueues caching model.

Let’s talk about how to use it first, it’s very simple.

The basic usage is as follows:

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

When initializing, just specify the cache capacity. It should be noted that due to the internal implementation of FIFO LRU, the actual capacity is twice the specified capacity. The above example specifies 10 (key-value pairs), but 20 can actually be stored.

The capacity size needs to be determined according to the actual application scenario. If it is too small, the hit rate will be low, if it is too large, the efficiency will be low.

During the development process, in order to review the cache effect, you can initialize the cache pool to the development version:

Copy code The code is as follows:

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

Just add a parameter at the end, just make it true. The cache pool initialized in this way will automatically count the hit rate, and the hit rate can be obtained through the hitRatio method. If this parameter is not added, the hit ratio obtained by the hitRatio method will always be 0.
Statistical hit rate will definitely consume resources, so it is not recommended to turn it on in a production environment.
Time to share the code:

Copy code The code is as follows:

 (function(exports){
     /**
* Pure class for inheritance
* @constructor
​​*/
     function Fn(){}
     Fn.prototype = Elimination.prototype;
     /**
* * Linked list-based cache elimination algorithm parent class
* @param maxLength cache capacity
* @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!");
     };
     /**
*Create nodes in the linked list
* @param data The data contained in the node, that is, the cached data value
* @param key The unique identifier of the node, that is, the cached key
* @returns {{}}
​​*/
     Elimination.prototype.buildNode = function(data, key){
         var node = {};
         node.data = data;
         node.key = key;
         node.use = 0;
         return node;
     };
     /**
* Pop a node from the head of the linked list
* @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;
     };
     /**
* Insert a node from the head of the linked list
* @param node node object
* @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;
     };
     /**
* Pop a node from the end of the linked list
* @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;
     };
     /**
*Remove the specified node from the linked list
* @param node node object
* @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;
     };
     /**
* The processing that needs to be done when the node is accessed, specifically moving the node to the head of the linked list
* @param node
​​*/
     Elimination.prototype.use = function(node){
         this.remove(node);
         this.unshift(node);
     };
 
     /**
* Implementation of LRU cache elimination algorithm
* @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);
     };
 
     /**
* Implementation of FIFO cache elimination algorithm
* @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 and FIFO algorithm encapsulation, becoming the new twoqueues cache elimination algorithm
* @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);
         }
     };
     /**
* Get hit rate
* @returns {*}
​​*/
     Agent.prototype.hitRatio = function(){
         var ret = this.getCount;
         if(ret){
             ret = this.hitCount / this.getCount;
         }
         return ret;
     };
     /**
      * 对外接口
* @param maxLength cache capacity
* @param dev Whether it is a development environment, the development environment will count the hit rate, otherwise it will not
* @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));

Finally, I would like to remind you again that the caching algorithm needs to be combined with the actual application scenario. There is no universal algorithm, and the appropriate one is the best!