Фильтр Блума в Java с использованием Guava

1. Обзор

В этой статье мы рассмотрим конструкцию фильтра Блума из библиотеки Guava . Фильтр Блума — это вероятностная структура данных с эффективным использованием памяти, которую мы можем использовать для ответа на вопрос о том, находится ли данный элемент в множестве .

Фильтр Блума не дает ложных срабатываний , поэтому, когда он возвращает false , мы можем быть на 100 % уверены, что элемента нет в наборе.

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

Для более глубокого анализа работы фильтра Блума вы можете пройти этот туториал .

2. Зависимость от Maven

Мы будем использовать реализацию фильтра Блума в Guava, поэтому давайте добавим зависимость guava :

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

Последнюю версию можно найти на Maven Central .

3. Зачем использовать фильтр Блума?

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

Благодаря этой компактности фильтр Блума легко поместится в памяти даже при огромном количестве элементов. Некоторые базы данных, в том числе Cassandra и Oracle, используют этот фильтр в качестве первой проверки перед переходом на диск или в кеш, например, когда приходит запрос на конкретный ID.

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

4. Создание фильтра Блума

Предположим, мы хотим создать фильтр Блума, содержащий до 500 целых чисел , и что мы можем допустить однопроцентную (0,01) вероятность ложных срабатываний.

Для этого мы можем использовать класс BloomFilter из библиотеки Guava . Нам нужно передать количество элементов, которые мы ожидаем вставить в фильтр, и желаемую вероятность ложного срабатывания:

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  500,
  0.01);

Теперь давайте добавим несколько чисел в фильтр:

filter.put(1);
filter.put(2);
filter.put(3);

Мы добавили всего три элемента и определили, что максимальное количество вставок будет равно 500, поэтому наш фильтр Блума должен давать очень точные результаты . Давайте проверим это, используя метод mayContain() :

assertThat(filter.mightContain(1)).isTrue();
assertThat(filter.mightContain(2)).isTrue();
assertThat(filter.mightContain(3)).isTrue();

assertThat(filter.mightContain(100)).isFalse();

Как следует из названия, мы не можем быть на 100% уверены, что данный элемент действительно находится в фильтре, когда метод возвращает true .

Когда в нашем примере mayContain() возвращает true , мы можем быть на 99 % уверены, что элемент находится в фильтре, и существует вероятность в один процент того, что результат будет ложноположительным. Когда фильтр возвращает false , мы можем быть на 100% уверены, что элемент отсутствует.

5. Перенасыщенный фильтр Блума

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

Предположим, что мы создали фильтр с желаемой вероятностью ложного срабатывания в один процент и ожидаемым числом элементов, равным пяти, но затем вставили 100 000 элементов:

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  5,
  0.01);

IntStream.range(0, 100_000).forEach(filter::put);

Поскольку ожидаемое количество элементов очень мало, фильтр будет занимать очень мало памяти.

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

assertThat(filter.mightContain(1)).isTrue();
assertThat(filter.mightContain(2)).isTrue();
assertThat(filter.mightContain(3)).isTrue();
assertThat(filter.mightContain(1_000_000)).isTrue();

Обратите внимание, что метод mayContatin () вернул значение true даже для значения, которое мы ранее не вставляли в фильтр.

6. Заключение

В этом кратком руководстве мы рассмотрели вероятностный характер структуры данных фильтра Блума с использованием реализации Guava .

Вы можете найти реализацию всех этих примеров и фрагментов кода в проекте GitHub .

Это проект Maven, поэтому его должно быть легко импортировать и запускать как есть.