[Android] Glide, Picasso 와 같은 라이브러리는 어떻게 이미지 로드를 최적화할까? — 2편 : LRU Cache 내부동작 살펴보기
지난 1편에서는 이미지를 더 낮은 해상도로 서브샘플링을 통해 더 효율적인 연산량과 메모리 사용량을 가져가는 방법에 대해 이야기했었습니다.
지난 포스팅에서도 이야기했다시피, 다운샘플링은 그자체로 상당한 컴퓨팅 자원 절약을할 수 있지만 완벽하게 최적화되진 않습니다. 이전에 로드했던 이미지 혹은 같은 이미지라도 매번 개별적으로 디코드작업을 수행해야하기 때문입니다. 이는 불필요한 컴퓨팅 자원 소비가 될 수 있고, 이미지뷰에 지속적으로 set해주는 작업으로인한 불필요한 메모리 할당이될 수 있습니다.
이를 해결하기 위해서는 이전에 로드했던 이미지(비트맵)는 메모리, 혹은 하드디스크상에 따로 저장해두고, 필요할 때마다 꺼내쓸 필요가 있습니다. 이 방식이 오늘 이야기해볼 Cache라는 기술입니다. 안드로이드에서는 이러한 비트맵의 효율적인 캐싱을 위해 LruCache<K, V> 를 제공해줍니다.
이번 포스팅은 LruCache의 내부동작에 이야기 해보려고 합니다.
LRU(Least Recently Used) Cache
LRU(Least Recently Used) 는 캐시가 최대 용량에 도달하였을 때, 가장 오랫동안 사용되지 않은 데이터부터 삭제하는 알고리즘입니다. 참조되는 데이터는 캐시 최상위로 옮겨서 참조되지 않은 데이터를 최하위로 밀어내는 방식입니다.
자주 접근하는 데이터 위주로 캐시에 남겨두기 때문에, 반복적인 데이터 접근이 필요한 안드로이드 비트맵 특성에 잘 맞는다고 생각합니다.
LruCache 내부 살펴보기
LinkedHashMap 사용
Android의 LruCache는 내부적으로 LinkedHashMap을 사용합니다. HashMap 이 아닌 LinkedHashMap 을 사용하는 다음 두가지 이유가 있었습니다.
첫 번째는 입력된 순서를 보장합니다. LinkedHashMap 은 HashMap 기존 해시맵에서 Node별로 앞, 또는 뒤에있는 노드의 주소값을 따로 저장하는 doubly-Linked 방식을 사용합니다. Node가 삽입될 때, 앞 또는 뒤의 노드의 주소값을 연결해주기 때문에, 입력 순서가 보장될 수 있습니다.
다음 코드와 같이, LinkedHashMapEntry 에서before, after를 각각 선언해주어 doubly-Linked 방법을 사용하는 것을 볼 수 있습니다.
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}두 번째는 LRU의 특성인 엑세스한 Node는 Map의 제일 뒤로 보낼 수 있습니다. LinkedHashMap 원문 주석에는 다음과 같이 마지막에 참조한 Entry는 least-recently-accessed 형태로 정렬할 수 있어 LRU 캐시 구현에 적합하다고 설명하고 있습니다.
* in which its entries were last accessed, from least-recently accessed to
* most-recently (<i>access-order</i>). This kind of map is well-suited to
* building LRU caches.해당 기능을 활성화 하려면 LinkedHashMap 의 accessOrder 플래그를 true로 설정하면 됩니다. 코드 내부적으로 해당 플래그값 여부에 따라 after, before 주소를 재지정하는 afterNodeAccess(…) 메서드를 구현하여 사용하고 있습니다. 해당 로직은 다음과 같이 get 관련 함수에 적용되어 있습니다.
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}Thread-Safe
LruCache 는 Thread-Safe 클래스입니다. LinkedHashMap 을 단일로 사용하게 될 경우 멀티쓰레딩 환경에서 동시접근시 안전성을 보장받지 못합니다. 그렇기에 LruCache 에서는 synchronized 키워드를 통해 임계영역을 만들어 동기화하는 부분을 확인할 수 있었습니다. 원문 주석에도 다음과 같이 설명되어있습니다.
trimToSize
현재 Cache 사이즈를 체크한 후, 오래된 데이터를 삭제하는 메서드입니다. put 연산이 끝날 때 해당 메서드를 호출합니다. 다음과 같이 현재 캐시 사이즈가 maxSize를 초과할 때, 가장 오래된(첫 번째) 데이터를 삭제하는 로직을 확인할 수 있습니다.
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
// 예외처리
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
// 현재 사이즈가 maxSize보다 적으면 break
if (size <= maxSize || map.isEmpty()) {
break;
}
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key); // 오래된 데이터 삭제
size -= safeSizeOf(key, value); // 사이즈 갱신
evictionCount++;
}
// entryRemoved : 데이터를 삭제했을 시점을 콜백형태로 제공하기 위해 호출.
entryRemoved(true, key, value, null);
}
}Must override `sizeOf`
LruCache 에서는 sizeOf 메서드를 통해 데이터의 size를 불러옵니다. 해당 값을 통해서 Cache의 maxSize 를 초과하는지 여부를 판별하고, 이를 통해 데이터를 삭제하거나, 삽입하기 위함입니다.
그러나 LruCache 는 제네릭을 통해 범용적으로 사용할 수 있도록 설계되었기 때문에, 데이터의 실제 size를 알 수 없습니다. 이것이 sizeOf 메서드의 기본 리턴값이 1로 되어있는 이유입니다.
protected int sizeOf(K key, V value) {
return 1;
}따라서 올바른 size를 계산하도록 하려면 LruCache를 초기화할 때, 다음과 같이 sizeOf 메서드를 실제 데이터 사이즈에 맞게 오버라이딩 해야합니다.
val cache = object : LruCache<String, Bitmap>(maxSize) {
override fun sizeOf(key: String?, value: Bitmap?): Int {
return value?.byteCount ?: 1
}
}May override `create` (Optional)
get 연산을 수행했을 때, 요청하는 데이터가 Cache에 없으면 create를 통해 기본값을 불러오고 Cache에 저장합니다. 해당 메서드 역시 제네릭의 특성상 기본값은 null 이며, 초기화 시점에 오버라이딩하면 됩니다. 해당 메서드는 synchronized 블럭 밖에서 실행되기 때문에 여러 쓰레드로부터 동시에 여러번 호출될 수 있다는 특징이 있습니다. 사용시 주의가 필요해 보입니다.
/**
* <p>The method is called without synchronization: other threads may
* access the cache while this method is executing.
*/
protected V create(K key) {
return null;
}마치며
이번 포스팅에서 LruCache에 내부동작에 대해 이야기해보았습니다. 캐시를 사용할 때 중요한 점은 maxSize를 사용하는 환경에 맞게 효율적으로 지정해야하는 것입니다. 용량이 너무 크면, OOM 위험성이 커지고, 너무 작으면 캐시 히트율이 급격히 떨어지기 때문입니다. 다음 포스팅에서는 비트맵을 직접 캐시해보고 메모리, 수행 시간 측면에서의 효율성에 대해 이야기해볼 예정입니다.
