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