Cache

한 번 접근한 메모리를 저장해두었다가 다시 요청할 때 빠르게 데이터를 제공하는 메모리.

데이터베이스 접근이나 네트워크 요청은 오래걸리기 때문에 이전에 요청했던 데이터를 저장해두었다가 다시 요청을 한다면 저장해놓을 걸 빨리 리턴해서 오래걸리는 요청작업 횟수를 줄이는 방식

사용자가 다시 요청할 데이터를 어떻게 알 수 있을까?

• 시간 지역성과 공간 지역성에 의해 저장

하지만 캐시는 데이터베이스보다는 용량이 작기 때문에 언젠가는 다 찬다. 그럼 어떤 데이터부터 제거하는게 최대한 캐시의 적중률을 높게 유지할 수 있는 방법일까?

FIFO

• 단순히 먼저 접근한 데이터를 먼저 제거
• 초기화에 사용하는 코드라면 이득이지만 앱 내내 사용되는 데이터라면 안 좋을 것

LFU (Least Frequently Used)

• 가장 적게 참조한 데이터를 삭제
• 데이터의 참조횟수를 저장하고 있다가 가장 참조횟수가 적은 데이터부터 삭제한다.
• 가장 참조횟수가 적은 데이터가 여러개면 제일 시간상으로 오래된 데이터부터 삭제한다.

LRU (Least Recently Used)

• 최근에 가장 덜 접근한 데이터를 삭제
• 사실 가장 좋은 알고리즘은 앞으로 가장 덜 접근할 데이터를 삭제하는게 이득일 것이다.
• 하지만, 미래는 알 수 없기 때문에 대신 과거에 제일 적게 접근한 데이터를 삭제하는 LRU가 나옴
• 현재 많이 사용하는 캐시 정책

LRU 구현하기

선형 데이터에서 최신 --> 오래된 순으로 저장할 때, 캐시에 있는 데이터를 참조할 때마다 해당 데이터를 맨 왼쪽으로 옮겨줌
-> 배열은 앞으로 넣을 때마다 나머지 데이터를 뒤로 한칸씩 옮겨줘야 하기 때문에 (O(n)) LinkedList가 좋을 것
-> 여기에 데이터 검색도 빠르게 하기 위해 HashMap 사용

LinkedHashMap 자료구조로 바로 사용가능하지만 LinkedList랑 HashMap을 따로 만들어서 구현해보았다.

class Cache {

    private var head: CacheNode? = null
    private var tail: CacheNode? = null
    private val map: MutableMap<String, CacheNode> = mutableMapOf()
    private val capacity: Int = 5

    fun contains(keyWord: String): Boolean {
        return if (map.contains(keyWord)) {
            moveToFront(keyWord)
            true
        } else {
            false
        }
    }

    fun get(keyWord: String): Any? {
        return map[keyWord]?.data
    }

    fun add(keyWord: String, data: Any) {
        if (map.size >= capacity) {
            removeOldest()
        }

        if (contains(keyWord)) {
            moveToFront(keyWord)
        } else {
            addNewNode(keyWord, data)
        }
    }

    private fun moveToFront(keyWord: String) {
        val node = map[keyWord]
        node?.let {
            if (it !== head) {
                it.pre?.next = it.next
                it.next?.pre = it.pre
                it.next = head
                head?.pre = it
                it.pre = null
                head = it
            }
            it.hitCount++
        }
    }

    private fun addNewNode(keyWord: String, cacheData: Any) {
        val newNode = CacheNode(keyWord, cacheData, 1, head)
        head?.pre?.let {
            it.pre = newNode
        }
        head = newNode
		
        if(tail == null) tail = head
        
        map[keyWord] = newNode
    }

    private fun removeOldest() {
        val last = tail
        
        tail = tail?.prev
        tail?.next = null

        last?.let {
            map.remove(it.keyWord)
        }
    }

    fun printCache(): String {
        val sb = StringBuilder()
        var current = head
        while (current != null) {
            sb.append("${current.keyWord}(${current.hitCount}) ")
            current = current.next
        }
        return if (sb.isEmpty()) {
            "저장된 키워드가 없습니다"
        } else {
            sb.toString()
        }
    }
}

data class CacheNode(
    val keyWord: String,
    val data: Any,
    var hitCount: Int = 0,
    var next: CacheNode? = null,
    var pre: CacheNode? = null
)