Фильтр Блума: множество, которое иногда ошибается

Представим сервис с миллионами идентификаторов. Нам нужно быстро отвечать на вопрос: встречался ли такой ID раньше?

Хранить все значения в условном HashSet может быть слишком дорого. Если точный положительный ответ не обязателен, можно использовать фильтр Блума.

Он возвращает один из двух результатов: точно отсутствует и возможно присутствует.

Ложноположительный ответ возможен. Ложноотрицательный - нет. Если фильтр говорит, что элемента не было, значит его действительно не добавляли.

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

Внутри находится массив битов и несколько хеш-функций.

При добавлении элемента вычисляется несколько позиций:

"java" -> [2, 7, 12]

0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 ↑ ↑ ↑

Биты в этих позициях устанавливаются в 1.

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

boolean mightContain(String value) { for (int index : indexes(value)) { if (!bits.get(index)) { return false; } } return true; }

Если все биты установлены, элемент, вероятно, добавляли. Те же позиции могли независимо занять другие значения, поэтому гарантировать наличие нельзя.

Как выглядела бы реализация на Java

Для хранения битов подойдет BitSet. Методу add() нужно вычислить несколько индексов и установить соответствующие биты. Метод mightContain() вычисляет те же индексы и проверяет, что каждый бит установлен.

Запускать отдельную хеш-функцию для каждого индекса необязательно. Обычно используют double hashing: вычисляют два хеша, а остальные получают из их комбинаций.

При создании фильтра задаются два параметра:

BloomFilter filter = new BloomFilter(1_000_000, 0.01);

Первый параметр - ожидаемое число элементов. Второй - допустимая вероятность ложного срабатывания.

Для миллиона элементов и вероятности ошибки 1% потребуется около 9,6 миллиона бит, то есть примерно 1,14 МБ. Оптимальное количество хешей в этом случае равно семи.

filter.add("order-42");

filter.mightContain("order-42"); // true filter.mightContain("order-99"); // скорее всего false

В реальном проекте писать такую структуру самостоятельно обычно не требуется. Например, готовая реализация есть в Guava:

BloomFilter filter = BloomFilter.create( Funnels.stringFunnel(StandardCharsets.UTF_8), 1_000_000, 0.01 );

Где это применяют

Фильтр Блума ставят перед обращением к диску, базе данных или удаленному сервису. Если он вернул false, дорогой запрос можно пропустить. Ответ true означает, что данные нужно проверить в основном хранилище.

Например, фильтр может содержать ключи, существующие в базе. Запроса с заведомо отсутствующим ключом до базы тогда не дойдет.

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

Еще одна проблема - переполнение. Если добавить намного больше элементов, чем планировалось, доля единичных битов вырастет. Вместе с ней быстро увеличится количество ложных срабатываний.