LRU cache 구현

페이지 교체 알고리즘에 사용되는 LRU 알고리즘을 double linked list 방식으로 구현해보겠다.

페이지 교체시 LRU 알고리즘은 가장 오래전에 참조한 페이지를 희생 페이지로 선택한다. 이를 구현하기 위해서는 여러 방법이 있겠으나 필자는 아래와 같은 방법으로 구현할 것이다.

• get 연산: 데이터를 참조하는 연산이다. 참조된 데이터는 가장 최근에 참조되었다고 표시해야한다.
• put 연산: 데이터를 삽입하는 연산이다. 새로 삽입한 데이터는 가장 최근에 참조되었다고 표시해야한다.

LinkedHashMap

이를 구현하기 위해서 어떤 자료구조가 적절할까? 바로 LinkedHashMap이다. LinkedHashMap는 입력된 순서대로 key가 보장된다. 또한 get 연산을 수행하면 해당 노드를 가장 후미에 위치시킨다. 실제로 jdk7u-jdk에서 LinkedHashMap 코드를 보면 아래와 같이 get 연산 수행 후 e.recordAccess(this)를 호출한다. 안드로이드 SDK에서는 구체적인 구현사항은 조금 다를 뿐 알고리즘은 동일하다.

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}

// ...

void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}

구현

먼저 선언부이다. 최대 크기를 가져야 하기 때문에 maxSize가 존재하고, 현재 데이터들의 크기를 상수 시간만에 얻기 위해 size가 있으며, key, value 데이터를 저장하기 위해 LinkedHashMap이 있다. 이때 꼭 LinkedHashMap의 accessOrder 인자로 true를 전달해야한다. 그래야 순서가 보장된다.

open class LruCache<K, V>(
    private val maxSize: Int
) {
    private var size: Int = 0
    private val map: LinkedHashMap<K, V> = LinkedHashMap(0, 0.75f, true)

    init {
        require(maxSize > 0)
    }

    // ...
}

get 연산은 LinkedHashMap의 도움을 받아 간단히 구현할 수 있다.

fun get(key: K): V? {
    return map[key]
}

put 연산은 고민이 필요하다. 데이터를 추가하였을 때 최대 크기를 초과하는 경우 최대 크기를 넘지 않을 때까지 가장 참조한지 오래된 데이터를 제거해야한다. 이는 trimToSize를 구현하여 해결할 수 있다. trimToSize는 map에서 가장 앞쪽의 데이터를 가장 참조한지 오래된 데이터로 취급하여 제거한다. 그 이유는 앞서 설명한대로 특정 데이터는 get 혹은 put 연산 후 리스트의 가장 후미에 위치되기 때문이다.

fun put(key: K, value: V) {
    val previous = map.put(key, value)
    if (previous != null) {
        size -= safeSizeOf(key, previous)
    }
    size += safeSizeOf(key, value)
    trimToSize(maxSize)
}

private fun trimToSize(maxSize: Int) {
    while (true) {
        check(size >= 0)
        check(!(map.isEmpty() && size != 0))

        if (size <= maxSize || map.isEmpty()) {
            return
        }

        val iterator = map.iterator().next()
        val key = iterator.key
        val value = iterator.value
        val sizeOfKey = safeSizeOf(key, value)
        size -= sizeOfKey
        map.remove(key)
    }
}

위의 코드를 보면 safeSizeOf 함수를 볼 수 있는데, 이는 특정 key, value를 가진 데이터의 크기를 개발자가 특정할 수 있도록 도와준다.

private fun safeSizeOf(key: K, value: V): Int {
    val sizeOfKey = sizeOf(key, value)
    check(sizeOfKey > 0)
    return sizeOfKey
}

open fun sizeOf(key: K, value: V): Int {
    return 1
}

위의 코드를 모아 아래와 같은 클래스를 만들 수 있다.

