syncmap

Die von der Go-Standardbibliothek bereitgestellte sync.Map ist eine nebenläufigkeitssichere Map. Bei der Verwendung ist keine Synchronisation mit Sperren oder ähnlichem erforderlich. Die Implementierung ist nicht besonders komplex - ohne Kommentare insgesamt nur zwei- bis dreihundert Zeilen Code.

Struktur

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

Sie hat insgesamt nur vier Felder:

• read, eine schreibgeschützte Map, die als Cache für dirty verstanden werden kann
• dirty, eine gewöhnliche Map
• misses, die Anzahl der Fehlzugriffe beim Zugriff auf read
• mu, schützt die Nebenläufigkeitssicherheit von dirty

read ist vom Typ sync.readonly, der intern ebenfalls eine Map enthält. Das Feld amended gibt an, ob dirty Keys enthält, die nicht in read vorhanden sind.

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

Der Typ entry hat folgende Struktur, wobei p ein Zeiger auf den Wert ist:

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

Für einen Entry gibt es drei mögliche Zustände:

1. Normaler Fall, der entsprechende Wert ist gespeichert
2. p ist nil, was bedeutet, dass das Schlüssel-Wert-Paar gelöscht wurde. In diesem Fall kann dirty leer sein oder das Paar kann weiterhin in dirty existieren.
3. p == expunged, expunged ist ein leeres Interface-Objekt und repräsentiert ebenfalls, dass das Schlüssel-Wert-Paar gelöscht wurde und nicht in dirty existiert.

Die Nebenläufigkeitssicherheit der Standardbibliotheks-Map wird durch Lese-Schreib-Trennung implementiert. Die in read und dirty gespeicherten entry-Zeiger zeigen alle auf denselben Wert. read ist schreibgeschützt, daher gibt es keine Sicherheitsprobleme beim Zugriff mehrerer Goroutinen. dirty kann geändert werden und ist durch einen Mutex geschützt. misses zeichnet die Anzahl der Fehlzugriffe auf Keys auf. Wenn die Anzahl einen bestimmten Wert erreicht, wird das aktuelle dirty zu read, und misses wird zurückgesetzt. Das ist die grobe Arbeitslogik von sync.Map, die später detaillierter analysiert wird.

Lesen

Die Leseoperation entspricht der Methode Map.Load, der Code lautet:

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

Zuerst wird auf read zugegriffen. Wenn der Key vorhanden ist, wird er direkt zurückgegeben. Andernfalls wird versucht, den mu-Mutex zu erhalten und dann erneut auf read zuzugreifen, da während des Erwerbs der Sperre dirty zu read befördert worden sein könnte. Wenn er immer noch nicht gefunden wird, wird schließlich auf dirty zugegriffen, ein Miss wird aufgezeichnet und die Sperre wird freigegeben.

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
}

Aus der Methode missLocked ist ersichtlich, dass die Schwellenbedingung für die Beförderung von dirty zu read m.misses >= len(m.dirty) ist.

Schreiben

Die Schreiboperation entspricht der Store-Methode, wird aber tatsächlich von der Swap-Methode ausgeführt. previous repräsentiert den vorherigen Wert, loaded gibt an, ob der Key existiert.

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

Der Ablauf der Schreiboperation ist in zwei Teile gegliedert. Wenn der angesprochene Key in read existiert, wird der entsprechende entry direkt abgerufen und dann der Wert des entry mittels CAS aktualisiert, ohne dass eine Sperre erforderlich ist.

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

Während des Spinnings, wenn p == expunged, bedeutet dies, dass der Key bereits gelöscht wurde, und es wird direkt zurückgegeben.

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

Wenn der Key nicht in read existiert, wird versucht, eine Sperre zu erhalten, um die folgenden Operationen durchzuführen. Es gibt drei Fälle. Im ersten Fall wurde dirty während des Erwerbs der Sperre zu read befördert. Wenn der gefundene entry expunged ist, bedeutet dies, dass er bereits gelöscht wurde und nicht in dirty existiert. In diesem Fall muss er zu dirty hinzugefügt werden, bevor der entsprechende Wert gespeichert wird.

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

Im zweiten Fall ist der Key nicht in read, aber in dirty vorhanden. Auch hier wird der entsprechende Wert direkt gespeichert:

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

Im dritten Fall ist der Key weder in read noch in dirty vorhanden. Wenn hier read.amended false ist, bedeutet dies, dass dirty leer ist. Dann werden mit m.dirtyLocked alle nicht gelöschten Schlüssel-Wert-Paare aus read nach dirty kopiert, read.amended wird auf true gesetzt, und schließlich wird ein neuer entry erstellt, um den entsprechenden Wert zu speichern.

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

Löschen

Die Löschoperation entspricht der Methode LoadAndDelete. Der Ansatz ist fast identisch mit der Leseoperation, nur mit einem zusätzlichen Aufruf der delete-Funktion.

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
}

Beim Löschen eines Schlüssel-Wert-Paares wird die delete-Operation nur auf dirty angewendet. Für read wird lediglich der Wert des gespeicherten Entry auf nil gesetzt.

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

Iteration

Die Iterationsoperation entspricht der Range-Methode:

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

Bei der Iteration wird nur read durchlaufen. Wenn read.amended true ist, bedeutet dies, dass Keys in read fehlen. In diesem Fall wird dirty direkt zu read befördert, dann wird mit einer for range-Schleife iteriert und für jedes Schlüssel-Wert-Paar die Callback-Funktion aufgerufen.

Leistung

sync.Map verwendet Lese-Schreib-Trennung für Nebenläufigkeitskontrolle. Sie eignet sich besser für Szenarien mit vielen Lese- und wenigen Schreiboperationen, da in den meisten Fällen beim Zugriff auf ein Schlüssel-Wert-Paar keine Sperre erforderlich ist. Wenn jedoch ein neues Element hinzugefügt werden soll, muss eine globale Sperre gehalten werden, die alle Operationen der aktuellen Map blockiert. Dies führt zu einer schlechten Schreibleistung. Daher ist sync.Map nicht für alle Situationen geeignet. Für Szenarien mit wenigen Lese- und vielen Schreiboperationen kann eine Segmentierungssperr-Implementierung verwendet werden, um eine globale Blockierung zu vermeiden. Hier wird eine Open-Source-Implementierung empfohlen: orcaman/concurrent-map: a thread-safe concurrent map for go (github.com), die mit Sharding implementiert ist und Generics unterstützt - sowohl in der Leistung als auch im Nutzungserlebnis besser.