sync.Map

sync.Map fornito dalla libreria standard di Go è una map concurrent-safe. Non è necessario usare lock o simili per controllarla durante l'uso. La sua implementazione non è particolarmente complessa, con solo due-trecento righe di codice rimuovendo i commenti.

Struttura

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

Ha solo quattro campi, come segue:

• read: map di sola lettura, può essere compresa come una cache di dirty
• dirty: una map ordinaria
• misses: numero di mancati accessi durante la lettura di read
• mu: protegge la sicurezza concurrent di dirty

read è di tipo sync.readonly, che internamente è ancora una map. Il campo amended indica se dirty contiene chiavi che read non ha.

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

Inoltre, la struttura del tipo entry è la seguente, dove p è un puntatore al valore.

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

Per un entry, ci sono tre possibili situazioni:

1. Situazione normale: contiene il valore corrispondente
2. p è nil: indica che la coppia chiave-valore è stata eliminata. In questo momento dirty potrebbe essere vuota, oppure potrebbe ancora essere presente in dirty.
3. p == expunged: expunged è un oggetto interfaccia vuoto, che rappresenta anche che la coppia chiave-valore è stata eliminata e non è presente in dirty.

La sicurezza concurrent della map standard è realizzata attraverso la separazione tra lettura e scrittura. I puntatori entry memorizzati in read e dirty puntano alla stessa area di valore. read è di sola lettura, quindi non ci sono problemi di sicurezza quando più goroutine accedono. dirty può essere modificato ed è protetto da un mutex. misses registra il numero di mancati accessi alle chiavi. Quando il numero accumulato raggiunge un certo valore, il dirty corrente diventa read, e misses viene azzerato. Questa è la logica di funzionamento generale di sync.Map. Di seguito analizzeremo più dettagliatamente le sue operazioni.

Lettura

L'operazione di lettura corrisponde al metodo Map.Load, come mostrato nel codice seguente:

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

Per prima cosa accede a read. Se esiste, restituisce direttamente. Altrimenti, prova ad acquisire il mutex mu. Durante il periodo di acquisizione del lock, dirty potrebbe essere promosso a read. Se ancora non trova, alla fine accede a dirty e registra un miss, poi sblocca.

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
}

Dal metodo missLocked si può vedere che la soglia per la promozione di dirty a read è m.misses >= len(m.dirty).

Scrittura

L'operazione di scrittura corrisponde al metodo Store, ma in realtà è completata dal metodo Swap. previous rappresenta il valore precedente, loaded indica se la chiave esiste.

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

Il processo di scrittura si divide in due parti. Se la chiave访问ata esiste in read, ottiene direttamente l'entry corrispondente, poi aggiorna il valore dell'entry tramite CAS, senza bisogno di acquisire il lock durante il processo.

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

Durante lo spin, se p == expunged, significa che la chiave è stata eliminata, quindi restituisce direttamente.

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

Se la chiave non esiste in read, prova ad acquisire il lock per le operazioni successive. Poi ci sono tre situazioni. Prima situazione: durante l'acquisizione del lock, dirty è stato promosso a read. Se l'entry访问ato è expunged, significa che è stato eliminato e non esiste in dirty. In questo caso è necessario aggiungerlo a dirty, poi memorizzare il valore corrispondente.

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

Seconda situazione: non c'è in read, ma c'è in dirty. Anche in questo caso memorizza direttamente il valore corrispondente.

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

Terza situazione: non c'è né in read né in dirty. Qui, se read.amended è false, significa che dirty è vuoto. Poi usa m.dirtyLocked per copiare tutte le coppie chiave-valore non eliminate da read a dirty. Quindi marca read.amended come true. Infine, crea direttamente un nuovo entry per memorizzare il valore corrispondente.

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

Eliminazione

L'operazione di eliminazione corrisponde al metodo LoadAndDelete. La sua logica è quasi completamente identica all'operazione di lettura, solo con una chiamata in più alla funzione 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
}

Quando si elimina una coppia chiave-valore, si esegue sempre solo l'operazione delete su dirty. Per quanto riguarda read, modifica solo il valore dell'entry memorizzato a 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
    }
  }
}

Iterazione

L'operazione di iterazione corrisponde al metodo 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
    }
  }
}

Durante l'iterazione, si itera solo su read. Se read.amended è true, significa che le chiavi in read sono mancanti. In questo caso, dirty viene promosso direttamente a read, poi si usa il ciclo for range per iterare e chiamare la funzione di callback per ogni coppia chiave-valore.

Prestazioni

sync.Map adotta la separazione tra lettura e scrittura per il controllo concurrent. È più adatto per scenari con molte letture e poche scritture, perché nella maggior parte dei casi l'accesso a una coppia chiave-valore non richiede lock. Tuttavia, se si deve aggiungere un elemento, è necessario acquisire un lock globale, che blocca tutte le operazioni sulla map corrente. Questo porta a basse prestazioni di scrittura, quindi sync.Map non è adatto per tutte le situazioni. Per scenari con poche letture e molte scritture, si può adottare un approccio con lock segmentati. Questo può evitare il blocco globale. Qui consiglio un'implementazione open source: orcaman/concurrent-map: a thread-safe concurrent map for go (github.com). È implementato con sharding e supporta i generici. Le prestazioni e l'esperienza d'uso sono migliori.