LRU 알고리즘을 기반으로 Nodejs에서 구현한 캐시 처리 연산 방법에 대한 자세한 설명

이 글에서는 주로 LRU 알고리즘을 기반으로 하는 Nodejs의 캐시 처리 동작을 소개하고, LRU 알고리즘의 원리와 기능, 그리고 LRU 알고리즘의 구현을 분석한다. 캐시 처리 작업 관련 구현 기술은

을 참고하세요. 이 글은 LRU 알고리즘을 기반으로 Nodejs로 구현한 캐시 처리 작업을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 자세한 내용은 다음과 같습니다.

LRU는 Least Recent Used의 약어입니다. 즉, 가장 최근에 사용된 페이지 교체 알고리즘으로 가상 페이지 저장소 관리 기능을 제공하고 페이지를 기반으로 메모리가 결정됩니다. 각 페이지의 미래 사용량을 예측하는 것은 불가능하므로 "가까운 미래"의 근사치로 "최근 과거"만 사용할 수 있습니다. 따라서 LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 제거합니다.

특수 스택을 사용하여 현재 사용 중인 각 페이지의 페이지 번호를 저장할 수 있습니다. 새 프로세스가 페이지에 액세스하면 페이지 번호가 스택의 맨 위로 푸시되고 다른 페이지 번호는 스택의 맨 아래로 이동됩니다. 메모리가 충분하지 않으면 스택의 맨 아래에 있는 페이지 번호가 됩니다. 제거됨. 이런 방식으로 스택의 맨 위는 항상 가장 최근에 액세스한 페이지의 번호이고, 스택의 맨 아래는 가장 최근에 방문한 페이지의 페이지 번호입니다.

예를 들어 4,7,0,7,1,0,1,2,1,2,6을 순서대로 입력하면

결과는 다음과 같습니다.

4
4 7
4 7 0
4 0 7
4 0 7 1
4 7 1 0
4 7 0 1
4 7 7 1 2
4 7 1 🎜>Node.js의 LRU 캐시
, 용량은 캐시 용량이며 일반 캐싱이 0일 때 구성됩니다.

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());*/

LRU 알고리즘은 브라우저가 되기를 원하거나 다음과 유사한 일부 실용적인 응용 프로그램에도 사용할 수 있습니다. Taobao 고객의 최종 애플리케이션은 이 원칙을 사용합니다. 웹을 검색할 때 브라우저가 다운로드한 사진을 로컬 컴퓨터의 폴더에 임시 저장한다는 사실은 누구나 알고 있습니다. 다음에 웹을 방문하면 로컬 컴퓨터의 임시 폴더에서 직접 읽을 수 있습니다. 그러나 사진을 저장하는 임시 폴더에는 특정 용량 제한이 있습니다. 너무 많은 웹 페이지를 탐색하면 가장 자주 사용하지 않는 일부 이미지가 삭제되고 가장 최근에 사용한 사진만 유지됩니다. 이때, 위 알고리즘의 특수 스택은 페이지의 일련 번호를 저장하지 않고 각 그림의 일련 번호나 크기를 저장하므로 위 스택의 요소는 다음과 같습니다.

Object Class

를 표현하여 스택에 객체를 저장할 수 있도록 합니다.

위 내용은 LRU 알고리즘을 기반으로 Nodejs에서 구현한 캐시 처리 연산 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!