在 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中文网其他相关文章！