/ / Filtro della fioritura o hashing del cuculo? - algoritmo, hash, filtro

Filtro Bloom o hashing cucù? - algoritmo, hash, filtro

Quale preferisci e perchè?

Entrambi possono essere utilizzati per svolgere compiti simili, ma sono curioso di vedere cosa le persone hanno utilizzato nelle applicazioni reali e il loro ragionamento per farlo.

risposte:

9 per risposta № 1

I filtri Bloom ed i filtri Cuckoo sono usati in situazioni simili ma ci sono molte differenze al di sotto che di solito determinano quale sia una scelta migliore.

I filtri Bloom sono utilizzati internamente nel databasemotori, in particolare Apache Cassandra. Le ragioni sono come hanno detto altri manifesti, per ridurre il costo delle operazioni di set lento. Fondamentalmente, qualsiasi operazione "questo è forse o sicuramente non esiste" con un costo elevato può utilizzare un filtro Bloom per ridurre il numero di controlli effettuati.

Un altro esempio comune con il modello SaaS di oggisarebbe un servizio REST remoto con un costo per chiamata. Qualsiasi chiamata API con una risposta binaria come "questo indirizzo NON VALIDO" può utilizzare un filtro "bloom" per eliminare oltre il 90% delle query duplicate! Si noti che poiché i filtri Bloom e Cuckoo hanno falsi positivi NON sono utili per l'operazione inversa "è questo indirizzo VALID"

Importante da ricordare è Bloom and Cuckooi filtri non hanno falsi negativi. Questo rende questi filtri utili per verifiche come "questo non è sicuramente o forse spam" ma non è utile per operazioni in cui i falsi positivi sono inaccettabili, come il controllo delle autorizzazioni dell'utente. In questo aspetto possono essere concettualmente considerati l'opposto di una cache. Entrambi i filtri e le cache di Bloom / Cuckoo vengono utilizzati principalmente per ridurre il costo delle operazioni costose con una risposta booleana, ad eccezione delle cache che non hanno falsi positivi e Bloom / Cuckoo non hanno falsi negativi.

Le differenze notevoli tra cuculo / fiore includono:

  • Combinazione. I filtri Bloom possono essere fusi in modo efficiente a condizione che vengano creati con gli stessi parametri. Sia rapidamente che con poca larghezza di banda. Questo è il motivo per cui li vedi usati frequentemente in sistemi ampiamente distribuiti, lo scambio di filtri Bloom è veloce. I filtri a cucù non sono facilmente componibili, rendendoli meno utili in queste circostanze.

  • Falso tasso positivo. I filtri a cucù sono più efficienti in termini di spazio. Molti casi d'uso per entrambe le strutture sono focalizzati su reti di basso livello. Su hardware debole, l'efficienza del ~ 40% più alta dei filtri Cuckoo per lo stesso tasso di falsi positivi può essere importante. L'implementazione di riferimento, in c ++, ordina gli elementi all'interno di ciascun bucket per ulteriori risparmi di spazio, sfruttando la posizione di un oggetto all'interno di un bucket per archiviare impronte più piccole.Le librerie aggiuntive che menzionerò più avanti (compresa la mia) non sembrano fai questo: se qualcuno usa la mia libreria, potrei aggiungerla :)

  • Costante tasso di falsi positivi. I filtri Bloom hanno tassi di falsi positivi asintoticamente peggiori in quanto superano le dimensioni progettate. Puoi continuare a inserire oggetti per sempre, ma alla fine il tuo tasso di falsi positivi sarà quasi del 100%. I filtri Cuckoo, essendo basati sull'hash Cuckoo, hanno una capacità impostata in cui gli inserimenti falliranno effettivamente. L'inserimento ripetuto di hash item non casuali può causare l'impossibilità di inserimento dei filtri Cuckoo, probabilmente molto prima del loro livello di riempimento progettato.

  • Velocità. Questo è soggettivo e dipende molto dall'hardware, ma i filtri Cuckoo sono generalmente più veloci nel caso medio (nella mia esperienza). La maggior parte dei progetti di filtri Bloom esegue una funzione hash due volte. Soprattutto quando si usano le funzioni di hash sicure, questo può essere un grosso handicap rispetto ai filtri Cuckoo che solo una volta ha inserito gli oggetti. Il codice che ho visto usa varie funzioni di hashing per i filtri Bloom e Cuckoo. Guava Bloom di Google usa Murmur3, molte altre implementazioni usano SHA1 o qualcos'altro. Se le collisioni di hash possono essere sfruttate per il tuo caso d'uso, assicurati che la libreria utilizzi un hash sicuro. È importante sapere che i filtri Bloom richiedono un tempo approssimativamente costante per l'inserimento mentre i filtri Cuckoo hanno un caso MEDIO costante. Poiché i filtri Cuckoo raggiungono una percentuale minima della capacità, le velocità di inserimento rallentano notevolmente. Anche in questo caso, solo la velocità di inserimento rallenta, tutte le altre operazioni sono costanti nel tempo medio.

  • Flessibilità. I filtri Bloom supportano solo l'inserimento e contengono. I filtri cucù supportano inoltre la cancellazione e il conteggio limitato. Nel progetto di riferimento, i filtri Cuckoo possono determinare quante volte è stato inserito un oggetto, fino a 7 volte. I filtri Bloom possono solo determinare si-no. I filtri Cuckoo supportano anche l'eliminazione degli oggetti inseriti, un grande vantaggio in molti casi d'uso rispetto a Bloom. Quando si utilizzano i filtri Bloom, è piuttosto normale ricreare il filtro da zero quando è "pieno" (la percentuale stimata di falsi positivi supera la soglia) poiché non è possibile eliminare i vecchi elementi. Si noti che la ricostruzione del filtro avviene ancora con i filtri Cuckoo quando si inseriscono iniziare a fallire, quindi a seconda del caso d'uso questo potrebbe essere discutibile. In certe situazioni i filtri cucù sono più utili in quanto è possibile eliminare gli elementi per rimanere entro i limiti del filtro invece di ricostruire.

  • Supporto. I filtri a cucù sono librerie nuove e stabili per molte lingue semplicemente non esistono.

