LRU Cache — 개념, 제거 알고리즘 및 작동 방식

LRU Cache란?

LRU Cache(Least Recently Used Cache)는 제한된 수의 요소를 저장하고 가장 적게 액세스된 요소를 자동으로 제거하는 고정 크기 데이터 구조입니다. 애플리케이션이 요소를 요청하면 해당 요소는 캐시의 “새로운” 부분으로 이동하고, 오랫동안 사용되지 않은 요소는 끝으로 밀려나 한계에 도달하면 제거됩니다.

“Least Recently Used”라는 이름은 제거 정책을 설명합니다: 저장된 모든 요소 중 가장 오랫동안 사용되지 않은 요소가 제거됩니다. 이는 참조의 지역성(locality of reference) 가정에 기반합니다 — 최근에 요청된 데이터는 다시 필요할 가능성이 매우 높습니다. 이것이 LRU가 대부분의 애플리케이션에 가장 효과적인 캐싱 전략 중 하나로 간주되는 이유입니다.

클래식 LRU Cache 구현에는 두 가지 데이터 구조가 필요합니다: 키로 모든 요소에 O(1) 액세스하기 위한 해시 테이블과 사용 순서를 추적하기 위한 이중 연결 리스트입니다. 해시 테이블은 리스트 노드에 대한 참조를 저장하고, 리스트는 가장 새로운 요소(헤드)에서 가장 오래된 요소(테일)까지 순서를 유지합니다.

LRU Cache 기본 작업

get(key) 작업은 키가 해시 테이블에 존재하는지 확인합니다. 요소가 발견되면 리스트의 헤드로 이동(가장 최신이 됨)하고 해당 값이 반환됩니다. 발견되지 않으면 null이 반환되거나 예외가 발생합니다. put(key, value) 작업은 새 요소를 삽입합니다: 키가 이미 존재하면 값이 업데이트되고 요소가 헤드로 이동합니다. 캐시가 가득 찬 경우, 삽입 전에 테일 요소가 제거됩니다. 모든 작업은 상수 시간 O(1)으로 실행됩니다.

LRU Cache 작동 방식

LRU Cache 알고리즘은 두 가지 원칙에 기반합니다: 시간 순서 액세스 카운팅과 오버플로우 시 제거 메커니즘입니다. 각 요소는 이중 연결 리스트 노드에 저장되며, 이러한 노드에 대한 포인터는 해시 테이블에 유지됩니다. 각 액세스 시 요소는 현재 위치에서 분리되어 리스트의 헤드에 삽입됩니다.

캐시 크기가 최대값(maxSize)에 도달하고 새 요소 삽입 요청이 들어오면, 알고리즘은 이중 연결 리스트의 테일 요소를 제거합니다 — 이것이 가장 최근에 사용되지 않은 요소입니다. 제거 후 새 요소를 위한 공간이 확보되며, 헤드에 삽입됩니다. 해시 테이블은 그에 따라 업데이트됩니다: 이전 키가 제거되고 새 키가 추가됩니다.

LRU의 특징은 순환 반복이 있는 액세스 패턴에 대한 민감성입니다. 애플리케이션이 캐시 크기보다 큰 데이터 세트를 주기적으로 액세스하는 경우, LRU는 스래싱(thrashing) — 각 새 요청이 이전 요청을 제거하는 빈번한 요소 교체 — 현상을 겪을 수 있습니다. 이러한 시나리오에서는 LFU(Least Frequently Used) 또는 적응형 알고리즘이 더 효과적일 수 있습니다.

캐시 크기 및 메트릭

LRU Cache 크기 선택은 메모리 소비와 히트율(성공적 액세스 비율) 간의 절충입니다. 모바일 애플리케이션의 일반적인 값: 이미지 캐시에 사용 가능한 메모리의 10~20%, 네트워크 응답 캐시에 50~200개 항목. 히트율 80~95%는 캐시가 메모리 비용을 정당화하는 좋은 지표로 간주됩니다. 모니터링을 위해 Android의 LruCache 구현에서 사용 가능한 hitCount 및 missCount 카운터가 사용됩니다.

LRU Cache 구현: HashMap + Doubly Linked List

