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

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

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

Хранение

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

Хэширование

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

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

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

На мой взгляд, есть не очень много способов получить произвольное количество хэш-функций со значениями в нужном диапазоне, да так, чтобы они использовали только информационную энтропию исходного сообщения:
  1. Резать на равные части вывод одной достаточно широкой функции. При этом функция должна иметь параметрическую ширину вывода в битах, чтобы не приходилось отбрасывать полезные биты.
  2. Иметь только две независимые хэш-функции переменной ширины h1 и h2 и образовывать производные функции gi по формуле h1 + i * h2 (по модулю числа значений функций). Об этом методе я узнал недавно отсюда.


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

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

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

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


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

Это сервер-контейнер, который хранит фильтр Блума в оперативной памяти и на диске. Доступ к операциям над фильтром предоставлен через 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го года. Эта команда позволяет производить несколько операций над битами в одной команде.
Поделиться с друзьями
-->

Комментарии (11)


  1. mwizard
    06.07.2016 11:01
    #9688502
    +8

    Следующим шагом будут HaaS и AaaS — Hashmap-as-a-Service и Array-as-a-Service. С REST-интерфейсом, конечно же, куда ж без того.


    1. YourChief
      06.07.2016 11:07
      #9688510
      +4

      Redis расшифровывается как REmote DIctionary, например. Так что уже есть.


  1. SBKarr
    06.07.2016 11:23
    #9688524
    +1

    А сможете сделать возможность собирать только вычислительную часть (без сервера и сохранения на диск) в виде библиотеки? Тогда можно будет, например, интегрировать фильтр с nginx или своим серверным приложением.


    1. YourChief
      06.07.2016 13:46
      #9688844

      Да, все функции, связанные с фильтром Блума уже отделены.

      Можно просто добавить файлы bf_* и md6_* в директорию с исходниками модуля и заинкудить заголовочные файлы bf_*.h.

      Можно собрать полноценную библиотеку .so и далее пользоваться ею:

      $ gcc -shared -fPIC bf_*.c md6_*.c -o libbloom.so
$ cat > libtest.c
#include "bf_types.h"
#include "bf_ops.h"
#include <stdio.h>

void main() {
    if (bf_create(1,1))
        puts("OK");
}
<CTRL+D>
$ gcc -L. -o libtest libtest.c -lbloom
$ LD_LIBRARY_PATH=. ./libtest
OK


      В случае с nginx проблема только в том, что у каждого воркера своя память, поэтому придётся создавать структуру в мастер-процессе в общей для всех воркеров памяти: или IPC SHM, или mmap с флагом MAP_ANONYMOUS. Второй вариант может быть быстрее и гарантирует, что память будет освобождена при любом завершении процесса. Однако он не является частью стандарта POSIX. Первый вариант требует очистки, так как сегменты общей памяти IPC не связаны с конкретным процессом и продолжают существовать после его выхода. Судя по исходникам nginx и модулей, которые используют общую память, в nginx принят первый подход и есть внутреннее API для получения общей зоны.

      Для использования общей памяти между процессами придётся сделать версии bf_create() и bf_destroy(), использующие общую память.


  1. bak
    06.07.2016 16:25
    #9689250

    Redis ограничивает длину битового поля в 512 мегабайт. Все реализации, которые я смог найти (1, 2) рассчитаны на использование только одного ключа Redis. Это ограничивает размер фильтра.

    Почему бы просто не запатчить redis с целью поддержки более длинных битовых полей?
    На данный момент эти библиотеки есть не для всех языков и платформ разработки.

    Для redis есть http_api, например такое. Можно поставить его и написать процедуру на lua в которой будет вся логика.
    HTTP намного более громоздкий чем родной redis-а, соотвественно часть времени будет тратится на парсинг и формирования запросов.
    Ну и самое главное:
    1) В redis есть журнал операций — соотвественно если инстанс редиса прибить он восстановит из журнала все последние записи. В вашем случае могут потерятся записи за последние 300 секунд.
    2) В redis имеется репликация, если один инстанс ляжет — приложение может сходить в другой.
    Ну а так вроде всё норм, только ещё бы batch запросы добавить.


    1. YourChief
      06.07.2016 17:49
      #9689506

      Почему бы просто не запатчить redis с целью поддержки более длинных битовых полей?

      Эта работа ведётся с 2012го года. Там есть много ограничений, от формата хранения строк до сообщений между кластерами и хранением. Даже когда эта работа будет проделана, всё равно потребуется сделать на стороне хэшера ширину хэша больше 32 бит. Поэтому, раз уж всё равно подстраиваться, лучше использовать несколько ключей редиса.

      1) В redis есть журнал операций — соотвественно если инстанс редиса прибить он восстановит из журнала все последние записи. В вашем случае могут потерятся записи за последние 300 секунд.
      По умолчанию в Redis-е AOF выключен, но да — функция стоящая. В моём случае реализовать её довольно просто, не нужно даже точно помнить позицию, откуда проигрывать — есть только одна операция и она идемпотентная. Меня сдерживает от реализации только тот факт, что при постоянном большом наплыве добавляемых элементов и длительной просадке дисковой производительности возникнет ситуация, что или будет разрастаться буфер записи бинлога, или придётся задерживать операции добавления. Так можно получить SIGKILL от OOM Killer-а в ситуации, когда в общем-то можно нормально работать.
      2) В redis имеется репликация, если один инстанс ляжет — приложение может сходить в другой.
      Не так просто, чтобы записать в слэйв что-то, нужно сначала разорвать его репликацию с упавшим мастером.

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


      1. bak
        06.07.2016 18:09
        #9689548

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

        Плохой вариант. Что будет если сначала лежал сервер A, а потом лежал сервер B? В итоге в сервер A никогда не доедут записи из сервера B, происходящие в тот момент когда A лежал, и наоборот. Параллельная запись всегда приводит к рассинхронам.


        1. YourChief
          06.07.2016 18:37
          #9689620

          Равное состояние фильтров не является самоцелью, они представляют интерес только в совокупности.


          1. bak
            06.07.2016 20:49
            #9689782

            Попробую ещё раз объяснить ситуацию. В случае если есть две реплики и они ложатся поочередно ваш агрегированный bloom фильтр будет давать неверные ответы. Цепь событий следующая:

            • ложится нода A
            • приходит запись 'key1'. Её хеши попадают только в ноду B
            • поднимается нода A
            • ложится нода B
            • приходит запрос на проверку наличия записи 'key1'. Нода A отвечает что бит нулевой. Нода B лежит и делать «ИЛИ» не с чем.

            Этот сценарий вполне реальный когда поочередно ложатся разные дата центры к примеру.


    1. YourChief
      06.07.2016 17:55
      #9689526

      Про batch-запросы: на данный момент можно использовать HTTP pipelining:

      $ cat > batch.txt
GET /check?e=123 HTTP/1.1
Host: localhost

GET /check?e=456 HTTP/1.1
Host: localhost

$ nc 0 8889 < batch.txt 
HTTP/1.1 200 OK
Content-Type: text/html; charset=UTF-8
Date: Wed, 06 Jul 2016 14:53:23 GMT
Content-Length: 8

MISSING
HTTP/1.1 200 OK
Content-Type: text/html; charset=UTF-8
Date: Wed, 06 Jul 2016 14:53:23 GMT
Content-Length: 8

MISSING


      Но лучше, конечно, внутри одного запроса — это я учту.


      1. bak
        06.07.2016 18:12
        #9689556

        В итоге на каждый запрос по 120 байт ответа (вместо одного бита в идеале). Уж лучше хоть какой-то батчинг (а ещё лучше кастомный протокол).