Інтерактивний посібник

Фільтр Блума: «точно ні» або «можливо так» за кілька біт

Фільтр Блума — компактна структура даних, яка відповідає на одне питання: «чи є цей елемент у множині?». Вона не зберігає самі елементи, лише масив бітів, тому займає в десятки разів менше пам’яті, ніж звичайний список. Плата за це — інколи вона помилково каже «так». Але ніколи не каже «ні» про те, що ви справді додали.

Бартон Блум, 1970 ≈ 9,6 біта на елемент при 1% помилок без хибних «ні» O(k) на операцію не залежить від довжини ключа

Уявіть табло з рядом лампочок і кілька «ворожок», які за будь-яким словом незмінно називають номер лампочки.

bit array, mТабло з лампочками

m лампочок, на старті всі вимкнені. Більше нічого фільтр не зберігає: ні слів, ні ключів, ні лічильників.

hash functions, kk ворожок

Кожна ворожка за словом називає свій номер лампочки. Для того самого слова — завжди той самий номер.

add(x)Додати = увімкнути

Питаємо всіх k ворожок і вмикаємо названі лампочки. Якщо котрась уже горить — так і лишається.

contains(x)Перевірити = подивитися

Хоч одна з k лампочок темна — слова точно не додавали. Усі горять — мабуть, додавали. Або їх запалили інші слова: це і є хибне «так».

Проблема

Дешево відсіяти «ні», перш ніж платити за дорогу перевірку

Найчастіше фільтр Блума стоїть перед чимось повільним: диском, мережею, базою. Якщо більшість запитів — про те, чого немає, фільтр відповідає на них з пам’яті за десятки наносекунд.

Приклад: база даних шукає ключ, якого немає, у 5 файлах на диску
Без фільтра
GET user:777→файл 1: дискфайл 2: дискфайл 3: дискфайл 4: дискфайл 5: диск
5 читань з диска
З фільтром на кожен файл
GET user:777→ф1: ніф2: ніф3: ніф4: ніф5: ні
0 читань з диска
Рідкий випадок
GET user:778→ф1: ніф2: ніф3: «можливо» → диск → немаєф4: ніф5: ні
1 зайве читання

Читання з SSD — порядку 100 мкс, перевірка фільтра в пам’яті — порядку 100 нс. При 1% хибних «так» з п’яти файлів зайве читання трапляється приблизно в одному запиті з двадцяти.

Що він дає

Відповідь «точно немає» без звернення до джерела. Пам’ять — кілька біт на елемент, незалежно від того, чи елемент — це 8-байтовий id чи 2-кілобайтний URL.

Чим платите

Частка хибних «так», яку ви обираєте заздалегідь: 1%, 0,1%… Що менша частка, то більше біт. І звичайний фільтр не вміє видаляти елементи.

Головне правило

«Ні» — остаточна відповідь. «Так» — лише привід перевірити в джерелі, якщо помилка неприпустима.

Лабораторія

Додайте слова й зловіть хибне «так»

Маленький фільтр на 16–64 біти, щоб усе було видно. Додавайте слова, перевіряйте інші. Під кожним бітом його номер; кольорові мітки h1…h5 показують, яка хеш-функція вказала на біт.

Бітів, m
Хеш-функцій, k
Різновид

Зміна m, k чи різновиду очищає фільтр.

Швидко:

Почніть з «додати 5 тварин»

Потім перевірте слово, якого не додавали, наприклад «вовк». Або натисніть «знайти хибне «так»» — лабораторія сама перебере слова, поки фільтр не помилиться.

Додані (клік — перевірити)
Журнал
Чому так

Хибне «так» буває, хибне «ні» — ніколи. Поки не почнете видаляти

гарантія Немає хибних «ні»

Додавання тільки вмикає біти і ніколи не вимикає. Тож біти доданого слова горять назавжди, і перевірка його обов’язково знайде.

ціна Хибні «так» бувають

Біти спільні для всіх слів. Коли увімкнено багато, у нового слова всі k позицій можуть випадково виявитися зайнятими чужими словами.

пастка Видалення ламає фільтр

Вимкнути біти слова не можна: ними можуть користуватися інші слова. Спробуйте в лабораторії «Видалити» у звичайному режимі — і побачите, як інше слово отримує «точно ні», хоча його додавали.

