Фильтр Блума: вероятность ошибки и реализация на Python

Фильтр Блума с формулами и Python: расчёт памяти, двойное хеширование, false positive, ограничения удаления и production-чек-лист.

Фильтр Блума быстро отвечает на вопрос «этот ключ точно отсутствует или, возможно, присутствует?». Он хранит не сами ключи, а битовый массив, поэтому экономит память ценой контролируемых ложноположительных ответов.

Это предварительный фильтр, а не источник истины. Ответ «точно нет» позволяет пропустить дорогой запрос. Ответ «возможно, да» означает, что нужно проверить настоящее хранилище.

Как устроена операция add

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

Например, три функции для строки alice выбрали позиции 2, 5 и 11:

индекс: 0 1 2 3 4 5 6 7 8 9 10 11
бит:    0 0 1 0 0 1 0 0 0 0  0  1

Добавление следующего ключа устанавливает ещё несколько битов, но никогда не сбрасывает существующие.

Как устроена проверка

Для искомого ключа вычисляются те же k позиций.

• Если хотя бы один бит равен нулю, ключ точно не добавляли: операция add обязательно установила бы его.
• Если все биты равны единице, ключ, возможно, добавляли. Эти позиции могли быть независимо заняты другими ключами.

Так возникает false positive. В стандартном insert-only фильтре нет false negative при условии, что конфигурация и хеширование не меняются и биты не повреждаются.

Откуда берётся вероятность ошибки

После добавления n элементов с k равномерными хешами вероятность того, что конкретный бит остался нулём, приближённо равна exp(−kn/m). Поэтому вероятность ложноположительного ответа оценивают формулой:

p ≈ (1 − exp(−kn/m))^k

Для заданных m и n выражение минимально примерно при:

k ≈ (m / n) · ln(2)

Если заранее известны ожидаемое число ключей n и допустимая ошибка p, размер можно выбрать так:

m = ceil(−n · ln(p) / ln(2)^2)
k = round((m / n) · ln(2))

Для 100 000 ключей и p = 0,01 получается около 958 506 бит, то есть примерно 117 КиБ, и семь проверяемых позиций на ключ. Это плановая вероятность для модели с качественным распределением хешей, а не обещание для любого входа и любой реализации.

Учебная реализация на Python

В примере используются два отдельно персонализированных вычисления BLAKE2b. Остальные позиции выводятся двойным хешированием по схеме h1(x) + i · h2(x). Работа Кирша и Митценмахера показывает, что такая конструкция позволяет не вычислять k полноценных независимых хешей без ухудшения асимптотической вероятности false positive.

from hashlib import blake2b
from math import ceil, log


