Модуль 7 ⏱ ~29 мин чтения 📐 3 Mermaid диаграмм

33.1. sync.Map под капотом. Read и dirty словари

В прошлой статье (33. Почему iteration по map случайный) мы завершили разбор стандартной мапы. Мы знаем, что она невероятно быстра, пока работает в рамках одной горутины. Но как только мы пытаемся использовать её как глобальный in-memory кэш на многоядерном сервере, мы обязаны защитить её мьютексом.

И тут начинается суровая проблема аппаратного уровня. Если 32 ядра процессора одновременно пытаются сделать RLock() для чтения из map + sync.RWMutex, они все пытаются атомарно инкрементировать один и тот же счетчик читателей (readerCount).

Каждая такая атомарная инструкция (например, LOCK XADD на x86) требует перевода процессорной кэш-линии в эксклюзивное состояние Modified по протоколу MESI. В результате кэш-линия с мьютексом непрерывно «прыгает» между L1/L2 кэшами разных процессорных ядер (эффект Cacheline Bouncing / False Sharing), а ядра простаивают сотни тактов, ожидая арбитража шины памяти и межъядерной синхронизации (подробнее в 15. Mutex и RWMutex под капотом). Высокая конкуренция читателей превращает «параллельное» чтение в тяжелейший аппаратный затор.

Чтобы решить эту проблему, в Go 1.9 добавили sync.Map — специализированную структуру для конкурентных словарей, которая в определенных сценариях работает вообще без блокировок (lock-free) и без инвалидации разделяемых кэш-линий.

Архитектурный контекст: Классическая модель Read/Dirty (Go 1.9–1.23) vs Hash Trie Map (Go 1.24+)

Начиная с версии Go 1.24, внутренняя архитектура sync.Map была полностью переработана: раздельные словари read и dirty заменены на конкурентный Hash Trie Map (пакет internal/sync), работающий на основе префиксного хэш-дерева. Это устранило тяжелый эффект «прогрева» и $O(N)$ копирование при добавлении новых ключей (режим с откатом доступен через GOEXPERIMENT=nosynchashtriemap).
Однако классическая архитектура двух словарей, разобранная ниже, является каноническим примером проектирования lock-free структур в Go и до сих пор составляет ядро вопросов на Senior-собеседованиях.

1. Архитектура: Два словаря (Go 1.9–1.23)

Секрет классической sync.Map в том, что внутри нее находится не одна, а две мапы.

type Map struct {
    mu Mutex

    read atomic.Pointer[readOnly] // Быстрый словарь (только для чтения и атомарных обновлений)
    dirty map[any]*entry          // Медленный словарь (защищен мьютексом mu)

    misses int                    // Счетчик промахов
}

// Вспомогательная структура readOnly, на которую указывает atomic.Pointer
type readOnly struct {
    m       map[any]*entry
    amended bool // true, если dirty содержит ключи, отсутствующие в m
}

read (Словарь для чтения): Это atomic.Pointer, который указывает на структуру readOnly с обычной встроенной мапой. Особенность в том, что мы никогда не меняем ключи в этой мапе напрямую (не добавляем новые). Мы можем только атомарно читать из нее или обновлять значения по уже существующим ключам. Доступ к read не требует захвата мьютекса — кэш-линия остается в состоянии Shared (S) во всех L1/L2 кэшах, обеспечивая максимальную скорость чтения.
dirty (Грязный словарь): Это обычная мапа, доступ к которой строго защищен встроенным мьютексом mu. Сюда попадают все новые ключи.
misses (Промахи): Счетчик, который растет каждый раз, когда мы не нашли ключ в read и были вынуждены пойти под мьютексом в dirty.

2. Структура `entry`: Указатели повсюду

В sync.Map ключи и значения хранятся не напрямую, как в обычной мапе, а через обертку entry (запись).

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

Это критически важно! И read, и dirty словари хранят указатели на одни и те же объекты entry.

Если Горутина А атомарно меняет значение в entry через read словарь, Горутина Б мгновенно увидит это изменение через dirty словарь, потому что они смотрят на один и тот же физический адрес в памяти.

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    subgraph SYNC_MAP ["sync.Map"]
        direction TB
        READ["read (atomic.Pointer[readOnly])<br>Ключ 'A', Ключ 'B'"]
        DIRTY["dirty (под мьютексом mu)<br>Ключ 'A', Ключ 'B', Ключ 'C'"]
    end

    ENT_A["entry A<br>p: *value_A"]:::entry
    ENT_B["entry B<br>p: *value_B"]:::entry
    ENT_C["entry C<br>p: *value_C"]:::entry

    READ -->|"Ключ 'A'"| ENT_A
    READ -->|"Ключ 'B'"| ENT_B

    DIRTY -->|"Ключ 'A'"| ENT_A
    DIRTY -->|"Ключ 'B'"| ENT_B
    DIRTY -->|"Ключ 'C' (новый)"| ENT_C

