Example of Nodejs cache processing operation based on LRU algorithm

This paper describes the cache processing operation of Nodejs based on LRU algorithm. Share it for your reference, as follows:

LRU is the abbreviation of Least Recently Used, that is, the page replacement algorithm is used at least recently, which serves for virtual page storage management, and makes decisions according to the usage of pages after being transferred into memory. Because it is impossible to predict the future usage of each page, we can only use "recent past" as the approximation of "recent future". Therefore, LRU algorithm is to eliminate the pages that have not been used for the latest longest time.

You can use a special stack to save the page numbers of each page currently in use. When a new process accesses a page, it pushes the page number into the top of the stack, and other page numbers move to the bottom of the stack. If there is not enough memory, the page number at the bottom of the stack is removed. In this way, the top of the stack is always the number of the most recently visited page, while the bottom of the stack is the page number of the most recently unvisited page.

If the following sequence is entered: 4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 6

The results are:

4
4 7
4 7 0
4 0 7
4 0 7 1
4 7 1 0
4 7 0 1
4 7 0 1 2
4 7 0 2 1
4 7 0 1 2
7 0 1 2 6

One LRU cache suitable for Node. js, capacity is the cache capacity, and a general cache is constructed when it is 0.

function CacheLRU(capacity) {
/*  Utilization Buffer Written 1 A LRU Cache, capacity Is the cache capacity, is the 0 Time unlimited capacity. 
myCache = new CacheLRU(capacity); // Construct cache 
myCache.get(key); // Read the file named key Cached value of 
myCache.put(key, value); // Write to a file named key Cached value of 
myCache.remove(key); // Delete a file named key Cached value of 
myCache.removeAll(); // Empty the cache 
myCache.info(); // Return myCache Cache information 
LRU Principle: For all cached data key Build hash Linked list, when a certain 1 Data progress get Or put Operation, set its key Mention the front end of the linked list (up to date). When proceeding put When the data exceeds the capacity, delete the cached data at the end of the linked list (the oldest). 
hash Linked list operation can be directly located key You don't have to go through the whole hash Object, so read and write very fast. Cache capacity no longer affects read-write speed. 
*/
  this.capacity = capacity || Number.MAX_VALUE;
  this.data = {};
  this.hash = {};
  this.linkedList = {
    length: 0,
    head: null,
    end: null
  }
  if (capacity <= 0) this.capacity = Number.MAX_VALUE;
};
CacheLRU.prototype.get = function(key) {
  key = '_' + key;
  var lruEntry = this.hash[key];
  if (!lruEntry) return;
  refresh(this.linkedList, lruEntry);
  return JSON.parse(this.data[key].toString());
};
CacheLRU.prototype.put = function(key, value) {
  key = '_' + key;
  var lruEntry = this.hash[key];
  if (value === undefined) return this;
  if (!lruEntry) {
    this.hash[key] = {key: key};
    this.linkedList.length += 1;
    lruEntry = this.hash[key];
  }
  refresh(this.linkedList, lruEntry);
  this.data[key] = new Buffer(JSON.stringify(value));
  if (this.linkedList.length > this.capacity) this.remove(this.linkedList.end.key.slice(1));
  return this;
};
CacheLRU.prototype.remove = function(key) {
  key = '_' + key;
  var lruEntry = this.hash[key];
  if (!lruEntry) return this;
  if (lruEntry === this.linkedList.head) this.linkedList.head = lruEntry.p;
  if (lruEntry === this.linkedList.end) this.linkedList.end = lruEntry.n;
  link(lruEntry.n, lruEntry.p);
  delete this.hash[key];
  delete this.data[key];
  this.linkedList.length -= 1;
  return this;
};
CacheLRU.prototype.removeAll = function() {
  this.data = {};
  this.hash = {};
  this.linkedList = {
    length: 0,
    head: null,
    end: null
  }
  return this;
};
CacheLRU.prototype.info = function() {
  var size = 0,
    data = this.linkedList.head;
  while (data){
    size += this.data[data.key].length;
    data = data.p;
  }
  return {
    capacity: this.capacity,
    length: this.linkedList.length,
    size: size
  };
};
//  Update the linked list and put get Or put Method manipulated by the key Mention linked list head Which means the latest 
function refresh(linkedList, entry) {
  if (entry != linkedList.head) {
    if (!linkedList.end) {
      linkedList.end = entry;
    } else if (linkedList.end == entry) {
      linkedList.end = entry.n;
    }
    link(entry.n, entry.p);
    link(entry, linkedList.head);
    linkedList.head = entry;
    linkedList.head.n = null;
  }
}
//  Link two linked list objects to form 1 Strip chain 
function link(nextEntry, prevEntry) {
  if (nextEntry != prevEntry) {
    if (nextEntry) nextEntry.p = prevEntry;
    if (prevEntry) prevEntry.n = nextEntry;
  }
}
module.exports = CacheLRU;
// test:
/*var user = new CacheLRU(5);
user.put('user1', {name:'admin', age: 30});
user.put('user2', {name:'user', age: 31});
user.put('user3', {name:'guest', age: 32});
user.put('user4', {name:'guest', age: 34});
user.put('user5', {name:'guest', age: 35});
console.log(user.get('user1'));
console.log(user.get('user2'));
console.log(user.get('user3'));
user.put('user6', {name:'guest', age: 36});
console.log(user.info());*/

LRU algorithm can also be used in some practical applications, such as you want to do a browser, or similar to Taobao client applications will use this principle. Everyone knows that when browsing the web page, the browser will temporarily save the downloaded pictures in a folder of this machine, and when visiting again next time, it will be read directly from the temporary folder of this machine. However, the temporary folder for saving pictures has a fixed capacity limit. If you browse too many web pages, you will delete some of the least frequently used images, and only keep the most recently used images. At this time, you can use LRU algorithm. At this time, this special stack in the above algorithm is not to save the serial number of the page, but the serial number or size of each picture; So the elements of the stack above are represented by the Object class, so that the stack can hold the object.

I hope this article is helpful to everyone's nodejs programming.