Dato un nome utente su una pagina di registrazione utente, come facciamo a sapere se è già stato registrato?

Mentre l'interrogazione di un database indicizzato aiuta, è lenta e comporta chiamate di rete.

Per velocizzare le cose, possiamo memorizzare nella cache l'elenco dei nomi utente registrati in un archivio di valori-chiave come Redis.

Tuttavia, ciò implica la memorizzazione nella cache di milioni di record e il raddoppio della nostra impronta di memoria.

Come possiamo fare meglio in questo problema apparentemente banale?

Il filtro bloom potrebbe essere la risposta, diamo un'occhiata!

Che cos'è un filtro Bloom?

Un filtro bloom risponde a una semplice domanda,

Esiste un elemento in un dato insieme?

Un filtro bloom è una struttura dati probabilistica. Data la domanda precedente, restituisce una delle seguenti risposte

• Probabilmente sì
• 100% no

E il suo più grande vantaggio è che lo fa in COSTANTE tempo e spazio.

Come funziona?

Un filtro bloom è costituito da due componenti

• Un array di bit di dimensione N
• Diverse funzioni di hashing

Viene inizialmente inizializzato come un array di bit di dimensioni N con tutti i suoi bit impostati su zero. Supponiamo che la lunghezza dell'array sia 10 per ora.

Aggiunta di un elemento

L'aggiunta di un elemento è banale

• L'elemento detto "tigre" viene sottoposto a hashing utilizzando una funzione di hashing
• L'hash generato è modificato dalla lunghezza dell'array per ottenere un indice limitato
• L'indice dell'array di bit viene quindi impostato su 1

Analogamente all'aggiunta di un elemento, eseguiamo l'hashing dell'elemento utilizzando una funzione di hashing e lo modifichiamo per ottenere un indice limitato.

L'output viene valutato come segue,

• Se il valore dell'indice dell'array di bit è 0, l'elemento NON è nell'insieme.
• Altrimenti, l'articolo è PROBABILMENTE nel set

Conservazione di un filtro bloom

Invece di memorizzare il filtro bloom come un array, possiamo convertire la sua rappresentazione in bit in un numero decimale.

Ad esempio, possiamo convertire un array contenente 10011in 19 e memorizzarlo in una cache.

Se l'elenco non cambia molto spesso, il server può inviare il numero decimale al client, consentendo la convalida da parte del client.

Possiamo fare di meglio?

Se la funzione di hashing restituisce l'indice 1 sia per "tigre" che per "mucca", controllando se "mucca" è nell'insieme si ottiene la risposta Sì anche se non lo è .

Possiamo ridurre la possibilità di falsi positivi attraverso le seguenti soluzioni.

• Aumentare la lunghezza dell'array
• Aumentare il numero di funzioni di hashing

Invece di un indice, possiamo ottenere più indici utilizzando diversi hash.

Quando si aggiunge un elemento, tutti gli indici ottenuti verranno impostati su 1.

Si afferma che un elemento è probabilmente nel set, solo se TUTTI gli indici sono impostati su 1.

Sfruttando questi metodi, potremmo ridurre significativamente la probabilità di falsi positivi.

Applicazioni

Diamo un'occhiata ad alcuni esempi di vita reale.

Controlla se esiste un nome utente in un flusso di registrazione utente

• Quando viene creato un nome utente, il nome utente viene aggiunto a un filtro bloom archiviato in un archivio di valori-chiave.
• Quando un utente digita un nome utente su una pagina di registrazione utente, il server interroga prima il filtro bloom.
• Se il nome utente NON è nel filtro bloom, il server restituisce immediatamente un errore al client.
• In caso contrario, il server esegue query e controlli incrociati nel database.

• Medium mantiene un filtro bloom per ogni utente.
• Prima di consigliare un articolo, Medium controlla se l'ID articolo esiste nel filtro bloom dell'utente.
• Si raccomandano all'utente gli articoli che sicuramente NON sono nel filtro bloom.

• Quando si accede a un URL, Chrome verifica innanzitutto se l'URL fa parte di un elenco dannoso.
• Invece di interrogare ogni volta il server di Google, Google crea un filtro bloom utilizzando un elenco malevolo predeterminato e lo invia al browser.
• Il browser esegue l'hashing dell'URL e esegue controlli incrociati con il filtro bloom prima di accedere al sito Web.

Anche se potrebbero esserci falsi positivi , un filtro bloom è utile quando vogliamo sapere se un elemento non è sicuramente in un elenco.

Può essere utilizzato come primo strato di filtraggio grazie alla sua efficienza sia nel tempo che nello spazio.

Spero che lo troverai utile e ci vediamo al prossimo!