Caching(draft)

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