# Caching

By [Primrose](https://paragraph.com/@primrose) · 2023-06-14

---

Caching Algorithm
=================

캐싱 알고리즘은 데이터의 재사용을 최적화하고, 성능을 향상시키기 위해 사용되는 여러 전략 중 하나다.

주로 가장 최근에 사용된, 혹은 가장 자주 사용되는 데이터를 빠르게 접근할 수 있도록 메모리에 보관한다.

이는 I/O 작업의 비용을 줄이고 응답 시간을 단축하는 데 도움이 된다.

다음은 캐싱 알고리즘의 몇 가지 예시 이다

### LRU (Least Recently Used)

가장 오래전에 사용된 항목을 캐시에서 제거하는 방식을 말한다.

새로운 항목이 캐시에 추가될 때, 가장 오래전에 접근한 항목부터 제거한다.

이 방식은 \*\*'가장 최근에 사용하지 않은 항목이 가장 나중에 다시 사용될 가능성이 작다'\*\*는 추정에 기반을 두고 있다.

Redis를 사용해봤다면 들어봤을 법한 용어일 것이다.

직접 LRU를 구현한다면 어떤식으로 구현할 수 있을까?

Linked list와 map을 이용해서 간단하게 구현 가능하다.

    package main
    
    import (
        "container/list"
        "fmt"
    )
    
    type LRUCache struct {
        size      int
        evictList *list.List
        items     map[interface{}]*list.Element
    }
    
    type entry struct {
        key   interface{}
        value interface{}
    }
    
    func NewLRUCache(size int) *LRUCache {
        return &LRUCache{size: size, evictList: list.New(), items: make(map[interface{}]*list.Element)}
    }
    
    // Set adds a value to the cache.
    func (c *LRUCache) Set(key, value interface{}) {
        // Check if item already exists
        if ee, ok := c.items[key]; ok {
            c.evictList.MoveToFront(ee)
            ee.Value.(*entry).value = value
            return
        }
    
        // Add new item
        ent := &entry{key, value}
        entry := c.evictList.PushFront(ent)
        c.items[key] = entry
    
        if c.evictList.Len() > c.size {
            c.removeOldest()
        }
    }
    
    // Get retrieves an item from the cache.
    func (c *LRUCache) Get(key interface{}) (value interface{}, ok bool) {
        if ent, ok := c.items[key]; ok {
            c.evictList.MoveToFront(ent)
            return ent.Value.(*entry).value, true
        }
        return
    }
    
    // removeOldest removes the oldest item from the cache.
    func (c *LRUCache) removeOldest() {
        ent := c.evictList.Back()
        if ent != nil {
            c.removeElement(ent)
        }
    }
    
    // removeElement removes a given list element from the cache.
    func (c *LRUCache) removeElement(e *list.Element) {
        c.evictList.Remove(e)
        kv := e.Value.(*entry)
        delete(c.items, kv.key)
    }
    
    func main() {
    
        lru := NewLRUCache(2)
    
        lru.Set("1", 1)
        lru.Set("2", 2)
        fmt.Println(lru.Get("1")) // returns 1
        lru.Set("3", 3)           // evicts key "2"
        fmt.Println(lru.Get("2")) // returns nil
        lru.Set("4", 4)           // evicts key "1"
        fmt.Println(lru.Get("1")) // returns nil
        fmt.Println(lru.Get("3"))
        fmt.Println(lru.Get("4"))
    }
    

### LFU (Least Frequently Used)

가장 적게 사용된 항목을 캐시에서 제거하는 방식을 말한다.

캐시가 꽉 찼을 때, 가장 적게 접근된 항목이 제거된다.

이는 \*\*'과거에 자주 사용되지 않은 항목은 앞으로도 자주 사용되지 않을 가능성이 크다'\*\*는 추정에 기반한다.

LFU는 주로 min heap을 이용해서 구현하는데, 코드가 꽤 길 것 같으므로 해당 부분은 생략하겠다.

### FIFO (First In, First Out)

가장 유명하다. 선입선출.

새로운 항목이 캐시에 추가될 때, 캐시에 가장 먼저 들어온 항목이 제거된다.

이 알고리즘은 구현이 쉽고 메모리 관리에 있어서 일관성이 있지만 늘 최적의 결과를 내지는 못할 수 있다.

각 알고리즘은 특정 상황에서 장점을 가지고 있으며, 어떤 알고리즘이 가장 적합한지는 특정 애플리케이션의 요구 사항에 따라 달라진다.

예를 들어, 데이터의 접근 패턴이 시간에 따라 변하지 않는다면 LFU가 좋은 성능을 보일 수 있다. 반면, 데이터의 접근 패턴이 시간에 따라 크게 변한다면 LRU가 더 적합할 수 있다.

---

*Originally published on [Primrose](https://paragraph.com/@primrose/caching)*