Implémenter un cache LRU dans Go

Vous avez donc besoin d'un petit cache et ne pouvez pas justifier une instance Redis ou Memcached. Voyons ce qu'il faut pour en implémenter un dans Go. Pour le plaisir, nous le réaliserons en utilisant des génériques afin qu'il soit réutilisable dans notre projet.

Un cache LRU a généralement une capacité fixe et la politique d'éjection la plus simple : éjecter l'élément qui a le plus de temps depuis son accès. Un simple cache lru implémentera l'interface suivante :

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
}

Nous savons que le cache stockera un élément de données sous la forme d'une entrée saisie par une certaine valeur. Cela ressemble à une carte. Qu’en est-il de la mise en œuvre de la politique d’éjection ? Une façon de procéder consiste à conserver une propriété timeAccessed avec chaque élément. Quelque chose comme :

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

Cependant, pensons aux performances, nous voulons pouvoir rechercher la clé de cache ainsi qu'insérer et expulser la plus ancienne, si nécessaire, le plus rapidement possible.

L'utilisation d'une carte, qui est une table de hachage, nous donnera des performances assez rapides pour les recherches. Et si vous trouviez l'entrée la plus ancienne ? Si votre structure de cache ressemble à :

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

Il faudra forcément parcourir la carte pour retrouver la plus ancienne lorsque viendra le temps d'expulser une entrée.

Nous avons besoin d'un moyen de stocker les entrées d'une manière qui nous permette efficacement de conserver une liste des entrées du cache triées. Il est préférable que nous n'ayons pas besoin d'utiliser une routine de tri.

Une liste à double lien est un bon moyen de le faire et nous n'avons pas besoin de stocker le temps d'accès dans l'entrée à moins que nous le souhaitions réellement. Supposons donc que nous ayons une liste chaînée qui implémente ce qui suit avec sa structure de nœud :

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

La structure du cache peut maintenant ressembler à :

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

La structure d'entrée du cache sera :

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

En réalité, vous utiliseriez probablement une interface pour la clé de cache. J'utilise une chaîne pour garder le code simple.

Dans l'implémentation ici, l'entrée du cache la plus récemment consultée sera en tête et la moins récemment utilisée sera en queue. Ainsi, quand vient le temps d’expulser, nous supprimons simplement l’élément tail de la liste chaînée.

L'implémentation de la fonction Get() est simple :

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 a juste besoin de récupérer l'entrée de carte pour la clé, puis de déplacer le nœud en tête de la liste puisqu'il est désormais le « le plus récemment utilisé ».

La fonction Put() est l'endroit où nous gérerons l'expulsion si cela est nécessaire :

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

Pour Put(), nous vérifions d’abord s’il existe déjà une valeur pour la clé donnée. Si tel est le cas, mettez à jour la valeur et déplacez le nœud en tête de liste. Sinon, nous créons une nouvelle entrée de cache, l'ajoutons à la liste en tant qu'en-tête et l'ajoutons à notre carte.

Enfin, n'oubliez pas de vérifier la capacité. Si la nouvelle entrée nous dépasse la capacité, nous expulsons l'entrée la plus ancienne qui est la queue de la liste et supprimons l'entrée de notre carte.

Notez que stocker la clé dans le cadre de l'entrée du cache nous permet de supprimer rapidement la clé de la carte. Si nous avions uniquement stocké les données dans l’entrée du cache, nous aurions alors besoin de parcourir la carte pour les trouver.

Il manque quelque chose de critique dans ce cache pour une application multithread. Il n'y a pas de synchronisation. En réalité, un cache serait accessible par plusieurs threads. La synchronisation est un sujet complexe. Pour notre implémentation, nous pouvons ajouter un mutex à la structure du cache :

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

puis ajoutez ce qui suit au début de chaque fonction.

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

Remarquez que nous utilisons un verrou en lecture/écriture. Certaines fonctions ne changent pas la structure du cache, nous pouvons donc utiliser la méthode de verrouillage en lecture fournie, par exemple la fonction Len() :

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

Notez que la stratégie de synchronisation choisie ici peut échouer si un grand nombre de threads tentent d'accéder au cache. C'est un sujet complexe qui pourrait faire l'objet d'une série de posts en soi.

Voir l'implémentation complète dans le référentiel indiqué dans le lien ci-dessous.

Que feriez-vous différemment pour implémenter un cache ? Comment aborderiez-vous la synchronisation ? Je suis intéressé à entendre vos réflexions sur celui-ci. Il n'y a pas de solution unique à ce problème, alors laissez vos commentaires ci-dessous.

Merci !

Le code de cet article et de tous les articles de cette série peut être trouvé ici

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!