Введение
Мы в 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-бит) ;
-
Murmur2/Murmur3
(32-бита).
Тестирование
Входные данные
В качестве входных данных мы будем использовать следующие наборы
данных
-
Набор реальных данных, составленный из
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.