Filtro Bloom o cuckoo hashing?

Question

Quale preferisci e perché?

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

Answer 1

Preferisco l'hashing del cuculo. Sono diffidente nei 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 molto grandi e stavamo riscontrando problemi di pressione della memoria. Si prega di consultare la mia libreria eCollections al http://codeplex.com/ecollections per l'implementazione di una variante di hashing del cuculo.

saluti,

Answer 2

Se posso tollerare i falsi positivi e spazio è critica, utilizzare un filtro Bloom perché richiede meno spazio. Altrimenti, uso un hash.

Answer 3

Quale preferisci, vino o formaggio?

Un filtro fioritura è per quando si dispone di spazio limitato , alta interrogazione costo, e query per lo più negativi.
In tal caso, un filtro fioritura con 8 bit per chiave e 4 funzioni hash si dà 2,5% tasso di falsi positivi; l'elaborazione delle query è quasi uguale a 40 volte più veloce rispetto a prima, al costo di 1 byte per chiave.

D'altra parte, se una qualsiasi delle condizioni precedenti non sono titolari, un tavolo hash che agisce come una cache ha un senso, anche se ovviamente ci vorrà molto più di un byte per ogni voce: -)

È possibile saltare anche le casse hard di cuckoo hashing se si tratta di un cache. Ciò rende anche i problemi di aumento delle dimensioni delle tabelle di hash di cuculo (o qualcosa di diverso dall'hash lineare).

Answer 4

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 dei degli autori blog:

Permettetemi di descrivere un filtro cuculo e un po 'di ciò che è nella carta per voi . Se vuoi evitare una discussione tecnica, tutto quello che devi sapere è che per set di dimensioni ragionevolmente grandi, con lo stesso tasso di falsi positivi di un filtro Bloom corrispondente, i filtri a cucù usano meno spazio dei filtri Bloom, sono più veloci nelle ricerche (ma più lenti su inserzioni/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 github repository per te con il codice per i filtri cucù.

Answer 5

I filtri Bloom ed i filtri Cuckoo sono utilizzati 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 nei motori di database, 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 oggi sarebbe 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 è che i filtri Bloom e Cuckoo 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.

Notevoli differenze tra cuculo/Bloom 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.

• False 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 articolo all'interno di un bucket per archiviare le impronte digitali più piccole. Le librerie aggiuntive che menzionerò più avanti (inclusa la mia) non sembrano farlo. Se qualcuno usa la mia libreria, potrei aggiungerla :).

• Tasso di falsi positivi costante. 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 utilizza varie funzioni di hashing per i filtri Bloom e Cuckoo. Guava Bloom di Google utilizza Murmur3, molte altre implementazioni utilizzano 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 vecchi elementi. Nota che la ricostruzione del filtro avviene ancora con i filtri Cuckoo quando gli inserti iniziano a fallire, quindi a seconda del caso d'uso questo potrebbe essere discutibile. In determinate 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 Cuckoo sono librerie nuove e stabili per molte lingue semplicemente non esistono.

Il più grande vantaggio dei filtri Bloom è che hanno un supporto di libreria 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 vergognoso: sono lo sviluppatore di una libreria di filtri Cuckoo per Java. . Manca il semi-ordinamento del secchio usato nella carta, quindi 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.

Si dovrebbe assolutamente dare un'occhiata alla fonte prima 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 Google Guava Bloom ha avuto la migliore qualità e test di codice (e supporta i limiti dell'array a 64 bit). Le uniche imperfezioni con Guava's Bloom è che non ha la possibilità di utilizzare una funzione di hash sicura e non è multi-thread.

In un sistema di produzione si potrebbe desiderare il multi-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 il threading simultaneo alla mia libreria di filtri Cuckoo. L'altro di cui sono a conoscenza non è thread-safe o non è concorrente.