Bloom-фильтр: как отвечать «точно нет» без обращения к хранилищу

Прямой ответ

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

Устройство:

• Битовый массив длиной m бит, изначально все нули.
• k хеш-функций, каждая из которых сопоставляет элементу позицию в массиве.
• Добавление: элемент хешируется k раз, соответствующие биты устанавливаются в 1.
• Проверка: элемент хешируется k раз; если хотя бы один бит равен 0 — элемента точно нет; если все единицы — элемент, вероятно, есть.

Ложное срабатывание возникает, когда все нужные биты оказались установлены другими элементами. Вероятность ложного срабатывания приблизительно:

p ≈ (1 - e^(-k·n/m))^k

где n — число добавленных элементов, m — размер массива в битах, k — число хеш-функций. Отсюда практические соотношения:

• Оптимальное число хеш-функций: k = (m/n) · ln 2.
• Размер массива для заданной вероятности p: m = -n · ln(p) / (ln 2)².

Для 1 млн элементов при целевой вероятности 1 % нужно около 9,6 Мбит, то есть примерно 1,2 МБ, и семь хеш-функций. Это цена за экономию миллионов обращений к диску.

import hashlib

class BloomFilter:
    def __init__(self, m: int, k: int):
        self.m, self.k = m, k
        self.bits = bytearray(m // 8 + 1)

    def _positions(self, item: bytes):
        for i in range(self.k):
            h = hashlib.blake2b(item, digest_size=8, salt=str(i).encode()).digest()
            yield int.from_bytes(h, "big") % self.m

    def add(self, item: bytes) -> None:
        for p in self._positions(item):
            self.bits[p >> 3] |= 1 << (p & 7)

    def might_contain(self, item: bytes) -> bool:
        return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._positions(item))

Практика: где применяется и как настраивать

1. LSM-хранилища. Каждый SSTable имеет свой фильтр. При чтении движок сначала спрашивает фильтры и открывает только те файлы, которые могут содержать ключ. Без этого чтение несуществующего ключа стоило бы обращения ко всем уровням — см. LSM-tree. В RocksDB размер фильтра задают в битах на ключ, типично 10 бит на ключ для вероятности около 1 %.

2. PostgreSQL. Расширение bloom создаёт индексный метод на основе фильтра Блума. Он полезен для таблиц с большим числом колонок, когда запросы фильтруют по произвольным их комбинациям: вместо десятка B-tree-индексов один фильтр отбрасывает заведомо неподходящие строки.

CREATE EXTENSION bloom;
CREATE INDEX tags_bloom ON posts USING bloom (tag1, tag2, tag3, tag4)
  WITH (length = 80, col1 = 2, col2 = 2, col3 = 2, col4 = 2);

3. Кэш и защита от пробоя. Перед обращением к базе можно спросить фильтр: если ключа точно нет, запрос отклоняется без нагрузки на БД. Так снижают влияние запросов к заведомо отсутствующим данным.

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

Рекомендации:

1. Считайте размер заранее. Фильтр нельзя расширить без перестроения. Переоценка числа элементов вдвое резко повышает долю ложных срабатываний.
2. Не используйте один хеш. Качественный выбор — несколько независимых хеш-функций или одна с разными солями; экономия на числе хешей повышает вероятность ошибки.
3. Помните: удаления невозможны. Сброс бита может удалить признак другого элемента. Если удаления нужны, используют counting Bloom filter со счётчиками вместо битов, ценой четырёхкратного роста памяти.
4. Фильтр не заменяет точную проверку. После положительного ответа обязательна проверка в источнике.
5. Учитывайте стоимость в памяти. Фильтры всех SSTable обычно держат в памяти; при большой базе это заметная статья расхода.

Практический сценарий: запросы к несуществующим ключам нагружали базу

Контекст: сервис кэшировал профили пользователей в Redis. Нагрузка на PostgreSQL выросла, хотя активных пользователей больше не стало.

1. Диагностика. Анализ запросов показал: 62 % обращений к БД — это ключи, которых в базе нет. Клиенты запрашивали удалённые и никогда не существовавшие идентификаторы, кэш их не содержал, поэтому каждый запрос шёл в базу.
2. Попытка 1. Кэширование отрицательных ответов с коротким TTL помогло частично, но память кэша росла, а доля мусорных ключей была велика — см. структуры Redis.
3. Решение. Добавили Bloom-фильтр на 20 млн идентификаторов при целевой вероятности 1 % — около 24 МБ в памяти. Фильтр строился при старте из выборки активных идентификаторов и пополнялся при регистрации.
4. Эффект. Отрицательные ответы фильтра отклоняли запрос до обращения к БД. Нагрузка на PostgreSQL по этому пути снизилась примерно на 60 %, доля ложных срабатываний на практике составила около 0,9 %.
5. Проверка. Раз в сутки измеряли фактическую долю ложных срабатываний на случайной выборке запросов, чтобы вовремя заметить рост при увеличении числа элементов.

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

FAQ

Может ли Bloom-фильтр сказать, что элемента нет, когда он есть? Нет. Если элемент добавляли, все его биты установлены, и проверка вернёт «возможно есть». Ошибка возможна только в противоположную сторону — ложное «есть».

Сколько хеш-функций оптимально? При соотношении 10 бит на элемент оптимум около семи хеш-функций. Увеличение числа хешей сверх оптимума не улучшает, а ухудшает результат, потому что быстрее заполняется массив.

Чем Bloom-фильтр отличается от хеш-таблицы? Он не хранит сами элементы и не может их вернуть — только ответить на вопрос о принадлежности, причём вероятностно. Зато память расходуется в разы экономнее. Устройство хеш-таблиц — в статье про хеш-таблицы и коллизии.

Что делать, когда элементы нужно удалять? Использовать counting Bloom filter или структуру с поддержкой удаления, например cuckoo filter. Обычный фильтр Блума рассчитан на множество, которое только растёт до перестроения.

Источники: RocksDB docs (Bloom Filter), PostgreSQL docs (bloom module), Wikipedia (Bloom filter) — ссылки в шапке.