От быстрой формулы к честному выбору владельца: как в VRH появилась N3

Иногда хеш-функцию проверяют на коллизии, смотрят на avalanche, запускают benchmark и считают задачу закрытой. Собственно я так и сделал с первой версией VRH. Формула была короткой, обратимой и хорошо подходила для SIMD. Но стоило поставить перед ней три специально выбранных узла, и один получил примерно половину ключей вместо трети.(и к сожалению один прод пострадал)

Задача и ошибка v1

В Rendezvous Hashing для каждого ключа вычисляется score(key, node) по всем узлам, а владельцем становится узел с максимальным score. Узлы могут иметь произвольные uint64 ID, поэтому такой подход удобен для разреженных и меняющихся наборов. Цена — O(N) вычислений на один ключ.

Исходная VRH v1 пыталась сделать каждое вычисление дешёвым: после одного SplitMix64(key) она применяла к node XOR, сложения, сдвиги и повороты без умножения в узловой части. Все преобразования по отдельности обратимы, значит при фиксированном ключе разные ID не сталкиваются по score. Это и было главным достоинством v1.

k = SplitMix64(key)
x = node XOR k
x += ROTL(k, 23)
x ^= x >> 29
x += ROTL(k, 41)
x ^= x << 17
score = x XOR (x >> 32)

Но отсутствие коллизий не означает равные шансы стать максимумом. На тройке {0, 1, 2^63} v1 распределяла ключи примерно как 25% / 25% / 50%. В первоначальном наборе из 83 проверочных наборов узлов она провалила 82. Для выбора владельца это критично: перегруженный узел получает больше данных и запросов, хотя отдельные score никогда не совпадают.

Сколько итераций было до N3

Одного честного числа попыток у меня нет, в моменте я просто устал создавал файлы с одним и тем же названием, я проверял целые сетки параметров, менял архитектуру score, отдельно искали быстрый key mixer и многократно усиливали тесты. Если считать крупные этапы пути от v1 до появления N3, их было шесть:

1. v1. Дешёвая обратимая shift/add-формула. Контрпример 25/25/50 показал, что её нельзя оставлять как универсальный HRW score.
2. v2 на SplitMix64. Первую плохую тройку она исправила, но позднее на {0, 2^29, 2^59} дала примерно 35,2% / 32,4% / 32,4%. Это около 1,9 процентного пункта сверх идеальной трети у первого узла, гораздо больше обычного шума миллиона ключей.
3. Опубликованный Murmur fmix64 как контроль. Он проходил обычные проверки на 279 наборах, но на новой структурной тройке {0, 2^30, 2^63} первый узел получил около 47,5%.
4. Собственное двухмультипликативное семейство. Я просмотрел сетку из 500 формул; кандидаты C и D сначала прошли большие holdout-проверки. Позже для них тоже нашлись тройки с сильным перекосом. Хорошая avalanche-матрица здесь оказалась недостаточной.
5. Подготовка ключа и новые линейные слои. Проверил, среди прочего, 36 вариантов key mixer и отдельную сетку из 48 новых score-формул. R2 и R3 выглядели убедительно на привычных битовых направлениях, пока смена базиса не дала им прямые контрпримеры: около 42,7% у одного узла для R2 и 39,3% для R3.
6. Переход к проверке самого порядка score. Вместо того чтобы смотреть только на равномерность битов, я начал изучать, как распределяется разница между двумя наибольшими score на почти полных XOR-кубах. Эта проверка вскрыла дефекты прежних кандидатов и подсказала новую архитектуру с дополнительным нелинейным слоем — N3.

Сетки в 500, 36 и 48 вариантов — отдельные эксперименты; их нельзя складывать в число полноценно проверенных формул. Короткий поисковый экран и независимое подтверждение проходили разные числа кандидатов. После появления N3 работа тоже не остановилась: я пытался искать более дешёвые варианты, например проверил отдельные сетки из 80 и 60 двухмультипликативных формул, но лучшие из них не выдержали независимых структурных проверок. История заняла гораздо больше одного удачного подбора констант.

Ключевой урок оказался простым. Для score вида P(node XOR K(key)) смена обратимого K переставляет полный набор ключей и не может исправить систематический перекос, заложенный в P. Проверки по двум узлам тоже мало что говорят: для этого семейства они дают точные 50/50 по всему пространству ключей. А вот неполные трёхузловые XOR-наборы уже показывают, кто чаще оказывается первым.

Что делает N3

N3 состоит из одноразовой подготовки ключа K, обратимого линейного слоя T и более длинного нелинейного хвоста:

k = key + 0x9e3779b97f4a7c15
k ^= k >> 32
k *= 0xbf58476d1ce4e5b9
k ^= k >> 27

x = k XOR node
x = x XOR ROTL(x, 17) XOR ROTL(x, 43)
x *= 0x2cb0f69f4abea221
x ^= x >> 27
x = ROTL(x, 23)
x *= 0xb19e04cb9dce3147
x ^= x >> 31
x *= 0xbf58476d1ce4e5b9
score = x XOR (x >> 33)

Все операции выполняются над uint64 по модулю 2^64. Нечётные множители, XOR со сдвигом, поворот и T(x) = x XOR ROTL(x,17) XOR ROTL(x,43) обратимы. Следовательно, разные узлы не получают одинаковый score при одном ключе. Это строгая гарантия отсутствия ничьих, не доказательство идеального баланса.

У T есть полезное для производительности свойство: T(k XOR node) = T(k) XOR T(node). Поэтому для большого кольца можно подготовить T(node) при создании кольца, вычислить T(k) один раз на запрос, а после полного скана обратить T только для победителя. Для 1–16 узлов используется короткий Go-путь; для больших колец на amd64 — нативный скан по подготовленным ID. В нынешней библиотеке исходные ID также хранятся ради Nodes(), так что после 16 узлов подготовка добавляет 8 байт на узел. В прототипе подготовленный массив заменял исходный, поэтому его оценка памяти отличается.

