Фильтр Блума

Вы делаете форму регистрации и не хотите разрешать пароли из утечек: 123456, qwerty, dragon и ещё десять тысяч таких же. Можно хранить весь список и искать в нём, но в Python множество из этих строк занимает почти мегабайт. А можно хранить 12,5 килобайта битов и отвечать так же быстро — ценой редкой и заранее известной ошибки. Ниже настоящий список десяти тысяч самых частых паролей, превращённый в фильтр прямо у вас в браузере. Попробуйте свои варианты.

Каждая оранжевая точка — бит, который зажёг какой-то пароль из утечки. Введите dragon: все его биты горят, и он правда в списке. Введите что-нибудь своё и длинное — скорее всего, хотя бы один бит окажется погашен, и фильтр ответит «точно нет». А иногда — примерно раз на сто проверок — все биты случайно окажутся зажжены чужими паролями. Это и есть ложное срабатывание.

Идея

Заведём массив из m битов и k хеш-функций. Чтобы добавить элемент, зажигаем k битов, на которые указывают его хеши. Чтобы проверить элемент, смотрим на те же k битов: если хоть один погашен — элемента точно нет; если горят все — он, возможно, есть.

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

Сам элемент фильтр не хранит, только следы от его хешей. Поэтому он и маленький: 10 000 паролей в среднем по 6,3 символа — это 73 килобайта текста, а фильтру с ошибкой около 1 % хватает 10 бит на пароль, то есть 12,5 килобайта на всё.

Откуда берутся ложные срабатывания

Посмотрим на крошечный фильтр: 64 бита, 3 хеша, пять слов внутри. Код из раздела ниже печатает для каждого проверяемого слова его три позиции:

dragon     maybe [30, 1, 36]
sunshine   no    [32, 39, 46]
Qwerty     maybe [25, 52, 15]
letmein    maybe [15, 52, 25]
bits set: 14 of 64

Qwerty с большой буквы в фильтр не добавляли — добавляли qwerty. Но его три бита 25, 52 и 15 — ровно те же, что у letmein, только в другом порядке. Фильтр не может отличить одно от другого и честно отвечает «возможно». В большом фильтре совпадение всех k битов с битами одного чужого слова почти невероятно; гораздо чаще биты проверяемого слова зажгли несколько разных слов, по одному-два бита каждое. Чем больше единиц в массиве, тем выше шанс, что все k окажутся единицами случайно.

Сколько будет ошибок

Пусть в фильтр добавили n элементов, и хеши разбрасывают биты равномерно. Один бит остаётся погашенным после одной вставки с вероятностью 1 − 1/m для каждого из k хешей, после всех вставок — с вероятностью

Ложное срабатывание — это когда все k битов нового элемента горят:

Формула показывает торг. Больше хешей — каждая проверка строже, но и массив быстрее забивается единицами. Минимум по k достигается при

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

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

Каждые 4,8 бита на элемент делают ошибку в десять раз реже. Это хорошее правило для прикидки: «один процент — около десяти бит на элемент, каждый следующий ноль после запятой — ещё пять».

Код

Где взять k независимых хеш-функций? Не нужно: в 2006 году Адам Кирш и Майкл Митценмахер показали, что хватит двух. Позиции h₁ + i·h₂ для i = 0, 1, …, k − 1 дают ту же асимптотическую ошибку, что и k настоящих хешей. Мы берём один 64-битный хеш FNV-1a и режем его на две половины. Младший бит h₂ принудительно ставим в единицу, чтобы шаг никогда не был нулевым.

Теперь настоящий список. Программа строит фильтр с разным числом битов на пароль, проверяет сто тысяч строк probe-0, probe-1, … — ни одной из них в списке нет — и считает, сколько из них фильтр принял за утёкшие. Python и Go печатают одно и то же до последней цифры: хеш у них общий.

Сколько это стоит

Вставка и проверка — по k вычислений позиции и обращений к массиву, то есть O(k), и от числа элементов это не зависит. Само вычисление хеша требует прохода по элементу, O(длина). Память — m битов, примерно 1,44·log₂(1/p) на элемент.

Для сравнения: хеш-таблица тоже отвечает за O(1), но хранит сами элементы. На наших паролях это 997 570 байт в Python против 12 501 у фильтра с ошибкой около 1 %: в 80 раз меньше. Это и есть цена ответа «возможно» вместо «да».

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

Чего фильтр не умеет

• Удалять. Погасить бит нельзя: его могли зажечь и другие элементы. Если удаление нужно, вместо битов хранят маленькие счётчики (считающий фильтр Блума) или берут кукушкин фильтр, который хранит короткие отпечатки и умеет удалять.
• Расти. Фильтр рассчитывают на n элементов. Если положить вдвое больше, ошибка вырастет не вдвое, а гораздо сильнее: фильтр на 10 бит и 7 хешей, получивший 5 бит на элемент, ошибается уже примерно в 14 % случаев вместо 1 %. Поэтому растущие наборы делят на несколько фильтров.
• Перечислять. Из битов нельзя восстановить, что внутри. Это бывает плюсом: список паролей нельзя достать из фильтра, хотя проверить любую строку по нему можно.

Где работает

Самое массовое применение — базы данных на LSM-деревьях, такие как RocksDB и Cassandra. Данные лежат на диске в неизменяемых файлах, и при поиске ключа пришлось бы открывать их все. У каждого файла есть маленький фильтр Блума в памяти, и файл, где ключа точно нет, даже не читают. Один погашенный бит экономит чтение с диска.

Похоже работают кэши в сетях доставки контента. Многие страницы запрашивают ровно один раз, и класть их в кэш — только вытеснять полезное. Поэтому страницу кэшируют со второго запроса, а помнит первые запросы фильтр Блума — дёшево, хоть и с маленькой ошибкой.

История

Бёртон Блум описал структуру в 1970 году в статье «Space/Time Trade-offs in Hash Coding with Allowable Errors». Его пример был про перенос слов: программа расстановки переносов справлялась простыми правилами с большинством слов, а для небольшой доли исключений нужен был словарь на диске. Фильтр в памяти отвечал, может ли слово быть исключением, и почти все слова обходились без обращения к диску. Ровно та же схема, что спустя полвека работает в базах данных: дешёвое «точно нет» перед дорогой проверкой.

Задачи

В первой задаче нужно рассчитать фильтр по формулам из статьи. Во второй — собрать его и отличить ложные срабатывания от настоящих.