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) в единички.

Теперь, чтобы проверить наличие ключа в наших данных, нам нужно вычислить значения 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 (и пользователю выводилось предупреждение).