Введение
Мы в Miro работаем над процессом шардирования баз Postgres и используем разные подходы в зависимости от бизнес-требований. Недавно перед нами встала задача шардирования новых баз, в ходе неё мы выбрали новый для нас подход к шардированию, основанный на согласованном хешировании (consistent hashing).
В ходе реализации этого подхода один из центральных вопросов заключался в том, какую реализацию не-криптографической хэш-функции нам лучше выбрать и использовать. В статье я опишу критерии и алгоритм сравнения, который мы выработали и использовали на практике для поиска наилучшей реализации.
Oб архитектурном подходе
Есть много продуктов (mongo, redis, и т.д.), использующих согласованное хеширование для шардинга, и наша реализация будет сильно похожа на них.
Пусть, на входе у нас есть множество сущностей с выбранными ключами шардирования, строкового типа. Для этих ключей с помощью хэш-функции мы получим хэш-код определенной длины, для которого через операцию деления по модулю определим необходимый слот. Кол-во слотов и соответствие сущностей слотам фиксировано. Также необходимо хранить соответствие диапазонов слотов и шардов, что не является сложной задачей, и для места хранения вполне подойдет конфигурационный файл.
Плюсами данного подхода являются:
-
равномерное распределение сущностей по шардам;
-
определение соответствия сущностей и шардов без дополнительного хранилища с минимум ресурсо-затрат;
-
возможность добавления новых шардов в кластер.
Из минусов:
-
неэффективность некоторых операций поиска, в которых необходимо делать запросы на все шарды;
-
достаточно сложный процесс решардинга.
Требования
Центральным местом решения является выбор java-реализации хэш-функции.
Функция принимает на вход ключ - объект строки, размером до 256 символов, и выдает хэш-код - беззнаковое целое число, размером до 4 байт. На самом деле мы будем сравнивать реализации которые генерируют хэш-коды размером 2 и 4 байта.
Критерии сравнения
Рассмотрим четыре распространенных критерия сравнения реализаций хэш-функций:
-
Скорость, функция должна работать быстро, на любых входных данных;
-
Вид распределения результатов. Очень важно, чтобы функция на выходе генерировала хэши, которые соответствуют равномерному распределению;
-
Устойчивость к коллизиям (первого и второго рода); -
Соответствие лавинному эффекту. Отражает зависимость всех выходных битов от каждого входного бита, на любых входных данных.
Для нашей задачи нам будут важны только первые два критерия: первый - поскольку операция расчета хэша будет очень частой; и второй - поскольку крайне важно, чтобы данные распределялись по шардам равномерно.
Отсутствие возможности атаки на характеристики функции делает для нас неважным третий критерий.
В случае несоответствия четвертому критерию мы можем получить только единичные выбросы из равномерного распределения, которые нас не сильно волнуют.
Реализации
Мы будем рассматривать самые популярные java-реализации не-криптографических хэш-функций:
-
DJB2 (32-бита);
-
SDBM (32-бита);
-
LoseLose (32-бита);
-
FNV-1 / FNV-1a (32-бита);
-
CRC16 (16-бит) ;
Тестирование
Входные данные
В качестве входных данных мы будем использовать следующие наборы данных
-
Набор реальных данных, составленный из 216,553 английских слов;
-
Набор синтетических данных, составленный из рандомно сгенерированных символов в кодировке UTF-8.
В обоих тестовых наборах мы будем иметь группы строк с определенными длинами (кол-во символов) - "2", "4", "8", "16", "32", "64", "128", "256".
Метрики
Для сравнения различных критериев мы будем использовать следующие метрики:
-
Для первого критерия, скорости - ops/ms (кол-во операций в миллисекунду работы);
-
Для второго критерия - факт удовлетворения критерию согласия Пирсона для равномерного распределения. Для этого нам придется ввести гипотезу о виде распределения результатов и проверить ее. Впрочем такая метрика будет бинарной, и для того чтобы визуально оценить насколько распределение хэш-кодов каждой из имплементаций близко к равномерному распределению, мы воспользуемся построением гистограмм относительных частот для каждой серии тестов.
Инструменты
Оценка скорости работы
Для оценки скорости работы мы воспользуемся нагрузочными тестами и библиотекой JMH. Общая схема тестовой итерации выглядит следующим образом:
Слова из каждого тестового набора мы сгруппируем по длине, при максимальном значении в 256 символов. Затем в каждой итерации будем подавать на вход хэш-функции слова из каждой группы, с одинаковой вероятностью.
Для бэнчмарков мы будем использовать следующие настройки
-
Кол-во warmup-итераций - 50;
-
Кол-во measurement-итераций - 100;
-
Режим -
throughput -
Добавим ограничение по памяти
-Xms1G, -Xmx8G -
Для оценки расхода памяти добавим GCProfiler
Полный код тестов можно посмотреть здесь.
Оценка распределения результатов
Для проверки соответствия выходных значений функции нашим ожиданиям проверим гипотезу о том, что выборка результатов при уровне значимости =0,05, распределена по равномерному закону. Для проверки мы будем использовать критерий согласия Пирсона.
Алгоритм для проверки гипотезы следующий:
-
Разобьем выборку на частичные интервалы, число которых найдем по формуле Стерджеса, а их длину найдем по правилу равноинтервальной группировки;
-
Для каждого интервала подсчитаем его характеристики - среднее значение, частоты, относительные частоты;
-
Подсчитаем выборочное среднее
, среднеквадратическое отклонение
и теоретические частоты,где n число элементов в выборке, а
вероятность попадания случайной величины в частичные интервалы, в
нашем случае она равна -,где
- одинаковая длина интервалов, a параметры a и b
-
,
; -
Можем приступить к расчёту критерия согласия, по формуле
,где
- эмпирические частоты, полученные из выборки,
- теоретические частоты, найденные по формулам выше; -
Определяем по таблице критических точек распределения
, по заданному уровню значимости и числу степеней свободы
k ; -
Если
, то принимаем гипотезу, если же данное условие не выполняется
отвергаем.
Код для расчёта критерия согласия и вероятностных характеристик выборок здесь.
Общая схема тестовой итерации похожа на схему в предыдущем разделе и выглядит следующим образом:
Слова из каждого тестового набора мы сгруппируем по длине, при максимальном значении символов в 256. Затем создадим входные тестовые выборки разных размеров в диапазоне 16384, 8192, 4096, 2048, 1024, в выборки поместим слова из каждой группы, с одинаковой вероятностью.
Все элементы каждой из групп подадим на вход хэш-функции и получим выходные выборки, состоящие из целочисленных хэш-кодов. После чего по алгоритму выше рассчитаем для них критерий согласия и определим, удовлетворяет ли он гипотезе о равномерном распределении.
Полный код тестов можно посмотреть здесь.
Результаты
Оценка скорости работы
Рассмотрим скорость работы (количество операций в миллисекунду) для различных имплементаций в зависимости от длины входных строк.
В диапазоне от двух до восьми символов:
Видно, что в этом диапазоне практически все алгоритмы работают с одинаковой скоростью, незначительно опережает всех loseLose, а очевидными аутсайдерами выглядят только crc16 и sdbm.
В диапазоне от 16 до 256 символов:
Функция murmur2 явный фаворит, ей немного уступает murmur; crc16 и sdbm остались в аутсайдерах и на этой выборке.
Оценка распределения результатов
Рассмотрим таблицу результатов соответствия критерию Пирсона
Видно, что имплементации crc16, murmur2, murmur3 удовлетворяют критерию Пирсона о равномерном распределении практически на всех выборках.
Рассмотрим гистограммы относительных частот, в разрезе разных выборок.
На гистограммах ниже, для loseLose, Djb2, Sdbm, не прошедших тест, видно, что распределение далеко от равномерного и больше похоже на геометрическое:
Для проваливших тест Fnv1 и Fnv1a ситуация похожа, распределения отдалённо напоминают нормальное:
.
Смотрим на тройку победителей:
За исключением некоторых всплесков, crc16, murmur2, murmur3 удовлетворяют критерию Пирсона, что согласуется с характеристиками их гистограмм относительных частот.
Выводы
Рассмотрим выбор наиболее подходящей реализации, которую мы оцениваем по двум выбранным критериям: скорость работы и удовлетворение гипотезы о равномерном распределении.
Скорость работы. Функции murmur2/murmur3 имеют лучшее время работы для входных строк длиной больше 8 символов.
Удовлетворение гипотезы о равномерном распределении. Можем выделить три функции, для которых гипотеза принимается для большинства наборов данных: crc16, murmur2/murmur3. Графики распределения гистограмм относительных частот подтверждают вид равномерного распределения для функций crc16, murmur2/murmur3.
Таким образом, исходя из двух критериев, лучшим выбором являются реализации murmur2/murmur3.
