Go Programming

Construire un cache LRU thread-safe en Go : modèles de concurrence et benchmarking par rapport à sync.Map

By admin · May 29, 2026 · 34 views 🤖 AI
Gogolangconcurrencyperformancelru-cachesync-mapbenchmark

La concurrence est l'un des principaux atouts de Go, mais elle introduit de la complexité lors de la gestion de l'état partagé. Un besoin courant dans les applications Go haute performance est un cache en mémoire avec une politique d'éviction LRU (Least Recently Used). Bien que la bibliothèque standard de Go propose sync.Map pour les magasins de clés-valeurs concurrents, il n'est pas optimisé pour les charges de travail de mise en cache. Dans cet article, nous explorerons comment implémenter un cache LRU robuste et thread-safe en utilisant un sync.Mutex et sync.Cond, et nous le comparerons à sync.Map pour comprendre leurs compromis respectifs.

Les défis de l'état partagé

Un cache LRU nécessite deux structures de données principales : une liste doublement chaînée pour maintenir l'ordre d'accès et une table de hachage pour les recherches en O(1). Lorsque plusieurs goroutines accèdent à cette structure de manière concurrente, des conditions de course peuvent corrompre les pointeurs de la liste ou les entrées de la table de hachage. L'approche naïve consistant à utiliser une variable globale est dangereuse. Nous avons besoin de primitives de synchronisation qui permettent un débit élevé sans créer de goulots d'étranglement.

Il existe deux décisions architecturales principales ici :

  • Verrouillage grossier (Coarse-grained locking) : L'utilisation d'un seul sync.Mutex protège l'ensemble de la structure du cache. Cette approche est simple à mettre en œuvre et est généralement suffisante pour de nombreux cas d'utilisation.
  • Verrouillage fin (Fine-grained locking / Sharding) : Division du cache en plusieurs segments, chacun avec son propre mutex, afin de réduire la contention des verrous.

Pour cette démonstration, nous nous concentrerons sur une implémentation propre et simple utilisant un seul mutex, car c'est souvent le point de départ le plus performant pour les caches de taille modérée.

Implémentation du cache LRU thread-safe

Notre implémentation enveloppera une liste doublement chaînée et une table de hachage. Le sync.Mutex garantira que des opérations telles que Get, Set et Evict sont atomiques.

package lru

import (
    "container/list"
    "sync"
)

// Cache représente un cache LRU thread-safe.
type Cache struct {
    mu    sync.Mutex
    items map[string]*list.Element
    ll    *list.List
    maxSize int
}

// element stocke la clé et la valeur dans la liste chaînée.
type element struct {
    key   string
    value interface{}
}

// New crée un nouveau cache LRU avec une taille maximale spécifiée.
func New(maxSize int) *Cache {
    return &Cache{
        items:   make(map[string]*list.Element),
        ll:      list.New(),
        maxSize: maxSize,
    }
}

// Get récupère une valeur du cache. Si la clé existe, elle est déplacée au début.
func (c *Cache) Get(key string) (interface{}, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()

    if elem, ok := c.items[key]; ok {
        // Déplacer au début (le plus récemment utilisé)
        c.ll.MoveToFront(elem)
        return elem.Value.(*element).value, true
    }
    return nil, false
}

// Set ajoute une paire clé-valeur au cache. Si le cache est plein, il évince l'élément le moins récemment utilisé.
func (c *Cache) Set(key string, value interface{}) {
    c.mu.Lock()
    defer c.mu.Unlock()

    // Vérifier si la clé existe déjà
    if elem, ok := c.items[key]; ok {
        c.ll.MoveToFront(elem)
        elem.Value.(*element).value = value
        return
    }

    // Évincer si la capacité est atteinte
    if c.ll.Len() >= c.maxSize {
        oldest := c.ll.Back()
        if oldest != nil {
            c.ll.Remove(oldest)
            delete(c.items, oldest.Value.(*element).key)
        }
    }

    // Ajouter le nouvel élément au début
    newElem := c.ll.PushFront(&element{key: key, value: value})
    c.items[key] = newElem
}

Benchmarking : sync.Mutex vs. sync.Map

sync.Map de Go est optimisé pour des cas d'utilisation spécifiques : lorsque les ensembles de clés sont disjoints entre les goroutines, ou lorsqu'il y a beaucoup plus de lectures que d'écritures. Cependant, pour un cache à usage général avec des opérations de lecture/écriture mixtes et des mises à jour fréquentes de clés, sync.Map sous-performe souvent en raison de sa complexité interne et de sa surcharge mémoire.

Examinons un scénario de benchmark conceptuel. Nous simulerons 100 000 lectures concurrentes et 10 000 écritures.

package main

import (
    "testing"
    "sync"
)

func BenchmarkLRUCache(b *testing.B) {
    cache := New(10000)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        cache.Set(string(rune(i)), i)
    }
}

func BenchmarkSyncMap(b *testing.B) {
    var m sync.Map
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        m.Store(string(rune(i)), i)
    }
}

Dans les benchmarks typiques impliquant un accès aléatoire aux clés et des mises à jour fréquentes, le cache LRU basé sur un mutex surpasse sync.Map de manière significative. sync.Map utilise de l'indirection et un verrouillage conditionnel en interne, ce qui ajoute de la latence. Le mutex standard, en particulier avec les versions modernes de Go (Go 1.12+), utilise l'épissage adaptatif (adaptive spinning) et des futexes efficaces, ce qui le rend très performant pour les sections critiques courtes comme nos opérations de cache.

Quand utiliser quoi ?

Utilisez le cache LRU personnalisé avec sync.Mutex lorsque :

  • Vous avez besoin de politiques d'éviction strictes (LRU, LFU, FIFO).
  • Votre charge de travail implique des modèles de lecture/écriture mixtes.
  • Vous souhaitez une utilisation de la mémoire prévisible et une surcharge réduite.

Utilisez sync.Map lorsque :

  • Vous avez des données statiques qui sont rarement supprimées.
  • Les lecteurs et les écrivains opèrent sur des ensembles de clés complètement disjoints.
  • Vous avez besoin d'une table de hachage concurrente rapide et sans surcharge, sans implémenter de logique d'éviction.

Conclusion

Construire un cache LRU thread-safe en Go est un exercice simple qui consiste à comprendre les primitives de synchronisation. Bien que sync.Map soit un outil puissant dans la bibliothèque standard, il ne remplace pas à lui seul les structures de mise en cache spécialisées. En implémentant un cache personnalisé avec sync.Mutex, les développeurs obtiennent un contrôle fin sur la logique d'éviction et atteignent souvent de meilleures performances dans les scénarios de mise en cache à usage général.

Pour les systèmes de production avec une concurrence extrême, envisagez de fragmenter (sharding) votre cache ou d'utiliser des bibliothèques éprouvées comme groupcache ou bigcache. Cependant, pour la plupart des applications, l'approche simple basée sur un mutex offre le meilleur équilibre entre simplicité, performance et contrôle.

Share:
Related Posts