Filtro CUCKOO vs BLOOM, dal punto di vista di Gopher

In questo articolo, sto cercando di implementare e testare l'efficienza di un filtro a cucù su un filtro a fioritura. (Leggi il precedente post su Chord DHT, implementando una tabella hash distribuita a Golang)

introduzione

Le strutture di dati probabilistici sono molto utili, specialmente quando si elaborano set di dati di grandi dimensioni. La maggior parte delle volte, mentre si lavora sul lato dati delle cose, si vorrebbe fare una semplice query "è l'articolo non presente" o "è l'elemento già presente" durante l'elaborazione dei dati in tempo reale. Supponi di voler rispondere alle query in tempo reale, come il numero di IP unici, IP più frequenti, se un annuncio è già stato offerto a un utente, l'utilizzo di strutture di dati probabilistici fornisce un modo efficiente in termini di spazio per rispondere a queste query. L'approccio tipico a tali query sarebbe di utilizzare una HashMap o una HashTable o di archiviarla in una cache esterna (come i redis), ma il problema è con set di dati di grandi dimensioni, queste strutture di dati semplici non possono adattarsi alla memoria. È qui che entrano in gioco le strutture probabilistiche dei dati a causa dei loro vantaggi in termini di spazio e tempo.

Esempio Casi d'uso

  • Google Bigtable, Apache HBase e Apache Cassandra e Postgresql utilizzano i filtri Bloom per ridurre le ricerche del disco per righe o colonne inesistenti. Evitare costose ricerche su disco aumenta notevolmente le prestazioni di un'operazione di query del database.
  • Medium utilizza i filtri Bloom per verificare se un articolo è già stato consigliato a un utente
  • Ethereum utilizza i filtri Bloom per trovare rapidamente i log sulla blockchain di Ethereum
  • Il browser Web Google Chrome utilizzato per utilizzare un filtro Bloom per identificare URL dannosi. Qualsiasi URL è stato prima verificato con un filtro Bloom locale e solo se il filtro Bloom ha restituito un risultato positivo è stato eseguito un controllo completo dell'URL (e l'utente ha avvertito, se anche quello ha restituito un risultato positivo)

Cosa c'è in un "cuculo"?

Abbiamo utilizzato i filtri bloom in molti punti per rispondere a tali domande sulla piattaforma dati. Di recente mi sono imbattuto in questo documento sul filtro a cucù che ha attirato il mio interesse. Il titolo stesso dice "Filtro a cucù: praticamente migliore della fioritura", quindi ho deciso di provarlo.

I filtri a cucù migliorano il design del filtro bloom offrendo eliminazione, conteggio limitato e una probabilità falsa positiva limitata, pur mantenendo una simile complessità spaziale. Usano l'hash del cuculo per risolvere le collisioni e sono essenzialmente una tabella di hash del cuculo compatta.

I filtri Cuckoo e bloom sono entrambi utili per impostare i test di appartenenza quando la dimensione dei dati originali è grande. Entrambi usano solo 7 bit per voce. Sono inoltre utili quando un'operazione costosa può essere evitata prima dell'esecuzione mediante un test di appartenenza impostato. Ad esempio, prima di eseguire una query su un database, è possibile eseguire un test di appartenenza impostato per verificare se l'oggetto desiderato si trova anche nel database.

Algoritmo

Parametri del filtro:
1. Due funzioni hash: h1 e h2
2. Un array B con n secchi. L'II-secchio si chiamerà B [i]

Input: L, un elenco di elementi da inserire nel filtro a cucù.

Algoritmo:
Mentre L non è vuoto:
    Lascia che x sia il primo elemento nell'elenco L. Rimuovi x dall'elenco.
    Se B [h1 (x)] è vuoto:
        posizionare x in B [h1 (x)]
    Altrimenti, se B [h2 (x) è vuoto]:
        posizionare x in B [h2 (x)]
    Altro:
        Sia y l'elemento in B [h2 (x)].
        Prependi y a L
        posizionare x in B [h2 (x)]

