Bloom Filters

Зачем

Когда нужно ответить на вопрос «видели ли мы этот элемент?» для миллиардов значений, классический HashSet хранит ключи целиком и съедает десятки гигабайтов RAM. Bloom filter решает ту же задачу за ~10 bits на элемент — порядка на полтора-два меньше — ценой допустимых false positives. False negatives при этом исключены: если фильтр сказал «нет», то элемент гарантированно не вставлялся.

Это даёт killer-pattern, который везде называется одинаково — skip expensive lookup:

• LSM-tree storage (BigTable, Cassandra, HBase, RocksDB, LevelDB) — Bloom filter лежит рядом с каждой SSTable. На read 99 SSTables из 100 не содержат ключа; bloom за 100ns отсеивает их и экономит дорогой disk seek (~150μs на NVMe, ~10ms на HDD).
• Web crawler — «уже краулили этот URL?» Bloom за 100ns даёт ответ без обращения к Postgres с миллиардами строк.
• Cache prefetch — «есть ли ключ в Redis?» Если bloom говорит NO → не делаем сетевой round-trip.
• Spell checker / safe browsing — слово в словаре? URL в малварной базе? Chrome держит multi-megabyte Bloom вместо 50MB raw list.

Главный сигнал, что Bloom — правильный инструмент: запросов «вероятно miss» на порядок больше, чем «вероятно hit», и каждый ложный поход за реальным ответом стоит дорого.

Mental model

Bloom filter = m-битный массив + k хеш-функций. Insert ставит k бит в единицу; lookup проверяет те же k бит. Все единицы — «возможно есть» (с FPR ε). Хоть один ноль — «точно нет» (с гарантией). Delete не поддерживается: бит может быть выставлен несколькими ключами сразу.

Ключевые свойства, которые отличают Bloom от обычного HashSet:

1. Памяти ~10 bits/element для ε=1% — не зависит от размера ключа. URL длиной 200 байт и uuid v4 займут одинаково.
2. No false negatives — если bloom сказал NO, можно скипать дорогую операцию без риска потерять данные.
3. False positives неизбежны — fingerprints коллидируют. Это фича, а не баг: мы заранее согласились платить ε% лишних seeks за остальные (100-ε)% сэкономленных.
4. Размер фиксирован при создании — нельзя дорастить, нужно создать новый и перевставить. Для эластичности — Scalable Bloom Filter.
5. Из фильтра нельзя достать обратно элементы — это hash, не индекс. Bloom отвечает только на yes/no.

Формулы, которые стоит держать в голове:

Optimal k       = (m/n) × ln 2
FPR ≈ (1 - e^(-kn/m))^k

Bits per element для целевого ε:
  ε = 10%   →  ~5 bits,  k=3
  ε = 1%    → ~10 bits,  k=7   ← industry default
  ε = 0.1%  → ~15 bits,  k=10
  ε = 0.01% → ~20 bits,  k=13

1 миллиард URLs с FPR 1% → ~1.2 GB Bloom (vs ~30 GB HashSet с overhead на pointers и string headers).

Что показывает диаграмма

На канвасе — упрощённая LSM-tree read path: клиент бьётся в app (query engine), у app в RAM лежит Bloom filter (1MB, k=7), а на диске — три SSTables. Edges с подписанной стоимостью: bloom check ~100ns, disk seek ~150μs — три порядка разницы, ради которых вся конструкция и затевается.

Скрипт намеренно держит bloom рядом с app (in-memory RAM-сосед) и отделяет storage в свою группу (disk). Это визуально подчёркивает, что bloom не заменяет базу — он стоит перед ней как cheap gate.

Сценарии

▶Walkthrough: positive-hit-fast (not found)

Happy path: ключ реально есть в SSTable-2. Bloom правильно говорит «вероятно есть», app делает один disk seek в нужную SSTable, возвращает значение. Обратите внимание: bloom не указывает в какой SSTable искать — он только подтверждает, что «искать имеет смысл». Поиск конкретной SSTable идёт по другим индексам (например, time range или sparse index).

▶Walkthrough: negative-skip-disk (not found)

Главный win Bloom filter. Клиент запрашивает ключ, которого нигде нет. Bloom видит хотя бы один ноль среди 7 битов — гарантированно возвращает NO. App не делает ни одного disk seek и отвечает клиенту через 100ns. Именно этот сценарий случается в LSM 70-99% времени (большинство ключей есть только в одной из десятков SSTables; для остальных bloom отсеет seek).

▶Walkthrough: false-positive-cost (not found)

Цена за компактность. Биты от других ключей случайно сложились так, что все 7 позиций нашего «фантомного» ключа оказались выставлены. Bloom говорит «вероятно есть» → app честно проходит все три SSTable → ловит MISS во всех → возвращает NOT FOUND. Потратили 3 лишних seek (~450μs). Это и есть тот самый 1% FPR: на 100 запросов один такой выстрел вхолостую — приемлемая цена за 99 сэкономленных seek по 150μs каждый.

▶Walkthrough: tuning-fpr (not found)