Лічильний фільтр (counting Bloom filter) розв’язує це: замість біта в кожній комірці лічильник, зазвичай 4-бітний. Додавання збільшує k лічильників, видалення зменшує. Перемкніть лабораторію на «Лічильний», щоб спробувати. Ціна — у 4 рази більше пам’яті і нова пастка: якщо «видалити» те, чого не додавали, але фільтр помилково вважав присутнім, зменшаться чужі лічильники.

Математика

Три числа визначають усе: m, n і k

m — скільки бітів, n — скільки елементів додали, k — скільки хеш-функцій. З них виходить частка хибних «так» p.

Імовірність хибного «так»p ≈ (1 − e−kn/m)k

У дужках — частка увімкнених бітів. Хибне «так» — коли всі k випадкових позицій влучили в увімкнені.

Найкраще kk = (m / n) · ln 2

Тоді рівно половина бітів увімкнена. Менше k — мало перевірок, більше — фільтр швидко заповнюється.

Скільки бітів на pm = −n · ln p / (ln 2)²

Тобто ≈ 1,44 · log₂(1/p) біта на елемент: 1% → 9,6 біта, 0,1% → 14,4 біта.

Стрес-тест: справжній фільтр, справжні вимірюваннядодаємо n ключів, перевіряємо 20 000 інших
теоріявиміряно на 20 000 ключахоптимальне k

Практика

Скільки пам’яті потрібно саме вам

Задайте, скільки елементів очікуєте і яку частку хибних «так» готові терпіти. Калькулятор порахує m і k і порівняє з хеш-множиною, що зберігає самі ключі.

Хеш-множина оцінена як ключ плюс ≈ 48 байт накладних витрат на запис (покажчики, заголовок об’єкта, порожні слоти). У конкретній мові буде інакше, але порядок той самий.

pБіт на елементОптимальне k1 млн елементів1 млрд елементів
Юзкейси

Фільтр Блума працює у ваших інструментах щодня

Бази на LSM-деревах

диск

Cassandra, RocksDB, LevelDB, HBase, ScyllaDB тримають фільтр для кожного файлу на диску (SSTable). Читання ключа спершу питає фільтри і відкриває лише файли з відповіддю «можливо». У Cassandra частку помилок задає параметр таблиці bloom_filter_fp_chance.

GET key→фільтри SSTable→1 файл з диска
Найкласичніший юзкейс.

Кеш у CDN: «диво одного разу»

мережа

Akamai описували, що близько трьох чвертей об’єктів запитують лише раз. Щоб не засмічувати ними диск кешу, об’єкт кешують лише при другому запиті: перший запит тільки записує URL у фільтр Блума.

URL→бачили раніше?→так: в кеш
Хибне «так» — просто один зайвий об’єкт у кеші.

Колонкові формати й join-и

аналітика

Parquet і ORC зберігають фільтри для колонок, тож Spark чи Trino пропускають цілі блоки файлу. Runtime-фільтри в Spark, Trino, Impala будують фільтр із ключів малої таблиці join-у і відкидають рядки великої ще під час читання.

WHERE id = 42→фільтр row group→пропустити блок
Менше I/O і менше даних у shuffle.

Redis як спільний фільтр

сервіси

Модуль RedisBloom (у Redis Stack і Redis 8) дає команди BF.ADD та BF.EXISTS. Типово: «чи зайнятий логін», «чи бачили цей email у розсилці», «чи вже показували користувачу цю статтю».

логін→BF.EXISTS→«можливо» → SELECT у БД
Фільтр знімає навантаження з бази, але не замінює її.

Веб-краулери і дедуплікація

потоки

Краулер, що обходить мільярди сторінок, має пам’ятати, які URL уже відвідав. Множина рядків не влізе в пам’ять, а фільтр на 1 млрд URL при 1% — це ≈ 1,1 ГБ. Хибне «так» означає лише пропущену сторінку.

новий URL→бачили?→ні: в чергу
Так само дедуплікують події в потоках.

Безпека і легкі клієнти

з застереженнями

Ранні версії Google Safe Browsing у Chrome тримали фільтр небезпечних адрес локально і ходили на сервер лише при збігу. Легкі гаманці Bitcoin (BIP 37) надсилали вузлу фільтр своїх адрес. Обидва згодом замінили: фільтр виявився не таким приватним, як здавалося.

URL→локальний фільтр→збіг: спитати сервер
Фільтр — не шифрування: він розкриває багато про вміст.
Вибір

Фільтр Блума, cuckoo, xor чи звичайна множина?

