因此您需要一個小型緩存，並且無法證明 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中文網其他相關文章！
