자바 캐시 알고리즘

1. 캐시 알고리즘이란?

   - 메모리의 캐시를 효율적으로 활용하여 데이터 접근 속도를 향상시킨다.

   - 캐시는 데이터를 임시로 저장하여 빠르게 읽기/쓰기가 가능하다.

 

2. 캐시 알고리즘 종류

   1) LRU (Least Recently Used): 가장 오래 전에 사용되지 않은 데이터를 캐시에서 제거하는 알고리즘이다.

    최근에 사용된 데이터가 캐시에 오래 남아 있고, 오랫동안 사용되지 않은 데이터는 빠르게 제거된다.

    자바의 LinkedHashMap 클래스에서 LRU 알고리즘을 구현하여 사용할 수 있다.

    메모리에 남아 있는 캐시 중 가장 오랫동안 사용되지 않은 캐시를 새로운 캐시로 교체한다.

   2) LFU (Least Frequently Used): 사용 빈도가 가장 낮은 데이터를 캐시에서 제거하는 알고리즘이다.

   자주 사용되는 데이터는 캐시에 오래 남아 있고, 사용 빈도가 낮은 데이터는 빠르게 제거한다.

   3) FIFO (First-In-First-Out): 가장 먼저 캐시에 들어온 데이터를 제거하는 알고리즘으로, 캐시에 들어온 순서대로 데이터가 제거된다.

   4) MRU (Most Recently Used): 가장 최근에 사용된 데이터를 캐시에 유지하는 알고리즘으로, LRU와 반대로 가장 최근에 사용된 데이터를 오래 유지한다.

   5) ARC (Adaptive Replacement Cache): LRU와 LFU 알고리즘을 결합한 알고리즘으로, 최근 사용 패턴에 따라 LRU와 LFU를 자동으로 조절하여 더 효율적으로 캐시를 관리한다.

 

3. LRU 

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // 세 번째 인자를 true로 설정하면 접근 순서대로 정렬하는 accessOrder를 사용합니다.
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // LinkedHashMap의 removeEldestEntry 메서드를 오버라이드하여 가장 오래된 엔트리를 제거하는 로직을 구현합니다.
        return size() > capacity;
    }

    public static void main(String[] args) {
        // LRU 캐시의 최대 용량을 3으로 설정
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);

        // 데이터 추가
        lruCache.put(1, "Apple");
        lruCache.put(2, "Banana");
        lruCache.put(3, "Orange");

        // 데이터 조회
        System.out.println(lruCache.get(1)); // Apple

        // 새로운 데이터 추가 (가장 오래된 2, Banana가 자동으로 제거됨)
        lruCache.put(4, "Grapes");

        // 전체 데이터 출력
        System.out.println(lruCache); // {1=Apple, 3=Orange, 4=Grapes}
    }
}

생성자에서 용량(capacity)과 로드 팩터(load factor) 그리고 accessOrder를 true로 설정해서 LRU 캐시의 특성을 가지게 한다.
removeEldestEntry 메서드는 가장 오래된 항목을 제거할지 여부를 선언한다. 캐시 크기가 용량을 초과하면 가장 오래된 엔트리를 제거한다.
main 메서드에서는 LRUCache 인스턴스를 생성하고, 데이터를 추가하고 조회한 후 새로운 데이터를 추가하여 LRU 캐시의 동작을 보여준다.

 

4. LFU

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

public class LFUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    private final Map<K, Integer> frequencyMap; // 각 항목의 사용 빈도를 기록하는 맵

    public LFUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
        this.frequencyMap = new LinkedHashMap<>(capacity, 0.75f, true);
    }

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

    @Override
    public V get(Object key) {
        V value = super.get(key);
        if (value != null) {
            frequencyMap.put((K) key, frequencyMap.getOrDefault(key, 0) + 1);
        }
        return value;
    }

    public static void main(String[] args) {
        int capacity = 3;
        LFUCache<Integer, String> lfuCache = new LFUCache<>(capacity);

        lfuCache.put(1, "One");
        lfuCache.put(2, "Two");
        lfuCache.put(3, "Three");

        System.out.println(lfuCache.get(2)); // "Two"
        System.out.println(lfuCache.get(1)); // "One"

        lfuCache.put(4, "Four"); // 용량 초과로 인해 가장 적게 사용된 3, Three가 제거됨

        System.out.println(lfuCache); // 출력: {2=Two, 1=One, 4=Four}
        System.out.println(lfuCache.frequencyMap); // 출력: {2=1, 1=1, 3=2, 4=1}
    }
}

frequencyMap은 각 항목의 카운트를 추적하기 위한 자료구조다. 

get 메서드를 호출할 때마다 해당 항목의 사용 빈도를 증가시키고, 용량 초과 시 가장 적게 사용된 항목을 제거한다. frequencyMap을 출력해보면 카운트를 확인할 수 있다.

 

5. LRU  vs LFU

   - LFU를 사용하는 경우 : 데이터 중 어떤 것이 자주 사용되고 어떤 것이 드믈게 사용되는지 파악하는게 중요한 경우에 LFU 사용한다.

 

   - LRU를 사용하는 경우 : 가장 최근에 사용된 데이터가 더 자주 다시 사용될 가능성이 높은 경우에 LRU 사용한다.