DEV Community

faangmaster
faangmaster

Posted on

2

Bloom Filter

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

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

Линейный поиск

Можно, просто, последовательно читать все файлы и проверять наличие записи с заданным ID. Такой подход не требует дополнительной памяти, но работает очень долго - за линейное время (O(N)). Если данных очень много, то такая проверка будет работать очень долго.

Индекс

Можно построить индекс данных. Например, создать отдельный файл, содержащий записи в формате: (ID, имя_файла + смещение в дата-файле). Затем отсортировать эти записи в индексе по значению ключа. Поиск по ключу в отсортированном индексе можно выполнять с помощью бинарного поиска, который работает быстрее, чем линейный поиск, и имеет логарифмическую сложность — O(log(N)). Кроме того, нам нужно отдельно хранить еще индекс.
Индекс можно организовать другими способами: с помощью бинарного дерева поиска, B-дерева или хеш-таблицы. Однако объём требуемой памяти для хранения индекса может быть значительным, так как необходимо хранить сами данные в индексе (как минимум ключи, а в максимальном случае — все данные или хотя бы название файла и смещение в файле).
Можно ли как-то оптимизировать количество требуемой памяти для задачи проверки наличия ключа в большом наборе данных?

Bloom Filter

В этой задаче, для оптимизации требуемой памяти, можно использовать Bloom Filter.
Вместо объёмного индекса можно использовать компактный битовый массив. Для этого необходимо применить несколько различных хеш-функций (k хеш-функций). Каждая из этих хеш-функций принимает на вход ключ (ID) и возвращает целое число, которое можно использовать в качестве индекса в битовом массиве.
Для каждого ключа (ID) в исходном наборе данных применяем k хеш-функций и вычисляем k индексов в битовом массиве. Устанавливаем значения битов на этих индексах в единицу.
Например, для ключей P, Q, R, выставляем биты по индексам H1(P), H2(P), H3(P), H1(Q), H2(Q), H3(Q), H1(R), H2(R), H3(R) в единички.

Image description

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

Если все биты установлены в единицу, то можно лишь предположить, что запись с таким ключом может присутствовать в данных. Это не гарантируется. Т.к. у hash-функций могут быть коллизии, и один и тот же бит может быть выставлен для разных ключей. При правильно подобранном наборе hash-функций мы может сократить вероятность ошибки (false positive - случаи, когда мы предположили, что ключ есть, но его в реальности нет в наших данных).
Bloom filter это вероятностная структура данных. Если она вернула результат - данных нет, то это гарантированно. Если она вернула, что данные есть, то это не гарантированно, а только с определенной вероятностью. На практике такая вероятность может быть сильно больше 99%.

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

  • Google Bigtable, Apache HBase, Apache Cassandra, ScyllaDB и PostgreSQL используют Bloom Filter для уменьшения количества обращений к диску при поиске несуществующих строк или столбцов. Избежание дорогостоящих обращений к диску значительно повышает производительность запросов к базе данных.
  • Google Chrome ранее использовал Bloom Filter для определения вредоносных URL-адресов. Сначала любой URL проверялся с помощью локального Bloom Filter, и только если фильтр возвращал положительный результат, проводилась полная проверка URL (и пользователю выводилось предупреждение).

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More