class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float) -> None:
        if expected_items <= 0:
            raise ValueError("expected_items must be positive")
        if not 0 < false_positive_rate < 1:
            raise ValueError("false_positive_rate must be between 0 and 1")

        self.bit_count = ceil(
            -expected_items * log(false_positive_rate) / log(2) ** 2
        )
        self.hash_count = max(
            1, round(self.bit_count / expected_items * log(2))
        )
        self.bits = bytearray((self.bit_count + 7) // 8)

    def _positions(self, value: str):
        raw = value.encode("utf-8")
        first = int.from_bytes(
            blake2b(raw, digest_size=8, person=b"bloom-h1").digest()
        )
        second = int.from_bytes(
            blake2b(raw, digest_size=8, person=b"bloom-h2").digest()
        )
        step = second % self.bit_count or 1

        for index in range(self.hash_count):
            yield (first + index * step) % self.bit_count

    def add(self, value: str) -> None:
        for position in self._positions(value):
            byte_index, bit_index = divmod(position, 8)
            self.bits[byte_index] |= 1 << bit_index

    def might_contain(self, value: str) -> bool:
        for position in self._positions(value):
            byte_index, bit_index = divmod(position, 8)
            if not self.bits[byte_index] & (1 << bit_index):
                return False
        return True


known_users = BloomFilter(expected_items=100_000, false_positive_rate=0.01)
known_users.add("alice")

print(known_users.might_contain("alice"))  # True
print(known_users.might_contain("mallory"))  # обычно False, но может быть True

Код демонстрирует устройство структуры, но не решает production-вопросы конкурентных обновлений, сериализации, совместимости версий и устойчивости к специально подобранным входам.

Почему нельзя удалять обычным сбросом бита

Позиции разделяются разными ключами. Если alice и bob установили один и тот же бит, удаление alice не даёт права обнулить его: bob всё ещё зависит от этой позиции. Простое удаление создаст false negative.

Counting Bloom filter заменяет бит небольшим счётчиком: add увеличивает, delete уменьшает. Это требует больше памяти и аккуратной защиты от переполнения и повторного удаления. Другой практический вариант — периодически перестраивать неизменяемый фильтр из актуального набора.

Переполнение меняет обещанную точность

Параметры выбираются под ожидаемое n. Если в фильтр, рассчитанный на 100 000 ключей, загрузить значительно больше, единиц станет слишком много и false positive rate вырастет. Сам массив не сообщает надёжное точное число уникальных вставок: повторное добавление того же ключа выглядит как обычная установка уже занятых битов.

Поэтому вместе с persisted-фильтром нужно хранить:

• версию формата и алгоритма хеширования;
• m, k и ожидаемую ёмкость;
• фактическое число операций или внешнюю оценку cardinality;
• целевой и измеренный false positive rate;
• правила перестроения и совместимости при rollout.

Где фильтр действительно экономит работу

Типичный pipeline выглядит так:

1. Запрос спрашивает ключ.
2. Фильтр отвечает «точно нет» — система сразу возвращает отсутствие.
3. Фильтр отвечает «возможно, да» — система читает индекс, диск или удалённое хранилище.
4. Настоящее хранилище подтверждает присутствие либо обнаруживает false positive.

Польза возникает, когда отрицательных запросов много, точная проверка заметно дороже нескольких хешей, а фильтр помещается в быструю память. Если точное множество и так мало и находится в памяти, дополнительный слой может только добавить CPU и сложность.

Практические сценарии:

• не читать SSTable или другой дисковый сегмент, если ключ точно отсутствует;
• не отправлять дорогой удалённый запрос для заведомо отсутствующего объекта;
• предварительно отсеивать отсутствующие идентификаторы перед точной проверкой.

Фильтр нельзя использовать как единственное доказательство существования пользователя, права доступа, платежа или уникальности. Ложноположительный ответ является частью контракта.

Как измерять реализацию

Теоретическое p нужно дополнить тестом на данных, похожих на production:

1. Добавьте n уникальных ключей из одного набора.
2. Проверьте, что для каждого добавленного ключа нет false negative.
3. Возьмите большой непересекающийся набор запросов и посчитайте долю ответов «возможно, да».
4. Повторите тест при 50%, 100% и 150% плановой ёмкости.
5. Измерьте не только точность, но и время хеширования, размер массива и сэкономленные обращения к основному хранилищу.

Нельзя подбирать тестовые отсутствующие ключи из того же набора, который добавлялся: тогда измеряется true positive rate, а не вероятность ошибки.

Ограничения математической модели и примера

Формула опирается на приближения и предположение о равномерном поведении хешей. Реальные корреляции, малые размеры, неудачный modulus и враждебный ввод могут изменить результат. Работа Кирша и Митценмахера обосновывает двойное хеширование асимптотически; она не сертифицирует любую конкретную нарезку digest или реализацию битового массива.

Оригинальная статья Бёртона Блума 1970 года формулировала компромисс между памятью, временем отбрасывания отсутствующего сообщения и допустимой частотой ошибок. Современные названия библиотек и аппаратные оптимизации меняются, но контракт остаётся тем же: отрицательный ответ точный, положительный — вероятностный.

Короткий инженерный вывод

Фильтр Блума полезен не потому, что «ищет быстрее hash set», а потому, что компактно защищает более дорогой слой от большей части отрицательных запросов. Перед внедрением нужно назвать дорогую операцию, рассчитать ёмкость, принять допустимый false positive rate и спроектировать перестроение. Без этих четырёх пунктов структура остаётся красивой формулой без измеримой пользы.