Il più grande vantaggio dei filtri Bloom è quellohanno un supporto bibliotecario più maturo nella maggior parte delle lingue. La matematica dietro i filtri Bloom è anche meglio compresa dagli scienziati. La maggior parte delle caratteristiche dei filtri Cuckoo è stata determinata empiricamente, mentre i filtri Bloom hanno una solida base numerica. Ciò esclude i filtri Cuckoo per i sistemi in tempo reale e quelli critici che devono avere la verifica delle loro prestazioni, anche se prove sperimentali mostrano che i filtri Cuckoo funzionano meglio nella maggior parte delle circostanze.

Plug Shameless: sono lo sviluppatore di una libreria di filtri Cuckoo per Java. CuckooFilter4J . Manca il semi-ordinamento del secchio usato nelcarta così l'efficienza dello spazio è leggermente inferiore all'implementazione di riferimento. Nel readme del progetto ho collegamenti ad altre implementazioni di cui sono a conoscenza. Quale struttura è migliore dipende dal tuo caso d'uso, ma soprattutto se esiste una solida implementazione del filtro Cuckoo per la tua lingua.

Dovresti assolutamente dare un'occhiata alla fonteprima di utilizzare un filtro Cuckoo / Bloom in produzione. Ho letto varie librerie prima di scrivere le mie ... molti di loro avevano limiti di dimensione silenziosi a causa di array sottostanti a 32 bit o problemi di prestazioni evidenti. La maggior parte ha avuto zero test. L'implementazione di Guava Bloom di Google ha avuto la migliore qualità e test di codice (e supporta i limiti dell'array a 64 bit). Le uniche lacune con Guava "s Bloom è che non ha la possibilità di utilizzare una funzione di hash sicura e isn" t multi-threaded.

In un sistema di produzione che potresti desideraremulti-threading per la velocità. La risposta per Guava's Bloom consiste nel creare un filtro diverso per ogni thread e combinarli occasionalmente poiché i filtri Cuckoo non possono essere combinati, ho aggiunto threading simultaneo alla mia libreria di filtri Cuckoo. L'altro è a conoscenza del fatto che non è sicuro o non è concatenato.


8 per risposta № 2

Quale preferisci, vino o formaggio?

UN filtro di fioritura è per quando hai spazio limitato, costo elevato per le query, e domande prevalentemente negative.
In tal caso, a filtro di fioritura con 8 bit per chiave e 4 funzioni di hash ti dà Tasso di falsi positivi del 2,5%; si elaborano le query quasi 40 volte più veloce di prima, al costo di 1 byte per chiave.

D'altra parte, se qualcuno dei le condizioni precedenti non reggono, a tabella hash che funge da cache ha senso, anche se ovviamente occorrerà un Molto più di un byte per voce :-)

Puoi anche saltare i casi di hard edge di cuckoo hashing se è una cache, questo fa anche aumentare i problemi di aumento delle dimensioni tavoli di hash cucù (o qualcosa di diverso dall'hash lineare) moot.


5 per risposta № 3

Filtro a cucù.

"Cuckoo Filter: Praticamente migliore di Bloom." Bin Fan, David Andersen, Michael Kaminsky, Michael Mitzenmacher CoNext 2014. http://dx.doi.org/10.1145/2674005.2674994

Da uno degli autori " blog:

Lasciatemi descrivere un filtro a cucù e alcuni di questiCosa c'è nella carta per te Se vuoi evitare una discussione tecnica, tutto quello che devi sapere è che per set di dimensioni ragionevolmente grandi, per lo stesso tasso di falsi positivi di un filtro Bloom corrispondente, i filtri a cucù usano meno spazio di Bloom filtri, sono più veloci nelle ricerche (ma più lenti sugli inserimenti / per costruire), e incredibilmente permettono anche la cancellazione di chiavi (che i filtri Bloom non possono fare). Se vuoi guardare il codice, c'è anche un repository github per te con il codice per i filtri cucù.


2 per risposta № 4

Preferisco l'hashing del cuculo. Sono diffidente nei confronti dei falsi positivi che possono presentarsi con filtri di fioritura a fattori di riempimento più elevati.
Ho usato l'hashing del cuculo in un'applicazione in cui disponevamo di tabelle hash di grandi dimensioni e abbiamo riscontrato problemi di pressione della memoria. Si prega di consultare la mia libreria eCollections all'indirizzo http://codeplex.com/ecollections per l'implementazione di una variante dell'hash cuculo.

Cordiali saluti,


0 per risposta № 5

Se riesco a tollerare i falsi positivi e lo spazio è fondamentale, utilizzo un filtro Bloom perché richiede meno spazio. Altrimenti, uso un hash.