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

Что это такое

Фильтр Блума состоит из массива в m битов и k хеш-функций. Добавление элемента устанавливает k битов, выбранных его хешами; запрос проверяет эти биты. Если хотя бы один бит не установлен, элемент никогда не добавляли. Если установлены все, элемент либо добавляли, либо эти биты установили другие элементы, что даёт ложноположительный ответ. Документация PostgreSQL описывает его индекс bloom как экономный по памяти, но допускающий ложноположительные ответы, поэтому каждое попадание индекса нужно перепроверять по фактической строке. Документация Redis позволяет создавать фильтр с желаемой вероятностью ложноположительного ответа и ожидаемой вместимостью. Базовый фильтр не поддерживает удаление: сброс бита может стереть свидетельство присутствия другого элемента. Для этого существуют счётные фильтры Блума и кукушечные фильтры.

Почему это важно

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

Как применять

• Рассчитывайте размер по ожидаемому числу элементов и целевой вероятности ложноположительного ответа. При превышении расчётной вместимости эта вероятность растёт, поэтому ориентируйтесь на максимум или используйте масштабируемый вариант.
• Считайте каждый положительный ответ указанием «проверить настоящее хранилище». Пропускайте перепроверку только там, где ложноположительный ответ безвреден, например приводит лишь к дополнительному промаху кеша.
• Храните фильтр вместе с идентификаторами его хеш-функций, начальным значением и размером; любое изменение требует перестроения по полному множеству.
• Применяйте его там, где преобладают безрезультатные поиски (неизвестные имена пользователей, удалённые ключи, редко используемые объекты), и измерьте долю отсеянных запросов, прежде чем оставлять его в системе.
• Периодически перестраивайте фильтр, когда исходное множество сокращается: сам фильтр только растёт.

Подводные камни

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