[Android] LRU Cache 살펴보기

최우성

Published in

삼치 스터디

6 min readJun 23, 2023

Glide를 사용하면서, 내부적으로 LRU Cache를 사용한다고 얘기를 많이 들어봤을것입니다.
Android에서는 이를 Collection의 한 형태로 제공하고 있습니다.

한번 내부를 뜯어보도록 합시다.

LRU Cache의 기본적인 개념

LRU는 Least Recently Used, 최근에 사용되지 않는 페이지를 교체하는 알고리즘 입니다.
LRU Cache는 객체를 생성할때, size를 고정적으로 정해야합니다

그리고 데이터가 추가되어 사이즈가 넘었을때,가장 오래된 데이터를 삭제시킵니다.

그렇다면 저장되어 있는 녀석을 읽는다면 어떻게 될까요?
get()을 해서 읽는다면 해당 데이터는 최근으로(가장 뒤) 이동하게 됩니다.

이렇게 주로 쓰이지 않는 데이터는 삭제시키고, 주로 쓰이는 데이터는 계속 머무르게 됩니다.

LRU Cache의 목적

Cache란 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 장소를 가리킵니다.
그렇다면 자주 사용되는 데이터를 저장해야겠죠? LRU는 이를 처리하기 위한 알고리즘 입니다.
가장 오랫동안 참조되지 않는 녀석을 캐시에서 제거하고, 반복되는 녀석들만 남겨서 히트율(캐시에서 재사용 된것을 히트했다고 말합니다.)을 높이는것 이죠.

LRU Cache의 내부구조

Android에서 LRU Cache는 LinkedHashMap으로 구현됩니다.
그렇다면 Linked HashMap을 알아볼까요?

Linked HashMap이란?

LinkedHashMap 은 HashMap과 다르게 순서를 보장할때 쓰입니다.

일반 HashMap에 비해 만드는 속도가 약간 느리긴 하지만, 그이외에는 읽기와 접근이 더 빠르다고 알려져 있습니다.

어떻게 순서가 보장될 수 있을까요?

바로 HashMap과 Double Linked List를 같이 사용하고 있기 때문입니다.

버킷안에 데이터와 Node를 저장하고, 다음 위치를 저장하고 있기때문에 iterate시 순서를 보장하는것이죠.

또 재밌는 점은 LRUCache 의 최근에 사용된 녀석이 뒤로 이동한다는 성질은, 바로 Linked HashMap에서 나옵니다.

정확히 말하자면 Linked HashMap은 생성시, accessOrder라는 녀석을 인자로 받는데 이녀석이 true임에따라, 접근하는 녀석들이 뒤로 이동하게 됩니다.
아래와 같이 Lru Cache는 기본적으로 true로 되어있습니다.

cache.put("A", 0) // [A]
    cache.put("B", 0) // [A, B]
    cache.put("C", 0) // [A, B, C]
    cache.put("D", 0) // [A, B, C, D]
    cache.put("E", 0) // [A, B, C, D, E] - A부터 E까지 캐싱 완료
    cache.put("F", 0) // [B, C, D, E, F] - F를 캐싱하면, A는 제거됨
    cache.put("D", 0) // [B, C, E, F, D] - D를 다시 캐싱하면 최근 참조된 상태로 변경
    println(cache.snapshot().keys)
    cache.get("C") // [B, E, F, D, C] - C를 통해 캐시된 데이터 접근시 최근 참조된 상태로 변경
    println(cache.snapshot().keys)
    cache.get("B")
    println(cache.snapshot().keys)
    
// result
[B, C, E, F, D]
// C가 뒤로 이동했다. 
[B, E, F, D, C]
// B가 뒤로 이동했다.
[E, F, D, C, B]