LRU 캐시 구현

LRU캐시란

캐시 evict 규칙을 가장 오래동안 사용하지 않는 순으로 삭제하는 것이다.

LRU캐시 구현

LinkedList와 LinkedHashMap으로 쉽게 구현이 가능하다. LinkedList보다 LinkedHashMap으로 구현한게 성능은 더 좋다.

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);
  }
}

LinkedHashMap에서 accessOrder를 true로 주면 LRU처럼 동장한다. 만약 ‘false`이면 insert되는 순서로 저장된다.

성능이 중요한 멀티쓰레딩 환경에서 LRU 캐시를 사용할 때

import java.io.Serializable;
import java.util.LinkedHashMap;
import java.util.Set;

public class LRUMap<K, V> implements Serializable {

  private static final long serialVersionUID = 99123123123L;

	// 성능 개선을 위해  accessOrder를   변경
  private final LinkedHashMap<K, V> cache = new LinkedHashMap<>(0, 0.75f, false); 

  private int cacheSize;

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

  // get과 put이 동시에 발생하므로 access에 대한 put을 별도로 진행하지 않음
  public V get(K key) {
    synchronized (cache) {
      return cache.get(key);
    }
  }

  public void put(K key, V v) {
    this.put(key, v, true);
  }

  public void put(K key, V v, boolean check) {

    if (check) {

      if (key == null || v == null) {
        throw new IllegalArgumentException("The key or the value is null.");
      }

      synchronized (cache) {

        if (cache.containsKey(key)) {
          cache.remove(key);
        } else {
          if (cache.size() >= cacheSize) {
            cache.remove(cache.keySet().iterator().next());
          }
        }

        // 테스트를 통해 삭제 후 put을 수행하는 것이 유리함을 확인함
        cache.put(key, v);
      }

    } else {

      cache.put(key, v);
    }
  }

  public void remove(K k) {
    synchronized (cache) {
      cache.remove(k);
    }
  }

  public boolean contains(K k) {
    synchronized (cache) {
      return cache.containsKey(k);
    }
  }

  public int size() {
    synchronized (cache) {
      return cache.size();
    }
  }

  public Set<K> keySet() {
    return cache.keySet();
  }

  @Override
  public String toString() {
    return "LRUMap{" +
      "cache=" + cache +
      ", cacheSize=" + cacheSize +
      '}';
  }
}