Go: Внутреннее устройство sync.Map, сравнение производительности с map + RWMutex

Upd.: теперь и на Хабре

Для тех, кто хочет понять, когда стоит использовать sync.Map, а когда достаточно обычной map с мьютексом.

Внутреннее устройство sync.Map

sync.Map - это потокобезопасная реализация карты в Go, оптимизированная для определенных сценариев использования.
Основная структура sync.Map выглядит примерно так:

type Map struct {
    mu Mutex
    read atomic.Value // readOnly
    dirty map[interface{}]*entry
    misses int
}

type readOnly struct {
    m       map[interface{}]*entry
    amended bool
}

type entry struct {
    p unsafe.Pointer // *interface{}
}

Здесь мы видим несколько ключевых полей:

mu - мьютекс для защиты доступа к dirty мапе
read - атомарное значение, содержащее readOnly структуру
dirty - обычная Go мапа, содержащая все актуальные значения
misses - счетчик промахов при чтении из read мапы

Основная идея sync.Map заключается в использовании двух внутренних карт: read (только для чтения) и dirty (для записи и чтения). Это позволяет оптимизировать операции чтения, которые часто не требуют блокировки.

Операция Load

При выполнении операции Load, sync.Map сначала пытается найти значение в read мапе. Если значение найдено, оно возвращается без какой-либо блокировки. Это очень быстрая операция.
Если значение не найдено в read мапе, увеличивается счетчик misses, и sync.Map проверяет dirty мапу, захватывая мьютекс. Если значение найдено в dirty мапе, оно возвращается.

Операция Store

При выполнении Store, sync.Map сначала проверяет, существует ли ключ в read мапе. Если да, она пытается обновить значение атомарно. Если это не удается (например, ключ был удален), она переходит к обновлению dirty мапы.
Если ключ не существует в read мапе, sync.Map захватывает мьютекс и обновляет dirty мапу.

Когда dirty заменяет read

Интересный момент происходит, когда количество промахов при чтении из read мапы (misses) превышает длину dirty мапы. В этом случае sync.Map выполняет операцию "продвижения":

1. Захватывается мьютекс
2. Содержимое dirty мапы копируется в новую read мапу
3. dirty мапа очищается
4. Счетчик misses сбрасывается

Это выглядит примерно так:

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
}

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

Сравнение производительности с map + RWMutex

Теперь давайте сравним производительность sync.Map с обычной map, защищенной sync.RWMutex.
Обычная потокобезопасная мапа может выглядеть так:

type SafeMap struct {
    mu sync.RWMutex
    m  map[interface{}]interface{}
}

func (sm *SafeMap) Load(key interface{}) (interface{}, bool) {
    sm.mu.RLock()
    defer sm.mu.RUnlock()
    val, ok := sm.m[key]
    return val, ok
}

func (sm *SafeMap) Store(key, value interface{}) {
    sm.mu.Lock()
    defer sm.mu.Unlock()
    sm.m[key] = value
}

Производительность этих двух подходов будет зависеть от конкретного сценария использования:

- Если у вас преимущественно операции чтения, sync.Map может быть быстрее, особенно если ключи стабильны (мало добавлений новых ключей).
- Если у вас много операций записи, особенно добавления новых ключей, map + RWMutex может показать лучшую производительность.
- При небольшом количестве горутин, работающих с мапой, разница может быть незначительной, и простота map + RWMutex может быть предпочтительнее.
- При большом количестве горутин, особенно на многоядерных системах, sync.Map может показать лучшую масштабируемость.

Заключение

sync.Map - не серебряная пуля. Её внутреннее устройство оптимизировано под определенные сценарии использования.