Фильтр Блума: вероятностная структура данных для поиска

Зачем нужен фильтр Блума?

Представьте: Chrome проверяет каждый URL, который вы открываете, по базе из миллионов опасных сайтов — и делает это локально, без отправки данных на сервер и без скачивания гигабайтной базы. Секрет — в фильтре Блума, вероятностной структуре данных, которая занимает в десятки раз меньше памяти, чем хеш-таблица, и гарантирует отсутствие ложноотрицательных результатов. Разберёмся, как это работает.

Основная идея: вероятностный «может быть»

Обычная структура данных (хеш-таблица, база данных) отвечает на вопрос «Есть ли X в коллекции?» однозначно: да или нет. Фильтр Блума отвечает иначе:

• «Точно НЕТ в наборе» — гарантированно верно, 100%.
• «Возможно, ДА» — может быть ложноположительный ответ.

Фильтр Блума никогда не говорит:

• «Точно ДА» с полной уверенностью.
• «НЕТ», когда элемент на самом деле есть (ложноотрицательные результаты невозможны).

Эта асимметрия — отсутствие ложноотрицательных при возможных ложноположительных — и есть ключевая особенность, делающая фильтр полезным.

Как это работает: битовый массив и хеш-функции

Фильтр Блума — это битовый массив размера m (изначально все нули) и k независимых хеш-функций.

Добавление элемента

# Битовый массив (m=16): [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

# Добавляем "malware.com"
# hash1("malware.com") % 16 = 2  → устанавливаем бит 2 в 1
# hash2("malware.com") % 16 = 7  → устанавливаем бит 7 в 1
# hash3("malware.com") % 16 = 11 → устанавливаем бит 11 в 1

# Массив: [0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0]
#             ↑           ↑     ↑
#           бит 2       бит 7  бит 11

Проверка элемента

# Проверяем "malware.com" (уже добавлен):
# hash1("malware.com") % 16 = 2  → бит 2 = 1 ✓
# hash2("malware.com") % 16 = 7  → бит 7 = 1 ✓
# hash3("malware.com") % 16 = 11 → бит 11 = 1 ✓
# Все биты установлены → «Возможно, в наборе» (верно)

# Проверяем "safe-site.com" (не добавлялся):
# hash1("safe-site.com") % 16 = 3  → бит 3 = 0 ✗
# Любой бит = 0 → «Точно НЕ в наборе» (верно)

# Проверяем "another-site.com" (не добавлялся, но...):
# hash1("another-site.com") % 16 = 2  → бит 2 = 1 (установлен malware.com)
# hash2("another-site.com") % 16 = 11 → бит 11 = 1 (установлен malware.com)
# hash3("another-site.com") % 16 = 7  → бит 7 = 1 (установлен malware.com)
# Все биты случайно оказались 1 → «Возможно, в наборе»
# → ЛОЖНОПОЛОЖИТЕЛЬНЫЙ РЕЗУЛЬТАТ!

Почему нет ложноотрицательных: если элемент был добавлен, все его биты установлены в 1. При проверке они остаются 1 (биты никогда не сбрасываются в базовом фильтре). Поэтому реальный член набора никогда не будет сообщён как отсутствующий.

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

Почему малый размер памяти — главное преимущество

Вот цифры, которые впечатляют:

• Хранить 1 миллион URL с 1% ложноположительных: хеш-таблица ~50-100 МБ, фильтр Блума ~1.2 МБ.
• Хранить 1 МИЛЛИАРД URL с 1%: хеш-таблица ~50-100 ГБ, фильтр Блума ~1.2 ГБ.

Фильтр Блума не хранит сами данные — только биты, указывающие, что «что-то сюда хешировалось». Именно поэтому Chrome может загрузить фильтр Блума со списком опасных сайтов как небольшое обновление и проверять URL полностью локально, без сетевого запроса для обычных (безопасных) сайтов.

Схема работы Chrome:

1. Пользователь переходит по URL.
2. Проверка локального фильтра Блума: «Этот URL возможно опасен?»
3. Если фильтр говорит «точно нет» → переход сразу, БЕЗ сетевого запроса (подавляющее большинство URL).
4. Если фильтр говорит «возможно да» → теперь делается сетевой запрос к полной базе Google для подтверждения (редко — только для ложноположительных и реально опасных URL).

Фильтр Блума работает как быстрый локальный префильтр, устраняя ~99% случаев, требующих сетевого обращения, и никогда не пропуская настоящие опасные URL.

Настройка вероятности ложноположительных ответов

Два параметра управляют точностью: размер битового массива m и количество хеш-функций k.

Формула (для понимания, не для запоминания на собеседовании):

Вероятность ложноположительного ≈ (1 - e^(-kn/m))^k

Где:
  n = количество вставленных элементов
  m = размер битового массива
  k = количество хеш-функций

