所以你需要一个小的缓存,并且不能证明 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)
}
注意,如果有大量线程尝试访问缓存,这里选择的同步策略可能会崩溃。这是一个复杂的主题,本身可能是一系列帖子。
请参阅下面链接中给出的存储库中的完整实现。
您会采取哪些不同的措施来实现缓存?您将如何解决同步问题?我很想听听您对此的想法。对此没有单一的解决方案,因此请在下面发表您的评论。
谢谢!
这篇文章以及本系列所有文章的代码可以在这里找到