3. Чтение (Load): Жизнь без блокировок

Посмотрим, что происходит при вызове m.Load("key"):

Fast Path: Рантайм атомарно читает указатель на read словарь и ищет там ключ. Если ключ найден:
- Он проверяет значение entry.p. Если оно не nil и не expunged, возвращает значение и true.
- Мьютекс не трогался, кэш-линии не инвалидировались. Скорость максимальная (единицы наносекунд).
Slow Path: Если ключа в read нет, но флаг read.amended == true (это означает, что в dirty есть ключи, которых еще нет в read):
- Рантайм захватывает мьютекс mu.
- Делает double-check (проверяет read еще раз — вдруг другая горутина успела скопировать dirty в read, пока мы ждали мьютекс).
- Если ключ всё еще не в read, ищет его в dirty.
- Вызывает missLocked(): инкрементирует счетчик misses (промахов).
- Отпускает мьютекс и возвращает результат.

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    LoadStart["Вызов m.Load(key)"]:::warning --> CheckRead{"Ключ есть в read?"}

    CheckRead -- "Да" --> CheckEntry{"entry.p валиден?<br>(не nil и не expunged)"}
    CheckEntry -- "Да" --> ReturnVal["Возврат value, true<br>(Fast Path, Lock-free!)"]
    CheckEntry -- "Нет" --> ReturnNotFound["Возврат nil, false"]

    CheckRead -- "Нет" --> CheckAmended{"read.amended == true?<br>(есть новые ключи в dirty)"}
    CheckAmended -- "Нет" --> ReturnNotFound

    CheckAmended -- "Да" --> LockMu["Захват mu.Lock()"]
    LockMu --> DoubleCheck{"Double-check в read"}
    DoubleCheck -- "Найден" --> UnlockReturn["mu.Unlock(), возврат value"]
    DoubleCheck -- "Не найден" --> CheckDirty{"Ключ есть в dirty?"}

    CheckDirty -- "Да" --> IncMisses["missLocked(): misses++"]
    CheckDirty -- "Нет" --> IncMisses
    IncMisses --> CheckPromo{"misses >= len(dirty)?"}
    CheckPromo -- "Да" --> DoPromo["Promotion: read = dirty,<br>dirty = nil, misses = 0"]
    CheckPromo -- "Нет" --> UnlockDirty["mu.Unlock()"]
    DoPromo --> UnlockDirty
    UnlockDirty --> ReturnDirtyVal["Возврат найденного значения"]

4. Запись (Store): Атомарность или Мьютекс

Что происходит при вызове m.Store("key", value):

Fast Path (Обновление существующего ключа):
- Ищем ключ в read.
- Если ключ найден, пытаемся атомарно обновить его через entry.tryStore(&value).
- Метод tryStore использует атомарный CAS (Compare-And-Swap). Если в ячейке не стоит статус expunged, CAS проходит успешно. Значение обновлено! Никаких мьютексов.
Slow Path (Новый ключ или раскомментирование expunged):
- Если ключа в read нет (или он помечен как expunged):
- Захватываем мьютекс mu.
- Делаем double-check в read.
- Если ключ в read есть, но был expunged (вычеркнут), сбрасываем expunged в nil и добавляем указатель на entry в dirty. Затем атомарно пишем новое значение.
- Если ключ есть в dirty, просто обновляем значение в entry.
- Если ключа нет нигде (новый ключ):
  - Если read.amended == false, помечаем amended = true.
  - Если dirty == nil, вызываем dirtyLocked(): создаем новый dirty словарь и копируем туда неудаленные ключи из read.
  - Создаем новый entry и добавляем его только в dirty словарь.
- Отпускаем мьютекс.

5. Повышение словарей (Promotion)

Мы выяснили, что новые ключи попадают только в dirty. Со временем read устаревает, и все чтения начинают проваливаться в dirty, захватывая мьютекс. Начинается деградация производительности.

Тут вступает в игру счетчик misses (промахи).
Каждый раз, когда чтение не находит ключ в read, misses увеличивается на 1.
Когда количество промахов становится равно длине dirty словаря (misses >= len(dirty)), происходит Promotion (Повышение):

Мьютекс уже захвачен (так как мы были в ветке медленного чтения dirty).
Рантайм просто берет указатель на dirty и атомарно записывает его в read! (Перезаписывая старый read).
dirty обнуляется (dirty = nil).
misses сбрасывается в 0.

Это операция за $O(1)$. Мы мгновенно превратили медленный словарь в быстрый простой перестановкой указателя в atomic.Pointer. Следующие чтения новых ключей пойдут по сверхбыстрому Fast Path.

