syncmap

Le sync.Map fourni par la bibliothèque standard Go est une map concurrentiellement sûre, son utilisation ne nécessite pas de verrous ou d'autres méthodes de contrôle. Son implémentation n'est pas particulièrement complexe, sans les commentaires elle ne fait qu'environ deux à trois cents lignes de code.

Structure

type Map struct {
    mu Mutex
    read atomic.Pointer[readOnly]
    dirty map[any]*entry
    misses int
}

Elle n'a que quatre champs :

• read, une map en lecture seule, peut être considérée comme un cache de dirty
• dirty, une map ordinaire
• misses, le nombre de fois où l'accès à read n'a pas abouti
• mu, protège la sécurité concurrentielle de dirty

read est de type sync.readonly, qui contient également une map. Le champ amended indique si dirty contient des clés que read n'a pas.

type readOnly struct {
  m       map[any]*entry
  amended bool // true if the dirty map contains some key not in m.
}

De plus, le type entry a la structure suivante, où p est un pointeur vers la valeur.

type entry struct {
  p atomic.Pointer[any]
}

Pour une entrée, il y a trois cas possibles :

1. Cas normal, elle contient la valeur correspondante
2. p est nil, ce qui indique que la paire clé-valeur a été supprimée. À ce moment, dirty peut être vide, ou l'entrée peut encore exister dans dirty.
3. p == expunged, expunged est un objet interface vide, qui indique également que la paire clé-valeur a été supprimée et n'existe pas dans dirty.

La sécurité concurrentielle de la map de la bibliothèque standard est réalisée par séparation lecture/écriture. Les pointeurs entry stockés dans read et dirty pointent tous vers la même zone de valeur. read est en lecture seule, donc l'accès par plusieurs goroutines ne pose pas de problème de sécurité. dirty peut être modifié et est protégé par un mutex. misses enregistre le nombre de fois où l'accès à une clé n'a pas abouti. Quand ce nombre atteint une certaine valeur, le dirty actuel devient read, et misses est remis à zéro. C'est la logique de fonctionnement générale de sync.Map, les opérations seront analysées plus en détail par la suite.

Lecture

L'opération de lecture correspond à la méthode Map.Load, dont le code est le suivant :

func (m *Map) Load(key any) (value any, ok bool) {
  read := m.loadReadOnly()
  e, ok := read.m[key]
  if !ok && read.amended {
    m.mu.Lock()
    read = m.loadReadOnly()
    e, ok = read.m[key]
    if !ok && read.amended {
      e, ok = m.dirty[key]
      m.missLocked()
    }
    m.mu.Unlock()
  }
  if !ok {
    return nil, false
  }
  return e.load()
}

Elle accède d'abord à read, si la clé existe elle retourne directement, sinon elle essaie d'acquérir le mutex mu, puis accède à nouveau à read, car pendant l'acquisition du verrou, dirty a pu être promu en read. Si la clé n'est toujours pas trouvée, elle accède finalement à dirty, enregistre un miss, puis libère le verrou.

func (m *Map) missLocked() {
  m.misses++
  if m.misses < len(m.dirty) {
    return
  }
  m.read.Store(&readOnly{m: m.dirty})
  m.dirty = nil
  m.misses = 0
}

La méthode missLocked montre que le seuil pour que dirty soit promu en read est m.misses >= len(m.dirty).

Écriture

L'opération d'écriture correspond à la méthode Store, mais elle est en fait réalisée par la méthode Swap. previous représente la valeur précédente, loaded indique si la clé existe.

func (m *Map) Swap(key, value any) (previous any, loaded bool)

Le processus d'écriture se divise en deux parties. Si la clé accédée existe dans read, on obtient directement l'entry correspondante, puis on met à jour la valeur de l'entry via CAS, sans avoir besoin de verrouiller.

read := m.loadReadOnly()
if e, ok := read.m[key]; ok {
    if v, ok := e.trySwap(&value); ok {
        if v == nil {
            return nil, false
        }
        return *v, true
    }
}

Pendant le spin, si p == expunged, cela signifie que la clé a été supprimée, et on retourne directement.

func (e *entry) trySwap(i *any) (*any, bool) {
  for {
    p := e.p.Load()
    if p == expunged {
      return nil, false
    }
    if e.p.CompareAndSwap(p, i) {
      return p, true
    }
  }
}

