Всем привет!

Снова про алгоритмы.
Представим ситуацию, когда для каждого нашего объекта нужно получить адрес, где его хранить. Это может быть сервер в случае шардированной БД или корзина в HashMap. Хорошим решением является функция, которая однозначно по уникальному идентификатору нашей сущности выдаёт адрес сервера. Альтернативой является хранение таблицы соответствия отдельно, в случае распределённой системы это будет отдельный микросервис, что означает +1 запрос и увеличение задержек. Тривиальной реализацией является простой алгоритм - остаток от деления на число серверов. Но у такого есть минус - при изменении числа серверов распределение объектов по серверам или корзинам сильно меняется. Мы же хотим равномерное распределение. Если перестроение HashMap в памяти обычно (!) не проблема, то в случае десятка серверов в сети - ещё какая проблема. Для решения этой проблемы есть алгоритм консистентного хэширования. Он не защищает от перераспределения данных, но фиксирует их размер.
https://jaidayo.livejournal.com/2645.html
P.S. HashMap данный алгоритм не использует, на размерах порядка 1 млн записей рекомендуется сразу задавать начальный размер равный предполагаемому умноженному на 1.5
P.P.S. Хозяйке на заметку: в nginx, при использовании его в качестве балансировщика включить консистентное вычисление хэша от URL запроса можно одной строкой hash $request_uri consistent
P...S А вот документация по использованию алгоритма в Openstack https://docs.openstack.org/swift/latest/ring_background.html

#algorithm #distributedsystem

Тест для проверки мозга после из новогодних праздников)

Почему? Тут будут алгоритмы)

Я уже писал про Consistent Ring Hashing - https://t.me/javaKotlinDevOps/46 - решение для для равномерного распределения данных по нодам\серверам\шардам
Но это не единственное решение, особенно когда появляются требования:
1) много нод (тысячи, десятки тысяч)
2) частое добавление и удаление нод
3) минимальный объем перемещения данных при ребалансировке нод
4) простота алгоритма и, соответственно, его отладки
5) минимальное потребление памяти для хранения данных маршрутизации
6) минимальное время вычисления целевой ноды
7) максимально равномерное распределение данных
8) возможность назначать веса нодам

Естественно, единственно оптимального решения для всех этих требований нет.
Но есть варианты:
1) Consistent Ring Hashing с виртуальными нодами
2) Rendezvous Hashing
3) Jump Consistent Hashing https://iq.opengenus.org/jump-consistent-hash/ (VPN)
4) Consistent Hashing with Bounded Loads https://gweb-research2023-stg.uc.r.appspot.com/blog/consistent-hashing-with-bounded-loads/

И парочка сравнительных статей с которых стоит начать:
https://dtf.ru/gamedev/1215676-consistent-protiv-rendezvous-chem-otlichayutsya-podhody-dlya-heshirovaniya-dannyh-na-servere
https://chaotic.land/ru/posts/2024/09/data-sharding-algorithms/

Для себя сделал такие выводы:
1) Consistent Ring Hashing - база
2) Rendezvous Hashing - простой алгоритм, равномерное распределение "из коробки", но медленнее, что сказывается при большом числе нод
3) Jump Consistent Hashing - быстрый, тоже равномерный "из коробки", но плохо себя ведет при частом изменении числа нод и необходимости добавления весов

P.S. С наступающим!)

#algorithm #distributedsystem