Всем привет!

Сегодня хочу рассказать про один интересный алгоритм - фильтр Блума.
Для начала ссылка на вики или хабр - по вкусу)
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 #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