在 Go 中实现 LRU 缓存-Golang-PHP中文网

在 Go 中实现 LRU 缓存

WBOY

发布： 2024-08-02 09:19:16

转载

1042人浏览过

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