Сознательно не переносил старый AVX2-код v2 под прежним названием: он вычислял бы другие scores. Сейчас BackendAVX2 для N3 возвращает ошибку. Скалярный amd64-путь и переносимый Go-путь дают одинаковых владельцев. Тут еще работа идет..

Итоги тестирования

Проверял текущую реализацию N3 через vrh.New, Ring.Owner и Ring.OwnerBatch. Сравнивал с go-rendezvous + XXH64, адаптером NSPCC и прямым сканом XXH64(key || node). Адаптер NSPCC сверял с первым элементом публичного Sort.

Условия: AMD Ryzen 5 2600, Linux amd64, Go 1.27.1. Однопоточные замеры — CPU 4, GOMAXPROCS=1, без фиксации частоты. В таблицах медианы пяти повторов: полные проходы по ключам для Owner, не менее 100 мс на повтор для остальных API-бенчмарков.

Проверено 114 сценариев: 16 размеров кольца от 1 до 16 384 узлов; последовательные и разреженные ID; случайные, последовательные и меняющиеся в старших 32 битах ключи; шесть наборов из прежних контрпримеров. На каждую реализацию — 23 396 352 наблюдения для распределения и ещё 7 340 032 в независимой проверке. Отдельно измерены 411 вариантов API-вызовов и 48 вариантов параллельного чтения.

Выбор владельца

Разреженные ID, случайные uint64 ключи. Время в нс/Owner. Создание кольца и преобразование ключей в строки/байты вынесены из замера; хеширование запроса и поиск владельца включены. go / VRH — отношение времени go-rendezvous к VRH.

У VRH минимальная медиана в 113 из 114 сценариев. Исключение — 64 разреженных узла с последовательными ключами: 156,13 нс у VRH и 152,99 нс у go-rendezvous. Диапазоны пяти повторов в этом случае пересекаются.

¹ NSPCC scan и XXH64 pair — локальные адаптеры. Для go-rendezvous вызывается публичный Lookup. Все реализации возвращают исходный uint64 ID.

Отдельный замер путей VRH, нс/Owner. Auto и Scalar выбирают одну реализацию; различия между их замерами связаны с условиями выполнения. OwnerScalar — прямой Go-скан без подготовленных ID.

На 17 узлах OwnerScalar показал 47,32 нс против 60,81 нс у Auto. На 64, 1024 и 16 384 узлах подготовленный путь оказался быстрее. BackendAVX2 для N3 возвращает ошибку.

Создание кольца и память

Время создания адаптера из []uint64, мкс. Включены преобразования ID, обёртка стенда и проверки конструктора. VRH проверяет дубликаты; проверки остальных конструкторов оставлены штатными.

Выделенные байты / число выделений на создание, включая временные структуры:

Прямой вызов vrh.New без обёртки стенда:

² Массивы ID занимают 8×N байт до 16 узлов и 16×N после 16. Размер указан без заголовков slice, структур и округления аллокатора. Б/создание включает временные выделения и отличается от памяти, занятой готовым кольцом.

Пакетная обработка

Время в нс/ключ, буфер результата используется повторно. У VRH вызывается OwnerBatch, у остальных — цикл вызовов Owner. В каждом повторе обрабатывается один и тот же пакет.

Также проверены пустой пакет, один ключ, dst=nil, короткий dst и запись на месте. В замерах Owner — 0 Б/op и 0 allocs/op. Для VRH это дополнительно проверено через AllocsPerRun на 260 размерах кольца.

Выделения на один OwnerBatch при 17 узлах:

При повторном использовании буфера и записи на месте выделений нет. При nil или коротком буфере непустой пакет требует одного выделения под результат.

Перестроение кольца

Один ID заменяется, кольцо создаётся заново, затем выполняются Q запросов. Время в мкс на весь цикл. Все реализации измеряются с полным перестроением.

Параллельное чтение

Суммарная пропускная способность, млн Owner/с. Одно неизменяемое кольцо, CPU 0–5 — шесть физических ядер. Для каждого значения GOMAXPROCS выполнено пять замеров по 200 мс или дольше.

Распределение и корректность

Независимая проверка — по 1 048 576 новых случайных ключей на набор. В ячейке максимальный Z и результат проверки порогов maxZ ≤ 7, χ² ≤ (N−1)+8√(2(N−1)). Метки v1, v2, Murmur, R2 и R3 обозначают наборы узлов из прежних контрпримеров. В столбце VRH во всех случаях используется N3; large — 16 384 разреженных узла.

Доли владельцев на прежнем контрпримере v2 {0, 2^29, 2^59}:

Число превышений статистических порогов:

Оба превышения NSPCC пришлись на кольца из 16 384 узлов с 16 384 ключами: maxZ = 7,000214 при среднем одном ключе на узел. Нормальная аппроксимация для такого малого числа наблюдений неточна. В независимой выборке с 64 ключами на узел в среднем все реализации прошли пороги.

У N3 превышений порогов не было. Проверки совпадения Auto, Scalar, OwnerScalar и batch, перестановки ID, добавления и удаления узлов, изоляции входных данных и конкурентного чтения прошли. Проверены размеры 1–257, 1024, 4096 и 16 384. Тесты, -race и go vet прошли для библиотеки и стенда; переносимый путь выполнен при GOARCH=386, arm64 проверен сборкой.

Для N3 пока нет доказанной оценки максимального перекоса на произвольных наборах узлов. На это нужно больше времени и знаний в математике. Подожду, когда товарищ освободится и поможет разобраться