캐싱

캐싱은 자료를 임시 메모리에 저장하는 과정으로 추후에 해당 자료가 다시 필요할 때 쉽게 해당 자료를 얻을 수 있다.

캐시 설계는 주로 두 가지 요소를 고려한다.

1. 시간적 지역성 : 최근에 접근한 메모리 위치를 다시 접근할 가능성이 높다.

2. 공간적 지역성 : 최근에 접근한 메모리 위치 주변의 위치를 다시 접근할 가능성이 높다.

LFU(최소 빈도 사용) 캐싱

LFU 캐싱은 운영체제가 메모리를 관리하기 위해 사용하는 캐싱 알고리즘이다. 운영체제는 어떤 블록이 메모리에서 참조된 횟수를 관리한다. 설계상 캐시가 자신의 한계를 초과하는 경우 운영체제는 가장 참조 빈도가 낮은 항목을 삭제한다. 

직관적인 접근법처럼 보이지만 메모리의 항목이 단시간에 반복적으로 참조된 다음 이후에 접근을 하지 않는 경우 이상적인 접근법이 아니다. 이러한 예로는 모바일 키보드 앱이 있다.

set, get 어려워

 

LFU 기본

function LFUNode(key, value) {
    this.prev = null;
    this.next = null;
    this.key = key;
    this.data = value;
    this.freqCount = 1;
}

