LRU Cache 자료구조 이해하기

LRU Cache = Least Recently Used Cache

 

Cache란 ?

데이터를 임시로 저장하는 임시 저장소의 개념이다. 실제로 서비스를 만들 때도, DB에 있는 진짜 데이터에 접근하는 시간을 절약하고 싶고, 실제로 DB까지 갔다올 필요가 없을 때 캐시의 의미를 활용 한다. 

 

그렇다면 LRU Cache란?

위에서 언급했듯이 cache는 임시 저장소 이므로, 용량이 크지 않다. 따라서 주기적으로 데이터들을 정리해준다. 이때 사용되는 기법중 하나이다. 이중 LRU는 최근에 가장 오랫동안 사용하지 않은 데이터 중심으로 삭제 한다. 

 

 

 

LRU Cache 구현

해당 기법은 Doubly Linked List를 통해 구현된다. head에 가까운 데이터일 수록 최근에 사용한 데이터/ tail에 가까울 수록 오랫동안 사용하지 않은 데이터이다. 따라서 새로운 데이터를 삽입 할때, cache 저장소가 용량 한계치를 넘은 경우, tail에 가까운 데이터 먼저 삭제 해준다. 그리고 새로 삽입한 데이터/ 최근에 찾은(get)한 데이터는 head로 옮겨주어, 우선순위를 높여준다. 

 

Node 정의

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

 

LRU Cache Class 정의

class LRUCache {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
        this.maxSize = 4;
        this.cache = {};
    }
}

 

Cache Set 정의

set(key, value) {
        let newNode
 
        // if the key not present in cache
        if (this.cache[key] === undefined) newNode = new Node(key, value);
 
        //if we have an empty list
        if(this.size === 0) {
            this.head = newNode;
            this.tail = newNode;
            this.size++;
            this.cache[key] = newNode;
            return this;
        }
 
        if (this.size === this.maxSize) {
            //remove from cache
            delete this.cache[this.tail.key]
 
            //set new tail
            this.tail = this.tail.prev;
            this.tail.next = null;
            this.size--;
        }
 
        //add an item to the head
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    
        //add to cache
        this.cache[key] = newNode; 
        return this;
        
}

 

Cache get 정의

get(key) {
        if (!this.cache[key]){
            return undefined
        }
 
        let foundNode = this.cache[key];
        
        if(foundNode === this.head) return foundNode;
 
        let previous = foundNode.prev;
        let next = foundNode.next;
 
        if (foundNode === this.tail){
            previous.next = null;
            this.tail = previous;
        }else{
            previous.next = next;
            next.prev = previous;
        }
 
        this.head.prev = foundNode;
        foundNode.next = this.head;
        foundNode.prev = null;
        this.head = foundNode;
 
        return foundNode;      
}

 

 

 

Reference

 

LRU 구현 

:progressivecoder.com/lru-cache-implementation-using-javascript-linked-list-and-objects/

 

LRU Cache 개념이해하기

: medium.com/dsinjs/implementing-lru-cache-in-javascript-94ba6755cda9

: doublesprogramming.tistory.com/254