Где крутить ручки. Формула FPR ≈ (1 - e^(-kn/m))^k диктует tradeoff: больше m/n (бит на элемент) → меньше FPR, но больше памяти; k = (m/n) × ln 2 — оптимальное число хешей. RocksDB по умолчанию даёт 10 bits/key и k=7 (FPR ≈1%). Для критичных hot paths (где даже 1% лишних seek дорог) поднимают до 20 bits/key и FPR ≈0.01%. Для cold-path аналитики где seek не критичен — наоборот, можно ужать до 5 bits/key и FPR 10%.

▶Walkthrough: real-uses (not found)

Один и тот же паттерн в разных доменах. BigTable, Cassandra, HBase, RocksDB — bloom per SSTable, отсев read-miss до диска. Chrome Safe Browsing — 1MB локального bloom вместо 50MB raw URL list, далее запрос в Google API только при positive. Akamai в начале 2000-х сэкономил ~10% origin traffic, ставя bloom на edge перед cache miss. Ethereum пишет bloom в каждый блок для дешёвой фильтрации event logs. Bitcoin SPV-клиенты (BIP 37) отправляют свой bloom фул-ноду, чтобы получать только relevant транзакции, не выкачивая весь блокчейн.

Trade-offs (ADR развёрнуто)

ADR на ноде app фиксирует ключевое решение: trade space + accuracy на скорость. Распакуем компоненты:

Контекст. Read на LSM-tree — это потенциально N disk seek (по одному на каждую SSTable от newest к oldest, пока не найдём). При compaction-уровне 100 SSTables и cold cache это 100×150μs = 15ms на NVMe или секунды на HDD. Большинство read-запросов в LSM — negative read (ключа нет вообще или есть только в одной SSTable), значит почти все seek впустую. HashSet альтернатива (держать множество всех ключей в RAM) на 1B URLs стоит ~30 GB — нерентабельно даже на инстансах с 256 GB.

Решение. Перед каждой SSTable держим Bloom filter в RAM. m/n = 10, k = 7, FPR ≈1%. Lookup — 7 хеш-вычислений + 7 случайных bit reads ~100ns. Insert при memtable flush в SSTable — одноразовая операция, амортизируется на тысячи последующих reads.

Что получаем:

• 100× throughput на negative reads. 99 SSTables из 100 отсекаются за 100ns каждая вместо disk seek.
• 1.2 GB RAM на 1B keys — в 25× меньше HashSet. Это уже помещается в RAM современного сервера.
• Embedded в SSTable формат — bloom сериализуется и mmap'ится вместе с данными, нет отдельной инфраструктуры.

Что платим:

• 1% false positives — лишний disk seek в одном проценте случаев. Для LSM это терпимо: тот же seek был бы и без bloom, плюс лишь редкий промах.
• No delete — для классического Bloom; нужен Counting Bloom (×4 памяти) или Cuckoo Filter (другая структура целиком).
• No resize — фиксированный размер; для эластичных workload — Scalable Bloom Filter (последовательность фильтров с возрастающим m).
• Cold-start cost — на первой записи в свежий SSTable bloom ещё пуст, FPR временно высок. На практике пренебрежимо.
• Параметры заранее — нужно угадать n (ожидаемое число элементов) при создании. Промах в 2× раздувает FPR в разы.

Альтернативы, которые рассматривались:

Структура	Bits/key для ε=1%	Delete	Resize	Note
HashSet	~200+	yes	yes	Памяти на 1-2 порядка больше
Bloom	10	no	no	Indust default
Counting Bloom	40	yes	no	4× памяти за delete
Cuckoo Filter	~7	yes	yes	Меньше bloom, сложнее код
Quotient Filter	~10	yes	yes	Merge-friendly, RocksDB opt
Xor Filter	~9	no	no	Быстрее lookup, но build дороже

Для LSM-tree победил Bloom: deletion не нужна (SSTable immutable, удаление через compaction), resize не нужна (размер SSTable известен на flush), а memory budget и lookup latency — критичны.

Реальные системы

• Google BigTable — Bloom per SSTable, описано в Bigtable paper (OSDI 2006). Канонический референс паттерна.
• Apache Cassandra — Bloom per SSTable; ручка bloom_filter_fp_chance per-table (default 0.01 для STCS, 0.1 для LCS — на levelled compaction false positive дешевле, поэтому FPR можно поднять).
• HBase — то же, плюс отдельный row-level и row+col-level bloom.
• RocksDB / LevelDB — bits_per_key = 10 по умолчанию; bloom встроен в SST формат. Recent: full filter + partitioned filter для уменьшения memory pressure.
• Apache Kafka — log compaction использует bloom для дедупликации tombstones.
• Akamai — early 2000-х: bloom на edge для cache-miss prediction перед origin lookup. ~10% origin traffic экономия.
• Chrome Safe Browsing — клиентский bloom для known-malicious URLs; positive → запрос в Google API, negative → молча пускаем дальше.
• Bitcoin SPV (BIP 37) — клиент отправляет свой bloom фул-ноде, та фильтрует irrelevant транзакции из каждого блока. Spoiler: оказался privacy-проблемой (фильтр выдаёт adversary паттерн интересов).
• Ethereum — каждый блок содержит 2048-bit bloom filter для logs; clients быстро ищут блоки с relevant events без full scan.
• Squid HTTP cache — bloom для cache digest, чтобы proxy peers обменивались знаниями «что у меня закешировано».
• Medium / Quora — feed dedup: «эту статью уже показывали этому юзеру?».
• Redis (RedisBloom module) — BF.RESERVE, BF.ADD, BF.EXISTS + Scalable Bloom встроены.

