Фильтры Блума

Односторонняя гарантия

Фильтр Блума — это вероятностная структура проверки членства. Ты добавляешь в неё элементы, а позже спрашиваешь «есть ли X в множестве?». Она отвечает одним из двух вердиктов, и асимметрия между ними — вся суть:

• «Точно отсутствует». Этот ответ всегда верен. У фильтра Блума никогда нет ложноотрицательных — если он говорит, что элемент не добавляли, его действительно не добавляли.
• «Возможно есть». Этот ответ может быть неверен. Есть настраиваемая вероятность ложноположительного: фильтр говорит «возможно» об элементе, который не добавляли.

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

Механизм: бит-массив и k хешей

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

Чтобы добавить элемент: хешируй его всеми k функциями для получения k позиций и установи эти k бит в 1.

Чтобы запросить элемент: хешируй его теми же k функциями и проверь эти k позиций. Если любая из них 0, элемент точно не добавляли → «точно отсутствует». Если все k равны 1, элемент «возможно есть» — но эти биты могли быть установлены в 1 другими элементами, случайно делящими эти позиции. Это совпадение и есть ложноположительный.

m-битный массив (m = 16, k = 3 здесь)

add "alice"  → хеши в биты 2, 7, 13   → установить
add "bob"    → хеши в биты 4, 7, 11   → установить
                                         (бит 7 теперь общий)

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

query "carol" → биты 2, 4, 13 → ВСЕ = 1 → «возможно есть»
                (но carol не добавляли — ЛОЖНОПОЛОЖИТЕЛЬНЫЙ,
                 её три позиции установлены alice/bob)
query "dave"  → биты 3, 8, 15 → бит 3 = 0 → «точно ОТСУТСТВУЕТ»

Поэтому нет ложноотрицательных: добавление элемента лишь устанавливает биты, никогда не сбрасывает, так что ранее добавленный элемент всегда находит все свои биты в 1. И поэтому ложноположительные есть: по мере добавления элементов больше бит переходит в 1, и в итоге k позиций несвязанного элемента могут все оказаться уже установленными.

Доля ложноположительных: размер, число и k

Вероятность ложноположительного — не фиксированное свойство, ты её настраиваешь. Она зависит от трёх чисел: m (бит в массиве), n (вставленных элементов) и k (числа хеш-функций). Интуиция: больше бит на элемент (m/n) — меньше коллизий и ниже доля ложноположительных; слишком мало или слишком много хеш-функций — обе вредят (слишком мало — каждый элемент плохо различает; слишком много — массив наполняется слишком быстро). Под целевую долю ложноположительных есть оптимальное k, и грубое инженерное правило: нужно порядка ~10 бит на элемент для ~1% ложноположительных — а добавление ~5 бит на элемент режет долю примерно ещё на порядок. Главное — выигрыш места: ~1,2 байта на элемент для стража множества против хранения полных ключей.

Жёсткое ограничение: фильтр надо размерить под число элементов, что вставишь. Продолжай добавлять за планируемое n — и бит-массив насыщается (слишком много единиц), доля ложноположительных лезет к 100%, и фильтр становится бесполезен — говорит «возможно» на всё. У простого фильтра Блума нет «просто увеличить»; ты перестраиваешь больший (или используешь масштабируемый вариант).

Где они отрабатывают своё

Фильтры Блума появляются везде, где ответ «точно-здесь-нет» позволяет пропустить дорогую операцию:

• Базы на LSM-деревьях (Log-Structured Merge-tree — структура, где записи сначала идут в память, а потом сбрасываются в неизменяемые файлы на диске; Cassandra, RocksDB, LevelDB, HBase) ставят фильтр Блума на каждый файл-таблицу на диске, чтобы чтение отсутствующего ключа пропускало сики диска для файлов, точно его не содержащих — история движка хранилища из вступления.
• Кэши используют фильтр, чтобы не запрашивать backing store для никогда не кэшированных ключей (и бороться с атаками пробивания кэша, долбящими БД известно-отсутствующими ключами).
• CDN и детекция «однохитовых»: CDN может использовать фильтр, чтобы не кэшировать контент, запрошенный лишь раз, сберегая место кэша под то, что вероятно запросят снова.
• Веб-краулеры проверяют «видел ли я уже этот URL?» по фильтру, а не по гигантскому множеству, принимая, что изредка пропустят новый URL (здесь ложноположительный — пропущенная страница, иногда приемлемо, иногда нет).

Cuckoo filter — более новая альтернатива, поддерживающая удаление и более экономичная по месту при низких долях ложноположительных, ценой более сложной вставки, которая может провалиться при слишком полной структуре. Counting и cuckoo — два варианта, к которым тянуться, когда кусает ограничение «нет удаления» простого фильтра.