[Java Algorithm] LRU 알고리즘이란?

LRU 알고리즘이란?

LRU 알고리즘은 Least Recently Used의 약자로 직역하자면 가장 최근에 사용되지 않은 것이라는 의미를 가지고 있다.

DB의 부하를 줄이기 위해 캐시 메모리를 사용한다. 하지만 캐시에도 용량이 존재하기 때문에 캐시 메모리 또한 관리를 해주어야 한다.

LRU 알고리즘은 캐시에서 작업할 때 가장 오랫동안 사용하지 않은 것을 제거하는 알고리즘이다.

 

Cache Hit / Miss

Cache Miss : 찾는 데이터가 캐시에 없는 상태로 해당 데이터가 추가될 경우 가장 앞에 위치하게 된다.

[1, 2, 3, 4, 5] -> 데이터 6 추가 [6, 1, 2, 3, 4]

 

Cache Hit : 찾는 데이터가 캐시에 있는 상태로 해당 데이터 앞에 있는 데이터들은 뒤로 밀리고 해당 데이터는 가장 앞에 위치하게 된다.

[6, 1, 2, 3, 4] -> 데이터 2 히트 [2, 6, 1, 3, 4]

 

구현

Java에서는 LinkedHashMap 이라는 자료구조로 쉽게 구현이 가능하다.

내부적으로 Map과 LinkedList를 사용하여 데이터의 순서를 보장하고, 생성자에서 accessOrder라는 값을 받아 접근 빈도에 따른 순서 변경을 설정해 줄 수 있다.

 

LinkedList로 구현

import java.util.LinkedList;

public class LRUList<T> {

  private final LinkedList<T> cache = new LinkedList<>();
  private int cacheSize;

  public LRUList(int cacheSize) {
    if (cacheSize <= 0) {
      throw new IllegalArgumentException("The maximum of the size should be a positive integer.");
    }
    this.cacheSize = cacheSize;
  }

  public T getData(T data) {
    // cache hit
    if(cache.remove(data)){
      cache.addFirst(data);
      // cache miss
    } else {
      int currentSize = cache.size();

      if(currentSize == cacheSize){
        cache.pollLast();
      }
      cache.addFirst(data);
    }
    return cache.getFirst();
  }

}

 

LinkedHashMap으로 구현

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUHashMap<K, V> extends LinkedHashMap<K, V> {

  private int size;

  private LRUHashMap(int size) {
    super(size, 0.75f, true);
    this.size = size;
  }

  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > size;
  }

  public static <K, V> LRUHashMap<K, V> newInstance(int size) {
    return new LRUHashMap<K, V>(size);
  }
}