Go에서 LRU 캐시 구현

따라서 작은 캐시가 필요하며 Redis 또는 Memcached 인스턴스를 정당화할 수 없습니다. Go에서 이를 구현하는 데 무엇이 필요한지 살펴보겠습니다. 재미삼아 제네릭을 사용하여 프로젝트에서 재사용할 수 있도록 만들겠습니다.

LRU 캐시는 일반적으로 고정된 용량과 가장 간단한 배출 정책을 가지고 있습니다. 즉, 액세스한 이후 가장 오랜 시간이 지난 요소를 배출합니다. 간단한 lru 캐시는 다음 인터페이스를 구현합니다.

type LRUCache[T any] interface {
    Get(key string) (value T, found bool)
    Put(key string, value T)
    Keys() []string
    Remove(key string) bool
    Clear()
    Capacity() int
    Len() int
}

우리는 캐시가 특정 값으로 입력되는 항목으로 데이터 항목을 저장한다는 것을 알고 있습니다. 지도처럼 들리네요. 퇴출 정책을 시행하는 것은 어떻습니까? 이를 수행하는 한 가지 방법은 각 항목과 함께 timeAccessed 속성을 유지하는 것입니다. 다음과 같습니다:

type cacheEntry[T any] struct {
  Data T
  LastAccessed time.time
}

그러나 성능을 생각해보면, 우리는 캐시 키를 검색할 수 있을 뿐만 아니라 필요한 경우 가장 오래된 키를 삽입하고 제거할 수 있기를 원합니다.

해시테이블인 지도를 사용하면 조회 성능이 매우 빨라집니다. 가장 오래된 항목을 찾는 것은 어떻습니까? 캐시 구조가 다음과 같은 경우:

type LRUCache[T any] {
  capacity int
  keyMap map[string]cacheEntry[T]
}

항목을 제거할 때가 되면 가장 오래된 항목을 찾기 위해 지도를 반복해야 합니다.

캐시 항목 목록을 정렬된 상태로 효율적으로 유지할 수 있는 방식으로 항목을 저장할 방법이 필요합니다. 정렬 루틴을 사용할 필요가 없는 것이 바람직합니다.

이중 연결 목록은 이를 수행하는 좋은 방법이며 실제로 원하지 않는 한 항목에 액세스 시간을 저장할 필요가 없습니다. 따라서 노드 구조체와 함께 다음을 구현하는 연결 목록이 있다고 가정해 보겠습니다.

type DoubleLinkedList[T any] interface {
    Head() *DoubleNode[T]
    Tail() *DoubleNode[T]
    // Append inserts new item at tail
    Append(data T) *DoubleNode[T]
    // Push appends new item at head
    Push(data T) *DoubleNode[T]
    Remove(node *DoubleNode[T]) *DoubleNode[T]
    RemoveTail() *DoubleNode[T]
    MoveToHead(node *DoubleNode[T])
}
type DoubleNode[T any] struct {
    Data T
    Prev *DoubleNode[T]
    Next *DoubleNode[T]
}

이제 캐시 구조는 다음과 같습니다.

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]*DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
}

캐시 항목 구조는 다음과 같습니다.

type lruCacheEntry[T any] struct {
    key   string
    value T
}

현실적으로는 캐시 키에 대한 인터페이스를 사용하게 될 것입니다. 코드를 단순하게 유지하기 위해 문자열을 사용하고 있습니다.

여기 구현에서는 캐시에서 가장 최근에 액세스한 항목이 헤드에 있고 가장 최근에 사용된 항목이 테일에 있게 됩니다. 따라서 제거할 때가 되면 연결 리스트의 꼬리 요소만 제거하면 됩니다.

Get() 함수 구현은 간단합니다.

func (l *lruCache[T]) Get(key string) (value T, found bool) {
    if node, ok := l.keyMap[key]; ok {
        l.list.MoveToHead(node)
        return node.Data.value, ok
    }
    var zero T
    return zero, false
}

Get은 키에 대한 맵 항목을 검색한 다음 이제 '가장 최근에 사용된' 항목이므로 해당 노드를 목록의 선두로 이동하면 됩니다.

Put() 함수는 필요한 경우 제거를 처리하는 곳입니다.

func (l *lruCache[T]) Put(key string, value T) {
    if node, ok := l.keyMap[key]; ok {
        node.Data = lruCacheEntry[T]{
            key:   key,
            value: value,
        }
        // move the element to the most recent position
        l.list.MoveToHead(node)
    } else {
        // insert the new element at the head
        newNode := l.list.Push(lruCacheEntry[T]{
            key:   key,
            value: value,
        })
        l.keyMap[key] = newNode
    }
    // is eviction necessary
    if len(l.keyMap) > l.capacity {
        nodeRemoved := l.list.RemoveTail()
        delete(l.keyMap, nodeRemoved.Data.key)
    }
}

Put()의 경우 먼저 지정된 키에 대한 값이 이미 있는지 확인합니다. 그렇다면 값을 업데이트하고 노드를 목록의 헤드로 이동하십시오. 그렇지 않으면 새 캐시 항목을 생성하여 목록에 헤드로 추가하고 지도에 추가합니다.

마지막으로 용량 확인도 잊지 마세요. 새 항목으로 인해 용량이 초과되면 목록의 꼬리인 가장 오래된 항목을 제거하고 맵에서 해당 항목을 삭제합니다.

키를 캐시 항목의 일부로 저장하면 지도에서 키를 빠르게 삭제할 수 있습니다. 캐시 항목에만 데이터를 저장했다면 이를 찾기 위해 맵을 반복해야 합니다.

이 캐시에는 다중 스레드 앱에 중요한 내용이 없습니다. 동기화가 없습니다. 현실적으로 캐시는 여러 스레드에서 액세스됩니다. 동기화는 복잡한 주제입니다. 구현을 위해 캐시 구조체에 뮤텍스를 추가할 수 있습니다:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
    mutex    sync.RWMutex
}

그런 다음 각 기능 시작 부분에 다음을 추가하세요.

    l.mutex.Lock()
    defer l.mutex.Unlock()

읽기/쓰기 잠금을 사용하고 있습니다. 일부 함수는 캐시 구조를 변경하지 않으므로 제공된 읽기 잠금 방법(예: Len() 함수)을 사용할 수 있습니다.

func (l *lruCache[T]) Len() int {
    l.mutex.RLock()
    defer l.mutex.RUnlock()
    return len(l.keyMap)
}

캐시에 액세스하려는 스레드 수가 많으면 여기에서 선택한 동기화 전략이 중단될 수 있습니다. 그 자체로 일련의 게시물이 될 수도 있는 복잡한 주제입니다.

아래 링크에 있는 저장소에서 전체 구현을 확인하세요.

캐시를 구현하려면 어떻게 해야 합니까? 동기화를 어떻게 해결하시겠습니까? 나는 이것에 대한 당신의 생각을 듣고 싶습니다. 이에 대한 단일 해결책은 없으므로 아래에 의견을 남겨주세요.

감사합니다!

이 게시물과 이 시리즈의 모든 게시물에 대한 코드는 여기에서 확인할 수 있습니다.

위 내용은 Go에서 LRU 캐시 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!