Cache 데이터의 저장

캐싱할 대상이 일부로 정해져 있어, 대상 부분만 캐싱하여 사용 할 수 있는 상황이 아니라면
캐시 저장소의 용량은 한정적이기 때문에 모든 데이터를 캐싱 할 수는 없고
가능한 사용될 가능성이 높은(히트율이 높은) 데이터를 캐싱하고 있는 것이 효율적 입니다.

LRU

LRU(Least Recently Used)는 운영체제 페이지 교체 알고리즘 중 하나로
페이지를 교체할 때 가장 오랫동안 사용되지 않은 페이지를 교체하는 방법입니다.

LRU Cache

LRU Cache는 운영체제의 LRU 페이지 교체 알고리즘과 유사하게,
캐시 공간이 부족할때 가장 오랫 동안 사용되지 않는 데이터는 앞으로 사용될 가능성이 가장 작다고 가정하고
가장 오랫동안 사용되지 않은 항목을 제거하고 새로운 데이터를 저장하는 방식으로 동작하는 캐시 입니다.

구현

필수 메소드

get(key) - 조회하기

• 키에 매핑되는 값이 있는지 확인
• 값이 있다면, 해당 노드의 사용 여부를 업데이트 하고 값을 반환

put(key, value) - 저장하기

• 키에 매핑되는 값이 있을때(기존에 있던 캐싱키일 경우)
  • 값 업데이트
  • 해당 노드의 사용 여부 업데이트
• 키에 매핑되는 값이 없을때(새로운 캐싱키)
  • 현재 캐시 사이즈가 지정된 사이즈 보다 작을 경우
    • 새로운 키/값 저장, 사용 여부 업데이트
  • 지정된 캐시 크키를 초과할 경우
    • 사용여부 업데이트가 가장 오래된 노드 삭제
    • 새로운 키/값 요소 저장, 사용 여부 업데이트

연결 리스트 사용

• 메소드 동작을 보면 가장 오래전에 사용된 요소를 삭제하고 새로운 노드를 삽입 할 수 있어야 하기 때문에
• 노드 간에 순서를 추적 할 수 있어야 하고 삽입, 삭제, 순서를 변경하는데 효율적이어야 합니다.
• 연결 리스트를 사용해 최근에 사용된 노드를 Head에 유지하도록 하면 최근 사용에 따라 순서를 유지하며
• 가장 최근에 사용하지 않는 노드를 마지막에 위치 시킬 수 있어 LRU Cache를 구현하는데 사용하기 적합합니다.

코드

구현 예시 코드

• Kotlin으로 작성된 코드이고
• https://leetcode.com/problems/lru-cache/solutions/173926/Kotlin-Implementation-of-LRUCache 를 참고한 코드 입니다

  class LRUCache<K, V>(private val capacity: Int) {
  
    private val map = hashMapOf<K, Node<K, V>>()
    private val head: Node<K, V> = Node()
    private val tail: Node<K, V> = Node()
  
    init {
        head.next = tail
        tail.prev = head
    }
  
    fun get(key: K): V {
        if (!map.containsKey(key)) {
            throw IllegalArgumentException("존재하지 않는 키 입니다: $key")
        }
        val node = map[key]!!
        remove(node)
        addAtHead(node)
        return node.value!!
    }
  
    fun put(key: K, value: V) {
        if (map.containsKey(key)) {
            remove(map[key]!!)
        }
        val node = Node(key, value)
        addAtHead(node)
        map[key] = node
        if (map.size > capacity) {
            val last = tail.prev!!
            remove(last)
            map.remove(last.key)
        }
    }
  
    private fun remove(node: Node<K, V>) {
        val next = node.next!!
        val prev = node.prev!!
        prev.next = next
        next.prev = prev
    }
  
    private fun addAtHead(node: Node<K, V>) {
        // Old Head 앞에 현재 노드를 위치 시킴
        val oldHead = head.next!!
        oldHead.prev = node;
        node.next = oldHead;
  
        // Head에 현재 노드를 위치 시킴
        node.prev = head;
        head.next = node;
    }
  
    data class Node<K, V>(val key: K?, val value: V?) {
        constructor() : this(null, null)
        var next: Node<K, V>? = null
        var prev: Node<K, V>? = null
    }
  }
  

테스트 코드

import org.assertj.core.api.Assertions.assertThat
import org.assertj.core.api.Assertions.assertThatThrownBy
import org.junit.jupiter.api.Assertions.*
import org.junit.jupiter.api.DisplayName
import org.junit.jupiter.api.Test

class LRUCacheTest {

    @DisplayName("캐시의 값을 잘 가져오는지 확인")
    @Test
    fun getTest() {
        val lruCache = LRUCache<String, Int>(3)
        lruCache.put("A", 10)
        lruCache.put("B", 11)
        lruCache.put("C", 12)
        lruCache.put("D", 13)

        val result = lruCache.get("D")

        assertThat(result).isEqualTo(13)
    }

    @DisplayName("Capacity를 초과하면 가장 오래 사용안된 노드는 삭제 되어야 함")
    @Test
    fun overCapacityTest() {
        val lruCache = LRUCache<String, Int>(3)
        lruCache.put("A", 10)
        lruCache.put("B", 11)
        lruCache.put("C", 12)
        lruCache.put("D", 13)

        assertThatThrownBy { lruCache.get("A") }
            .isInstanceOf(IllegalArgumentException::class.java)
            .hasMessage("존재하지 않는 키 입니다: A")
    }

    @DisplayName("캐시가 사용되면 순서가 가장 앞으로 이동해야 함")
    @Test
    fun addAtHeadWhenGetTest() {
        val lruCache = LRUCache<String, Int>(3)
        lruCache.put("A", 10)
        lruCache.put("B", 11)
        lruCache.put("C", 12)
        lruCache.get("A")   // "A"가 사용됨
        lruCache.put("D", 13)
        lruCache.put("E", 14)

        val result = lruCache.get("A")

        assertThat(result).isEqualTo(10)
    }

    @DisplayName("캐시 값이 업데이트 되면 순서가 가장 앞으로 이동해야 함")
    @Test
    fun addAtHeadWhenUpdateValueTest() {
        val lruCache = LRUCache<String, Int>(3)
        lruCache.put("A", 10)
        lruCache.put("B", 11)
        lruCache.put("C", 12)
        lruCache.put("A", 1000)   // "A" 값이 업데이트 됨
        lruCache.put("D", 13)
        lruCache.put("E", 14)

        val result = lruCache.get("A")

        assertThat(result).isEqualTo(1000)
    }
}