所以你需要一个小的缓存，并且不能证明 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)
}
注意，如果有大量线程尝试访问缓存，这里选择的同步策略可能会崩溃。这是一个复杂的主题，本身可能是一系列帖子。
请参阅下面链接中给出的存储库中的完整实现。
您会采取哪些不同的措施来实现缓存？您将如何解决同步问题？我很想听听您对此的想法。对此没有单一的解决方案，因此请在下面发表您的评论。
谢谢！
这篇文章以及本系列所有文章的代码可以在这里找到
本站部分资源来源于网络，仅限用于学习和研究目的，请勿用于其他用途。
如有侵权请发送邮件至1943759704@qq.com删除
码农资源网 » 在 Go 中实现 LRU 缓存
