Detailed explanation of the cache processing operation method implemented by Nodejs based on the LRU algorithm

This article mainly introduces the cache processing operation of Nodejs based on the LRU algorithm. It analyzes the principles and functions of the LRU algorithm and the implementation of the LRU algorithm in nodejs based on specific examples. For related implementation skills of cache processing operations, friends in need can refer to

This article describes the cache processing operations implemented by Nodejs based on the LRU algorithm. Share it with everyone for your reference. The details are as follows:

LRU is the abbreviation of Least Recently Used, which is the least recently used page replacement algorithm. It serves virtual page storage management and is loaded into memory according to the page. Usage decisions are made. Since it is impossible to predict the future usage of each page, we can only use the "recent past" as an approximation of the "near future". Therefore, the LRU algorithm eliminates the pages that have not been used for the longest time.

A special stack can be used to save the page number of each page currently being used. When a new process accesses a page, the page number is pushed to the top of the stack, and other page numbers are moved 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 accessed page, and the bottom of the stack is the page number of the page that has not been accessed for the longest time.

If you enter the following sequence: 4,7,0,7,1,0,1,2,1,2,6

the result is:

4
4 7
4 7 0
4 0 7
4 0 7 1
4 7 1 0
4 7 0 1
4 7 7 0 1 2
4 7 1 Cache, capacity is the cache capacity, constructed when it is 0 General caching.

function CacheLRU(capacity) {
/* 利用Buffer写的一个LRU缓存，capacity为缓存容量，为0时不限容量。
myCache = new CacheLRU(capacity); //构造缓存
myCache.get(key); //读取名为key的缓存值
myCache.put(key, value); //写入名为key的缓存值
myCache.remove(key); //删除名为key的缓存值
myCache.removeAll(); //清空缓存
myCache.info(); //返回myCache缓存信息
LRU原理：对所有缓存数据的key构建hash链表，当对某一数据进行get或put操作时，将其key提到链表前端（最新）。当进行put数据超出容量时，删除链表尾端（最旧）的缓存数据。
hash链表操作可直接定位key，无需历遍整个hash对象，故读写极快。缓存容量不再影响读写速度。
*/
  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 = &#39;_&#39; + 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 = &#39;_&#39; + 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 = &#39;_&#39; + 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
  };
};
// 更新链表，把get或put方法操作的key提到链表head，即表示最新
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;
  }
}
// 对两个链表对象建立链接，形成一条链
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(&#39;user1&#39;, {name:&#39;admin&#39;, age: 30});
user.put(&#39;user2&#39;, {name:&#39;user&#39;, age: 31});
user.put(&#39;user3&#39;, {name:&#39;guest&#39;, age: 32});
user.put(&#39;user4&#39;, {name:&#39;guest&#39;, age: 34});
user.put(&#39;user5&#39;, {name:&#39;guest&#39;, age: 35});
console.log(user.get(&#39;user1&#39;));
console.log(user.get(&#39;user2&#39;));
console.log(user.get(&#39;user3&#39;));
user.put(&#39;user6&#39;, {name:&#39;guest&#39;, age: 36});
console.log(user.info());*/

The LRU algorithm can also be used in some practical applications, such as if you want to be a browser, or similar to Taobao customers End applications will use this principle. Everyone knows that when browsing the web, the browser will temporarily save the downloaded pictures in a folder on the local machine. The next time you visit it, it will be read directly from the temporary folder on the local machine. However, the temporary folder that saves pictures has a certain capacity limit. If you browse too many web pages, some of the images that you use least frequently will be deleted, and only the pictures that you use most recently will be retained. At this time, the LRU algorithm can be used. At this time, the special stack in the above algorithm does not save the serial number of the page, but the serial number or size of each picture; so the elements of the above stack are all using
Object Class

is represented, so that the stack can save the object.

The above is the detailed content of Detailed explanation of the cache processing operation method implemented by Nodejs based on the LRU algorithm. For more information, please follow other related articles on the PHP Chinese website!