Всем привет!

Сегодня хочу рассказать про один интересный алгоритм - фильтр Блума.
Для начала ссылка на вики или хабр - по вкусу)
https://ru.wikipedia.org/wiki/Фильтр_Блума
https://habr.com/ru/company/otus/blog/541378/
Ссылки сразу можно не читать, там много теории, расскажу в чем суть на примере.

Есть два микросервиса. Первый предварительно обрабатывает запросы клиента, назовем его web controller. Второй - оркестратор, выполняет длительные операции. web controller выполняет авторизацию, валидацию, кэширование...
Предположим, мы разрешаем выполнение некой операции по черному списку. Или белому - не суть. Это может быть список клиентов, телефонов, диапазонов IP. Список большой, миллионы элементов. Выглядит логично использовать controller для фильтрации, чтобы снять лишнюю нагрузку со оркестратора. Но список динамический, он хранится в отдельном микросервисе.
Какие есть варианты:

1) вызывать микросервис черного списка. Получаем задержку обработки клиентского запроса
2) закэшировать данные в controller с неким TTL. Уже лучше, но так мы потеряем сотни Мб ОЗУ. А это лишь часть функционала controller.
3) закэшировать хэши значений списка. Размер данных скорее всего уменьшится, зависит от выбора хэш-функции и размера данных. Но все равно - десятки Мб.
4) использовать фильтр Блума. Вот калькулятор, показывающий сколько займут данные в фильтре Блума - https://hur.st/bloomfilter/?n=1000000&p=0.01&m=&k=. Как правило, объем меньше раз в 10 благодаря хитрой математике.
Но чудес не бывает, есть подводный камень - фильтр допускает ложноположительные ответы. Т.е. ответ false на запрос входит ли значение в список - это всегда false, а true - с некой вероятностью не true. Вероятность - входной параметр фильтра.
Чем меньше % ошибок - тем больше объем данных.
Соответственно, в нашем примере проверка по черному списку должна быть и в оркестраторе. Но при этом 99.99% "левых" запросов будет отбито в controller.
Может возникнуть вопрос: дублирование - это же плохо? Увы, в микросервисной архитектуре дублирование проверок - это нормально. Главное, не допускать дублирования реализации алгоритма проверки, иначе при его изменении возможен рассинхрон и неприятные баги.

Реализовывать алгоритм самому не нужно, все-таки под капотом у него довольно сложная математика. Есть готовая реализация в Google Guava: https://www.baeldung.com/guava-bloom-filter

#algorithm #java #cache

Всем привет!

Снова про алгоритмы.
Представим ситуацию, когда для каждого нашего объекта нужно получить адрес, где его хранить. Это может быть сервер в случае шардированной БД или корзина в 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