Всем привет!

Снова про алгоритмы.
Представим ситуацию, когда для каждого нашего объекта нужно получить адрес, где его хранить. Это может быть сервер в случае шардированной БД или корзина в HashMap. Хорошим решением является функция, которая однозначно по уникальному идентификатору нашей сущности выдаёт адрес сервера. Альтернативой является хранение таблицы соответствия отдельно, в случае распределённой системы это будет отдельный микросервис, что означает +1 запрос и увеличение задержек. Тривиальной реализацией является простой алгоритм - остаток от деления на число серверов. Но у такого есть минус - при изменении числа серверов распределение объектов по серверам или корзинам сильно меняется. Мы же хотим равномерное распределение. Если перестроение HashMap в памяти обычно (!) не проблема, то в случае десятка серверов в сети - ещё какая проблема. Для решения этой проблемы есть алгоритм консистентного хэширования. Он не защищает от перераспределения данных, но фиксирует их размер.
https://jaidayo.livejournal.com/2645.html #algorithm #distributedsystem
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