VictoriaMetrics объяснила устройство map в Go 1.24 на Swiss Tables

Компания VictoriaMetrics (разработчик открытой распределённой базы временных рядов) опубликовала технический разбор того, как устроен встроенный тип map в Go после того, как в Go 1.24 его старую реализацию заменили новой, основанной на структуре Swiss Tables. Материал продолжает более раннюю статью той же компании о старой реализации map и явно ссылается на официальный пост команды Go «Faster Go maps with Swiss Tables», авторы говорят, что идут тем же путём, но более пошагово и наглядно, с расчётом на читателя без глубокого бэкграунда.

Переменная map в Go, это указатель на внутреннюю структуру internal/runtime/maps.Map с полями used (счётчик текущих записей, именно из-за него len(m) работает за O(1), без обхода всей карты), seed (случайное число, своё для каждой карты: из-за него одинаковый ключ в двух разных map даёт разные хеши и по-разному раскладывается по памяти) и указателями на хранилище (dirPtr, dirLen).

Базовая единица хранения, «группа»: она вмещает до 8 пар ключ-значение и восьмибайтовое «управляющее слово», по одному контрольному байту на каждый слот. Хеш ключа делится на две части: старшие 57 бит (H1) определяют, с какой группы начинать поиск, младшие 7 бит (H2) кладутся в контрольный байт. Старший, восьмой по счёту бит контрольного байта показывает, жив ли слот: 0, в слоте есть запись и в байте лежит H2, 1, служебное состояние: 10000000 значит «слот пуст», 11111110, «слот удалён» (такой байт называют tombstone, «надгробие»). На AMD64 Go одной SIMD-инструкцией сравнивает H2 сразу со всеми 8 контрольными байтами группы и получает битовую маску кандидатов; на других архитектурах тот же результат получают побитовыми операциями над 64-битным управляющим словом, но уже не одной упакованной операцией, а по байту. Только после этого Go построчно сверяет сами ключи в отобранных слотах.

Когда записей в группе становится больше 8, Go переходит на структуру «таблица», которая управляет уже несколькими группами: число групп удваивается (2, 4, 8… вплоть до 128 групп на одну таблицу, это 1024 слота, 128 × 8). Стартовая группа для ключа вычисляется как «H1 по модулю числа групп»; если она заполнена, Go проверяет остальные группы не подряд, а по «треугольной последовательности проб», со смещением +1, +2, +3 и так далее по кругу, и поскольку число групп всегда степень двойки, такая последовательность гарантированно обходит каждую группу ровно один раз. Как только карта перерастает одну группу, указатель dirPtr начинает вести не на саму группу, а на «каталог» (directory), массив указателей на таблицы.

Рост таблицы ограничен коэффициентом заполнения: доля живых записей плюс удалённых (tombstone) от общего числа слотов не должна превышать 7/8, то есть 87,5%. В примере из статьи таблица на 16 слотов с 10 живыми записями заполнена на 10/16, то есть на 62,5%; лимит вставок для неё, 14 записей (16 × 7/8), а после 10 вставленных записей счётчик оставшихся вставок growthLeft равен 4. При поиске Go может остановиться сразу, наткнувшись на пустой слот, но обязан продолжать проверку дальше, если встретил tombstone, иначе можно пропустить существующую запись, «перепрыгнувшую» через удалённый слот при вставке. Если таблице на 1024 слота (128 групп) снова не хватает места, Go не продолжает удваивать её, а разбивает данные на две отдельные таблицы. Отдельно авторы упоминают, что Go сейчас тестирует (но ещё не выпустил) альтернативную раскладку группы, с отдельными массивами для ключей и для значений, чтобы улучшить локальность при поиске ключа и убрать издержки на выравнивание памяти.

Ключевые факты