Implementazione

L'implementazione sembra piuttosto semplice, quindi ho deciso di provarlo e di confrontare quanto spazio / tempo è efficiente rispetto a un filtro bloom. Il filtro Cuculo è costituito da una tabella hash Cuculo che memorizza le "impronte digitali" degli elementi inseriti. L'impronta digitale di un elemento è una stringa di bit derivata dall'hash di quell'elemento. Una tabella di hash del cuculo è composta da una matrice di bucket in cui un elemento da inserire è mappato su due possibili bucket in base a due funzioni di hash. Ogni secchio può essere configurato per memorizzare un numero variabile di impronte digitali. In genere, un filtro a cucù è identificato dall'impronta digitale e dalla dimensione della benna. Ad esempio, un filtro a cucù (2,4) memorizza le impronte digitali della lunghezza di 2 bit e ogni secchio nella tabella hash del cuculo può memorizzare fino a 4 impronte digitali.

Inserimento

Algoritmo:

f = impronta digitale (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
se bucket [i1] o bucket [i2] ha una voce vuota, allora
   aggiungi f a quel secchio;
   reso Fatto;
// deve ricollocare gli articoli esistenti;
i = seleziona casualmente i1 o i2;
per n = 0; n 
// Hashtable è considerato pieno;
reso non riuscito;

Codice:

Ricerca

Algoritmo:

f = impronta digitale (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
se bucket [i1] o bucket [i2] ha f allora
    return True;
restituire False;

Codice:

Elimina

Algoritmo:

f = impronta digitale (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
se bucket [i1] o bucket [i2] ha f allora
   rimuovere una copia di f da questo bucket;
   return True;
restituire False;

Codice:

Test della prestazione

Ho usato la libreria di Will Fitzgerald per il test sul filtro Bloom. Il rapporto FPP (False Positive Probability) preso per il filtro a cucù è 0,001

Complessità spaziale

Per quanto riguarda i filtri a cucù e bloom, si comportano in modo diverso a diverse probabilità di falsi positivi. Quando la probabilità di falsi positivi del filtro è inferiore o uguale al 3%, il filtro a cucù ha meno bit per voce. Quando è maggiore, il filtro bloom ha meno bit per voce.

Complessità temporale

Nell'hash del cuculo, inserire un elemento sembra molto peggio di O (1) nel peggiore dei casi perché potrebbero esserci molti casi durante la collisione, in cui dobbiamo rimuovere un valore per fare spazio al valore corrente. Inoltre, se esiste un ciclo, è necessario ripetere la revisione dell'intera tabella.

Effettuando un'analisi temporale di entrambi i filtri si ottengono i seguenti risultati:

Durante questo esperimento (tenendo presente che il mio codice potrebbe non essere completamente ottimizzato), i filtri Bloom sembrano funzionare eccezionalmente bene nella complessità dello spazio, occupando meno spazio per un gran numero di elementi. Il filtro a cucù sembra funzionare meglio all'inserimento di un gran numero di elementi, ma un po 'più lento nella ricerca (tempi di ricerca) a causa della sua implementazione.

Inferenza

Non vorrei davvero schierarmi su quale filtro raccomandare, penso che entrambi abbiano i loro casi d'uso. I filtri Bloom non supportano le eliminazioni perché l'hashing è in perdita e irreversibile. Sebbene il conteggio dei filtri di fioritura risolva questo problema, i filtri a cucù sono utili nel caso in cui avresti bisogno di eliminazioni. Naturalmente i filtri a cucù generano un errore quando il filtro è pieno, e questo ha i suoi vantaggi, mentre in un filtro Bloom non c'è controllo sulla capacità, si rifà solo sull'array di bit esistente.

Codice

Riferimenti

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

P.S Se trovi qualcosa di sbagliato nei test / implementazione, non esitare a lasciare i tuoi suggerimenti / commenti.