표준 LRU Cache 구현은 해시 테이블과 이중 연결 리스트의 조합을 사용합니다. 해시 테이블은 키로 모든 노드에 O(1) 액세스를 제공하고, 이중 연결 리스트는 O(1)로 노드를 헤드로 이동하고 테일에서 제거할 수 있게 합니다. 중요한 점은 리스트가 이중 연결되어 있다는 것입니다: 이는 모든 요소를 반복하지 않고 리스트 중간에서 노드를 분리할 수 있게 합니다.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

구현에서 각 노드(Node)는 값과 이전 및 다음 노드에 대한 참조를 저장합니다. 센티널 노드 head와 tail은 경계 케이스를 단순화합니다 — 삽입 및 제거 시 null을 확인할 필요가 없습니다. get 메서드는 찾은 노드를 헤드로 이동하고, put은 오버플로우 시 테일 요소를 제거합니다. 별도의 메서드 removeKeyByValue는 노드 참조로 해시 테이블에서 키를 찾아 제거합니다.

Android의 내장 LruCache 구현

Android SDK는 android.util 패키지에 즉시 사용 가능한 LruCache 클래스를 제공하며, access-order 모드에서 LinkedHashMap을 사용하여 LRU 알고리즘을 구현합니다. 이 클래스는 스레드 안전하며, hit/miss 카운팅을 지원하고, 요소 제거 시 리소스 정리를 위한 entryRemoved 콜백을 제공합니다. 캐시 크기는 임의 단위(바이트, 요소 수)로 설정됩니다 — sizeOf 메서드를 재정의하기만 하면 됩니다.

LRU Cache vs FIFO 및 LIFO

세 알고리즘 — LRU, FIFO 및 LIFO — 모두 동일한 문제를 해결합니다: 오버플로우 시 요소를 제거하여 메모리 소비를 제한합니다. 그러나 희생자 선택에 근본적으로 다른 기준을 사용하며, 이는 다양한 시나리오에서의 효과를 결정합니다.

FIFO는 액세스 빈도와 관계없이 삽입 시간 기준으로 가장 오래된 요소를 제거합니다. 이는 오래된 요소가 여전히 관련 있는 경우 비효율적일 수 있습니다. LRU는 액세스 패턴을 고려하여 이 단점을 피합니다. LIFO는 가장 최근에 추가된 요소를 제거합니다 — 실행 취소 시나리오에는 유용하지만, 새 데이터가 이전 데이터보다 더 필요한 경우가 많기 때문에 캐싱에는 부적합합니다. LRU는 대부분의 애플리케이션에서 구현 복잡성과 히트율 간의 최적 균형으로 간주됩니다.

LRU Cache 코드 예제

다운로드한 이미지를 캐싱하기 위해 Android SDK의 내장 LruCache 클래스 사용을 살펴보겠습니다. 예제는 애플리케이션의 사용 가능한 메모리의 1/8로 캐시를 초기화하는 방법을 보여주며, 이는 이미지 캐싱에 대한 Google의 표준 권장 사항입니다.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

sizeOf 메서드는 cacheSize가 지정된 동일한 단위로 요소 크기를 반환합니다. 여기서는 킬로바이트 단위의 Bitmap 크기가 사용됩니다(rowBytes × height / 1024). 모든 요소의 sizeOf 합계가 cacheSize를 초과하면 LruCache는 자동으로 가장 최근에 사용되지 않은 Bitmap을 제거합니다. entryRemoved 콜백은 bitmap.recycle() 호출에 사용할 수 있습니다 — 제거 전 메모리를 해제합니다.

Swift에서 LRU Cache 구현

iOS에는 내장 LRU Cache 클래스가 없지만, NSCache(유사하지만 문서화되지 않은 제거 정책 사용) 또는 Dictionary + 이중 연결 리스트를 사용한 사용자 정의 구현을 통해 쉽게 구현할 수 있습니다. 아래에 설명되어 있습니다.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

이 Swift 구현에서 Node는 value, next 및 prev 필드가 있는 내부 클래스입니다. moveToHead 메서드는 노드를 현재 위치에서 분리하여 리스트의 헤드에 삽입합니다. 오버플로우 시 테일 — 가장 최근에 사용되지 않은 요소 — 가 제거됩니다. 프로덕션 환경에서는 NSLock 또는 DispatchQueue를 통한 스레드 안전성 추가가 권장됩니다.