Implementieren Sie einen LRU-Cache in Go

Sie benötigen also einen kleinen Cache und können eine Redis- oder Memcached-Instanz nicht rechtfertigen. Mal sehen, was nötig ist, um eines in Go zu implementieren. Aus Spaß erstellen wir es mithilfe von Generika, sodass es in unserem Projekt wiederverwendbar ist.

Ein LRU-Cache hat im Allgemeinen eine feste Kapazität und die einfachste Auswurfrichtlinie: Wirf das Element aus, auf das am längsten zugegriffen wurde. Ein einfacher LRU-Cache implementiert die folgende Schnittstelle:

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
}

Wir wissen, dass der Cache ein Datenelement als Eintrag speichert, der durch einen bestimmten Wert verschlüsselt ist. Das klingt nach einer Karte. Wie sieht es mit der Umsetzung der Auswurfrichtlinie aus? Eine Möglichkeit hierfür besteht darin, zusammen mit jedem Element eine timeAccessed-Eigenschaft beizubehalten. Etwas wie:

type cacheEntry[T any] struct {
  Data T
  LastAccessed time.time
}

Denken wir jedoch an die Leistung. Wir möchten in der Lage sein, so schnell wie möglich nach dem Cache-Schlüssel zu suchen und bei Bedarf den ältesten einzufügen und zu entfernen.

Die Verwendung einer Karte, bei der es sich um eine Hashtabelle handelt, ermöglicht uns eine ziemlich schnelle Leistung bei Suchvorgängen. Wie wäre es mit der Suche nach dem ältesten Eintrag? Wenn Ihre Cache-Struktur wie folgt aussieht:

type LRUCache[T any] {
  capacity int
  keyMap map[string]cacheEntry[T]
}

Wir müssen unbedingt die Karte durchlaufen, um den ältesten zu finden, wenn es an der Zeit ist, einen Eintrag zu entfernen.

Wir benötigen eine Möglichkeit, Einträge so zu speichern, dass wir eine Liste der Cache-Einträge effizient sortiert halten können. Es ist vorzuziehen, dass wir keine Sortierroutine verwenden müssen.

Eine doppelt verknüpfte Liste ist eine gute Möglichkeit, dies zu tun, und wir müssen die Zugriffszeit nicht im Eintrag speichern, es sei denn, wir möchten sie tatsächlich. Nehmen wir also an, wir haben eine verknüpfte Liste, die zusammen mit ihrer Knotenstruktur Folgendes implementiert:

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]
}

Die Cache-Struktur kann jetzt etwa so aussehen:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]*DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
}

Die Cache-Eintragsstruktur lautet:

type lruCacheEntry[T any] struct {
    key   string
    value T
}

Realistisch gesehen würden Sie wahrscheinlich eine Schnittstelle für den Cache-Schlüssel verwenden. Ich verwende eine Zeichenfolge, um den Code einfach zu halten.

In der Implementierung hier befindet sich der Eintrag im Cache, auf den zuletzt zugegriffen wurde, am Anfang und der Eintrag, der am längsten nicht verwendet wurde, am Ende. Wenn es also an der Zeit ist, sie zu entfernen, entfernen wir einfach das Endelement der verknüpften Liste.

Die Implementierung der Get()-Funktion ist einfach:

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 muss lediglich den Karteneintrag für den Schlüssel abrufen und dann den Knoten an den Anfang der Liste verschieben, da er jetzt der „zuletzt verwendete“ ist.

Mit der Put()-Funktion führen wir bei Bedarf die Räumung durch:

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)
    }
}

Für Put() prüfen wir zunächst, ob für den angegebenen Schlüssel bereits ein Wert vorhanden ist. Wenn ja, aktualisieren Sie den Wert und verschieben Sie den Knoten an den Anfang der Liste. Andernfalls erstellen wir einen neuen Cache-Eintrag, fügen ihn als Kopf zur Liste hinzu und fügen ihn unserer Karte hinzu.

Vergessen Sie nicht, die Kapazität zu überprüfen. Wenn der neue Eintrag die Kapazität überschreitet, entfernen wir den ältesten Eintrag, der am Ende der Liste steht, und löschen den Eintrag aus unserer Karte.

Beachten Sie, dass das Speichern des Schlüssels als Teil des Cache-Eintrags es uns ermöglicht, den Schlüssel schnell von der Karte zu löschen. Wenn wir die Daten nur im Cache-Eintrag gespeichert hätten, müssten wir die Karte durchlaufen, um sie zu finden.

Diesem Cache fehlt etwas Wichtiges für eine Multithread-App. Es gibt keine Synchronisierung. Realistisch gesehen würden mehrere Threads auf einen Cache zugreifen. Synchronisation ist ein komplexes Thema. Für unsere Implementierung können wir der Cache-Struktur einen Mutex hinzufügen:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
    mutex    sync.RWMutex
}

Fügen Sie dann am Anfang jeder Funktion Folgendes hinzu.

    l.mutex.Lock()
    defer l.mutex.Unlock()

Beachten Sie, dass wir eine Lese-/Schreibsperre verwenden. Einige der Funktionen verändern die Struktur des Caches nicht, daher können wir die bereitgestellte Lesesperrmethode verwenden, zum Beispiel die Funktion Len():

func (l *lruCache[T]) Len() int {
    l.mutex.RLock()
    defer l.mutex.RUnlock()
    return len(l.keyMap)
}

Beachten Sie, dass die hier gewählte Synchronisierungsstrategie möglicherweise fehlschlägt, wenn eine große Anzahl von Threads versucht, auf den Cache zuzugreifen. Es ist ein komplexes Thema, das eine ganze Reihe von Beiträgen umfassen könnte.

Sehen Sie sich die vollständige Implementierung im Repository an, das im Link unten angegeben ist.

Was würden Sie bei der Implementierung eines Caches anders machen? Wie würden Sie die Synchronisierung angehen? Ich bin daran interessiert, Ihre Gedanken dazu zu hören. Hierfür gibt es keine Patentlösung. Geben Sie daher unten Ihre Kommentare ab.

Danke!

Den Code für diesen Beitrag und alle Beiträge dieser Reihe finden Sie hier

Das obige ist der detaillierte Inhalt vonImplementieren Sie einen LRU-Cache in Go. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!