Чотири питання — і рекомендація, що взяти.

Чи допустиме інколи хибне «так»?
Що потрібно знати про елемент?
Чи треба видаляти елементи?
Як змінюється множина?
СтруктураБіт на елемент при 1%ВидаленняДоповненняКоли брати
Bloom≈ 9,6нітакУніверсальний вибір, є в кожній мові та базі.
Counting Bloom≈ 38 (4-біт. лічильники)тактакТреба видаляти, а пам’ять не критична.
Scalable Bloomтрохи більше за Bloomнітак, без межРозмір наперед невідомий: додає нові шари, що ростуть.
Cuckoo filter≈ 9–10тактак, до заповненняВидалення; при p нижче ~3% ще й компактніший за Bloom.
Xor / binary fuse≈ 8–9ніні, лише перебудоваНабір відомий заздалегідь: файли, релізи, статичні списки.
Blocked Bloomтрохи більше за BloomнітакМаксимальна швидкість: усі k біт в одному кеш-рядку CPU.
Хеш-множина8 × (ключ + накладні)тактакПомилки неприпустимі або елементів мало.
Як написати і як узяти готове

Тридцять рядків власноруч або одна бібліотека

Своя реалізація корисна, щоб зрозуміти. У продакшні беріть готову: там уже є серіалізація, правильні хеші і перевірені параметри.

import hashlib, math

class BloomFilter:
    def __init__(self, n, p):
        self.m = math.ceil(-n * math.log(p) / math.log(2) ** 2)  # бітів
        self.k = max(1, round(self.m / n * math.log(2)))       # хеш-функцій
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        # Подвійне хешування: два хеші дають k позицій
        d = hashlib.sha256(item.encode()).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:16], "little") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

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

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


seen = BloomFilter(n=1_000_000, p=0.01)  # ≈ 1,14 МБ, k = 7
seen.add("https://example.com/a")
"https://example.com/a" in seen   # True — завжди
"https://example.com/b" in seen   # False, або True з імовірністю ≈ 1%
Для інженерів

Подвійне хешування, об’єднання і підводні камені

Рахувати k незалежних криптографічних хешів дорого. Кірш і Міценмахер (2006) показали, що досить двох: позиції gᵢ(x) = h₁(x) + i · h₂(x) mod m для i = 0…k−1 дають ту саму асимптотичну частку помилок. Так роблять майже всі бібліотеки, і так влаштована лабораторія на цій сторінці.

Дві деталі: h₂ варто робити непарним (або взаємно простим з m), інакше при m = 2ᵗ позиції почнуть повторюватися. І хеш має бути якісним: слабкий хеш на схожих ключах (user:1, user:2…) скупчує позиції, і реальна p виявляється в рази гіршою за формулу.

// Те, що робить лабораторія вище
const [h1, h2] = twoHashes(word);         // FNV-1a + перемішування, два різні seed
for (let i = 0; i < k; i++) positions.push((h1 + i * (h2 | 1)) % m);
Тест

Перевір себе

Вісім питань від базових до інженерних. Відповідь і пояснення з’являються одразу.

Терміни

Короткий словник

Bloom filter
Імовірнісна структура для перевірки належності до множини: «точно ні» або «можливо так».
m
Розмір бітового масиву фільтра.
n
Кількість доданих елементів.
k
Кількість хеш-функцій, тобто бітів, які вмикає і перевіряє кожен елемент.
False positive
Хибне «так»: фільтр каже «можливо є», а елемента не додавали.
False negative
Хибне «ні». У звичайному фільтрі Блума його не буває, якщо нічого не видаляти.
FPR, p
Частка хибних «так» серед перевірок елементів, яких немає.
Double hashing
Отримання k позицій з двох хешів: h₁ + i·h₂.
Counting Bloom filter
Лічильники замість бітів, тому підтримує видалення.
Scalable Bloom filter
Ланцюжок фільтрів, що ростуть, для невідомого наперед n.
Cuckoo filter
Зберігає короткі відбитки ключів у хеш-таблиці; підтримує видалення.
Xor / binary fuse filter
Статичні фільтри: компактніші за Bloom, але будуються раз із готового набору.
SSTable / LSM
Незмінні відсортовані файли в базах на LSM-деревах; кожен має свій фільтр.
Count-Min sketch
Родич фільтра Блума для наближеного підрахунку частот.
HyperLogLog
Структура для наближеного підрахунку кількості різних елементів.