큐를 이용한 캐시 교체 알고리즘 (LRU)

1. LRU란?

LRU(Least Recently Used) 알고리즘은 가장 오랫동안 사용되지 않은 캐시 항목을 제거하여 새로운 데이터를 저장하는 캐시 교체 알고리즘이다. 이는 제한된 크기의 캐시에서 효율적인 데이터 관리를 위해 사용된다.

2. 알고리즘이 필요한 이유

• 캐시는 한정된 크기를 가지므로, 새로운 데이터를 추가할 때 불필요한 데이터를 제거해야 한다.
• 자주 사용하는 데이터를 유지하여 성능을 최적화한다.
• 운영체제의 페이지 교체, 데이터베이스의 쿼리 캐싱 등에 활용된다.

3. LRU 알고리즘 동작 방식

1. 데이터를 요청하면 캐시에 존재하는지 확인한다.
2. 존재하면 해당 데이터를 가장 최근 사용한 위치로 갱신한다.
3. 존재하지 않으면 새로운 데이터를 캐시에 추가한다.
4. 캐시 크기를 초과하면 가장 오랫동안 사용되지 않은 데이터를 제거한다.

4. 수식 표현

캐시의 상태를 (C = {c_1, c_2, ..., c_n}) 라고 할 때,

• 새로운 데이터 (x)가 들어오면:
  • ( x \in C )이면, ( x )를 가장 최근 위치로 이동
  • ( x \notin C )이면, ( |C| \geq \text{capacity} ) 인 경우, ( C )의 첫 번째 요소를 제거하고 ( x )를 추가

5. Dart 코드 구현

import 'dart:collection';

class LRUCache<K, V> {
  final int capacity;
  final LinkedHashMap<K, V> cache = LinkedHashMap();

  LRUCache(this.capacity);

  V? get(K key) {
    if (!cache.containsKey(key)) return null;
    V value = cache.remove(key)!;
    cache[key] = value;
    return value;
  }

  void put(K key, V value) {
    if (cache.containsKey(key)) {
      cache.remove(key);
    } else if (cache.length >= capacity) {
      cache.remove(cache.keys.first);
    }
    cache[key] = value;
  }

  void displayCache() {
    print("캐시 상태: \${cache.keys.toList()}");
  }
}

void main() {
  LRUCache<int, String> cache = LRUCache(3);
  cache.put(1, "A");
  cache.put(2, "B");
  cache.put(3, "C");
  cache.displayCache(); // [1, 2, 3]
  
  cache.get(1);
  cache.displayCache(); // [2, 3, 1]
  
  cache.put(4, "D");
  cache.displayCache(); // [3, 1, 4] (2가 제거됨)
}

6. 실행 결과

캐시 상태: [1, 2, 3]
캐시 상태: [2, 3, 1]
캐시 상태: [3, 1, 4]

7. LRU의 장단점

장점

• 자주 사용하는 데이터를 우선 유지하여 성능 최적화
• 데이터 접근 패턴을 반영한 효율적인 캐싱 기법

단점

• 구현 시 추가적인 데이터 구조(해시맵 + 연결 리스트) 필요
• 캐시 크기가 작을 경우 예상치 못한 성능 저하 가능

8. 마무리

LRU 알고리즘은 캐시 시스템에서 가장 많이 활용되는 방식 중 하나로, 데이터베이스, 운영체제 메모리 관리, 웹 브라우저 캐싱 등에 널리 사용된다. Dart에서 LinkedHashMap을 활용하면 쉽게 구현할 수 있다.