Ловушка / Gotcha. Налог на добавление (Demotion)

Если dirty стал nil после Promotion, а мы хотим добавить совершенно новый ключ, рантайму нужно заново создать dirty словарь.
Как он это делает? Он проходит циклом по всему read словарю и копирует все неудаленные entry в новый dirty.
Это операция за $O(N)$. Если в вашей sync.Map миллион элементов, и вы постоянно добавляете новые уникальные ключи, каждый раз при пересоздании dirty ваш сервер будет испытывать чудовищные тормоза на копировании.

6. Три состояния удаления: nil и expunged

Самое сложное в sync.Map — это удаление (Delete).
Мы не можем просто удалить ключ из read мапы, потому что она предназначена только для безопасного конкурентного чтения.
Поэтому sync.Map использует Soft Delete (Мягкое удаление).

Указатель entry.p может находиться в трех состояниях:

*Value — Указывает на реальные данные в памяти.
nil — Ключ удален (Soft Delete). Запись еще живет в read, но считается пустой.
expunged (вычеркнут) — Специальный глобальный маркер-синглтон (var expunged = new(any)), означающий, что ключ физически отсутствует в dirty.

stateDiagram-v2
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    [*] --> Value: Создание (Store)
    Value --> Nil: Delete() (Soft Delete в read)
    Nil --> Value: Store() по старому ключу
    Nil --> Expunged: Создание нового dirty (dirtyLocked)
    Expunged --> Value: Store() под мьютексом mu<br>(unexpungeLocked + добавление в dirty)

Зачем нужен expunged?
Вспомним фазу копирования (когда dirty == nil и мы создаем его из read).
Если бы мы копировали в dirty ключи со значением nil, dirty словарь рос бы бесконечно, храня мусорные ключи, которые когда-то давно удалили.
Поэтому при создании нового dirty рантайм:

Проходит по read.
Если видит nil, он атомарно меняет его через CAS на expunged и НЕ копирует этот ключ в dirty.
В dirty попадают только живые ключи.

Теперь, если вы захотите снова записать данные по ключу, который помечен как expunged, рантайм поймет: «Ага, этого ключа нет в dirty!». Он захватит мьютекс, сбросит expunged на nil, добавит ключ обратно в dirty и запишет новое значение.

Mechanical Sympathy: Когда использовать sync.Map?

Знание архитектуры дает нам четкие правила использования:

✅ Идеальные сценарии (sync.Map уничтожает RWMutex):

Append-only кэши (Read-Heavy): Ключи добавляются один раз (например, при инициализации или медленном прогреве), а затем читаются 99% времени. dirty быстро промовируется в read, и вся работа идет без блокировок.
Disjoint Keys (Разделенные ключи): Разные горутины работают с совершенно разными ключами (читают, пишут, удаляют). В этом случае RWMutex вызвал бы глобальную пробку, а sync.Map атомарно обновляет независимые entry в read словаре без взаимных блокировок.

❌ Плохие сценарии (sync.Map медленнее обычного RWMutex):

Write-Heavy в классической архитектуре (Частая запись НОВЫХ ключей): Если вы постоянно пишете новые (уникальные) ключи в классической sync.Map (Go 1.9–1.23), вы постоянно промахиваетесь мимо read. Вы постоянно захватываете мьютекс для dirty, а главное — рантайм регулярно выполняет $O(N)$ копирование из read в dirty. (Примечание: в Go 1.24+ с внедрением Hash Trie Map это ограничение устранено — древовидная структура эффективно масштабирует параллельные записи).
Предсказуемый размер: sync.Map нельзя инициализировать с заранее заданным capacity (как make(map, 1000)). Она будет динамически расти через внутренние аллокации.

Итог

sync.Map оптимизирована под многоядерные архитектуры, чтобы избежать инвалидации кэш-линий при частом чтении.
Она состоит из двух словарей: read (lock-free, обновляется атомарно) и dirty (защищен мьютексом, принимает новые ключи).
При частых промахах (misses) dirty мгновенно становится read ($O(1)$).
При появлении новых ключей read копируется в новый dirty ($O(N)$). Это самое узкое место структуры.
Удаление происходит мягко (атомарная подмена на nil или expunged), мусор очищается лениво при фазе копирования.

Мы завершили огромный блок, посвященный коллекциям и памяти: массивы, слайсы, словари и их конкурентные аналоги. Все они хранят какие-то данные.
Чаще всего в бэкенде этими данными являются строки. В Go строки таят в себе не меньше подвохов, чем слайсы: они иммутабельны, но при этом могут вызывать катастрофические утечки памяти.

В следующей статье мы разберем анатомию текста:
34. Внутреннее устройство string