syncmap

El sync.Map proporcionado por la biblioteca estándar de Go es un map concurrentemente seguro. No es necesario usar locks u otras formas de control al utilizarlo. Su implementación no es particularmente compleja, con solo dos o trescientas líneas de código sin comentarios.

Estructura

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

Tiene solo cuatro campos, que son los siguientes:

• read: map de solo lectura, puede entenderse como un caché de dirty
• dirty: un map ordinario
• misses: número de veces que no se encontró al acceder a read
• mu: protege la seguridad concurrente de dirty

read es del tipo sync.readonly, que internamente también es un map. El campo amended indica si dirty contiene alguna clave que no está en read.

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

Además, la estructura del tipo entry es la siguiente, donde p es un puntero al valor.

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

Para una entrada, hay tres situaciones posibles:

1. Situación normal, almacena el valor correspondiente
2. p es nil, indica que el par clave-valor ha sido eliminado. En este momento dirty puede estar vacío, o puede que todavía exista en dirty.
3. p == expunged, donde expunged es un objeto de interfaz vacío, que también representa que el par clave-valor ha sido eliminado y no existe en dirty.

La seguridad concurrente del map de la biblioteca estándar se logra mediante separación de lectura/escritura. Los punteros entry almacenados en read y dirty apuntan a la misma área de valores. read es de solo lectura, por lo que no habrá problemas de seguridad cuando múltiples goroutines accedan. dirty puede ser modificado y está protegido por un mutex. misses registra el número de veces que no se encontró la clave al acceder. Cuando este número se acumula a cierto valor, el dirty actual se convertirá en read, y misses se reiniciará a cero. Esta es la lógica de funcionamiento general de sync.Map. Posteriormente se analizarán sus operaciones con más detalle.

Lectura

La operación de lectura corresponde al método Map.Load, el código es el siguiente:

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

Primero accede a read. Si existe, se devuelve directamente. De lo contrario, intenta adquirir el mutex mu. Durante el período en que se tiene el lock, dirty puede haber sido promovido a read. Si todavía no se encuentra, finalmente se accede a dirty y se registra un miss, luego se libera el lock.

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
}

A través del método missLocked se puede ver que el umbral para que dirty sea promovido a read es m.misses >= len(m.dirty).

Escritura

La operación de escritura corresponde al método Store, pero en realidad es completada por el método Swap. previous representa el valor anterior, y loaded indica si la clave existe.

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

El proceso de escritura se divide en dos partes. Si la clave accedida existe en read, se obtiene directamente el entry correspondiente, y luego se actualiza el valor del entry mediante CAS. No es necesario adquirir lock durante este proceso.

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 el spin, si p == expunged, significa que la clave ha sido eliminada, y se devuelve directamente.

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 clave no existe en read, se intenta adquirir el lock para las siguientes operaciones. Luego hay tres situaciones. Primera situación: durante la adquisición del lock, dirty fue promovido a read. Si el entry accedido es expunged, significa que ha sido eliminado y no existe en dirty. En este caso, es necesario agregarlo a dirty y luego almacenar el valor correspondiente.

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

Segunda situación: no está en read, pero está en dirty. También se almacena directamente el valor correspondiente.

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

Tercera situación: no está en read ni en dirty. Aquí, si read.amended es false, significa que dirty está vacío. Luego se usa m.dirtyLocked para copiar todos los pares clave-valor no eliminados de read a dirty. Después se marca read.amended como true. Finalmente, se crea directamente un nuevo entry para almacenar el valor correspondiente.

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

Eliminación

La operación de eliminación corresponde al método LoadAndDelete. Su lógica es casi completamente consistente con la operación de lectura, solo que se agrega una llamada a la función 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
}

Al eliminar un par clave-valor, solo se ejecuta delete en dirty. Para read, solo se modifica el valor del entry almacenado 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
    }
  }
}

Iteración

La operación de iteración corresponde al método 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 la iteración, solo se itera sobre read. Si read.amended es true, significa que las claves en read están incompletas. En este caso, dirty se promueve directamente a read. Luego se itera mediante un bucle for range, y se llama a la función de callback para cada par clave-valor.

Rendimiento

sync.Map adopta la separación de lectura/escritura para el control de concurrencia. Es más adecuado para escenarios con muchas lecturas y pocas escrituras, porque en la mayoría de los casos no es necesario adquirir lock al acceder a un par clave-valor. Pero si se va a agregar un nuevo elemento, es necesario adquirir un lock global, lo que bloqueará todas las operaciones del map actual. Esto conduce a un bajo rendimiento de escritura, por lo que sync.Map no es adecuado para todas las situaciones. Para situaciones con pocas lecturas y muchas escrituras, se puede adoptar la forma de lock segmentado. Aquí se recomienda una implementación de código abierto orcaman/concurrent-map: a thread-safe concurrent map for go (github.com), implementada mediante sharding y con soporte para genéricos. El rendimiento y la experiencia de uso serán mejores.