Мы в Miro работаем над процессом шардирования баз Postgres и используем разные подходы в зависимости от бизнес-требований. Недавно перед нами встала задача шардирования новых баз, в ходе неё мы выбрали новый для нас подход к шардированию, основанный на согласованном хешировании (consistent hashing).

В ходе реализации этого подхода один из центральных вопросов заключался в том, какую реализацию не-криптографической хэш-функции нам лучше выбрать и использовать. В статье я опишу критерии и алгоритм сравнения, который мы выработали и использовали на практике для поиска наилучшей реализации.

Oб архитектурном подходе

Есть много продуктов (mongo, redis, и т.д.), использующих согласованное хеширование для шардинга, и наша реализация будет сильно похожа на них.

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

Плюсами данного подхода являются:

• равномерное распределение сущностей по шардам;

• определение соответствия сущностей и шардов без дополнительного   хранилища с минимум ресурсо-затрат;

• возможность добавления новых шардов в кластер.

Из минусов:

• неэффективность некоторых операций поиска, в  которых необходимо делать запросы на все шарды;

• достаточно сложный процесс решардинга.

Требования 

Центральным местом решения является выбор java-реализации хэш-функции.

Функция принимает на вход ключ - объект строки, размером до 256 символов, и выдает хэш-код - беззнаковое целое число, размером до 4 байт. На самом деле мы будем сравнивать реализации которые генерируют хэш-коды размером 2 и 4 байта.

Критерии сравнения

Рассмотрим четыре распространенных критерия сравнения реализаций хэш-функций:

1. Скорость, функция должна работать быстро, на любых входных данных;

2. Вид распределения результатов. Очень важно, чтобы функция на выходе генерировала хэши, которые соответствуют равномерному распределению;

3. Устойчивость к коллизиям (первого и второго рода);

4. Соответствие лавинному эффекту. Отражает зависимость всех выходных битов от каждого входного бита, на любых входных данных.

Для нашей задачи нам будут важны только первые два критерия: первый - поскольку операция расчета хэша будет очень частой; и второй - поскольку крайне важно, чтобы данные распределялись по шардам равномерно. 

Отсутствие возможности атаки на характеристики функции делает для нас неважным третий критерий. 

В случае несоответствия четвертому критерию мы можем получить только  единичные выбросы из равномерного распределения, которые нас не сильно волнуют. 

Реализации

Мы будем рассматривать самые популярные java-реализации  не-криптографических хэш-функций:

1. DJB2  (32-бита);

2. SDBM (32-бита);

3. LoseLose (32-бита);

4. FNV-1 / FNV-1a (32-бита);

5. CRC16 (16-бит) ;

6. Murmur2/Murmur3 (32-бита).

Тестирование

Входные данные 

В качестве входных данных мы будем использовать следующие наборы данных

1. Набор реальных данных, составленный из 216,553 английских слов;

2. Набор синтетических данных, составленный из рандомно сгенерированных символов в кодировке UTF-8.

В обоих тестовых наборах мы будем иметь группы строк с определенными длинами (кол-во символов) -  "2", "4", "8", "16", "32", "64", "128", "256".

Метрики

Для сравнения различных критериев мы будем использовать следующие метрики:

1. Для первого критерия, скорости - ops/ms (кол-во операций в миллисекунду работы);

2. Для второго критерия - факт удовлетворения критерию согласия Пирсона для равномерного распределения. Для этого нам придется ввести гипотезу о виде распределения результатов и проверить ее. Впрочем такая метрика будет бинарной, и для того чтобы визуально оценить насколько распределение хэш-кодов каждой из имплементаций близко к равномерному распределению, мы воспользуемся построением гистограмм относительных частот для каждой серии тестов.

Инструменты

Оценка скорости работы

Для оценки скорости работы мы воспользуемся нагрузочными тестами и библиотекой JMH.  Общая схема тестовой итерации выглядит следующим образом:

Слова из каждого тестового набора мы сгруппируем по длине, при максимальном значении в 256 символов. Затем в каждой итерации будем подавать на вход хэш-функции слова из каждой группы, с одинаковой вероятностью.

Для бэнчмарков мы будем использовать следующие настройки

• Кол-во warmup-итераций - 50;

• Кол-во measurement-итераций - 100;

• Режим - throughput

• Добавим ограничение по памяти -Xms1G, -Xmx8G

• Для оценки расхода памяти добавим GCProfiler

Полный код тестов можно посмотреть здесь.

Оценка распределения результатов

Для проверки соответствия выходных значений функции нашим ожиданиям проверим гипотезу о том, что выборка результатов при уровне значимости ?=0,05, распределена по равномерному закону. Для проверки мы будем использовать критерий согласия Пирсона.

Алгоритм для проверки гипотезы следующий:

1. Разобьем выборку на частичные интервалы, число которых найдем по формуле Стерджеса, а их длину найдем по правилу равноинтервальной группировки;

2. Для каждого интервала подсчитаем его характеристики -  среднее значение, частоты, относительные частоты;

3. Подсчитаем выборочное среднее   , среднеквадратическое отклонение
   и теоретические частоты

   

   где n — число элементов в выборке, а — вероятность попадания случайной величины в частичные интервалы, в нашем случае она равна -  

   

   где - одинаковая длина интервалов, a параметры a и b -

4. Можем приступить к расчёту критерия согласия, по формуле

   ,

   где - эмпирические частоты, полученные из выборки, - теоретические частоты, найденные по формулам выше;

5. Определяем по таблице критических точек распределения , по заданному уровню значимости ? и числу степеней свободы k ;

6. Если , то принимаем гипотезу, если же данное условие не выполняется — отвергаем.

Код для расчёта критерия согласия и вероятностных характеристик выборок здесь. 

Общая схема тестовой итерации похожа на схему в предыдущем разделе и выглядит следующим образом:

Слова из каждого тестового набора мы сгруппируем по длине, при максимальном значении символов в 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.