ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Автор: Казачкин Даниил Михайлович · Обновлено
Фильтр Блума с формулами и Python: расчёт памяти, двойное хеширование, false positive, ограничения удаления и production-чек-лист.
Фильтр Блума быстро отвечает на вопрос «этот ключ точно отсутствует или, возможно, присутствует?». Он хранит не сами ключи, а битовый массив, поэтому экономит память ценой контролируемых ложноположительных ответов.
Это предварительный фильтр, а не источник истины. Ответ «точно нет» позволяет пропустить дорогой запрос. Ответ «возможно, да» означает, что нужно проверить настоящее хранилище.
Пусть есть массив из 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 позиций.
Так возникает 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 КиБ, и семь проверяемых позиций на ключ. Это плановая вероятность для модели с качественным распределением хешей, а не обещание для любого входа и любой реализации.
В примере используются два отдельно персонализированных вычисления 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-фильтром нужно хранить:
Типичный pipeline выглядит так:
Польза возникает, когда отрицательных запросов много, точная проверка заметно дороже нескольких хешей, а фильтр помещается в быструю память. Если точное множество и так мало и находится в памяти, дополнительный слой может только добавить CPU и сложность.
Практические сценарии:
Фильтр нельзя использовать как единственное доказательство существования пользователя, права доступа, платежа или уникальности. Ложноположительный ответ является частью контракта.
Теоретическое p нужно дополнить тестом на данных, похожих на production:
Нельзя подбирать тестовые отсутствующие ключи из того же набора, который добавлялся: тогда измеряется true positive rate, а не вероятность ошибки.
Формула опирается на приближения и предположение о равномерном поведении хешей. Реальные корреляции, малые размеры, неудачный modulus и враждебный ввод могут изменить результат. Работа Кирша и Митценмахера обосновывает двойное хеширование асимптотически; она не сертифицирует любую конкретную нарезку digest или реализацию битового массива.
Оригинальная статья Бёртона Блума 1970 года формулировала компромисс между памятью, временем отбрасывания отсутствующего сообщения и допустимой частотой ошибок. Современные названия библиотек и аппаратные оптимизации меняются, но контракт остаётся тем же: отрицательный ответ точный, положительный — вероятностный.
Фильтр Блума полезен не потому, что «ищет быстрее hash set», а потому, что компактно защищает более дорогой слой от большей части отрицательных запросов. Перед внедрением нужно назвать дорогую операцию, рассчитать ёмкость, принять допустимый false positive rate и спроектировать перестроение. Без этих четырёх пунктов структура остаётся красивой формулой без измеримой пользы.
Самостоятельный редакционный разбор ЯдроКода по работам Burton H. Bloom, Adam Kirsch и Michael Mitzenmacher и официальной документации Python. Факты и идеи изложены редакцией самостоятельно; фрагменты исходного текста, код и иллюстрации не воспроизводятся.
Иллюстрации и листинги первоисточников не копируются. Битовая схема и Python-код подготовлены редакцией.