Фильтр Блума: как сжать 96 МБ URL до 1,2 МБ и ускорить поиск в 3 раза

Андрей Отинов -

Как изменилась работа: пример из статьи

В команде, разрабатывающей веб‑краулер, возникла проблема: при обработке миллиона URL‑адресов хэш‑таблица, в которой хранились все посещённые страницы, занимала 96 МБ памяти, а сама программа потребляла 128 МБ ОЗУ. Это означало, что почти половина памяти была отведена только на отслеживание URL‑ов.

Источник: Habr

В статье описывается, как автор заменил обычную хэш‑таблицу на фильтр Блума. После замены размер структуры сократился до 1,2 МБ, а общая память, потребляемая программой, упала до 18 МБ. Это 10‑разовое уменьшение памяти. Время поиска в фильтре Блума составило 45 нс, что почти в три раза быстрее, чем 150 нс в хэш‑таблице. При этом уровень ложноположительных результатов составил 0,8 % (8 000 из 1 млн запросов).

Почему это важно сейчас

В современных AI‑пайплайнах и LLM‑приложениях часто приходится обрабатывать огромные объёмы данных: кэшировать эмбеддинги, хранить токены, проверять наличие уже обработанных элементов. Если каждый элемент занимает целые байты, память быстро исчерпывается, а скорость работы падает из‑за частых обращений к памяти.

Фильтр Блума позволяет хранить информацию о наличии элемента, используя только несколько битов. Это экономит память и ускоряет поиск, но вводит риск ложноположительных результатов. В большинстве случаев небольшое число повторных операций не приводит к сбоям, а лишь слегка увеличивает нагрузку.

Как применить: пошаговый подход

  1. Определите задачу – например, проверка, был ли уже обработан токен, URL или эмбеддинг.
  2. Оцените объём данных – сколько уникальных элементов вы ожидаете хранить.
  3. Выберите размер битов – чем больше битов на элемент, тем ниже вероятность ложноположительных результатов.
  4. Реализуйте фильтр – в большинстве языков есть готовые библиотеки (C, C++, Python).
  5. Проверьте производительность – измерьте потребление памяти и время поиска на реальных данных.
  6. Настройте порог – если 0,8 % ложных положительных слишком высок, увеличьте размер битов.

Ограничения и риски

  • Ложноположительные результаты – иногда элемент будет считаться «уже обработанным», хотя его ещё нет. Это приводит к повторной обработке, но не к ошибке.
  • Непредсказуемость при больших объёмах – при росте количества элементов вероятность ложных положительных может увеличиться, если размер битов не масштабируется.
  • Требуется настройка – слишком маленький размер битов экономит память, но повышает риск ошибок.

Что проверить сейчас: чеклист для команды

  1. Сколько памяти занимает ваш текущий набор данных?
  2. Какой процент ложноположительных результатов допустим в вашем бизнес‑контексте?
  3. Нужна ли вам точность 100 % или можно позволить небольшие дублирования?
  4. Есть ли готовые библиотеки для выбранного языка?
  5. Можно ли провести пилотный запуск на небольшом наборе данных?
  6. Какой бюджет на дополнительную память при необходимости?

Дополнительные примеры применения

Фильтры Блума активно используются в базах данных (например, в Apache Cassandra и PostgreSQL) для ускорения поиска по индексам. В распределённых системах они помогают избежать лишних сетевых запросов, проверяя наличие данных на узлах. В AI‑пайплайнах фильтры применяются для дедупликации обучающих выборок и кэширования результатов вычислений.

Сравнение с альтернативами

Помимо фильтра Блума существуют другие вероятностные структуры данных: кукушкин фильтр (cuckoo filter) и фильтр-счётчик (counting Bloom filter). Кукушкин фильтр поддерживает удаление элементов и даёт более низкую вероятность ложноположительных результатов при том же объёме памяти. Фильтр-счётчик позволяет отслеживать количество добавлений элемента, что полезно для частотного анализа. Выбор зависит от конкретных требований: нужна ли поддержка удаления или подсчёт повторений.

Практические рекомендации по внедрению

При внедрении фильтра Блума в реальный проект важно учитывать несколько ключевых аспектов. Во-первых, необходимо правильно оценить ожидаемое количество элементов и допустимую вероятность ложноположительных результатов. Для этого можно воспользоваться онлайн-калькуляторами, которые помогут подобрать оптимальный размер битового массива и количество хэш-функций. Во-вторых, стоит протестировать фильтр на синтетических данных, имитирующих реальную нагрузку, чтобы убедиться, что производительность соответствует ожиданиям. В-третьих, рекомендуется внедрять фильтр поэтапно: сначала на небольшом подмножестве данных, затем постепенно расширять. Это позволит выявить потенциальные проблемы на ранних стадиях и скорректировать настройки без серьёзных последствий для системы.

Типичные ошибки при использовании

Одна из распространённых ошибок — использование фильтра Блума для задач, где требуется абсолютная точность, например, в финансовых транзакциях или медицинских записях. В таких случаях даже небольшой процент ложноположительных результатов может привести к серьёзным последствиям. Другая ошибка — игнорирование необходимости периодической перестройки фильтра при изменении объёма данных. Если количество элементов превышает изначально запланированное, вероятность ложноположительных результатов может резко возрасти. Также важно помнить, что фильтр Блума не поддерживает удаление элементов, поэтому для задач с частыми удалениями лучше использовать кукушкин фильтр или фильтр-счётчик.

Источники

Что почитать дальше