Практический компромисс:

• Больше битов на элемент (больше m относительно n) → ниже вероятность ложноположительного, больше памяти.
• Оптимальное k: k ≈ (m/n) × ln(2). Слишком мало хеш-функций — недостаточное покрытие битов, выше ложноположительные. Слишком много — массив быстро заполняется, тоже выше ложноположительные.

Типичные значения:

• ~10 бит на элемент, 7 хеш-функций → ~1% ложноположительных.
• ~15 бит на элемент, 10 хеш-функций → ~0.1% ложноположительных.

Фраза для собеседования: «Фильтры Блума обменивают память на точность — вы выбираете приемлемую вероятность ложноположительных заранее, и это определяет, сколько бит на элемент нужно. Удвоение битов примерно квадратично улучшает точность (в 10 раз меньше ложноположительных при ~50% увеличении битов в практическом диапазоне).»

Counting Bloom Filter: добавление удаления

Базовый фильтр Блума не позволяет удалять элементы — биты разделяются между элементами, сброс бита «сломает» проверку для других элементов. Counting Bloom Filter использует маленькие счётчики вместо одиночных битов:

# Базовый: [0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0]
# Counting: [0,0,2,0,0,0,0,1,0,0,0,3,0,0,0,0]
#              ↑               ↑
#         2 элемента   3 элемента

# Добавление: увеличить счётчики
# Удаление: уменьшить счётчики (если счётчик = 0, бит сброшен)
# Проверка: все ли счётчики > 0?

Цена: Counting Bloom Filter использует больше памяти (обычно 4 бита на счётчик вместо 1 бита), но всё равно значительно меньше, чем хранение самих элементов, и поддерживает удаление.

Реальная реализация: Cassandra и SSTables

Cassandra хранит данные в неизменяемых файлах SSTable. На одном узле могут быть сотни таких файлов. Без фильтра Блума пришлось бы проверять каждый SSTable на диске — каждый раз делать медленное чтение. Фильтр Блума для каждого SSTable хранится в памяти. Перед чтением Cassandra проверяет: «Может ли ключ быть в этом SSTable?» Если «точно нет» — файл пропускается, диск не читается. В результате вместо сотен дисковых чтений — 1-2. Это одна из причин высокой производительности Cassandra.

Реальная реализация: Akamai и «однохитовые» запросы

Akamai сталкивается с проблемой: огромная доля запросов к исходным серверам — это «однохитовые» запросы (ресурс запрашивается один раз и больше никогда). Кэшировать их — тратить место впустую. Akamai использует фильтр Блума:

1. Первый запрос URL X → проверка фильтра: «точно не видели» → НЕ кэшируем, но добавляем в фильтр.
2. Второй запрос того же URL → проверка: «возможно видели» → теперь кэшируем.

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

Фильтр Блума против хеш-таблицы: когда что использовать

Используйте фильтр Блума, когда:

• Нужно проверить «может ли X быть в огромном наборе?»
• Память ограничена относительно размера набора.
• Ложноположительные допустимы (они вызывают более дорогую, но точную проверку).
• Не нужно получать или перечислять сами элементы.

Используйте хеш-таблицу, когда:

• Нужна точная проверка (ложноположительные недопустимы).
• Нужно получать или перебирать элементы.
• Память не является ограничением.

Сценарий на собеседовании: снижение нагрузки на БД

Вопрос: Ваше приложение часто проверяет «существует ли такое имя пользователя?» — и большинство проверок для имён, которых НЕТ (новые регистрации). Как оптимизировать?

Ответ: «Большинство проверок — для несуществующих имён, каждый запрос к БД — впустую. Я бы поддерживал фильтр Блума со всеми существующими именами, храня его в памяти и обновляя при регистрации. Проверка: сначала фильтр Блума. Если «точно нет» — имя свободно, запрос к БД не нужен. Если «возможно да» — тогда запрос к БД для подтверждения. Поскольку большинство проверок — для несуществующих имён, это устраняет основную массу чтений БД. Фильтр нужно синхронизировать — обновлять его синхронно при создании пользователя (дёшево — установить несколько битов), чтобы не было ложноотрицательных для новых пользователей.»

Практический вывод

Фильтр Блума — мощный инструмент для экономии памяти и ускорения проверок, когда допустимы ложноположительные ответы. Напишите свою реализацию на Python прямо сейчас: используйте bitarray или просто целое число как битовую маску, возьмите пару хеш-функций (например, hashlib.md5 и hashlib.sha1) и протестируйте на 1000 элементах. Вы увидите, как легко достичь 1% ложноположительных при 10 битах на элемент. Это понимание пригодится и на собеседованиях, и в реальных проектах, где нужно быстро отсеивать заведомо отсутствующие данные.