# Caching

**Published by:** [Primrose](https://paragraph.com/@primrose/)
**Published on:** 2023-06-14
**URL:** https://paragraph.com/@primrose/caching

## Content

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가 더 적합할 수 있다.

## Publication Information

- [Primrose](https://paragraph.com/@primrose/): Publication homepage
- [All Posts](https://paragraph.com/@primrose/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@primrose): Subscribe to updates