open class LruCache<K, V>(
    private val maxSize: Int
) {
    private var size: Int = 0
    private val map: LinkedHashMap<K, V> = LinkedHashMap(0, 0.75f, true)

    init {
        require(maxSize > 0)
    }

    fun get(key: K): V? {
        return map[key]
    }

    fun put(key: K, value: V) {
        val previous = map.put(key, value)
        if (previous != null) {
            size -= safeSizeOf(key, previous)
        }
        size += safeSizeOf(key, value)
        trimToSize(maxSize)
    }

    private fun trimToSize(maxSize: Int) {
        while (true) {
            check(size >= 0)
            check(!(map.isEmpty() && size != 0))

            if (size <= maxSize || map.isEmpty()) {
                return
            }

            val iterator = map.iterator().next()
            val key = iterator.key
            val value = iterator.value
            val sizeOfKey = safeSizeOf(key, value)
            size -= sizeOfKey
            map.remove(key)
        }
    }

    private fun safeSizeOf(key: K, value: V): Int {
        val sizeOfKey = sizeOf(key, value)
        check(sizeOfKey > 0)
        return sizeOfKey
    }

    open fun sizeOf(key: K, value: V): Int {
        return 1
    }
}

코드를 테스트해보자. 최대 크기 3인 캐시에 a, b, c, d를 순차적으로 넣으니 a가 가장 오래전에 참조되었기 때문에 삭제된 모습이다. 그 후 b를 참조하고 e를 넣으면 캐시에는 가장 오래전에 참조된 c가 삭제된다.

fun main() {
    val cache = LruCache<String, Int>(3)

    cache.put("a", 1)
    cache.put("b", 2)
    cache.put("c", 3)
    cache.put("d", 4)

    println(cache.get("a")) // null

    cache.get("b")
    cache.put("e", 5)

    println(cache.get("b")) // 2
    println(cache.get("c")) // null
}

활용

안드로이드에서는 Glide가 이미지 캐시를 위해 이 알고리즘을 사용한다고 한다. 앱에서 그리드 뷰나 리스트 뷰와 같은 곳에서 이미지가 보일 때 해당 이미지는 다시 로드될 가능성이 높다. 이때마다 새롭게 비트맵을 로드하기 보다는 앞서 설명한 LRU cache를 사용한다면 더 빠르게 이미지를 로드할 수 있다.

절대적인 캐시 크기는 없으며 앱마다 아래와 같은 사항을 고민하여 캐시 크기를 결정해야한다.

• 액티비티 및 애플리케이션의 나머지 부분이 얼마나 많은 메모리를 사용하나?
• 한 번에 몇 개의 이미지가 화면에 표시되나? 화면에 표시할 준비가 되어야 할 이미지 수는 몇 개인가?
• 기기의 화면 크기와 밀도는 어떻게 되나?
• 비트맵의 크기와 구성은 어떻게 되며 그에 따른 각각의 메모리 사용량은 어떻게 되나?
• 이미지는 얼마나 자주 액세스되나? 다른 이미지보다 더 자주 액세스되는 이미지가 있나? 그런 경우 특정 항목을 항상 메모리에 두거나 서로 다른 그룹의 비트맵에 여러 개의 LruCache 객체를 둘 수 있다.
• 품질과 수량의 균형을 맞출 수 있나? 때로 더 낮은 품질의 비트맵을 다수 저장하여 잠재적으로 다른 백그라운드 작업에 더 높은 품질 버전을 로드할 수 있도록 하는 것이 더 유용할 수 있다.

캐시가 너무 작으면 아무런 이점 없이 오버헤드만 발생하고, 반대로 캐시가 너무 크면 OutOfMemory 예외가 발생할 수 있고 앱에 필요한 메모리가 부족할 수 있다.

OS에서는?

운영체제에서는 페이지 교체 알고리즘인 LRU를 구현할 때 double linked list 방식을 사용하지 않는다. 그 이유는 double linked list로 페이지 교체 알고리즘인 LRU를 구현하기 위해서는 TLB 이상의 하드웨어 지원이 있어야 하다. 메모리 참조가 발생할 때마다 node를 이동시키기 위해서 페이징 테이블에 쓰기 연산이 필요하다. 이러한 작업을 소프트웨어로 구현하기 위해 인터럽트를 사용한다면 오버헤드가 상당하다.

따라서 운영체제는 참조 비트를 둔 LRU 근사 알고리즘을 사용한다. 참조 비트는 페이지 테이블에 있는 각 항목과 대응되며 시스템에서 하드웨어 지원을 해준다. 때문에 double linked list 방식에 비해 속도가 빠르다.

대표적으로 Clock 알고리즘이 있다. 참조 비트가 0이면 페이지를 교체하고 1이면 참조 비트를 0으로 수정하고 다음 페이지로 넘어간다. 이를 순환 큐로 구현한다. 최악의 경우 모든 참조 비트가 1인 경우 포인터는 큐를 한 바퀴 돈다.