Фильтр Блума для веб-разработчиков

На хабре уже немало рассказано про фильтр Блума. Напомню, что это структура данных, которая позволяет проверить принадлежность элемента ко множеству, не храня при этом сам элемент. Существует вероятность ложно-положительного ответа, но отрицательный ответ всегда достоверен. В фильтре с точностью 1% требуется всего лишь несколько бит на элемент.

Эта структура часто применяется для ограничения числа запросов к хранилищу данных, отсекая обращения за элементами, которых там заведомо нет. Кроме того, её можно применять для примерного подсчёта числа уникальных событий, пользователей, просмотров и т.д. Больше примеров интересных применений.

Однако есть трудности, которые могут сдерживать веб-разработчиков от применения фильтра Блума.

Хранение

Все экземпляры веб-приложения на всех серверах должны иметь доступ к некоторому общему набору данных с возможностью быстро поменять или проверить несколько битов в большом битовом векторе. Кроме этого, данные должны быть надёжно сохранены на диск.

Хэширование

Для того, чтобы на практике приблизиться к теоретическим рабочим параметрам фильтра Блума, нужно проделать аккуратную работу с хэшами от исходного элемента. Фильтр длиной m бит c k хэш-функций требует образовать от исходного элемента k независимых значений, равномерно распределённых от 0 до m-1.

Большинство реализаций, что я видел, в лучшем случае используют 32-битный murmurhash, добавляя для каждого очередного хэша соль, зависящую от номера этого хэша. Нет никаких доказательств, что такой подход не увеличивает асимптотическую вероятность ложного срабатывания.

Кроме того, если используется 32-битный хэш, это задаёт верхнюю границу размера фильтра в 512 мегабайт. Это не мало, но и не много, особенно если требуется очень низкий процент ложных срабатываний и/или внушительное количество элементов в фильтре.

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

1. Резать на равные части вывод одной достаточно широкой функции. При этом функция должна иметь параметрическую ширину вывода в битах, чтобы не приходилось отбрасывать полезные биты.
2. Иметь только две независимые хэш-функции переменной ширины h₁ и h₂ и образовывать производные функции g_i по формуле h₁ + i * h₂ (по модулю числа значений функций). Об этом методе я узнал недавно отсюда.

Производительность

Чтобы эта конструкция находила применение в сдерживании запросов к хранилищу, она должна отвечать как минимум на порядок быстрее, чем оберегаемое хранилище.

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

Предлагаемое решение

Я хочу предложить вам решение, которое позволяет удобно интегрировать фильтры Блума в инфраструктуру вашего веб-приложения.

Это сервер-контейнер, который хранит фильтр Блума в оперативной памяти и на диске. Доступ к операциям над фильтром предоставлен через HTTP.

Персистентность хранения обеспечивается снапшотами, не блокирующими работу демона. Снапшот записывается во временный файл с нетривиальным именем и замещает старый только после окончания записи. Сохранение набора данных происходит по таймеру, при завершении работы сервера и при получении процессом сигнала USR1.

Алгоритм образования хэшей — нарезка хэша MD6 длиною k*w бит на k ключей по w бит. Число раундов MD6 — стандартное.

HTTP-интерфейс был выбран для простоты интеграции на стороне разработчиков: большинство платформ разработки имеют развитый инструментарий для осуществления синхронных, асинхронных и параллельных (curl-multi) HTTP-запросов. Несмотря на простоту интерфейса, он перенял все достоинства стандарта HTTP, и допускает конвейеризацию запросов в рамках одного соединения.

Предлагаемое мною приложение прошло длительное тестирование на production-системах и может быть рассмотрено как стабильное.

Сервер написан на C с использованием libevent2. На процессоре Intel® Pentium® CPU G4400 @ 3.30GHz приложение показывает в Apache Benchmark ~35000 RPS на проверке и добавлении элементов длиной 300 байт.

Поддерживаемые и оттестированные платформы:

• GNU/Linux (различные версии и дистрибутивы)
• FreeBSD 8, 9, 10
• Mac OS X 10.11
• Solaris 11

Примеры

Запуск демона с параметрами по умолчанию (1 Гбайт, 10 ключей — для 500,000,000 элементов с вероятностью ложно-положительных 0,1%):

$ bloom habrahabr.snap
Creating space ...
Initializing new file storage...
Saving snapshot...
Initial snapshot written.

Проверяем элемент:

$ curl http://localhost:8889/check?e=Hello%20Habr%21
MISSING

Добавляем элемент:

$ curl http://localhost:8889/add?e=Hello%20Habr%21
ADDED

Проверяем снова:

$ curl http://localhost:8889/check?e=Hello%20Habr%21
PRESENT

Проверяем наличие и добавляем одним запросом:

$ curl http://localhost:8889/checkthenadd?e=unexistent
MISSING
$ curl http://localhost:8889/checkthenadd?e=unexistent
PRESENT

Альтернативные решения

Существуют библиотеки, которые работают на стороне приложения и содержат общие данные в Redis. Они манипулируют битами в битовых картах Redis командами SETBIT и GETBIT.

В сравнении, их плюсы:

• Подсчёт хэша происходит на стороне веб-приложения, и это не загружает сервер вычислительной работой. Раз на раз не приходится, в некоторых случаях они считают хэш хранимой процедурой на Lua.
• Используют Redis, который многим хорошо знаком, обладает богатым набором функций, возможностью скриптинга и кластеризации.

Минусы:

• Redis ограничивает длину битового поля в 512 мегабайт. Все реализации, которые я смог найти (1, 2) рассчитаны на использование только одного ключа Redis. Это ограничивает размер фильтра.
• На данный момент эти библиотеки есть не для всех языков и платформ разработки.
• Эти решения не подходят для мультиязыковых проектов: каждая реализация хэширует по-своему и такие фильтры между собой несовместимы.
• Производительность. Такие решения используют две стратегии для работы с редисом: или устанавливают биты для каждого ключа через конвейер (pipeline), или вызывают хранимую процедуру на Lua в редисе, которая считает хэш и отдаёт команды. В первом случае, даже при скорости Redis в 200,000 операций в секунду, такие решения уже начинают проигрывать на фильтрах с количеством ключей от шести и больше, так как каждый бит — это отдельная операция. Во втором случае всё то же самое, но вдобавок ещё будет потрачено время на запуск скрипта и при проверке и добавлении хэш будет считаться дважды. Однако, ситуация может улучшиться с введением команды BITFIELD в Redis 3.2.0, который вышел в мае 2016го года. Эта команда позволяет производить несколько операций над битами в одной команде.

Автор: YourChief

Источник