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

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

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

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

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

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

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

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는 주로 min heap을 이용해서 구현하는데, 코드가 꽤 길 것 같으므로 해당 부분은 생략하겠다.

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

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

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

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

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

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

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

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

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

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

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

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

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는 주로 min heap을 이용해서 구현하는데, 코드가 꽤 길 것 같으므로 해당 부분은 생략하겠다.

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

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

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

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

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