Bloom Filter in Java mit Guava

1. Übersicht

In diesem Artikel betrachten wir das Bloom-Filterkonstrukt aus der Guava- Bibliothek. Ein Bloom-Filter ist eine speichereffiziente, probabilistische Datenstruktur, mit der wir die Frage beantworten können, ob sich ein bestimmtes Element in einer Menge befindet oder nicht .

Bei einem Bloom-Filter gibt es keine falsch negativen Ergebnisse. Wenn er also falsch zurückgibt , können wir zu 100% sicher sein, dass das Element nicht in der Menge enthalten ist.

Ein Bloom-Filter kann jedoch falsch positive Ergebnisse zurückgeben. Wenn er also true zurückgibt , besteht eine hohe Wahrscheinlichkeit, dass sich das Element in der Menge befindet, aber wir können nicht 100% sicher sein.

In diesem Tutorial erfahren Sie mehr über die Funktionsweise eines Bloom-Filters.

2. Maven-Abhängigkeit

Wir werden Guavas Implementierung des Bloom-Filters verwenden, also fügen wir die Guavenabhängigkeit hinzu :

 com.google.guava guava 29.0-jre 

Die neueste Version finden Sie auf Maven Central.

3. Warum Bloom Filter verwenden?

Der Bloom-Filter ist platzsparend und schnell ausgelegt . Wenn wir es verwenden, können wir die Wahrscheinlichkeit falsch positiver Antworten angeben, die wir akzeptieren können, und gemäß dieser Konfiguration belegt der Bloom-Filter so wenig Speicher wie möglich.

Aufgrund dieser Raumeffizienz passt der Bloom-Filter auch für eine große Anzahl von Elementen problemlos in den Speicher . Einige Datenbanken, einschließlich Cassandra und Oracle, verwenden diesen Filter als erste Überprüfung, bevor sie auf die Festplatte oder den Cache gehen, z. B. wenn eine Anforderung für eine bestimmte ID eingeht.

Wenn der Filter zurückgibt, dass die ID nicht vorhanden ist, kann die Datenbank die weitere Verarbeitung der Anforderung stoppen und zum Client zurückkehren. Andernfalls geht es auf die Festplatte und gibt das Element zurück, wenn es auf der Festplatte gefunden wird.

4. Erstellen eines Bloom-Filters

Angenommen, wir möchten einen Bloom-Filter für bis zu 500 Ganzzahlen erstellen und können eine Wahrscheinlichkeit von einem Prozent (0,01) für falsch positive Ergebnisse tolerieren.

Wir können die BloomFilter- Klasse aus der Guava- Bibliothek verwenden, um dies zu erreichen. Wir müssen die Anzahl der Elemente, von denen wir erwarten, dass sie in den Filter eingefügt werden, und die gewünschte falsch positive Wahrscheinlichkeit übergeben:

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

Fügen wir nun dem Filter einige Zahlen hinzu:

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

Wir haben nur drei Elemente hinzugefügt und definiert, dass die maximale Anzahl von Einfügungen 500 beträgt. Daher sollte unser Bloom-Filter sehr genaue Ergebnisse liefern . Testen wir es mit der Methode mayContain () :

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

Wie der Name schon sagt, können wir nicht 100% sicher sein, dass sich ein bestimmtes Element tatsächlich im Filter befindet, wenn die Methode true zurückgibt .

Wenn mayContain () in unserem Beispiel true zurückgibt , können wir zu 99% sicher sein, dass sich das Element im Filter befindet, und es besteht eine Wahrscheinlichkeit von einem Prozent, dass das Ergebnis falsch positiv ist. Wenn der Filter false zurückgibt , können wir zu 100% sicher sein, dass das Element nicht vorhanden ist.

5. Übersättigter Blütenfilter

Bei der Entwicklung unseres Bloom-Filters ist es wichtig, dass wir einen einigermaßen genauen Wert für die erwartete Anzahl von Elementen angeben . Andernfalls gibt unser Filter falsch positive Ergebnisse mit einer viel höheren Rate als gewünscht zurück. Sehen wir uns ein Beispiel an.

Angenommen, wir haben einen Filter mit einer gewünschten falsch-positiven Wahrscheinlichkeit von einem Prozent und erwarteten Elementen von fünf erstellt, aber dann haben wir 100.000 Elemente eingefügt:

BloomFilter filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

Da die erwartete Anzahl von Elementen so gering ist, belegt der Filter nur sehr wenig Speicher.

Wenn wir jedoch mehr Elemente als erwartet hinzufügen, wird der Filter übersättigt und hat eine viel höhere Wahrscheinlichkeit, falsch positive Ergebnisse zurückzugeben als das gewünschte Prozent:

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

Beachten Sie, dass die mightContatin () Methode zurückgegeben wahr sogar für einen Wert, den wir nicht einfügen haben vorher in den Filter.

6. Fazit

In diesem kurzen Tutorial haben wir uns mit der Wahrscheinlichkeit der Bloom-Filterdatenstruktur befasst und dabei die Guava- Implementierung verwendet.

Die Implementierung all dieser Beispiele und Codefragmente finden Sie im GitHub-Projekt.

Dies ist ein Maven-Projekt, daher sollte es einfach zu importieren und auszuführen sein.