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

33. Почему iteration по map случайный

Если вы напишете простейший код, который кладет в мапу три ключа и выводит их через цикл for k, v := range m, а затем запустите его несколько раз, вы заметите странность.

Порядок ключей будет непрерывно меняться. Сегодня это A, B, C, через секунду B, C, A, затем C, A, B.

Каждый разработчик быстро усваивает базовое правило: порядок ключей в мапе не гарантирован. Но Senior-инженер и системный программист обязаны задать более глубокие вопросы: как именно рантайм достигает этой случайности под капотом, почему эта случайность реализована программно, и главное — зачем создатели языка сознательно тратят на это драгоценные такты процессора?

Природа хэш-таблиц: Иллюзия порядка

Любая хэш-таблица по своей математической природе не упорядочена. Элементы распределяются по бакетам (см. 31. Внутреннее устройство map. hmap, bucket, overflow) на основе хэш-функции.

Если вы вставите ключи "Alice", "Bob" и "Charlie", они могут попасть в бакеты 5, 1 и 7 соответственно. Если бы мы просто итерировались по памяти от нулевого бакета к последнему, мы бы всегда получали порядок "Bob", "Alice", "Charlie".

В ранних версиях Go (до версии 1.3) так и было. Порядок итерации не был отсортирован по алфавиту или времени добавления, но он был стабильным в рамках одного запуска приложения, если мапа не менялась.

Более того, на одном и том же наборе данных и на одинаковой архитектуре CPU итератор послушно шел по цепочке ячеек памяти: сначала ячейка 0 бакета 0, затем ячейка 1 бакета 0... Казалось бы, в чем проблема? Какая разница, что обход детерминирован, если в спецификации написано, что он случаен?