function LFUDoublyLinkedList() {
    this.head = new LFUNode('buffer head', null);
    this.tail = new LFUNode('buffer tail', null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
}

function LFUCache(capacity) {
    this.keys = {}; // stores LFUNode
    this.freq = {}; // stores LFUDoublyLinkedList
    this.capacity = capacity;
    this.minFreq = 0;
    this.size = 0;
}

삽입 제거(삽입은 헤드, 제거는 테일)

LFUDoublyLinkedList.prototype.insertAtHead = function(node) {
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
    node.prev = this.head;
    this.size++;
}

LFUDoublyLinkedList.prototype.removeAtTail = function() {
    var oldTail = this.tail.prev;
    var prev = this.tail.prev;
    prev.prev.next = this.tail;
    this.tail.prev = prev.prev;
    this.size--;
    return oldTail;
}

LFUDoublyLinkedList.prototype.removeNode = function(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
    this.size--
}

LFU set 구현

LFUCache.prototype.set = function(key, value) {
    var node = this.keys[key];

    if (node == undefined) {
        node = new LFUNode(key, value);

        this.keys[key] = node;

        if (this.size != this.capacity) {
            // insert without deleting
            if (this.freq[1] === undefined) {
                this.freq[1] = new LFUDoublyLinkedList();
            }
            this.freq[1].insertAtHead(node);
            this.size++;
        } else {
            // delete and insert
            var oldTail = this.freq[this.minFreq].removeAtTail();
            delete this.keys[oldTail.key];

            if (this.freq[1] === undefined) {
                this.freq[1] = new LFUDoublyLinkedList();
            }

            this.freq[1].insertAtHead(node);
        }
        this.minFreq = 1;
    } else {
        var oldFreqCount = node.freqCount;
        node.data = value;
        node.freqCount++;

        this.freq[oldFreqCount].removeNode(node);

        if (this.freq[node.freqCount] === undefined) {
            this.freq[node.freqCount] = new LFUDoublyLinkedList();
        }

        this.freq[node.freqCount].insertAtHead(node);

        if (oldFreqCount == this.minFreq && Object.keys(this.freq[oldFreqCount]).size == 0) {
            this.minFreq++;
        }

    }
}

LFU get 구현

LFUCache.prototype.get = function(key) {
    var node = this.keys[key];

    if (node == undefined) {
        return null;
    } else {

        var oldFreqCount = node.freqCount;
        node.freqCount++;

        this.freq[oldFreqCount].removeNode(node);

        if (this.freq[node.freqCount] === undefined) {
            this.freq[node.freqCount] = new LFUDoublyLinkedList();
        }

        this.freq[node.freqCount].insertAtHead(node);

        if (oldFreqCount == this.minFreq && Object.keys(this.freq[oldFreqCount]).length == 0) {
            this.minFreq++;
        }
        return node.data;
    }
}


var myLFU = new LFUCache(5);
myLFU.set(1, 1); // state of myLFU.freq: {1: 1}
myLFU.set(2, 2); // state of myLFU.freq: {1: 2<->1}
myLFU.set(3, 3); // state of myLFU.freq: {1: 3<->2<->1}
myLFU.set(4, 4); // state of myLFU.freq: {1: 4<->3<->2<->1}
myLFU.set(5, 5); // state of myLFU.freq: {1: 5<->4<->3<->2<->1}
myLFU.get(1); // returns 1, state of myLFU.freq: {1: 5<->4<->3<->2, 2: 1}
myLFU.get(1); // returns 1, state of myLFU.freq: {1: 5<->4<->3<->2, 3: 1}
myLFU.get(1); // returns 1, state of myLFU.freq: {1: 5<->4<->3<->2, 4: 1}
myLFU.set(6, 6); // state of myLFU.freq: {1: 6<->5<->4<->3, 4: 1}
myLFU.get(6); // state of myLFU.freq: {1: 5<->4<->3, 4: 1, 2: 6}

LRU(가장 오래전 사용) 캐싱

LRU 캐싱은 가장 오래된 항목을 먼저 제거하는 캐싱 알고리즘이다. 따라서 교체될 항목은 가장 오래전에 접근한 항목이다. 캐시의 항목에 접근하면 해당 항목은 리스트의 뒤로 이동한다. 캐시가 없는 항목에 접근하면 가장 앞에 있는 항목이 제거되고 신규 항목이 리스트의 가장 뒤에 삽입된다.

 

LUR 기본

function DLLNode(key, data) {
  this.key = key;
  this.data = data;
  this.next = null;
  this.prev = null;
}

function LRUCache(capacity) {
  this.keys = {};
  this.capacity = capacity;
  this.head = new DLLNode("", null);
  this.tail = new DLLNode("", null);
  this.head.next = this.tail;
  this.tail.prev = this.head;
}

삽입, 제거

LRUCache.prototype.removeNode = function (node) {
  var prev = node.prev,
    next = node.next;
  prev.next = next;
  next.prev = prev;
};

LRUCache.prototype.addNode = function (node) {
  var realTail = this.tail.prev;
  realTail.next = node;

  this.tail.prev = node;
  node.prev = realTail;
  node.next = this.tail;
};

set

LRUCache.prototype.set = function (key, value) {
  var node = this.keys[key];
  if (node) {
    this.removeNode(node);
  }

  var newNode = new DLLNode(key, value);

  this.addNode(newNode);
  this.keys[key] = newNode;

  // evict a node
  if (Object.keys(this.keys).length > this.capacity) {
    var realHead = this.head.next;
    this.removeNode(realHead);
    delete this.keys[realHead.key];
  }
};

 get

LRUCache.prototype.get = function (key) {
  var node = this.keys[key];
  if (node == undefined) {
    return null;
  } else {
    this.removeNode(node);
    this.addNode(node);
    return node.data;
  }
};

var myLRU = new LRUCache(5);

myLRU.set(1, 1); // 1
myLRU.set(2, 2); // 1 <-> 2
myLRU.set(3, 3); // 1 <-> 2 <-> 3
myLRU.set(4, 4); // 1 <-> 2 <-> 3 <-> 4
myLRU.set(5, 5); // 1 <-> 2 <-> 3 <-> 4 <-> 5

myLRU.get(1); // 2 <-> 3 <-> 4 <-> 5 <-> 1
myLRU.get(2); // 3 <-> 4 <-> 5 <-> 1 <-> 2

myLRU.set(6, 6); // 4 <-> 5 <-> 1 <-> 2 <-> 6
myLRU.set(7, 7); // 5 <-> 1 <-> 2 <-> 6 <-> 7
myLRU.set(8, 8); // 1 <-> 2 <-> 6 <-> 7 <-> 8

 

캐싱 요약

최적 : 구현 불가능

LFU : 어떤 자료가 특정 시점에 자주 사용된 경우 성능이 떨어짐

LRU : 이중 연결 리스트와 해시맵을 사용