Всем привет!

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

Всем привет!

При изучении NoSQL СУБД может возникнуть вопрос - ага, тут у нас ключ-значение, где-то я это уже видел. А, распределенные кэши. Redis, EhCache, Memcached, Hazelcast, Ignite. В чем разница? Это тоже NoSQL?
Если посмотреть на рейтинг СУБД https://db-engines.com/en/ranking - то да, все они там есть. Кстати, хороший сайт, аналог рейтинга Tiobe для языков программирования. Там даже Microsoft Access есть) Сайт хороший, но мне такой критерий определения: СУБД или нет - не очень нравится.
Я бы сказал: критерий отнесения к NoSQL хранилищам в персистентности, а если быть точным - позиционируют ли создатели системы ее как долговременное хранилище данных. Почему это важно? Если разработчики не предполагают, что в их системе можно долго, а в предельном случае вечно хранить данные, то там наверняка не будет необходимых для этого средств. Это могут быть утилиты для резервного копирования, а оно нужно даже при наличии репликации для возможности отката при порче данных из-за программной ошибки\взлома. Или тонких настроек взаимодействия с файловой системой. Или гарантии персистентности при сбое сервера сразу после ответа клиенту об успешной записи, которая (гарантия) обычно обеспечивается предварительной записью в Write Ahead Log (WAL) или лог транзакций. И чего-то еще, что я не знаю т.к. не являюсь DBA.
Redis - вообще говоря это первая NoSQL система, просто ее спроектировали как замену RDBMS еще до того, как появилось понятие NoSQL. Хотя Redis можно использовать как распределенный кэш. Поддерживает все необходимое для долгосрочного хранения данных https://redis.io/docs/management/persistence/
Memcached и EhCache. Это все-таки распределенные кэши с персистентностью, а не NoSQL. Может возникнуть вопрос - EhCache разве распределенный? Уже да - https://www.ehcache.org/documentation/3.1/caching-concepts.html Но судя по описанию архитектуры сервиса - уровень хранения на диске для Ehcache вторичен.
Аналогично Memcached - https://github.com/memcached/memcached/wiki/Extstore По умолчанию хранение на диске выключено. Цель дискового храненения - увеличение процента попадания в кэш.
Hazelcast и Ignite относятся к категории IMDG In-Memory Data Grid. Суть в том, что данные шардированы по разным серверам и есть возможность выполнять вычисления на одном сервере с данными. А это радикально увеличивает быстродействие и дает возможность в онлайне рассчитывать какую-то аналитику, подсказки и спецпредложения для клиента, выявлять фрод и т.д. Также можно сравнить IMDG с хранимыми процедурами в СУБД, которые тоже позволяли ускорить обработку данных, но в отличие от хранимых процедур код здесь написан на стандартных языках программирования.
При этом Hazelcast позиционирует себя как In-memory NoSQL - https://hazelcast.com/use-cases/in-memory-nosql/ В примерах использования в целом говорится о том же - https://hazelcast.com/use-cases/, см. сравнение с Cassandra, а это напомню NoSQL типа "семейство столбцов" - не замена, а способ улучшить производительность Cassandra. К слову - персистентность выключена по умолчанию и доступна только в Enterprise версии https://docs.hazelcast.com/hazelcast/5.2/storage/configuring-persistence
С Ignite интереснее. Есть 3 канала записи на диск - WAL, checkpointing (сброс незафиксированных данных на диск) и собственно запись данных на диск. Первые два должны обеспечивать достаточную надежность при сбоях https://ignite.apache.org/docs/latest/persistence/native-persistence
Себя позиционируют как NoSQL, только с SQL - хорошо звучит)))) - и транзакциями, правда ограниченными https://ignite.apache.org/faq.html
Но с другой стороны я знаю практический кейс, когда кластер Ignite очень долго допиливали и "тюнили" с целью заставить восстанавливаться в приемлемые сроки после сбоя. Прямо очень очень долго. Т.е. необходимый функционал есть, вопрос в отказоустойчивости и падении производительности при сбоях. Так что использовать Ignite как NoSQL хранилище можно, но осторожно, но с обязательным НТ и chaos engineering тестами.

#cache #imdg #nosql #rdbms

Всем привет!

Хочу порекомендовать хорошую статью на Хабре о необходимости кэша.
https://habr.com/ru/companies/oleg-bunin/articles/883422/
Со сравнительными тестами Redis, Memcached, PostgreSQL и MySQL.

Из статьи я почерпнул для себя несколько основных тезисов:

1) в наше время получить 1 000 000 rps с сервера на чтение - это реальность. И это круто! Речь про стандартный сервер, а не 100 ядер\1000 Гб памяти как можно было бы подумать