Anti-patterns

• Bloom для exact-answer workload. В finance, инвентаре, бронировании — 1% false positives означает 1% ошибочных списаний. Используйте HashSet, B-tree, или Cuckoo (deletion нужна).
• Слишком маленький m относительно n. Если по факту вставили 10× больше элементов, FPR взлетает к 30-50% — bloom становится бесполезен. Мониторьте fill rate.
• Слишком большой k (например, k=20 «на всякий случай»). Каждый lookup делает 20 hash + 20 bit reads — медленнее, чем небольшой HashSet. Оптимум k = (m/n) × ln 2.
• Bloom поверх small set (<10K elements). Overhead конструкции, hash вычислений и cache misses не оправдан — HashSet выиграет и по памяти, и по скорости.
• Плохой выбор hash function. CRC32, FNV1a кластеризуют биты, реальный FPR может быть в разы выше теоретического. MurmurHash3, xxHash, CityHash — проверенный выбор.
• k независимых хешей вместо double hashing. k вызовов хеша на каждый lookup — дорого. На практике делают h_i(x) = h_a(x) + i × h_b(x) mod m — два хеша вместо k, разница в FPR пренебрежима.
• bloom_filter_fp_chance = 0 в Cassandra. Это выключает bloom (FPR 100%, всегда seek), а не делает его идеальным. Частая ошибка.
• Bloom в DB как BLOB с lookup'ами через query. SQL round-trip на каждый probe убивает весь смысл. Bloom должен жить в RAM процесса, который его проверяет.
• Игнор adversarial inputs. Если злоумышленник знает hash seeds, может конструировать ключи с гарантированным positive — DoS через false positive flood. Защита: keyed hash (SipHash) или Cuckoo с random seeds.
• Reset/resize в hot path. Resize классического Bloom = создать новый + перевставить все элементы (которые мы уже не помним!). Нужна Scalable Bloom или внешний полный set.

Когда НЕ использовать

Bloom — не серебряная пуля. Не берите его, если:

• Нужна гарантированная точность. Например, проверка уникальности username при регистрации. Используйте unique constraint в БД.
• Workload требует delete. Counting Bloom (×4 памяти, риск counter overflow) или Cuckoo Filter (другая структура целиком) подойдут лучше.
• Размер множества заранее неизвестен и сильно меняется. Scalable Bloom Filter решает, но lookup становится O(filters_count) вместо O(1). Если эластичность критична — Cuckoo или Quotient Filter.
• Нужен payload, а не yes/no. Bloomier Filter существует, но возвращает garbage value при false positive. Чаще нужен Hash Map с лучшей упаковкой.
• Set маленький. Меньше ~10K элементов — HashSet всегда дешевле и проще.
• Hot path даёт mostly-positive ответы. Если 99% запросов реально найдены, bloom только добавляет latency перед disk seek. Win bloom — на mostly-negative нагрузке.
• Безопасность критична. Раскрытие bloom (как в BIP 37) даёт adversary паттерн интересов. Для приватных множеств — privacy-preserving альтернативы (Private Set Intersection).

Дальше читать

Оригинальные статьи:

• Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors (1970) — оригинал, ACM DL.
• Broder & Mitzenmacher, Network Applications of Bloom Filters: A Survey (2002) — must-read обзор паттернов.
• Fan, Andersen et al., Cuckoo Filter: Practically Better Than Bloom (2014) — современная альтернатива с delete.
• Almeida et al., Scalable Bloom Filters (2007) — для динамических множеств.
• Putze et al., Cache-, Hash- and Space-Efficient Bloom Filters (2007) — blocked bloom для cache locality.

Production docs:

• Bigtable paper (OSDI 2006) — каноничный LSM + bloom.
• RocksDB Bloom Filter wiki — реальные tuning recipes.
• Cassandra operating docs — bloom_filter_fp_chance в production.
• RedisBloom commands — managed API.

Связанные темы:

• [CONCEPT]caching-strategies — bloom как gate перед cache.
• Cuckoo filters — следующая ступень с deletion и resize.
• HyperLogLog, Count-Min Sketch — другие probabilistic data structures для cardinality и frequency.

Книги:

• Gakhov, Probabilistic Data Structures and Algorithms (2019), Ch. 2 — полный разбор вариантов.
• Leskovec et al., Mining of Massive Datasets — bloom в stream processing.

Интерактивные визуализации:

• https://llimllib.github.io/bloomfilter-tutorial/ — пошаговый туториал с anim.
• https://www.jasondavies.com/bloomfilter/ — играй с m, k, n руками.