Bloom Filter в Java с помощта на Guava

1. Общ преглед

В тази статия ще разгледаме конструкцията на филтъра Bloom от библиотеката на Guava . Блум филтърът е ефективна от паметта, вероятностна структура от данни, която можем да използваме, за да отговорим на въпроса дали даден елемент е в набор или не .

Няма лъжливи отрицания с филтър Bloom, така че когато връща false , можем да бъдем 100% сигурни, че елементът не е в комплекта.

Филмът Bloom обаче може да върне фалшиви положителни резултати , така че когато връща true , има голяма вероятност елементът да е в комплекта, но не можем да бъдем сигурни на 100%.

За по-задълбочен анализ на това как работи филтър Bloom, можете да преминете през този урок.

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

Ще използваме реализацията на Guava на филтъра Bloom, така че нека добавим зависимостта на guava :

 com.google.guava guava 29.0-jre 

Най-новата версия може да бъде намерена на Maven Central.

3. Защо да използвам Bloom Filter?

Филтърът Bloom е проектиран да бъде космически ефективен и бърз . Когато го използваме, можем да посочим вероятността от фалшиво положителни отговори, които можем да приемем и според тази конфигурация филтърът Bloom ще заема възможно най-малко памет.

Благодарение на тази космическа ефективност, филтърът Bloom лесно ще се побере в паметта дори за огромен брой елементи. Някои бази данни, включително Cassandra и Oracle, използват този филтър като първа проверка преди да отидете на диск или кеш, например, когато влезе заявка за конкретен ID.

Ако филтърът върне, че идентификаторът не присъства, базата данни може да спре по-нататъшната обработка на заявката и да се върне на клиента. В противен случай той отива на диска и връща елемента, ако бъде намерен на диска.

4. Създаване на Bloom Filter

Да предположим, че искаме да създадем Bloom филтър за до 500 Integers и че можем да толерираме еднопроцентна (0,01) вероятност от фалшиви положителни резултати.

За да постигнем това, можем да използваме класа BloomFilter от библиотеката Guava . Трябва да предадем броя на елементите, които очакваме да бъдат вмъкнати във филтъра, и желаната фалшиво положителна вероятност:

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

Сега нека добавим няколко числа към филтъра:

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

Добавихме само три елемента и определихме, че максималният брой вмъквания ще бъде 500, така че нашият филтър Bloom трябва да даде много точни резултати . Нека го тестваме, използвайки метода mightContain () :

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

Както подсказва името, не можем да бъдем 100% сигурни, че даден елемент всъщност е във филтъра, когато методът връща true .

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

5. Пренаситен филтър за цъфтеж

Когато проектираме нашия филтър Bloom, е важно да предоставим разумно точна стойност за очаквания брой елементи . В противен случай нашият филтър ще върне фалшиви положителни резултати с много по-висока скорост от желаната. Да видим пример.

Да предположим, че създадохме филтър с желана фалшиво положителна вероятност от един процент и очаквани някои елементи, равни на пет, но след това вмъкнахме 100 000 елемента:

BloomFilter 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();

Обърнете внимание, че mightContatin () методът се връща вярно дори и за стойност, която ние не поставите във филтъра преди това.

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

В този бърз урок разгледахме вероятностния характер на структурата от данни на филтъра Bloom - използвайки внедряването на Guava .

Можете да намерите изпълнението на всички тези примери и кодови фрагменти в проекта GitHub.

Това е проект на Maven, така че трябва да е лесно да се импортира и да се изпълнява както е.