Bloom Filter in Java utilizzando Guava

1. Panoramica

In questo articolo, esamineremo il costrutto del filtro Bloom dalla libreria Guava . Un filtro Bloom è una struttura dati probabilistica efficiente in termini di memoria che possiamo utilizzare per rispondere alla domanda se un dato elemento è o meno in un insieme .

Non ci sono falsi negativi con un filtro Bloom, quindi quando restituisce false , possiamo essere certi al 100% che l'elemento non è nel set.

Tuttavia, un filtro Bloom può restituire falsi positivi , quindi quando restituisce vero , c'è un'alta probabilità che l'elemento sia nel set, ma non possiamo esserne sicuri al 100%.

Per un'analisi più approfondita di come funziona un filtro Bloom, puoi seguire questo tutorial.

2. Dipendenza da Maven

Useremo l'implementazione di Guava del filtro Bloom, quindi aggiungiamo la dipendenza guava :

 com.google.guava guava 29.0-jre 

L'ultima versione può essere trovata su Maven Central.

3. Perché utilizzare il filtro Bloom?

Il filtro Bloom è progettato per essere poco ingombrante e veloce . Quando lo si utilizza, possiamo specificare la probabilità di risposte false positive che possiamo accettare e, in base a quella configurazione, il filtro Bloom occuperà la minor memoria possibile.

Grazie a questa efficienza di spazio, il filtro Bloom si adatterà facilmente alla memoria anche per un numero enorme di elementi. Alcuni database, tra cui Cassandra e Oracle, utilizzano questo filtro come primo controllo prima di accedere al disco o alla cache, ad esempio, quando arriva una richiesta di un ID specifico.

Se il filtro restituisce che l'ID non è presente, il database può interrompere l'ulteriore elaborazione della richiesta e tornare al client. Altrimenti, va sul disco e restituisce l'elemento se si trova sul disco.

4. Creazione di un filtro Bloom

Supponiamo di voler creare un filtro Bloom per un massimo di 500 numeri interi e di poter tollerare una probabilità dell'uno percento (0,01) di falsi positivi.

Possiamo usare la classe BloomFilter dalla libreria Guava per ottenere questo risultato. Dobbiamo passare il numero di elementi che ci aspettiamo vengano inseriti nel filtro e la probabilità di falso positivo desiderata:

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

Ora aggiungiamo alcuni numeri al filtro:

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

Abbiamo aggiunto solo tre elementi e abbiamo definito che il numero massimo di inserimenti sarà 500, quindi il nostro filtro Bloom dovrebbe fornire risultati molto accurati . Proviamolo usando il metodo mightContain () :

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

Come suggerisce il nome, non possiamo essere sicuri al 100% che un dato elemento sia effettivamente nel filtro quando il metodo restituisce true .

Quando mightContain () restituisce true nel nostro esempio, possiamo essere sicuri al 99% che l'elemento è nel filtro e c'è una probabilità dell'1 % che il risultato sia un falso positivo. Quando il filtro restituisce false , possiamo essere certi al 100% che l'elemento non è presente.

5. Filtro Bloom troppo saturo

Quando progettiamo il nostro filtro Bloom, è importante fornire un valore ragionevolmente accurato per il numero previsto di elementi . In caso contrario, il nostro filtro restituirà falsi positivi a una velocità molto più alta di quella desiderata. Vediamo un esempio.

Supponiamo di aver creato un filtro con una probabilità di falsi positivi desiderati dell'uno percento e di alcuni elementi previsti pari a cinque, ma poi abbiamo inserito 100.000 elementi:

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

Poiché il numero previsto di elementi è così piccolo, il filtro occuperà pochissima memoria.

Tuttavia, poiché aggiungiamo più elementi del previsto, il filtro diventa eccessivamente saturo e ha una probabilità molto più alta di restituire risultati falsi positivi rispetto all'uno percento desiderato:

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

Notare che il metodo mightContatin () ha restituito true anche per un valore che non abbiamo inserito nel filtro in precedenza.

6. Conclusione

In questo breve tutorial, abbiamo esaminato la natura probabilistica della struttura dei dati del filtro Bloom, facendo uso dell'implementazione Guava .

Puoi trovare l'implementazione di tutti questi esempi e frammenti di codice nel progetto GitHub.

Questo è un progetto Maven, quindi dovrebbe essere facile da importare ed eseguire così com'è.