Закон Хайрама (Hyrum's Law)

Стабильность итерации сыграла с разработчиками злую шутку.

В программной инженерии существует эмпирическое правило, сформулированное инженером Google Хайрамом Райтом:

«Если у вашего API есть достаточное количество пользователей, то неважно, что именно вы обещаете в контракте: любое наблюдаемое поведение вашей системы станет зависимостью для кого-то из пользователей.»

В официальной спецификации языка Go было четко написано: «Порядок итерации по мапе не специфицирован». Но разработчики — люди практичные и склонные к удобным предположениям. Они писали юнит-тесты, сравнивали сериализованный JSON или строковый вывод, видели, что range m выдает ["A", "B", "C"] стабильно, и завязывали логику тестов (или даже бизнес-логику!) на этот конкретный порядок.

Когда команда Go попыталась улучшить хэш-функцию мапы (чтобы сделать её быстрее и защитить от коллизионных DoS-атак через рандомизацию seed), это привело к изменению распределения ключей по бакетам. В результате сотни тысяч тестов по всему миру упали, потому что код неявно полагался на «случайный, но стабильный» порядок.

Хуже того: код, работавший на x86-64, мог тихо сломаться при переносе на ARM64 или при минорном обновлении компилятора.

Решение Go: Принудительная случайность

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

Каждый раз, когда вы вызываете for k, v := range m, компилятор генерирует вызов функции рантайма runtime.mapiterinit. 

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
    Start["Цикл for k, v := range m"]:::entry --> Init["Вызов runtime.mapiterinit()"]
    Init --> R1["Вызов fastrand() для выбора startBucket"]
    Init --> R2["Вызов fastrand() для выбора offset (0..7)"]

    R1 --> SetHiter["Инициализация структуры hiter<br>(startBucket, offset, bucket = startBucket)"]
    R2 --> SetHiter

    SetHiter --> Loop["Вызов runtime.mapiternext()"]
    Loop --> CheckEnd{"Обошли все бакеты<br>и слоты?"}
    CheckEnd -- "Нет" --> Yield["Возврат k, v в тело цикла"]
    Yield --> NextSlot["Смещение к следующему слоту/бакету<br>(с учетом кольцевого обхода)"]
    NextSlot --> Loop
    CheckEnd -- "Да" --> Exit["Завершение цикла range"]

Функция runtime.mapiterinit аллоцирует на стеке структуру итератора hiter и выполняет две ключевые операции:

  1. Случайный стартовый бакет: Рантайм вызывает встроенный ультрабыстрый генератор псевдослучайных чисел fastrand() (в современных версиях cheaprand()). С помощью полученного числа он выбирает случайный бакет, с которого начнется обход (например, бакет номер 2 из 4).
  2. Случайное смещение (Offset): Выбрав стартовый бакет, рантайм снова использует fastrand(), чтобы выбрать смещение внутри бакета — от 0 до 7 (так как в бакете bmap ровно 8 слотов).
flowchart LR
    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 BUCKETS ["Массив бакетов (hmap.buckets)"]
        direction TB
        B0["Бакет 0"]:::process
        B1["Бакет 1"]:::process
        B2["Бакет 2"]:::process
        B3["Бакет 3"]:::process
    end

    RAND1{"fastrand()<br>Случайный бакет"} -->|"Выпало 2"| B2

    subgraph BMAP2 ["Бакет 2 (8 слотов)"]
        direction LR
        S0[0] -.- S1[1] -.- S2[2] -.- S3[3] -.- S4[4] -.- S5[5] -.- S6[6] -.- S7[7]
    end

    B2 --> BMAP2
    RAND2{"fastrand()<br>Случайный оффсет"} -->|"Выпало 5"| S5

    S5 -->|"Старт итерации"| S6

Итератор стартует с бакета 2, со слота 5. Он дочитывает бакет до конца (слоты 6, 7), затем переходит к бакету 3 (читая слоты 5, 6, 7, 0, 1, 2, 3, 4 — смещение сохраняется для всех бакетов), затем перепрыгивает на бакет 0, затем на 1, пока не обойдет всю структуру и не вернется к исходной точке.

Go 
// Упрощенный фрагмент структуры итератора runtime/map.go
type hiter struct {
    key         unsafe.Pointer // Указатель на текущий ключ
    elem        unsafe.Pointer // Указатель на текущее значение
    t           *maptype       // Тип мапы
    h           *hmap          // Указатель на саму мапу
    buckets     unsafe.Pointer // Массив бакетов на момент старта итерации
    bptr        *bmap          // Текущий бакет
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    startBucket uintptr        // Номер стартового бакета (из fastrand)
    offset      uint8          // Смещение первого слота (0..7 из fastrand)
    wrapped     bool           // Сделали ли полный круг по массиву
    B           uint8
    i           uint8
    bucket      uintptr
    checkBucket uintptr
}

Mechanical Sympathy. Цена случайности

Стоит ли эта случайность процессорного времени?

Генерация чисел через fastrand() занимает единицы тактов (это побитовый сдвиг внутреннего состояния). Для обычного range это практически бесплатно по сравнению со стоимостью обхода указателей в куче.

Но если вы делаете микро-оптимизации в горячих циклах (Hot Paths), вы должны понимать:

  • Итерация по слайсу — это аппаратная симпатия (Data Locality, линейное чтение, Prefetcher в CPU счастлив).
  • Итерация по мапе — это всегда Pointer Chasing (прыжки по памяти) + накладные расходы на запуск mapiterinit + сложнейшая логика обхода X/Y развилок, если мапа прямо сейчас находится в состоянии эвакуации (как мы обсуждали в 32. Рост и эвакуация map).

Итерация по мапе — это очень тяжелая операция для рантайма. По возможности избегайте полных обходов больших словарей в критических путях бэкенда.

Итог

  1. Итерация по мапе в Go намеренно рандомизирована при каждом запуске цикла range.
  2. Это защита от Закона Хайрама: рантайм насильно заставляет разработчиков не закладываться на неопределенное поведение, сохраняя за создателями языка право менять алгоритмы хэширования под капотом.
  3. Технически это реализовано через выбор случайного стартового бакета и случайного начального индекса (от 0 до 7) внутри этого бакета через функцию fastrand().
  4. Эта случайность «дешевая», но не криптографически честная (не подходит для алгоритмов равномерной случайной выборки).

Мы полностью разобрали стандартную мапу. Она невероятно быстрая для одной горутины, но, как мы помним, одновременное чтение и запись из разных потоков вызывает неизлечимый fatal error.

Что если нам нужен глобальный In-Memory кэш на 32-ядерном сервере? Обернуть мапу в sync.RWMutex — значит убить производительность кэш-линий (False Sharing). Для решения этой чисто аппаратной проблемы инженеры Go создали отдельную lock-free структуру.

В следующей статье мы разберем её магию: 33.1. sync.Map под капотом. Read и dirty словари