Si la clé n'existe pas dans read, on essaie d'acquérir le verrou pour les opérations suivantes. Il y a trois cas possibles. Premier cas, pendant l'acquisition du verrou, dirty a été promu en read. Si l'entry accédée est expunged, cela signifie qu'elle a été supprimée et n'existe pas dans dirty. Dans ce cas, il faut l'ajouter à dirty, puis stocker la valeur correspondante.

read = m.loadReadOnly()
if e, ok := read.m[key]; ok {
    if e.unexpungeLocked() {
        m.dirty[key] = e
    }
    if v := e.swapLocked(&value); v != nil {
        loaded = true
        previous = *v
    }
}

Deuxième cas, la clé n'est pas dans read mais est dans dirty, on stocke directement la valeur correspondante :

if e, ok := m.dirty[key]; ok {
    if v := e.swapLocked(&value); v != nil {
        loaded = true
        previous = *v
    }
}

Troisième cas, la clé n'est ni dans read ni dans dirty. Ici, si read.amended est false, cela signifie que dirty est vide. On utilise alors m.dirtyLocked pour copier toutes les paires clé-valeur non supprimées de read vers dirty, puis on marque read.amended à true. Enfin, on crée une nouvelle entry pour stocker la valeur correspondante.

else {
    if !read.amended {
        // We're adding the first new key to the dirty map.
        // Make sure it is allocated and mark the read-only map as incomplete.
        m.dirtyLocked()
        m.read.Store(&readOnly{m: read.m, amended: true})
    }
    m.dirty[key] = newEntry(value)
}

func (m *Map) dirtyLocked() {
  if m.dirty != nil {
    return
  }

  read := m.loadReadOnly()
  m.dirty = make(map[any]*entry, len(read.m))
  for k, e := range read.m {
    if !e.tryExpungeLocked() {
      m.dirty[k] = e
    }
  }
}

Suppression

L'opération de suppression correspond à la méthode LoadAndDelete, son principe est presque identique à l'opération de lecture, avec seulement un appel supplémentaire à la fonction delete.

func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
  read := m.loadReadOnly()
  e, ok := read.m[key]
  if !ok && read.amended {
    m.mu.Lock()
    read = m.loadReadOnly()
    e, ok = read.m[key]
    if !ok && read.amended {
      e, ok = m.dirty[key]
      delete(m.dirty, key)
      m.missLocked()
    }
    m.mu.Unlock()
  }
  if ok {
    return e.delete()
  }
  return nil, false
}

Lors de la suppression d'une paire clé-valeur, on n'exécute l'opération delete que sur dirty. Pour read, on se contente de modifier la valeur de l'entry stockée à nil.

func (e *entry) delete() (value any, ok bool) {
  for {
    p := e.p.Load()
    if p == nil || p == expunged {
      return nil, false
    }
    if e.p.CompareAndSwap(p, nil) {
      return *p, true
    }
  }
}

Parcours

L'opération de parcours correspond à la méthode Range :

func (m *Map) Range(f func(key, value any) bool) {
  read := m.loadReadOnly()
  if read.amended {
    m.mu.Lock()
    read = m.loadReadOnly()
    if read.amended {
      read = readOnly{m: m.dirty}
      m.read.Store(&read)
      m.dirty = nil
      m.misses = 0
    }
    m.mu.Unlock()
  }

  for k, e := range read.m {
    v, ok := e.load()
    if !ok {
      continue
    }
    if !f(k, v) {
      break
    }
  }
}

Lors du parcours, on ne parcourt que read. Si read.amended est true, cela signifie que des clés manquent dans read. Dans ce cas, on promeut directement dirty en read, puis on parcourt avec une boucle for range en appelant la fonction de rappel pour chaque paire clé-valeur.

Performance

sync.Map adopte une séparation lecture/écriture pour le contrôle de concurrence. Elle est mieux adaptée aux scénarios avec beaucoup de lectures et peu d'écritures, car dans la plupart des cas, l'accès à une paire clé-valeur ne nécessite pas de verrouillage. Cependant, pour ajouter un nouvel élément, il faut détenir un verrou global, ce qui bloque toutes les opérations sur la map actuelle. Cela entraîne de mauvaises performances en écriture. Donc sync.Map n'est pas adaptée à toutes les situations. Pour les scénarios avec peu de lectures et beaucoup d'écritures, on peut adopter une approche par verrous segmentés pour éviter le blocage global. Je recommande une implémentation open source orcaman/concurrent-map: a thread-safe concurrent map for go (github.com), qui utilise une approche par segments et supporte les génériques, offrant de meilleures performances et une meilleure expérience d'utilisation.