Статьи

Использование Guava BloomFilter для условий охраны


Когда проект Guava выпустил версию 11.0, одним из новых дополнений стал класс BloomFilter.
BloomFilter — это уникальная структура данных, используемая для указания того, содержится ли элемент в наборе. Что делает BloomFilter интересным, так это то, что он будет указывать, если элемент
абсолютно не содержится или
может бытьсодержится в наборе. Это свойство отсутствия ложного отрицания делает BloomFilter отличным кандидатом для использования в качестве защитного условия, помогающего предотвратить выполнение ненужных и дорогостоящих операций. В то время как BloomFilters в последнее время получили хороший отклик, использование одного означало переход на другой или поиск в Google кода. Проблема с прокруткой вашего собственного BloomFilter заключается в получении правильной хеш-функции, чтобы сделать фильтр эффективным. Учитывая, что Guava использует Murmur Hash для его реализации, теперь у нас есть полезный эффективный BloomFilter, находящийся вдали от библиотеки.

Ускоренный курс BloomFilter

BloomFilters по существу являются битовыми векторами. На высоком уровне BloomFilters работают следующим образом:

  1. Добавьте элемент в фильтр.
  2. Сделайте хэш-код несколько раз, затем установите биты равными 1, где индекс соответствует результатам хэша.

При проверке наличия элемента в наборе вы выполняете ту же процедуру хеширования и проверяете, установлены ли биты на 1 или 0. Этот процесс позволяет BloomFilter гарантировать, что элемент не существует. Если биты не установлены, элемент просто не может быть в наборе. Однако положительный ответ означает, что элемент находится в наборе или произошло столкновение хэширования. Более подробное описание BloomFilter можно найти здесь, а хорошее руководство по BloomFilters здесь . Согласно википедии , Google использует BloomFilters в BigTable, чтобы избежать поиска на диске несуществующих элементов. Еще одно интересное использование — использование BloomFilter для оптимизации SQL-запросов .

Использование Guava BloomFilter

Guava BloomFilter создается путем вызова статического метода create для класса BloomFilter,
передавая объект Funnel и int, представляющий ожидаемое количество вставок. Воронка, также новая в Guava 11, — это объект, который может отправлять данные в Sink . Следующий пример является реализацией по умолчанию и имеет процент ложных срабатываний 3%. Guava предоставляет класс Funnels, содержащий два статических метода, обеспечивающих реализации интерфейса Funnel для вставки CharSequence или байтового массива в фильтр.

//Creating the BloomFilter
BloomFilter bloomFilter = BloomFilter.create(Funnels.byteArrayFunnel(), 1000);

//Putting elements into the filter
//A BigInteger representing a key of some sort
bloomFilter.put(bigInteger.toByteArray());

//Testing for element in set
boolean mayBeContained = bloomFilter.mayContain(bitIntegerII.toByteArray());

Соображения

Очень важно правильно оценить количество ожидаемых вставок. Когда число вставок в фильтр приближается или превышает ожидаемое число, BloomFilter начинает заполняться и в результате генерирует больше ложных срабатываний до такой степени, что становится бесполезным. Существует другая версия метода BloomFilter.create, принимающая дополнительный параметр, double, представляющий желаемый уровень вероятности ложного попадания (должен быть больше 0 и меньше единицы). Уровень вероятности ложного попадания влияет на количество хэшей для хранения или поиска элементов. Чем ниже требуемый процент, тем больше будет выполнено хэшей.

Вывод

BloomFilter — это полезный элемент, который разработчик может иметь в своем наборе инструментов. Теперь проект Guava упрощает использование BloomFilter, когда в этом возникает необходимость. Я надеюсь, вам понравился этот пост. Полезные комментарии и предложения приветствуются.

Рекомендации