Современные высоконагруженные приложения хранят данные в СУБД с несколькими узлами. Такая архитектура требует согласованности данных, а также важно обеспечить равномерное распределение данных между узлами. Для достижения этих целей используются алгоритмы балансировки данных.
Хеширование является основой практически всех систем балансировки данных. С момента появления классического консистентного хеширования для этой цели было разработано множество алгоритмов.
Одной из целей балансировщика нагрузки данных является обеспечение масштабируемости кластера с данными. Для производительности всей системы крайне важно перемещать как можно меньше записей таблиц во время добавления или удаления узла. Наибольшее влияние на этот процесс оказывает алгоритм хеширования, используемый балансировщиком нагрузки.
В данной работе произведена экспериментальная оценка нескольких алгоритмов хеширования, используемых для балансировки нагрузки. Проведен ряд экспериментов как модельного характера, так с реальными системами. Для оценки производительности алгоритмов был разработан тестовый стенд на основе Unidata MDM [20] — масштабируемого набора инструментов для решения различных задач управления мастер-данными (Master Data Management). Для оценки производительности были использованы три критерия, перечислены в порядке приоритета:
• Однородность полученного распределения данных по узлам;
• Количество перемещаемых при ребалансировке записей;
• Скорость вычислений.
По результатам экспериментов составлена таблица, в которой каждому алгоритму дана оценка по вышеуказанным критериям.
В данной работе было изучено влияние алгоритмов хеширования на процесс ребалансировки данных в распределенном хранилище. Для этого был выполнен обзор предметной области и изучено устройство следующих алгоритмов: Linear Hashing, Consistent Hashing, Rendezvous, RUSH, Maglev и Jump. Было выработано 3 критерия оцени применимости алгоритмов, а именно равномерность распределения полученных, количество перемещенных записей и вычислительные затраты. Также была реализована подсистема ребалансировки данных в платформе Unidata MDM и проведен ряд экспериментов: моделирование балансировки данных в Colab, оценка времени расчета шарда внутри платформы и ребалансировка платформы с использованием распределенного хранилища.
Эксперименты показали, что из семи рассмотренных алгоритмов есть два явных победителя — AnchorHash и Maglev. Еще два, Linear Hashing и Jump, также могут быть применимы.
По результатам работы опубликована статья “Benchmarking Hashing Algorithms for Load Balancing in a Distributed Database Environment” [18] на конференции MEDI 2022.
