Элегантная математика фильтров Блума

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

В этой статье речь пойдёт об изяществе математики, лежащей в основе фильтров Блума. Мы разберём аспекты точности работы и компромиссов при конфигурировании этих фильтров, а также узнаем, почему в некоторых случаях они могут стать отличным выбором, особенно в сфере больших данных и системах OLAP ^[1], когда подразумевается обработка огромных и статичных датасетов.

Фильтр Блума

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

При размере всего в несколько мегабайт, фильтр Блума может с вероятностью >99% спрогнозировать присутствие элемента внутри многомиллионного датасета. Он также может со 100% уверенностью определить, что элемент в датасете отсутствует. Эти качества, за счёт исключения лишних вычислений, делают такие фильтры прекрасным выбором для систем, обрабатывающих большое число запросов на чтение данных из огромных датасетов.

Фильтр Блума состоит из:

• массива битов (фильтра),
• набора не криптографических хэш-функций,
• функции для вставки (insert) элемента в фильтр,
• функции для проверки (check) присутствия элемента в отражаемом им датасете.

▍ Пример

Вот 32-битный (или 4-байтовый) массив, где все биты установлены на 0.

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

Предположим, у нас есть датасет из трёх элементов (от item_1 до item_3) и набор из 3 хэш-функций. Давайте вставим (insert) все эти элементы в фильтр:

filter.intert(item_1) // => {18, 28, 26}
filter.insert(item_2) // => {4, 7, 24}
filter.insert(item_3) // => {21, 16, 24}

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

▍ Проверка элементов

Функция check похожа на функцию insert. Единственное их отличие в том, что вместо использования хэшей в качестве позиций для установки битов на 1, в этом случае мы используем их в качестве позиций для проверки, установлен ли соответствующий бит на 1.

Проверим, находится ли элемент unknown_1 в нашем датасете:

filter.check(unknown_1) // => {26, 13... => В датасете отсутствует

Функция check уверенно сообщает, что элемент unknown_1 в датасете отсутствует. Один из хэшей обозначает позицию в фильтре, где бит не установлен (0), из чего мы делаем вывод, что unknown_1 в фильтр не добавлялся.

Далее нам нужно предположить, что в фильтр были вставлены все элементы датасета.

Проверим ещё один.

filter.check(unknown_2) // => {28, 24, 26} => Возможно, присутствует в датасете

Функция check ошибочно предполагает, что элемент unknown_2, вероятно, находится в датасете. В данном примере используется небольшой набор данных, и, глядя на элементы, мы понимаем, что unknown_2 в нём нет. Тем не менее все хэши unknown_2 указывают на позиции фильтра, где биты установлены на 1, в связи с чем функция check даёт ложноположительный результат.

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

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

Ложноположительные: математический расчёт

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

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

▍ Аппроксимация к большому m

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

Ожидается, что m будет большим, поэтому данное тождество вполне подходит для реальных сценариев. Член e⁻¹ очень близок к (1−1/m)^k, значит, можно написать так:

▍ Оптимизация фильтра

В функции присутствует соотношение n/m, и мы интуитивно понимаем, что лучше использовать такое m (размер фильтра), величина которого не меньше n (количества элементов в датасете). Мы предполагаем, что n дано, и его величину можно лишь аппроксимировать. Если мы в качестве примера аппроксимируем количество элементов в датасете до примерно 4 миллионов, то насколько большим тогда должен быть m?

• 500 КБ? Это 4 миллиона битов, что соответствует примерному числу элементов в датасете. В этом случае даже при одной хэш-функции наш фильтр будет слишком заполнен 1, и мы получим очень высокий показатель ложноположительных.
• 1 МБ? Это примерно вдвое больше количества имеющихся элементов. Если у нас будет две хэш-функции, то мы можем получить ту же частоту ложноположительных, поскольку каждая операция вставки создаёт две позиции. В этом случае у нас может быть слишком много хэш-функций относительно n/m.
• 100 МБ? При таком объёме точно останется много места для вставки битов с минимумом коллизий. Тем не менее подобный произвольный выбор очень большого размера выглядит опрометчивым. А если размер фильтра окажется непропорционально велик? Тогда мы будем впустую тратить лишнюю память.

