Golang의 LRU 캐시 알고리즘에 대한 자세한 분석.-Golang-php.cn

집

백엔드 개발

Golang

Golang의 LRU 캐시 알고리즘에 대한 자세한 분석.

Jun 19, 2023 pm 08:28 PM

golang LRU 캐시 알고리즘 상세한 분석

효율적이고 안정적인 시스템을 개발할 때 캐싱은 필수적인 최적화 방법 중 가장 일반적인 캐싱 알고리즘 중 하나가 LRU 알고리즘입니다. LRU 알고리즘은 "Least Recent Used" 알고리즘으로, 캐시의 각 요소의 사용량을 기록하여 가장 최근에 사용되지 않은 요소를 제거함으로써 캐시 활용 효율성을 극대화할 수 있습니다. Golang에서는 LRU 캐시 알고리즘도 쉽게 구현할 수 있습니다.

이 기사에서는 양방향 연결 목록과 해시 테이블을 사용하여 구현하는 방법, 캐시를 업데이트하고 제거하는 방법, 스레드를 수행하는 방법 등 Golang에서 LRU 캐시 알고리즘을 구현하는 방법을 자세히 소개합니다. 안전한 운영.

이중 연결 리스트와 해시 테이블을 사용하여 LRU 캐싱 알고리즘 구현

Golang에서 이중 연결 리스트는 LRU 캐싱 알고리즘을 쉽게 구현할 수 있는 기본 데이터 구조입니다. 구체적인 구현 방법은 캐시의 각 요소를 노드로 캡슐화하고 이중 연결 목록을 사용하여 이러한 노드를 관리하는 것입니다. 동시에 해시 테이블(지도)을 사용하여 각 노드의 위치를 기록하므로 빠른 검색과 업데이트가 가능합니다.

다음은 Golang에서 LRU 캐시 알고리즘을 구현하기 위한 기본 코드 구조입니다.

type Node struct {
    Key  int
    Val  int
    Prev *Node
    Next *Node
}

type LRUCache struct {
    Size       int
    Capacity   int
    Cache      map[int]*Node
    Head, Tail *Node
}

func Constructor(capacity int) LRUCache {
    head, tail := &amp;Node{}, &amp;Node{}
    head.Next, tail.Prev = tail, head
    return LRUCache{
        Cache:     make(map[int]*Node),
        Capacity:  capacity,
        Size:      0,
        Head:      head,
        Tail:      tail,
    }
}

func (l *LRUCache) Get(key int) int {
    if node, ok := l.Cache[key]; ok {
        l.MoveToHead(node)
        return node.Val
    }
    return -1
}

func (l *LRUCache) Put(key, val int) {
    if node, ok := l.Cache[key]; ok {
        node.Val = val
        l.MoveToHead(node)
        return
    }
    node := &amp;Node{Key: key, Val: val}
    l.Cache[key] = node
    l.AddToHead(node)
    l.Size++
    if l.Size &gt; l.Capacity {
        removed := l.RemoveTail()
        delete(l.Cache, removed.Key)
        l.Size--
    }
}

func (l *LRUCache) MoveToHead(node *Node) {
    l.RemoveNode(node)
    l.AddToHead(node)
}

func (l *LRUCache) RemoveNode(node *Node) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (l *LRUCache) AddToHead(node *Node) {
    node.Prev = l.Head
    node.Next = l.Head.Next
    l.Head.Next.Prev = node
    l.Head.Next = node
}

func (l *LRUCache) RemoveTail() *Node {
    node := l.Tail.Prev
    l.RemoveNode(node)
    return node
}

로그인 후 복사

