Как устроена map в Go? Почему она не thread-safe?

Устройство map в Go

Map (или хэш-таблица) в Go — это встроенный тип данных для хранения пар **ключ-значение**. Внутренняя реализация оптимизирована для производительности и использует несколько интересных подходов.

Внутренняя структура

Основные компоненты реализации:

// Упрощенное представление структуры hmap (реальный код в runtime/map.go)
type hmap struct {
    count     int    // текущее количество элементов
    flags     uint8
    B         uint8  // логарифм количества bucket'ов (2^B)
    noverflow uint16 // примерное количество overflow bucket'ов
    hash0     uint32 // seed для хэш-функции
    
    buckets    unsafe.Pointer // массив bucket'ов
    oldbuckets unsafe.Pointer // старый массив bucket'ов при росте
    nevacuate  uintptr        // прогресс эвакуации
    
    extra *mapextra // дополнительные поля для больших map
}

Bucket (ведро) — это основная единица хранения:

// Каждый bucket содержит 8 пар ключ-значение
type bmap struct {
    tophash  [8]uint8  // старшие биты хэшей ключей
    keys     [8]keytype // ключи
    values   [8]valuetype // значения
    overflow *bmap     // указатель на overflow bucket
}

Принципы работы

1. Хэширование: При добавлении элемента вычисляется хэш ключа с использованием горячей хэш-функции (AES-based для процессоров с поддержкой AES-NI).

2. Поиск bucket'а: Младшие биты хэша определяют номер bucket'а (hash & (2^B - 1)).

3. Поиск в bucket'е: Старшие 8 бит хэша (tophash) сравниваются с записями в bucket'е. При совпадении проверяется равенство ключей.

4. Разрешение коллизий: Используется метод цепочки через overflow bucket'ы.

Процесс роста (rehashing)

При достижении определенного коэффициента загрузки (≈6.5 элементов на bucket) происходит рост:

• Создается новый массив bucket'ов в 2 раза больше
• Переход происходит постепенно (incremental rehashing)
• При последующих операциях элементы перемещаются из oldbuckets в новые buckets

// Пример постепенного перехеширования
if h.growing() {
    // Выполнить часть работы по перемещению
    hashGrow(t, h)
}

Почему map не thread-safe

Основные причины

1. Производительность: Добавление блокировок в базовую реализацию замедлило бы все операции. В Go предпочитают предоставить легковесные примитивы, а сложную синхронизацию реализовывать явно.

2. Семантика операций: Даже с мьютексами есть тонкости:

   // Проблема: между проверкой и записью другая горутина может изменить map
   if _, ok := m[key]; !ok {
       // Другая горутина может добавить key здесь!
       m[key] = value // Возможна гонка данных
   }
   

3. Внутренняя изменчивость: Операции, кажущиеся атомарными, на самом деле состоят из нескольких шагов:

   • Рехеширование может перемещать элементы между bucket'ами
   • Удаление элементов изменяет внутренние структуры
   • Даже чтение не полностью безопасно при параллельной записи

Конкретные примеры проблем

Гонка данных при записи:

// Две горутин пытаются записать в map
go func() { m[1] = "a" }()
go func() { m[1] = "b" }()
// Результат неопределен, может привести к панике

Проблемы с итерацией:

// Одна горутина итерирует, другая изменяет
go func() {
    for k, v := range m {
        fmt.Println(k, v)
        // Может получить устаревшие, дублированные или пропущенные значения
    }
}()
go func() {
    m[2] = "new"
}()

Решения для многопоточного доступа

1. sync.RWMutex для контроля доступа:

var mu sync.RWMutex
var m = make(map[string]int)

// Запись
mu.Lock()
m["key"] = 42
mu.Unlock()

// Чтение
mu.RLock()
value := m["key"]
mu.RUnlock()

1. sync.Map для специфических случаев:

var sm sync.Map
sm.Store("key", "value")
value, ok := sm.Load("key")

1. Шардирование для уменьшения конкуренции:

type ShardedMap []*shard

type shard struct {
    sync.RWMutex
    m map[string]interface{}
}

// Каждая горутина работает со своим шардом

Компромиссы проектирования

Разработчики Go сознательно выбрали простоту и предсказуемость:

• Легко понять поведение map в однопоточном контексте
• Явная синхронизация делает код более читаемым
• Можно выбирать оптимальную стратегию синхронизации под конкретную задачу

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