Выбор хэш-функции в задаче шардирования данных28.12.2020 07:32

Введение

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

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

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

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

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

e9aaf44225e5a3999b2cbcd690e7f193

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

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

Из минусов:

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

Требования

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

33b91a462ca1c01cfb8dcb47dfacd5a2

Функция принимает на вход ключ — объект строки, размером до 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. Общая схема тестовой итерации выглядит следующим образом:

7b0173ad0b6368196a2fdbcfb3cba210

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

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

Кол-во warmup-итераций — 50;
Кол-во measurement-итераций — 100;
Режим — throughput
Добавим ограничение по памяти -Xms1G, -Xmx8G
Для оценки расхода памяти добавим GCProfiler

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

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

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

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

Разобьем выборку на частичные интервалы, число которых найдем по формуле Стерджеса, а их длину найдем по правилу равноинтервальной группировки;
Для каждого интервала подсчитаем его характеристики — среднее значение, частоты, относительные частоты;
Подсчитаем выборочное среднее $\overline{x_{b}}$ , среднеквадратическое отклонение $\sigma_{b} = \sqrt{D_{b}}$ и теоретические частоты
$\hat{n_{i}}=np_{i}$ ,
где n — число элементов в выборке, а $p_{i}$ — вероятность попадания случайной величины в частичные интервалы, в нашем случае она равна —
$p_{i} = \frac{x_{length}}{b - a}$ ,
где $x_{length}$ — одинаковая длина интервалов, a параметры a и b — $a = \overline{x_{b}} - \sqrt{3\sigma_{b}}$ , $b = \overline{x_{b}} + \sqrt{3\sigma_{b}}$ ;
Можем приступить к расчёту критерия согласия, по формуле
$\chi_{набл}^2 = \sum\frac{n_{i}-\hat{n_{i}}}{\hat{n_{i}}}$ ,
где $n_{i}$ — эмпирические частоты, полученные из выборки, $\hat{n_{i}}$ — теоретические частоты, найденные по формулам выше;
Определяем по таблице критических точек распределения $\chi_{кр}^2(\alpha, k)$ , по заданному уровню значимости α и числу степеней свободы k;
Если $\chi_{набл}^2<\chi_{кр}^2$ , то принимаем гипотезу, если же данное условие не выполняется — отвергаем.

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

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

46e08c42f05e4083ca6eab11567c2092

Слова из каждого тестового набора мы сгруппируем по длине, при максимальном значении символов в 256. Затем создадим входные тестовые выборки разных размеров в диапазоне 16384, 8192, 4096, 2048, 1024, в выборки поместим слова из каждой группы, с одинаковой вероятностью.

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

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

Результаты

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

Рассмотрим скорость работы (количество операций в миллисекунду) для различных имплементаций в зависимости от длины входных строк.

В диапазоне от двух до восьми символов:

Диаграмма

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

В диапазоне от 16 до 256 символов:

Диаграмма

Функция murmur2 явный фаворит, ей немного уступает murmur; crc16 и sdbm остались в аутсайдерах и на этой выборке.

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

Рассмотрим таблицу результатов соответствия критерию Пирсона

47bca2beba5d879fdcae50016e5cac85

Видно, что имплементации crc16, murmur2, murmur3 удовлетворяют критерию Пирсона о равномерном распределении практически на всех выборках.

Рассмотрим гистограммы относительных частот, в разрезе разных выборок.

На гистограммах ниже, для loseLose, Djb2, Sdbm, не прошедших тест, видно, что распределение далеко от равномерного и больше похоже на геометрическое:

ДиаграммаДиаграммаДиаграмма

Для проваливших тест Fnv1 и Fnv1a ситуация похожа, распределения отдалённо напоминают нормальное:

.

ДиаграммаДиаграмма

Смотрим на тройку победителей:

ДиаграммаДиаграммаДиаграмма

За исключением некоторых всплесков, crc16, murmur2, murmur3 удовлетворяют критерию Пирсона, что согласуется с характеристиками их гистограмм относительных частот.

Выводы

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

Скорость работы. Функции murmur2/murmur3 имеют лучшее время работы для входных строк длиной больше 8 символов.

Удовлетворение гипотезы о равномерном распределении. Можем выделить три функции, для которых гипотеза принимается для большинства наборов данных: crc16, murmur2/murmur3. Графики распределения гистограмм относительных частот подтверждают вид равномерного распределения для функций crc16, murmur2/murmur3.

Таким образом, исходя из двух критериев, лучшим выбором являются реализации murmur2/murmur3.