LRU Cache란?

캐쉬 알고리즘중 대표적인 알고리즘인 LRU에 관한 포스팅입니다.
Lru의 개념과 java의 LinkedHashMap으로 구현하기, 테스트로 검증하여 보겠습니다.

LRU

운영체제의 페이지 교체 알고리즘중 하나이며 LRU (Least Recently Used) 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.
이 알고리즘을 캐시에 적용하면 캐시의 용량 부족시 가장 오랫동안 사용되지 않은 항목을 제거하고 새로운 데이터를 입력합니다.

LinkedHashMap으로 LRU 간단 구현하기

class LruCache<String, Any>(private val maxSize: Int) :
    LinkedHashMap<String, Any>(maxSize, 0.75f, true) {

    override operator fun get(key: String): Any? {
        return super.get(key)
    } // 문법지원을 위한 override 구현하지 않으셔도 됩니디.

    override fun removeEldestEntry(eldest: Map.Entry<String, Any>): Boolean {
        return this.size > maxSize
    }
}

removeEldestEntry는 entry를 삭제해야할때 어떤 기준으로 삭제해야하는지에 대한 분기 메서드입니다.
현재의 사이즈가 maxsize보다 크면 삭제하도록 하였습니다.

Test로 검증하기

internal class LruCacheTest {
    private lateinit var maxLruCache: LruCache<String, Int>

    @BeforeEach
    fun setup() {
        maxLruCache = LruCache(maxSize = 5)
        maxLruCache["1st"] = 1
        maxLruCache["2nd"] = 2
        maxLruCache["3rd"] = 3
        maxLruCache["4th"] = 4
        maxLruCache["5th"] = 5
    }

    @Test
    fun `maxsize까지 입력된 캐시에 데이터를 넣습니다`(){
        //given //when
        maxLruCache["6th"] = 6
        //then 가장 마지막으로 접근한 1번 데이터가 사라지고 6번데이터가 입력됩니다
        assertAll(
            { assertThat(maxLruCache.size,`is`(5)) },
            { assertThat(maxLruCache["1st"],`is`(nullValue())) },
        )
    }

    @Test
    fun `lru캐시는 데이터를 삭제시 가장 마지막에 접근한 삭제합니다`(){
        //given
        maxLruCache["1st"]
        //when
        maxLruCache["6th"] = 6
        //then 1번데이터를 한번 조회하여 head순서를 head 6-1-5-4-3-2로 업데이트합니다. 마지막 2번이 삭제됩니다.
        assertAll(
            { assertThat(maxLruCache.size,`is`(5)) },
            { assertThat(maxLruCache["2nd"],`is`(nullValue())) },
        )
    }
}

실행결과입니다.

개인적으로 가장 많이쓰는 캐시알고리즘중 하나입니다.
대부분의 경우가 접근한지 오래된 데이터의 경우 새로 정보를 업데이트 해야하던지 조회조차 안된 데이터의 경우 앞으로도 조회 할 일이 많지 않은경우가 많아 정말 효율적인 캐시전략같습니다.