[Перевод] Фильтр Блума – вероятностная структура данных для проверки принадлежности элемента множеству
Целевая аудитория статьи:
технические работники,
технические руководители,
студенты.
Для понимания статьи обязательным условием является наличие фундаментальных знаний структур данных и алгоритмов. Статья не является исчерпывающим руководством по вероятностным структурам данных
Вступление
Структуры данных такие как HashSet могут использоваться для небольшого набора данных, позволяя проверять принадлежность элемента множеству. При этом использование проверки принадлежности элемента на большом наборе данных может быть затратным. Временная и пространственная сложность могут быть линейными в худшем случае.
Вероятностные структуры данных предоставляют постоянную временную и пространственную сложность за счет предоставления недетерминированного ответа.
Требования
Дизайн структуры данных со следующими характеристиками:
постоянная временная сложность для проверки принадлежности элемента структуре,
небольшой объем памяти для проверки принадлежности элемента структуре,
операции вставки и запроса должны быть распараллеливаемыми,
проверка принадлежности элемента структуре может давать приблизительные результаты.
Что такое фильтр Блума?
Фильтр Блума — это компактная вероятностная структура данных, которая используется для проверки принадлежности элемента множеству. Фильтр Блума сообщает о принадлежности элемента множеству, если элемент принадлежит множеству, но может ложно сообщить о принадлежности элемента множеству, хотя на элемент не входит во множество (ложноположительная ошибка). Фильтр верно сообщает об отсутствии элемента во множестве. Элементы могут добавляться в фильтр Блума, но не могут быть удалены из него.
Фильтр Блума поддерживает следующие операции:
добавление элемента во множество,
проверка принадлежности элемента множеству.
Как работает фильтр Блума?
Фильтр Блума как структура данных представляется массивом битов длины n как показано на рисунке 1. Позиции сегментов представлены индексами от 0 до 9 для массива битов длиной 10. Все биты в фильтре Блума имеют нулевое значение при инициализации, что соответствует пустому фильтру. Фильтр Блума не хранит значение элемента, а только сохраняет набор битов идентифицирующих его после вычисления хеш-функций над значением элемента.
Рисунок 1: Пустой фильтр Блума.
Как добавляется элемент в фильтр Блума?
Операции выполняемые при добавлении элемента в фильтр Блума:
Для элемента вычисляется k хеш-функций;
Полученные хеши делятся по модулю на n (по длине массива битов), чтобы получить k значений идентифицирующих позиции битов массива фильтра Блума;
Все биты в идентифицирующих позициях устанавливаются в значение равное 1.
Есть вероятность, что некоторые биты в массиве могут быть установлены в значение 1 многократно ввиду коллизий хеш-функций.
Рисунок 2: Добавление элемента в фильтр Блума.
.На рисунке 2, приведены красный и синий элементы, добавляемые в фильтр Блума. Сегменты, которые должны быть установлены в значение один для красного элемента определяются по результатам деления по модулю рассчитанных хеш-функций:
h1(red) mod 10 = 1,
h2(red) mod 10 = 3,
h3(red) mod 10 = 5.
Сегменты которые должны быть установлены в один для синего элемента также определяются по результатам деления по модулю рассчитанных хеш-функций:
h1(blue) mod 10 = 4,
h2(blue) mod 10 = 5,
h3(blue) mod 10 = 9.
Сегмент в позиции пять устанавливался в единицу при добавлении и красного, и синего элементов.
Как проверить принадлежность элемента фильтру Блума?
Операции выполняемые при проверке принадлежности элемента фильтру Блума:
Для элемента вычисляются k хеш-функций;
Полученные хеши делятся по модулю на n (по длине массива битов), чтобы получить k значений идентифицирующих позиции битов массива фильтра Блума;
Выполняется проверка, что полученные сегменты установлены в единицу.
Рисунок 3: Проверка принадлежности элемента фильтру Блума.
Если любой из битов имеет нулевое значение, то элемент не добавлялся в фильтр Блума. Если все биты имеют значение один, то элемент возможно добавлялся в фильтр Блума. Неопределенность по принадлежности элемента возникает из-за возможности установки некоторых битов при добавлении разных элементов или из-за коллизий хеш функций.
На рисунке 3, выполняется проверка принадлежности синего элемента фильтру Блума. Проверяемые сегменты получены после деления по модулю значений полученных из хеш-функций, рассчитанных для элемента.
h1(blue) mod 10 = 4,
h2(blue) mod 10 = 5,
h3(blue) mod 10 = 9.
Синий элемент возможно принадлежит фильтру Блума, так как все биты установлены в единицу.
Рисунок 4: Проверка, что элемент не принадлежит фильтру Блума.
На рисунке 4, выполняется проверка принадлежности черного элемента, которого нет в фильтре Блума:
h1(black) mod 10 = 0,
h2(black) mod 10 = 3,
h3(black) mod 10 = 6.
Черный элемент не принадлежит фильтру Блума, так как в сегменте ноль значение бита имеет значение ноль. Проверка остальных битов может быть пропущена.
Ложноположительное срабатывание фильтра Блума
Рисунок 5. Ложноположительное срабатывание фильтра Блума.
На рисунке 5, выполняется проверка принадлежности зеленого элемента фильтру Блума, который в него не добавлялся:
h1(green) mod 10 = 3,
h2(green) mod 10 = 4,
h3(green) mod 10 = 5.
Фильтр Блума сообщит о принадлежности элемента, хотя зеленый элемент не добавлялся в него, а соответствующие биты были установлены при добавлении красного и синего элементов.
Какая асимптотическая сложность фильтра Блума?
Производительность фильтра Блума зависит от используемых хеш-функций. Чем быстрее вычисляется хеш-функция, тем быстрее отрабатывает каждая операция над фильтром Блума.
Временная сложность
Операция | Временная сложность |
добавление элемента | O (k) или константа |
проверка принадлежности элемента | O (k) или константа |
Где k количество хеш-функций.
Временная сложность фильтра Блума не зависит от количества элементов уже добавленных в фильтр. Все k проверок независимы и могут быть выполнены параллельно.
Пространственная сложность
Несмотря на количество находящихся в фильтре Блума элементов, фильтр требуется постоянное число битов, используя под каждый элемент несколько битов. Фильтр Блума не хранит значения добавляемых элементов, а значит имеет константную сложность O (1).
Калькулятор для фильтра Блума
Калькулятор для фильтра Блума на hur.st может быть использован для подбора нужного размера фильтра и для исследования влияния различных параметров. Точность работы фильтра зависит от следующих параметров:
количество хеш-функций (k),
качество хеш-функций,
длина массива бит (n),
количество элементов добавляемых в фильтр Блума.
Для фильтра Блума хеш-функции должны обладать следующими свойствами:
скорость,
независимость,
равномерное распределение.
Преимущества фильтра Блума
Преимуществами фильтра Блума являются:
константная временная сложность;
константная пространственная сложность;
операции могут выполняться параллельно;
нет ложноотрицательных срабатываний;
обеспечивает конфиденциальность, так как не хранит значения элементов;
возможность побитового объединения или побитового пересечения двух фильтров Блума одинаковой размерности, использующих одинаковые хеш-функции (пер.: добавлено из комментариев к статье).
Недостатки фильтра Блума
Недостатки фильтра Блума следующие:
не поддерживает операцию удаления;
ложноположительные срабатывания нельзя устранить в ноль;
необходимость произвольного доступа к битам массива, индикаторы которых генерируются случайным образом хеш-функциями.
Удаление элемента из фильтра Блума не поддерживается, так как нет возможности идентифицировать какие биты должны быть удалены. В фильтре Блума могут находится другие элементы использующие те же биты, и их очистка может привести в ложноотрицательным ошибкам.
Сценарии использования фильтра Блума
Рисунок 6: Фильтр Блума используется для сокращения количества запросов к базе данных.
Фильтры Блума полезны в высоконагруженных системах для предотвращения дорогостоящих операций с дисками. На рисунке 6, например, сервис выполняется поиск элемента в большой таблице на диске, что может привести к деградации пропускной способности сервиса. Фильтр Блума может предварительно обрабатывать поиски и отсекать ненужные операции с диском, за исключением случаев ложноположительных срабатываний. Фильтр Блума может быть применен в следующих случаях:
сокращение обращений к диску для не существующих в базе ключей;
определять получен ли идентификатор пользователя;
фильтрация ранее показанных публикаций для рекомендательных движков;
проверка слов на наличие орфографических ошибок и ненормативной лексики в спеллчекерах;
идентификация опасных url, заблокированных IP-адресов и мошеннических транзакций;
хранилища, использующие журнально-структурированное дерево со слиянием (LSM-дерево), такие как Cassandra, используют фильтр Блума для проверки существования ключа в SSTable;
MapReduce использует фильтр Блума для эффективной обработки больших наборов данных.
Реализации фильтра Блума
Модуль RedisBloom поддерживает фильтр Блума из коробки. Фильтр может занимать объем около 2% памяти требуемой для произвольного набора данных и будет работать быстрее чем обработка отдельных элементов набора как с множеством.
Реализация фильтра Блума в node.js для учебных целей доступна в репозитории github.com/guyroyse.
Хеш-функции общего назначения, такие как MurmurHash или FNV могут быть использованы в фильтре Блума.
Модификации фильтра Блума
Фильтр Блума с подсчетом
Рисунок 7: Фильтр Блума с подсчетом.
Фильтр Блума с подсчетом включает массив счетчиков для каждого бита. Массив счетчиков инициализируется нулями. Счетчики для связанных битов увеличиваются на единицу при добавлении в фильтр Блума с подсчетом. Проверка принадлежности элемента фильтру Блума работает как в базовом фильтре. Фильтр Блума с подсчетом поддерживает операцию удаления элемента из фильтра. Операции выполняемые для удаления элемента из фильтра Блума с подсчетом:
Для элемента вычисляется k хеш-функций
Полученные хеши делятся по модулю на n (по длине массива битов), чтобы получить k значений идентифицирующих позиции битов массива фильтра Блума
Счетчики полученных позиций битов уменьшаются на единицу
Соответствующие биты устанавливаются в ноль, если счетчик после вычитания получает значение равное нулю
Фильтр Блума с подсчетом занимает больше памяти по сравнению с классическим, так как требуется хранить значения счетчиков, даже если большая часть значений будет равна нулю. Поэтому важно оценить насколько большими могут быть значения счетчиков и как их размер зависит от длины фильтра n и количества хеш-функций k.
Масштабируемый фильтр Блума
Рисунок 8: Масштабируемый фильтр Блума.
Фильтр Блума невозможно изменить после его насыщения элементами, так как невозможно определить какие элементы добавлены в фильтр. При этом фильтры Блума могут объединяться для масштабируемости. Как только фильтр блума наполняется элементами, новый фильтр большей емкости может быть добавлен поверх текущего фильтра. Запрос на принадлежность элемента фильтру Блума требует проверки в каждом фильтре. Дополнительно, при добавлении нового элемента требуется проверка наличия элемент в каждом нижележащем фильтре прежде, чем добавить в фильтр верхнего уровня
Полосатый (striped) фильтр Блума
Striped фильтр Блума реализуется с использованием массива беззнаковых 64-битных целых чисел и разделяется на шарды для распараллеливания. Каждый шард содержит свой мьютекс, обеспечивающий повышенную пропускную способность добавления и поиска. Единственное имеющееся ограничение фильтра заключается в том, что размер фильтра Блума должен быть кратен количеству шардов.
Другие вариации фильтра Блума
Существуют другие вариации фильтра Блума и структуры данных похожие по функциональности на фильтр Блума. Например (пер.: большая часть примеров добавлена при переводе):
Резюме
Фильтры Блума полезные структуры данных в высоконагруженных системам. Фильтры Блума имеют константную временную и пространственную сложность. Компромиссом при использовании фильтров Блума и его вариаций является не детерминированный результат.