В Go 1.24 старую реализацию встроенного типа map заменили новой, построенной на структуре Swiss Tables.
Базовая единица хранения, группа на 8 пар ключ-значение с восемью контрольными байтами; на AMD64 Go одной SIMD-инструкцией сравнивает все 8 контрольных байтов сразу, на других архитектурах, то же самое, но побайтово.
Хеш ключа делится на H1 (57 бит, выбор стартовой группы) и H2 (7 бит, метка в контрольном байте, отличающая живую запись от пустого или удалённого слота).
Таблица растёт от 2 до 128 групп (максимум 1024 слота) с лимитом заполнения 7/8 (87,5%); при нехватке места сверх этого лимита Go разбивает данные на две таблицы, а не продолжает удваивать одну.
Go тестирует (пока не выпустил) альтернативную раскладку группы с раздельными массивами ключей и значений, для лучшей локальности памяти при поиске.

Почему это важно

Go 1.24 переписал реализацию встроенного типа map, структуры, которую использует практически любая программа на Go, на архитектуру Swiss Tables. VictoriaMetrics, уже писавшая разбор старой реализации, выпустила доступный визуальный гид по новому устройству: от структуры группы и контрольных байтов до роста таблиц. Материал не открывает новую тему, а объясняет уже вышедшую и широко затрагивающую всех Go-разработчиков смену внутреннего устройства базового типа языка.

Кому это важно

В первую очередь, Go-разработчикам, которые пишут производительный или системный код и хотят понимать, как ведёт себя map при заполнении, росте и удалении записей. Отдельно это касается авторов инфраструктурного и системного ПО (сама VictoriaMetrics разрабатывает распределённую базу временных рядов, где такие детали влияют на реальную производительность), а также всех, кто интересуется устройством хеш-таблиц как таковых, подход Swiss Tables пришёл из библиотеки Abseil для C++ и используется не только в Go.

Как это применить

Материал даёт рабочую модель для рассуждений о производительности map: len(m), это не обход всей карты, а O(1) обращение к счётчику; поиск ключа быстрый благодаря тому, что 8 контрольных байтов группы проверяются одной SIMD-операцией на AMD64, а не по одному; лимит заполнения в 7/8 (87,5%) и удвоение числа групп при росте (вплоть до 1024 слотов на таблицу, дальше, разбиение на две таблицы) помогают прикинуть, сколько реаллокаций вызовет заполнение большой map, если её размер не задан заранее через make(map[K]V, n). Понимание того, что поиск останавливается на пустом слоте, но обязан продолжаться после удалённого (tombstone), объясняет, почему интенсивные вставки вперемешку с удалениями могут заметно замедлять последующие поиски.

Можно ли доверять

VictoriaMetrics, известная в опенсорс-сообществе компания-разработчик СУБД временных рядов, ранее уже публиковавшая разбор старой реализации map, на который этот материал прямо ссылается как на предыдущую часть. Текст описывает реальную структуру рантайма Go (internal/runtime/maps.Map) и сверяется с официальным постом команды Go в блоге Go, «Faster Go maps with Swiss Tables», прямо называя его и указывая, что даёт более пошаговое и наглядное изложение того же материала. В доступном фрагменте текста нет ни имени автора статьи, ни даты публикации, источник их просто не приводит. Сама выгрузка обрывается на полуслове (на фразе «Each time the…») перед разделом о дальнейшем поведении при росте и об удалённых записях, пересказ выше покрывает всё, что попало в выгрузку, но не финальную часть статьи о завершении роста и судьбе tombstone-слотов.

Риски и подводные камни

В доступном тексте нет ни одного измерения производительности, ни сравнения скорости старой и новой реализации map, ни абсолютных цифр; поэтому делать из этого материала вывод о том, «насколько быстрее» стал Go 1.24, нельзя, сам источник об этом не говорит. Упомянутая альтернативная раскладка группы с раздельными массивами ключей и значений, это то, что Go пока только тестирует, а не то, что уже работает по умолчанию; путать экспериментальную ветку с текущим поведением не стоит. Разбор доходит до раздела о коэффициенте заполнения и обрывается до того, как в статье, судя по всему, должно идти дальнейшее описание удаления записей и очистки от tombstone.