Что такое фильтр Блума и где он применяется?

Устройство. Массив из m бит, изначально нули, и k независимых хеш-функций, каждая даёт позицию в массиве.

• добавить x — вычислить k позиций и выставить эти биты в 1;
• проверить x — если хоть один из k бит равен 0, x точно не добавляли; если все 1 — возможно, добавляли (или биты выставили другие элементы).

Вероятность ложного срабатывания после n вставок: p ≈ (1 − e^(−kn/m))^k. Оптимальное k = (m/n) · ln 2. На практике:

• 10 бит на элемент, k = 7 → около 1%;
• 15 бит → около 0,1%;
• каждые ~4,8 бита на элемент уменьшают p в 10 раз.

Миллион элементов при 1% — около 1,2 МБ, сколько бы ни весили сами элементы (URL, адреса, ключи).

Применения — везде, где проверка «нет» дешевле дорогого поиска:

• LSM-хранилища (RocksDB, Cassandra, HBase) — фильтр у каждого SSTable: при чтении ключа пропускаем файлы, где его точно нет;
• перед кэшем и базой — отсечь запросы к несуществующим ключам (защита от перебора id и cache penetration);
• CDN — кэшировать объект только при втором запросе (Akamai: фильтр «уже видели один раз»), не засоряя кэш одноразовыми;
• браузеры и антифишинг — локальная проверка URL по списку;
• распределённые JOIN — передать фильтр ключей вместо самих ключей;
• рекомендации и ленты — «уже показывали этому пользователю».

Ограничения:

• удаление невозможно — обнуление бита сломает другие элементы. Counting Bloom filter хранит счётчики вместо бит; cuckoo filter поддерживает удаление и компактнее при малых p;
• размер нужно знать заранее: при переполнении p растёт. Scalable Bloom filter добавляет новые слои;
• хеш-функции — быстрые некриптографические (MurmurHash, xxHash); k хешей получают из двух: h1 + i·h2.

В Redis — модуль RedisBloom (BF.ADD, BF.EXISTS), в Java — Guava BloomFilter.

import hashlib, math

class Bloom:
    def __init__(self, n, p=0.01):
        self.m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
        self.k = round(self.m / n * math.log(2))
        self.bits = bytearray((self.m + 7) // 8)

    def _pos(self, item):
        d = hashlib.blake2b(item.encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(d[:8], "little"), int.from_bytes(d[8:], "little")
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for p in self._pos(item): self.bits[p // 8] |= 1 << (p % 8)

    def __contains__(self, item):
        return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._pos(item))