위 코드에서 LRUCache는 Cache 해시 테이블을 포함하는 구조입니다. , Head 포인터와 Tail 포인터는 이중 연결 리스트의 헤드 및 테일 노드와 캐시의 각 요소 위치를 기록하는 데 사용됩니다. 그 중 Cache 해시 테이블의 키는 요소의 키이고 값은 Head 요소의 헤드 노드를 가리키는 노드 포인터입니다. 이중 연결 목록 및 Tail은 꼬리 노드를 가리킵니다. 크기는 현재 캐시의 요소 수를 나타내고, 용량은 캐시의 최대 용량을 나타냅니다. LRUCache是一个结构体，包含一个Cache哈希表、一个Head指针和一个Tail指针，用于记录双向链表的头尾节点和缓存中每个元素的位置。其中，Cache哈希表的键是元素的键，值是元素的节点指针；Head指向双向链表的头节点，Tail指向尾节点。Size表示当前缓存中元素的个数，Capacity表示缓存的最大容量。

在Constructor函数中，我们初始化了一个空的双向链表，并返回一个LRUCache结构体。在Get函数中，我们首先判断缓存中是否存在指定的元素，如果存在，则将该元素移动到链表头部，并返回其值；否则返回-1。在Put函数中，我们首先判断缓存中是否存在指定的元素，如果存在，则更新该元素的值，将其移动到头部；否则新增一个元素，并将其添加到头部。如果缓存大小超过了最大容量，则删除最近最少使用的元素，并将其从哈希表中删除。

MoveToHead、RemoveNode、AddToHead和RemoveTail分别对应实现双向链表的节点移动和删除操作，具体实现方式在代码中给出。

更新与淘汰缓存

在使用LRU缓存算法时，需要保证缓存中元素的访问顺序按照最近使用的时间顺序排列。每当从缓存中读取或更新一个元素时，需要将其移动到链表的头部；同时，当缓存大小超过最大容量时，需要淘汰最近最少使用的元素，即链表中的最后一个元素。

下面是MoveToHead函数的实现方式：

func (l *LRUCache) MoveToHead(node *Node) {
    l.RemoveNode(node)
    l.AddToHead(node)
}

로그인 후 복사

MoveToHead函数接受一个指向缓存节点的指针node作为参数，首先从链表中删除该节点，然后将该节点添加到链表头部。

下面是RemoveTail函数的实现方式：

func (l *LRUCache) RemoveTail() *Node {
    node := l.Tail.Prev
    l.RemoveNode(node)
    return node
}

로그인 후 복사

RemoveTail函数返回链表中的最后一个节点，并将该节点从链表中删除。

线程安全操作

在多线程环境下，需要保证LRU缓存操作的线程安全性。为此，我们可以使用sync包中提供的互斥锁（Mutex）来实现。具体方式是，在需要进行缓存操作的函数中加入互斥锁的操作，避免同时对缓存进行读写操作。下面是Golang中实现LRU缓存算法的线程安全版本的代码结构：

type LRUCache struct {
    Size       int
    Capacity   int
    Cache      map[int]*Node
    Head, Tail *Node
    Mutex      sync.Mutex
}

func (l *LRUCache) Get(key int) int {
    l.Mutex.Lock()
    defer l.Mutex.Unlock()

    ...
}

func (l *LRUCache) Put(key, val int) {
    l.Mutex.Lock()
    defer l.Mutex.Unlock()

    ...
}

...

로그인 후 복사

上面的代码中，我们在结构体LRUCache中添加了一个Mutex

Constructor 함수에서는 빈 이중 연결 목록을 초기화하고 LRUCache 구조를 반환합니다. Get 함수에서는 먼저 지정된 요소가 캐시에 있는지 확인합니다. 존재하는 경우 해당 요소를 연결된 목록의 헤드로 이동하고 해당 값을 반환합니다. 그렇지 않으면 -1이 반환됩니다. Put 함수에서는 먼저 지정된 요소가 캐시에 있는지 확인합니다. 존재하는 경우 해당 요소의 값을 업데이트하고 헤드로 이동합니다. 그렇지 않으면 새 요소를 추가합니다. 머리에. 캐시 크기가 최대 용량을 초과하면 최근에 가장 적게 사용된 요소가 제거되고 해시 테이블에서 제거됩니다.