1) 정의
LRU(Least Recently Used)는 캐시 교체 알고리즘의 하나다.
말 그대로 가장 오랫동안 사용되지 않은 항목을 먼저 제거한다.
즉, 최근에 쓰인 데이터는 앞으로도 쓸 가능성이 높고, 오래 안 쓰인 데이터는 다시 쓸 확률이 낮다고 가정하는 방식이다.
이 원리를 기반으로 제한된 저장소(메모리 캐시, 디스크 캐시 등)의 크기를 관리한다.
2) 동작 원리
캐시에 접근할 때마다 해당 항목을 "가장 최근에 사용됨"으로 표시한다.
캐시가 가득 찼을 때 새로운 항목을 넣으려 하면,
가장 오래 사용되지 않은 항목(least recently used)을 찾아서 제거한다.
새로운 항목을 삽입하고, 이를 최근 사용된 것으로 표시한다.
이 과정을 반복하면서 캐시는 항상 최근 사용된 항목들을 유지한다.
3) 자료구조 구현
일반적으로 이중 연결 리스트(Doubly Linked List)와 해시맵(HashMap)을 조합하여 구현한다.
해시맵: O(1) 시간에 키를 찾아서 노드를 얻는다.
연결 리스트: 노드를 앞으로 옮기거나 뒤에서 제거할 때 O(1)로 처리한다.
이 조합으로 조회, 삽입, 삭제 모두 평균 O(1) 시간 복잡도를 달성한다.
4) 캐시에서의 LRU
Flutter의 PaintingBinding.instance.imageCache 역시 LRU 정책을 따른다.
캐시에 저장된 이미지가 많아져서 maximumSize(개수)나 maximumSizeBytes(용량) 상한을 넘으면,
가장 오래 안 쓰인 이미지부터 차례로 제거한다.
이렇게 해서 자주 쓰이는 이미지(최근 접근된 이미지)는 계속 캐시에 남게 된다.
5) 장단점
장점
구현이 비교적 단순하다.
“지역성(Locality)” 원리를 활용해 실제 워크로드에서 효율이 좋다.
단점
데이터 접근 패턴이 특정 방식(예: 순환 접근)일 경우 효율이 떨어질 수 있다.
모든 접근 시점을 기록해야 하므로 구현에 추가 자료구조가 필요하다.
6) 예시
캐시 크기가 3개라고 가정한다.
순서대로 항목 A, B, C를 넣으면 캐시는 [A, B, C]다.
D를 넣으려 하면 캐시가 가득 찼으므로, 가장 오래 안 쓰인 A가 제거되고 [B, C, D]가 된다.
이후 B를 다시 접근하면 B가 "최근 사용"으로 올라가서 [C, D, B] 순서가 된다.
다음에 E를 넣으면 C가 제거되고 [D, B, E]가 된다.
7) 실제 사용 사례
운영체제의 페이지 교체 알고리즘
브라우저의 탭/리소스 캐시
DB 쿼리 캐시
Flutter ImageCache (PaintingBinding.instance.imageCache)
