Bloom Filter: Вероятностное 'Может быть'

Цели урока

• Понять trade-off: память vs точность
• Освоить структуру: битовый массив + k хешей
• Реализовать add и contains
• Знать когда применять Bloom Filter

Предварительные знания

• Хеш-таблицы
• Битовые операции

• Хеш-таблицы

Каждый раз когда вы открываете страницу в Chrome, браузер проверяет URL в списке из миллионов вредоносных сайтов. Но этот список занимает всего пару мегабайт благодаря Bloom Filter.

• Google Chrome - Safe Browsing проверка URL
• Cassandra/HBase - избежание лишних чтений с диска
• Bitcoin SPV - проверка транзакций без полной ноды
• Akamai - 'one-hit-wonder' фильтр для CDN кеша

Бёртон Блум и компромисс пространство/время

Бёртон Говард Блум представил фильтр в статье 1970 года под названием «Space/Time Trade-offs in Hash Coding with Allowable Errors». Он изучал задачи вроде переноса слов, где программе нужно было решить, принадлежит ли слово большому словарю, а хранить полный набор слов было слишком дорого. Его идея состояла в том, что если допустить небольшую долю ложноположительных срабатываний, объём хранения можно резко сократить: держать только битовый массив, ставить k битов на элемент с помощью k хеш-функций и мириться с тем, что изредка несовместимые элементы совпадают по всем k битам. Отрицательный ответ всегда точен, ведь отсутствующий элемент оставил бы хотя бы один бит несброшенным. Именно эта асимметрия, «точно нет» против «возможно да», и делает структуру полезной в роли дешёвого предфильтра. Сегодня она охраняет чтения в Bigtable, Cassandra и HBase, обеспечивает проверки безопасного просмотра в Chrome и сокращает лишнюю работу в CDN.

Проблема: Быстрая проверка членства

**Задача:** проверять, есть ли элемент в огромном множестве (миллиарды элементов).

**Компромисс:** Bloom Filter жертвует 100% точностью ради огромной экономии памяти. Иногда говорит 'да' когда ответ 'нет', но НИКОГДА не скажет 'нет' когда ответ 'да'.

Идея: Битовый массив + несколько хешей

**Структура:** битовый массив размера m, изначально все 0. Используем k разных хеш-функций.

**Почему несколько хешей?** Один хеш даёт много коллизий. Несколько хешей: вероятность, что ВСЕ совпадут случайно, экспоненциально мала.

Операции: Add и Contains

**Нельзя удалять элементы!** Сброс бита может 'удалить' другие элементы, использующие этот же бит. Для удаления нужен Counting Bloom Filter.

Математика: Размер и вероятность ошибки

**Вероятность false positive:** p ≈ (1 - e^(-kn/m))^k

**Правило:** ~10 бит на элемент даёт ~1% false positive rate. 15 бит → 0.1%.

Где используется Bloom Filter

• **Chrome/Firefox** - проверка вредоносных URL (Safe Browsing)
• **Cassandra/HBase** - проверка 'есть ли ключ на диске?' перед I/O
• **Bitcoin** - SPV wallets для проверки транзакций
• **Medium** - 'уже читал эту статью?' (рекомендации)
• **Akamai CDN** - 'был ли этот запрос раньше?' (one-hit-wonder filter)

**Паттерн:** Bloom Filter как быстрый 'первый барьер'. Если 'нет' - экономим ресурсы. Если 'да' - делаем точную проверку.

Bloom Filter

• Битовый массив + k хеш-функций
• False negatives невозможны ('нет' = точно нет)
• False positives возможны ('да' = возможно да)
• ~10 бит/элемент → ~1% ошибок
• Удаление не поддерживается (без Counting BF)

Вероятностные структуры

Bloom Filter - часть семейства вероятностных структур. Другие: Count-Min Sketch (подсчёт частот), HyperLogLog (подсчёт уникальных).

• HyperLogLog — Другая вероятностная структура для подсчёта уникальных

Связанные уроки

• ds-06-hash-intro — Несколько хеш-функций устанавливают и проверяют биты массива
• ds-26-hyperloglog — Обе жертвуют точностью ради крошечной вероятностной памяти
• prob-01-intro — Вероятность ложного срабатывания - величина, которую надо оценить
• db-34-lsm — БД на LSM-деревьях используют фильтры Блума, чтобы избегать чтений с диска
• net-40-cdn — CDN используют фильтры Блума, чтобы дёшево отсекать промахи кэша
• crypto-19-hash-functions