syncmap

sync.Map, предоставляемый стандартной библиотекой Go, является потокобезопасной map-структурой. При использовании не требуется применять блокировки. Его реализация не особенно сложна, всего около двух-трёх сотен строк кода после удаления комментариев.

Структура

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

Имеет всего четыре поля:

• read: map только для чтения, можно понимать как кэш для dirty
• dirty: обычная map
• misses: счётчик промахов при доступе к read
• mu: защищает потокобезопасность dirty

read имеет тип sync.readonly, внутри всё ещё является map. Поле amended указывает, содержит ли dirty ключи, которых нет в read.

type readOnly struct {
  m       map[any]*entry
  amended bool // true, если dirty map содержит некоторые ключи, отсутствующие в m.
}

Кроме того, структура типа entry следующая, где p — указатель на значение:

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

Для entry возможны три случая:

1. Нормальный случай: хранит соответствующее значение
2. p равен nil: указывает, что пара ключ-значение была удалена. В это время dirty может быть пустой, или всё ещё существовать в dirty.
3. p == expunged: expunged — объект пустого интерфейса, также указывает, что пара ключ-значение была удалена и не существует в dirty.

Потокобезопасность стандартной библиотечной map достигается за счёт разделения чтения и записи. Указатели на entry, хранящиеся в read и dirty, указывают на одно и то же значение. read доступен только для чтения, поэтому проблем безопасности при доступе нескольких goroutine нет. dirty может модифицироваться и защищается мьютексом. misses записывает количество промахов доступа к ключам. Когда счётчик накапливается до определённого значения, текущий dirty становится read, а misses обнуляется. Это общая логика работы sync.Map. В последующих разделах будут более детально проанализированы операции.

Чтение

Операция чтения соответствует методу Map.Load:

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

Сначала обращается к read. Если существует, возвращает напрямую. Иначе пытается захватить мьютекс mu, затем снова обращается к read. Это потому, что во время захвата блокировки dirty мог быть повышен до read. Если всё ещё не найдено, в конечном итоге обращается к dirty, записывает промах, затем разблокирует.

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
}

Из метода missLocked видно, что пороговое условие для повышения dirty до read — m.misses >= len(m.dirty).

Запись

Операция записи соответствует методу Store, но фактически завершается методом Swap. previous представляет предыдущее значение, loaded указывает, существует ли ключ.

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

Процесс операции записи делится на две части. Если обращаемый ключ существует в read, напрямую получает соответствующий entry, затем обновляет значение entry через CAS, без блокировки в процессе.

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

Во время спиннинга, если p == expunged, указывает, что ключ был удалён, поэтому возвращается напрямую.

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

Если ключ не существует в read, пытается захватить блокировку для последующих операций. Далее три случая. Первый случай: во время захвата блокировки dirty был повышен до read. Если обращаемый entry равен expunged, указывает, что он был удалён и не существует в dirty. В этом случае его нужно добавить в dirty, затем сохранить соответствующее значение.

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

Второй случай: нет в read, но существует в dirty. Также напрямую сохраняет соответствующее значение:

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

Третий случай: нет в read, и нет в dirty. Здесь, если read.amended равен false, указывает, что dirty пуст. Затем использует m.dirtyLocked для копирования всех неудалённых пар ключ-значение из read в dirty, помечает read.amended как true, и наконец создаёт новый entry для хранения значения.

else {
    if !read.amended {
        // Добавляем первый новый ключ в dirty map.
        // Убеждаемся, что она выделена и помечаем read-only map как неполный.
        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
    }
  }
}

Удаление

Операция удаления соответствует методу LoadAndDelete. Её логика почти полностью согласована с операцией чтения, просто с дополнительным вызовом функции 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
}

При удалении пары ключ-значение операция delete выполняется только на dirty. Для read только модифицирует сохранённое значение entry в 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
    }
  }
}

Итерация

Операция итерации соответствует методу 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
    }
  }
}

Во время итерации итерируется только read. Если read.amended равен true, указывает, что в read отсутствуют ключи. В этом случае dirty напрямую повышается до read, затем итерируется через цикл for range, вызывая функцию обратного вызова для каждой пары ключ-значение.

Производительность

sync.Map использует разделение чтения и записи для управления конкурентностью. Более подходит для сценариев с преимущественным чтением, потому что доступ к паре ключ-значение в большинстве случаев не требует блокировки. Однако, если добавлять новый элемент, требуется захватить глобальную блокировку, что блокирует все операции на текущей map. Это приводит к плохой производительности записи. Поэтому sync.Map подходит не для всех ситуаций. Для сценариев с преимущественной записью можно использовать сегментированную блокировку для избежания глобальной блокировки. Вот рекомендуемая реализация с открытым исходным кодом: orcaman/concurrent-map: потокобезопасная конкурентная map для go (github.com). Реализована с использованием шардирования, поддерживает дженерики и обеспечивает лучшую производительность и пользовательский опыт.