2) реляционные СУБД приблизились к кэшам (key-value noSQL хранилищам если хотите) по скорости чтения

3) как правильно заметил автор: будь он СТО - не разрешил бы использовать СУБД как кэш. И вот почему. Сравнимая производительность БД-кэш достигается при 2 условиях - нет операций записи в БД (а соответственно и блокировок записей) и все выборки идут по первичному ключу (это самая быстрая операция выборки). Казалось бы - соблюдай эти условия и все будет работать. Но ведь у нас СУБД. Окей, GRANT на запись отберем у всех. Но ведь СУБД может сложные JOIN-ы. И это никак не ограничить правами. Там могут быть сложные индексы. И рано или поздно найдется разработчик, которые эти возможности захочет использовать))) И в пике производительность упадет даже не в разы, а на порядки. Например, не провели НТ. Или забыли обновить профиль НТ. С кэшом такого по понятным причинам не произойдет. Вывод - у каждого инструмента свое назначение.

4) проблема неконсистентности данных кэш-БД все равно будет. Поэтому перед тем, как добавлять в систему кэш - стоит подумать, провести НТ и еще раз подумать. Возможно где-то есть или планируется архивная реплика БД. Там проблема констистентности данных решается механизмом репликации .Если часть нагрузки на чтение увести на нее - возможно кэш и не нужен.

P.S. Отдельная интересная тема: PostgreSQL показывает, что принцип число процессов ОС = числу ядер - не аксиома)

#rdbmc #cache #arch_compromises

PostgreSQL и кэш

Речь не про кэширование JPA, а про собственное кэширование БД.

1) на сервере есть 2 уровня кэширования: PostgreSQL buffer cache и Linux page cache. В отличие от Kafka, где он один.
А если использовать кэширование на уровне JPA, в итоге получается 4 уровня)

2) по умолчанию кэша выделяется мало, для PROD like его размер нужно увеличить.
Посмотреть сколько:

SHOW shared_buffers

Изменить:

ALTER SYSTEM SET shared_buffers TO <your_value>; -- при наличии прав

или через /etc/postgresql/../postgresql.conf
c рестартом сервера.

Универсальных рекомендаций по размеру быть не может, но можно начать с 1/4 ОЗУ.

3) размером Linux page cache напрямую управлять нельзя. Но его максимальный размер можно ограничить косвенно, через

sysctl vm.swappiness

Да, это процент использования swap файла, но как побочный эффект он ограничивает использование ОЗУ под page cache, и оставшееся пространство можно выделить PostgreSQL.

Зная эти два параметра можно рассчитать максимальное значение для кэша PostgreSQL:

shared_buffers ~= ОЗУ * vm.swappiness - резерв ОС - резерв PostgreSQL

4) со значением shared_buffers нужно быть осторожным, также как и с настройкой heap space в JVM. PostgreSQL ожидает, что вся эта память будет ему доступна.
Если ОЗУ закончится, а процесс будет все равно пытаться запрашивать память, придет злой OOM Killer и убьет его).

5) есть расширение pg_buffercache, предоставляющее одноименное view с информацией о страницах кэша PostgreSQL: к какой таблице относится, как используется.
Перед его использованием нужно само собой установить:

CREATE EXTENSION pg_buffercache;

перегрузить сервер и дать права:

GRANT pg_monitor TO xxx;

Использование:

SELECT count(*)
FROM pg_buffercache
WHERE relfilenode = pg_relation_filenode('table'::regclass);

6) при старте PostgreSQL все кэши пустые.
Интересно, что "SELECT *" не заполняет кэш на 100%, т.к. используется более хитрый механизм, когда для каждой выполняемой операции выделяется часть кэша.
А вот изменение данных, которое тоже идет через буфер, точно кэширует все изменяемые данные.

7) изменение данных - плохой способ заполнить кэш.
А часто прогреть кэш нужно, как минимум для справочных данных.
Да вообще говоря и для любых данных, т.к. если удастся поместить всю БД в кэш, то это ускорит работу с БД на пару порядков (ОЗУ vs диски).
Ну и если быть точным - ускорит серверную часть процесса, см. https://t.me/javaKotlinDevOps/487

И ... для прогрева кэша тоже есть расширение:

CREATE EXTENSION pg_prewarm;
ALTER SYSTEM SET shared_preload_libraries = 'pg_prewarm';

и рестарт.

Использование:

SELECT pg_prewarm('table');

8) PostgreSQL сам чистит кэш в фоновом режиме, а явно сбросить кэш можно только перезагрузкой сервера. Что-то мне это напоминает из мира Java)

#cache #postgresql #performance