Чуть позже мы с помощью математики найдём оптимальный размер m относительно n. В математическом смысле поиск оптимального m поможет заранее прикинуть размер фильтра. Но здесь важно отметить, что m имеет ограничения контекста.

Пока что возьмём соотношение n/m как константу, установленную путём аппроксимации размера n и учёта ограничений контекста m.

▍ Оптимальное количество хэш-функций

Продолжая наш пример, предположим, что n=4,000,000 элементов, а m=25,000,000 бит (3,125 МБ). Нам известно, что слишком много или слишком мало хэш-функций ведёт к повышению вероятности ложноположительных результатов. По факту мы можем видеть, как число хэш-функций k создаёт в нашей функции границы: (1−e^−n/m*k)^k. В результате, если k окажется слишком большим, внутренний член приблизится к 1, а если слишком маленьким, то уменьшится внешняя экспонента, что тоже излишне приблизит результат к 1.

Но есть золотая середина, в которой число хэш-функций относительно n/m даёт минимальную вероятность ложноположительных. На языке матанализа это минимум функции p(k)=(1−e^−n/m*k)^k.

▍ Поиск минимума

Вместо прямой дифференциации p(k) мы можем получить производную из lnp(k). Это упростит уравнение, и две производных будут разделять один отрезок x, который технически указывает на одно и то же минимальное значение p(k).

Применив правило ln(a^b)=bln(a), мы можем изолировать k и упростить выражение.

Мы получаем первую производную из части уравнения, отмеченной красным, и приравниваем её к 0.

Далее мы объявим q=e^−n/m*k. Это также означает, что ln(q)=−n/m*k. После этого заменим все синие фрагменты на q и ln(q) соответственно.

Теперь решить это уравнение будет совсем несложно, и в результате мы выясним, что:

Поскольку q=e^−n/m*k, верно и следующее:

Решив вышеприведённое уравнение для k, мы, наконец, получаем минимум для p(k):

ln(2)m/n — это количество хэш-функций, дающее минимальную вероятность получения ложноположительных. Однако здесь есть проблема. В нашем примере: ln(2)m/n=4,3321. Но результатом должно быть целое число.

Исправить это несложно. Мы можем округлить результат вверх и вниз, подставить оба варианта в функцию p(k) и посмотреть, какой из них приведёт к наименьшей вероятности. Тем не менее, если отличие между этими значениями несущественно, следует выбирать округлённое вниз.

В нашем случае округление k вниз даёт чуть лучший результат, p(⌊m/n⋅ln(2)⌋)=0,0499. Выходит, что фильтр размером 3,125 МБ в тандеме с 44 хэш-функциями может проверять присутствие элемента в датасете из ≈4,000,000 элементов, давая ≈5% ложноположительных результатов.

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

▍ Оптимальный размер фильтра

Теперь, когда мы знаем, как выражать k через m и n, можно развернуть наш изначальный вопрос о вероятности ложноположительных и написать полностью обобщённое уравнение, чтобы найти оптимальное соотношение между размером фильтра и количеством элементов датасета, при котором эта вероятность будет минимальной. Иными словами, мы можем спросить: «Сколько битов на элемент нужно использовать, чтобы вероятность была равна ε?»

В завершение перестроим его, чтобы получить соотношение битов на элемент (m/n).

Заключительные вычисления

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

Выходит, если в нашем датасете 4 миллиона элементов, то оптимальный фильтр должен содержать следующее число битов:

Округлив результат, мы понимаем, что размер фильтра должен быть примерно 4,79 МБ. Далее мы можем подставить эти числа в наше выражение, чтобы получить оптимальное число хэш-функций:

Фильтр из 38,340,23338,340,233 бит (~4,79 МБ) с 66 хэш-функциями может проверять присутствие элементов в датасете размером 4,000,000, давая всего ~1% ложноположительных. Впечатляет.

Обобщение

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

Напоследок я решил оставить вам небольшую задачку. Вы наверняка уже поняли, что удалять биты из фильтра нельзя, так как один и тот же бит может быть занят несколькими элементами. Как нам тогда представлять удалённые элементы, используя такой фильтр?