LRU 캐시

LRU(Least Recently Used) 캐시는 고정된 용량을 가진 자료구조로, 용량이 초과되면 가장 오래 전에 접근한 항목을 제거합니다. 해시 맵을 통한 키 조회와 이중 연결 리스트(doubly linked list)를 활용한 접근 순서 추적을 결합하여, 조회와 삽입 모두 O(1) 시간 복잡도를 제공합니다. LRU 캐시는 이미지 로딩 라이브러리, 데이터베이스 쿼리 캐싱, 그리고 안드로이드 플랫폼 전반의 메모리 관리에서 핵심적인 역할을 합니다. 특히 안드로이드 면접에서 캐싱 관련 질문은 빈번하게 출제되므로, 내부 동작 원리를 정확히 이해해 두시는 것이 중요합니다.

이번 면접 질문을 통하여 아래 내용들을 학습하실 수 있습니다.

• LRU 캐시의 제거 전략(eviction strategy)과 자료구조 설계를 설명할 수 있습니다.
• 안드로이드의 LruCache 클래스가 어떻게 동작하고 어떤 방식으로 사용되는지 파악할 수 있습니다.
• LinkedHashMap을 사용하여 기본적인 LRU 캐시를 직접 구현할 수 있습니다.
• 안드로이드 라이브러리 및 프레임워크에서 LRU 캐싱이 실제로 어떻게 활용되는지 파악할 수 있습니다.
• 용량 기반 제거(capacity based eviction)와 시간 기반 만료(time based expiration)의 차이를 구분할 수 있습니다.

LRU 캐시의 동작 원리

LRU 캐시는 두 가지 핵심 불변 조건(invariant)을 유지합니다. 첫째, 모든 항목은 해시 맵을 통해 상수 시간 내에 키로 조회할 수 있어야 합니다. 둘째, 이중 연결 리스트를 통해 항목들이 접근 시점 순서대로 정렬되어 있어야 합니다. 항목에 접근하거나 새로 삽입하면 해당 항목은 리스트의 맨 앞(head)으로 이동합니다. 캐시 용량이 초과되면, 리스트의 맨 뒤(tail)에 있는 항목이 가장 오래 전에 사용된 것이므로 제거 대상이 됩니다.

이러한 구조 덕분에 get, put, 그리고 제거 연산 모두 O(1) 성능을 제공할 수 있습니다. 해시 맵은 노드에 대한 직접 접근을 가능하게 하며, 연결 리스트는 노드를 이동시킬 때 단 4개의 포인터만 갱신하면 되므로 상수 시간 내에 재정렬이 이루어집니다.

제거 정책은 결정적(deterministic)입니다. 가장 오래 접근되지 않은 항목이 항상 먼저 제거되므로, LRU 캐시는 예측 가능하고 동작을 추론하기 쉽습니다. 이 특성은 캐시 관련 성능 문제를 디버깅할 때 매우 유용합니다. 다만 트레이드오프도 존재합니다. LRU는 접근 빈도(frequency)를 고려하지 않으므로, 오래 전에 한 번만 접근한 항목과 천 번 접근한 항목이 동일하게 취급됩니다. 더 최근에 접근된 항목이 들어오면, 빈도와 관계없이 기존 항목이 밀려나게 되는 것입니다.

LinkedHashMap을 활용한 구현

코틀린의 LinkedHashMap은 생성자에서 accessOrder 매개변수를 true로 설정하면 접근 순서 추적을 지원합니다. 이 특성 덕분에 LRU 캐시를 구현하는 데 매우 적합한 기반 자료구조가 됩니다.

class LruCache<K, V>(private val capacity: Int) {
    // accessOrder = true로 설정하여 접근 순서 기반 정렬 활성화
    private val map = LinkedHashMap<K, V>(
        capacity, 0.75f, true
    )

    fun get(key: K): V? = map[key]

    fun put(key: K, value: V) {
        if (map.size >= capacity && !map.containsKey(key)) {
            // 가장 오래 전에 접근된 항목 (이터레이터의 첫 번째)을 제거
            val eldest = map.entries.iterator().next().key
            map.remove(eldest)
        }
        map[key] = value
    }
}

accessOrder가 true이면, get 또는 put이 호출될 때마다 접근한 항목이 이터레이션 순서의 맨 끝으로 이동합니다. 따라서 이터레이터의 첫 번째 항목이 항상 가장 오래 전에 사용된 항목이 됩니다. 삽입 시 용량을 초과하면 해당 항목을 제거하여 캐시 크기를 유지합니다.

안드로이드의 LruCache 클래스

안드로이드 SDK는 android.util.LruCache를 제공하며, 내부적으로 LinkedHashMap을 감싸서 스레드 안전한 접근과 크기 기반 제거 정책을 제공합니다. 단순히 항목 수를 세는 대신, 오버라이드 가능한 sizeOf 메서드를 통해 전체 크기를 추적하는 것이 특징입니다.