因此您需要一个小型缓存，并且无法证明 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中文网其他相关文章！
