Всем привет!
Сегодня хочу рассказать про один интересный алгоритм - фильтр Блума.
Для начала ссылка на вики или хабр - по вкусу)
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
Сегодня хочу рассказать про один интересный алгоритм - фильтр Блума.
Для начала ссылка на вики или хабр - по вкусу)
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
Wikipedia
Фильтр Блума
Фи́льтр Блу́ма (англ. Bloom filter) — вероятностная структура данных, сконструированная Бёртоном Блумом в 1970 году, позволяющая проверять принадлежность элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента…
Всем привет!
При изучении 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
При изучении 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
Хочу порекомендовать хорошую статью на Хабре о необходимости кэша.
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
Хабр
Нужен ли нам сейчас кеш-слой перед СУБД
Уже лет 20 существует миф (или не миф), что современный Highload-проект невозможен без кэшей. Они всегда нас выручали, когда не справлялись базы данных. Но с тех пор, как появились первые кэши,...