LRU Cache Algorithm

LRU (least recently used) Cache 알고리즘.

직역하면 '최근까지 최소로 사용되었다' 즉 사용한지 가장 오래된 데이터를 퇴출시키는 알고리즘이라 볼 수 있다.
OS의 페이지 교체 알고리즘(Page Replacement Algorithm)으로 사용되는 방식으로, 새로운 페이지를 할당 시 공간이 부족한 경우, 기존에 사용중인 페이지를 교체해야하는데, 교체시 가장 사용한지 오래된 영역의 페이지를 선정하여 교체하기위해 사용된다. 
LRU외에도 흔히아는 OPT, FIFO, LFU, NUR, SCR 등등이 있으며 OPT알고리즘의 실현 가능성이 희박하기때문에 차선으로 LRU 캐시를 사용한다.

In Memory 기반의 NoSQL인 Redis에서도 LRU 페이지 교체 알고리즘이 존재한다. 

http://redis.io/topics/lru-cache

LRU Cache의 기본적인 알고리즘.
최근까지 사용되지 않은 페이지를 교체한다.

[그림1] LRU 페이지 교체 방식

LRUCache.java
Node간 연결을 위해 Linked List를 이용하여 구현하도록 한다. Page Fault발생가 발생하여 Node의 퇴출 시, 각 Node간의 연결을 위해 사용한다.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class LRUCache {
  int capacity;
  HashMap<Integer, Node> map = new HashMap<Integer, Node>();
  Node head;
  Node end;
  public LRUCache(int capacity) {
    this.capacity = capacity;
  }
  public void remove(Node n){
    if(n.pre != null){
      n.pre.next = n.next;
    }else{
      head = n.next;
    }

    if(n.next != null){
      n.next.pre = n.pre;
    }else{
      end = n.pre;
    }
  }
  public void setHead(Node n){
    n.next = head;
    n.pre = null;

    if(head != null)
      head.pre = n;

    head = n;

    if(end == null){
      end = head;
    }
  }
  public int get(int key){
    if(map.containsKey(key)){
      Node n = map.get(key);
      remove(n);
      setHead(n);
      return n.value;
    } else {
      return -1;
    } 
  }
  public void set(int key, int value){
    if(map.containsKey(key)){
      Node n = map.get(key);
      n.value = value;
      remove(n);
      setHead(n);
    }else{
      Node n = new Node(key,value);
      System.out.println("size : " + map.size() + " , capacity : " + capacity);
      if(map.size() >= capacity){
        map.remove(end.key);
        remove(end);
      }
      setHead(n);
      map.put(key,n);
    }
  }
  public void print(){
    for(Integer key : map.keySet()){
      System.out.println( "Key: "+key+", Value: "+map.get(key).value);
    }
  }
}

Node.java

public class Node {
  int key;
  int value;
  Node pre;
  Node next;
  public Node(int key, int value){
    this.key = key;
    this.value = value;
  }
}

Main.java

public class Main {
  public static void main(String args[]){
    LRUCache cache = new LRUCache(3);
    cache.set(3,3);
    cache.print();
    System.out.println("====================================");

    cache.set(6,6);
    cache.print();
    System.out.println("====================================");

    cache.set(9,9);
    cache.print();
    System.out.println("====================================");

    cache.set(7,7);
    cache.print();
    System.out.println("====================================");

    cache.set(9,9);
    cache.print();
    System.out.println("====================================");
  }
}

결과

size : 0 , capacity : 3

Key: 3, Value: 3

====================================

size : 1 , capacity : 3

Key: 3, Value: 3

Key: 6, Value: 6

====================================

size : 2 , capacity : 3

Key: 3, Value: 3

Key: 6, Value: 6

Key: 9, Value: 9

====================================

size : 3 , capacity : 3

Key: 6, Value: 6

Key: 7, Value: 7

Key: 9, Value: 9

====================================

Key: 6, Value: 6

Key: 7, Value: 7

Key: 9, Value: 9

====================================