LRU Cache 란?

안드로이드의 이미지 라이브러리에 자주 활용되는 LRU Cache에 대해 자세히 알아보고자 한다.
일반적인 알고리즘 개념부터 코틀린에서 어떻게 구현되어있는지까지 살펴보자.

LRU 알고리즘의 개념

가장 오랫동안 사용되지 않은 데이터를 우선적으로 제거하는 방식이다. (Least Recently Used Algorithm)

정해진 capacity 안에서 최근에 사용되어진 데이터를 가장 앞에 보내고, capacity가 꽉 찼을 때 새로운 값이  들어온다면

가장 오랜기간 사용되지 않은 데이터를 삭제하고 새로운 값을 넣는 방식이다.

아래 그림과 같이 테이블 안에 있는 값이 get이나 put이 되면 최상단으로 불러오게 하고,

테이블이 꽉 찼을 때 새로운 값이 들어온다면 가장 오래된 값을 제거하는 모습을 볼 수 있다. (Fig 7 참고)

https://www.geeksforgeeks.org/lru-cache-implementation/

 

글로는 이해가 어려울 수 있으므로,  가장 이해하는데 도움을 많이 준 유튜브 영상도 첨부해두겠다.

https://www.youtube.com/watch?v=HpuIrGiHwTo&t=360s

 

LRU 알고리즘의 활용처

LRU 알고리즘은 캐시에서만 사용되는 것이 아니다.

운영체제의 페이지 교체 알고리즘, 데이터베이스의 버퍼 관리 등에도 사용되어진다.

다양한 곳에서 핵심기능으로 활용되므로, 그만큼 중요한 알고리즘이라고 할 수 있다

 

LRU Cache 구현

이러한 LRU 알고리즘을 통해 캐싱을 구현한 것이 LRUCache이다.

안드로이드에선 이미지 라이브러리의 캐싱을 위해 자주 사용되곤 한다.

그렇다면  어떻게 구현되었을까? 내부 구조를 한번 살펴보고자 한다.

 

아래와 같이 LruCache<K,V>는 생성자에서 maxSize를 활용해 생성할 수 있다.

여기서 maxSize는 기본적으로 항목 개수를 의미한다.

하지만 sizeOf를 Override하면 모든 항목의 크기 합으로 계산된다.

당연하지만 sizeOf의 반환값은 중간에 변하지 않을 고정 크기여야 한다.

val cache = object : LruCache<String, Bitmap>(maxSize) {
    override fun sizeOf(key: String?, value: Bitmap?): Int {
        return value?.byteCount ?: 1
    }
}

 

그다음 map 변수를 봐보자. LruHashMap으로 구현되어있는 것을 볼 수 있다. 

그렇다면 LruHashMap의 구현을 들어가보자

아래처럼 LinkedHashMap으로 구현되어있는 것을 알 수 있다.

그렇다면 왜 LinkedHashMap을 사용하는지 생각해보자.

LruCache는 가장 최근에 사용된 것이 맨 뒤에 와야 하므로, 순서가 있어야 한다.

거기에 HashMap을 통해 조회속도를 빠르게 하기 위해, 순서가 있는 HashMap인 LinkedHashMap을 사용한 것이다. 

자바의 LinkedHashMap은 양방향 연결리스트로 구현된 Hash Map이기 때문에, LruCache를 구현하기에 적절하다. 

그림으로 본다면 다음과 같이 연결되어있다. (위가 해시테이블, 아래가 연결 리스트라고 생각하면 된다.)

더하여 LinkedHashMap에는 accessOrder라는 기능이 있다.

이는 엑세스한 노드는 맨 뒤로 보내는 기능이다.(최근에 사용했다는 의미) 

아래처럼  assessOrder가 true일때는 afterNodeAccess를 작동시키는 걸 볼 수 있다.

 

오래된 값 제거

trimToSize는 현재 Cache 사이즈 를 체크한 후, 오래된 데이터를 삭제하는 메서드이다.

put 연산이 끝날 때 해당 메서드를 호출한다.

현재 캐시 사이즈가 maxSize를 초과할 때, 가장 오래된(첫 번째) 데이터를 삭제하는 로직을 확인할 수 있다.

 

LRUCache의 멀티 스레드 안정성

LinkedHashMap을 단일로 사용하게 될 경우 멀티쓰레딩 환경에서 동시접근시 안전성을 보장받지 못한다.

따라서 LruCache는 synchronized를 통해  임계영역을 만들어 사용한다.

 

정리

이처럼 LRUCache는 연결리스트 + 해시맵인 LinkdeHashMap으로 구현되어 있다.

accessOrder등을 활용하여 LRU 알고리즘의 각종 기능을 구현하고 있고, 멀티스레드에서의 안전성도 갖추고 있다.

추가적으로 적절한 maxSize나, 라이브러리에서는 어떻게 활용하는지 찾아보고자 한다.