Как избежать перекоса нагрузки при распределении слов по машинам с помощью хэш-функции

Что проверяют

Понимаете ли вы, что перекос бывает двух видов: от плохого разбиения ключей и от неравномерности самих данных. Хэш лечит первое и бессилен против второго. Следом обычно спрашивают, что будет, когда в кластер добавят ещё одну машину.

Как отвечать

Начните с того, откуда берётся перекос:

• нестабильный или слабый хэш: в .NET Core и новее string.GetHashCode() рандомизирован для каждого процесса, поэтому на разных машинах одно слово получит разный хэш. Для распределения нужен стабильный некриптографический хэш, например XxHash64 из пакета System.IO.Hashing или MurmurHash3. SHA-256 здесь избыточен и медленнее;
• остаток от деления на N: hash % N распределяет ровно, пока N не меняется. Добавили машину, и переехала почти каждая запись. Лечится консистентным хэшированием с виртуальными узлами (сотни точек на кольце на каждую машину) или rendezvous hashing;
• горячие ключи: слова распределены по закону Ципфа, «и», «в», «the» встречаются на порядки чаще остальных. Одинаковый ключ всегда уходит на одну машину, и никакая хэш-функция это не исправит.

Против горячих ключей работают три приёма. Локальная предагрегация: каждый узел сначала сам считает свои слова и отправляет дальше пары «слово, сумма», как combiner в MapReduce. Солирование: к горячему ключу добавляют суффикс word#0 … word#k, он разъезжается по k машинам, а на втором шаге частичные суммы складываются. Выявление тяжёлых ключей по выборке или через Count-Min Sketch, чтобы солить только их, а не всё подряд.

Закончите мониторингом: смотреть надо не на среднюю нагрузку, а на максимум по машинам и размер самой большой партиции.

Где спотыкаются

Берут GetHashCode() и не знают про рандомизацию. На одной машине в тестах всё работает, а в кластере счётчики одного слова оказываются на разных узлах.

Пишут Math.Abs(hash) % n. На int.MinValue это бросает OverflowException, а обычный % от отрицательного числа даёт отрицательный индекс. Надёжнее привести хэш к uint или сразу брать беззнаковый.

Отвечают только про выбор хэш-функции. Интервьюеру важно услышать, что при перекосе данных проблема в ключах, а не в формуле.