Share
Nel caso d'uso giusto, i filtri Bloom sembrano magici. Questa è un'affermazione audace, ma in questo tutorial esploreremo la curiosa struttura dei dati, il modo migliore di usarlo e alcuni esempi pratici che utilizzano Redis e Node.js.
I filtri Bloom sono una struttura dati probabilistica a senso unico. La parola 'filtro' può essere fonte di confusione in questo contesto; il filtro implica che sia una cosa attiva, un verbo, ma potrebbe essere più semplice pensarla come memoria, un nome. Con un semplice filtro Bloom puoi fare due cose:
Queste sono limitazioni importanti da comprendere: non è possibile rimuovere un elemento né è possibile elencare gli elementi in un filtro Bloom. Inoltre, non puoi dire con certezza se un elemento è stato aggiunto al filtro in passato. È qui che entra in gioco la natura probabilistica di un filtro Bloom: i falsi positivi sono possibili, ma i falsi negativi non lo sono. Se il filtro è impostato correttamente, i falsi positivi possono essere estremamente rari.
Esistono filtri Variants of Bloom e aggiungono altre abilità, come rimozione o ridimensionamento, ma aggiungono anche complessità e limiti. È importante prima capire i filtri Bloom semplici prima di passare alle varianti. Questo articolo riguarderà solo i semplici filtri Bloom.
Con queste limitazioni hai una serie di vantaggi: dimensioni fisse, crittografia basata su hash e ricerche rapide.
Quando imposti un filtro Bloom, gli dai una dimensione. Questa dimensione è fissa, quindi se hai un articolo o un miliardo di elementi nel filtro, non crescerà mai oltre la dimensione specificata. Man mano che aggiungi altri elementi al filtro, aumenta la possibilità di un falso positivo. Se hai specificato un filtro più piccolo, questa percentuale di falsi positivi aumenterà più rapidamente rispetto a una dimensione maggiore.
I filtri Bloom sono basati sul concetto di hashing a senso unico. Proprio come la corretta memorizzazione delle password, i filtri Bloom utilizzano un algoritmo hash per determinare un identificatore univoco per gli elementi passati in esso. Gli hash, per loro natura, non possono essere invertiti e sono rappresentati da una sequenza di caratteri apparentemente casuale. Quindi, se qualcuno ottiene l'accesso a un filtro Bloom, non rivelerà direttamente alcun contenuto.
Infine, i filtri Bloom sono veloci. L'operazione richiede molti meno confronti rispetto ad altri metodi e può essere facilmente archiviata in memoria, impedendo il successo dei database di performance rubando.
Ora che conosci i limiti e i vantaggi dei filtri Bloom, diamo un'occhiata ad alcune situazioni in cui puoi usarli.
Useremo Redis e Node.js per illustrare i filtri Bloom. Redis è un supporto di archiviazione per il filtro Bloom; è veloce, in memoria e ha alcuni comandi specifici (GETBIT, ImpostaBit) che rendono l'implementazione efficiente. Immagino che tu abbia Node.js, npm e Redis installati sul tuo sistema. Il tuo server Redis dovrebbe essere in esecuzione localhost alla porta di default per far funzionare i nostri esempi.
In questo tutorial, non implementeremo un filtro da zero; invece, ci concentreremo su usi pratici con un modulo predefinito in npm: bloom-redis. bloom-redis ha una serie di metodi molto concisa: Inserisci, contiene e chiaro.
Come accennato in precedenza, i filtri Bloom necessitano di un algoritmo di hash per generare identificatori univoci per un articolo. bloom-redis utilizza il noto algoritmo MD5, che, sebbene non sia la soluzione perfetta per un filtro Bloom (un po 'lento, eccessivo sui bit), funzionerà benissimo.
I nomi utente, in particolare quelli che identificano un utente in un URL, devono essere unici. Se si crea un'applicazione che consente agli utenti di modificare il nome utente, è probabile che si desideri un nome utente che lo ha mai stato usato per evitare confusione e sniping di nomi utente.
Senza un filtro Bloom, avresti bisogno di fare riferimento a una tabella in cui ogni username sia mai stato usato, e su scala può essere molto costoso. I filtri Bloom ti consentono di aggiungere un elemento ogni volta che un utente adotta un nuovo nome. Quando un utente controlla se viene utilizzato un nome utente, tutto ciò che devi fare è controllare il filtro Bloom. Sarà in grado di dirti, con assoluta certezza, se il nome utente richiesto è stato precedentemente aggiunto. È possibile che il filtro restituisca erroneamente che un nome utente è stato utilizzato quando non è stato utilizzato, ma questo errore va dalla parte della cautela e non può causare alcun danno reale (a parte un utente potrebbe non essere in grado di rivendicare 'k3w1d00d47').
Per illustrare questo, costruiamo un rapido server REST con Express. In primo luogo, crea il tuo package.json file e quindi eseguire i seguenti comandi del terminale.
npm install bloom-redis --save
npm install express --save
npm install redis --save
Le opzioni predefinite per bloom-redis hanno la dimensione impostata a due megabyte. Questo va dalla parte della cautela, ma è piuttosto grande. L'impostazione della dimensione del filtro Bloom è fondamentale: troppo grande e sprechi memoria, troppo piccola e il tuo tasso di falsi positivi sarà troppo alto. La matematica coinvolta nel determinare la dimensione è abbastanza coinvolta e va oltre lo scopo di questo tutorial, ma per fortuna c'è un calcolatore delle dimensioni del filtro Bloom per fare il lavoro senza scomporre un libro di testo.
Ora crea il tuo app.js come segue:
"javascript var Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
app, client, filtro;
// imposta il nostro Express server app = express ();
// crea la connessione a Redis client = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, // assicurati che il modulo Bloom utilizzi la nostra connessione appena creata alla chiave Redis: 'username-bloom-filter', // la chiave di Redis
// dimensione calcolata del filtro Bloom. // Questo è il punto in cui vengono effettuate le compensazioni di dimensione / probabilità //http://hur.st/bloomfilter?n=100000&p=1.0E-6 dimensioni: 2875518, // ~ 350kb numHashes: 20);
app.get ('/ check', function (req, res, next) // verifica che la stringa di query abbia 'username' if (typeof req.query.username === 'undefined') // skip questa rotta, passa a quella successiva - comporterà un 404 / non trovato dopo ('route'); else filter.contains (req.query.username, // il nome utente dalla funzione stringa di query (err, risultato ) if (err) next (err); // se si verifica un errore, inviarlo al client else res.send (username: req.query.username, // se il risultato è falso, quindi sappiamo che l'oggetto ha non stato usato // se il risultato è vero, allora possiamo supporre che l'oggetto sia stato utilizzato: risultato? 'used': 'free'); ); );
app.get ('/ save', function (req, res, next) if (typeof req.query.username === 'undefined') next ('route'); else // prima, abbiamo bisogno per assicurarsi che non sia ancora nel filtro filter.contains (req.query.username, function (err, result) if (err) next (err); else if (result) // true result significa esiste già, quindi informa l'utente res.send (username: req.query.username, status: 'not-created'); else // aggiungeremo il nome utente passato nella stringa di query al filtro filter.add (req.query.username, function (err) // Gli argomenti di callback a Inserisci non fornisce alcuna informazione utile, quindi controlleremo solo che non sia stato superato alcun errore se (err) next (err); else res.send (username: req.query.username, status: 'created'); ); ); );
app.listen (8010);"
Per eseguire questo server: nodo app.js. Vai al tuo browser e puntalo a: https: // localhost: 8010 / check username = kyle. La risposta dovrebbe essere: "Nome utente": "Kyle", "status": "libero".
Ora, salviamo il nome utente puntando il tuo browser su http: // localhost: 8010 / save username = kyle. La risposta sarà: "Nome utente": "Kyle", "status": "creata". Se torni all'indirizzo http: // localhost: 8010 / check username = kyle, la risposta sarà "Nome utente": "Kyle", "status": "usato". Allo stesso modo, tornando a http: // localhost: 8010 / save username = kyle risulterà in "Nome utente": "Kyle", "stato": "non-creato".
Dal terminale, puoi vedere la dimensione del filtro: redis-cli strlen nomeutente-filtro-fioritura.
In questo momento, con un oggetto, dovrebbe mostrare 338622.
Adesso vai avanti e prova ad aggiungere altri nomi utente con /salvare itinerario. Prova tutti quelli che desideri.
Se quindi si verifica nuovamente la dimensione, è possibile notare che le dimensioni sono leggermente aumentate, ma non per ogni aggiunta. Curioso, giusto? Internamente, un filtro Bloom imposta bit individuali (1/0) in posizioni diverse nella stringa salvata su username-bloom. Tuttavia, questi non sono contigui, quindi se si imposta un bit all'indice 0 e quindi uno all'indice 10.000, tutto tra 0 sarà 0. Per gli usi pratici, inizialmente non è importante capire la meccanica precisa di ogni operazione, basta sapere che questo è normale e il tuo spazio di archiviazione in Redis non supererà mai il valore specificato.
Il contenuto fresco di un sito web fa sì che un utente torni indietro, quindi come fai a mostrare all'utente ogni volta qualcosa di nuovo? Utilizzando un approccio basato su un database tradizionale, è possibile aggiungere una nuova riga a una tabella con l'identificativo utente e l'identificatore della storia, quindi si invierà la query su tale tabella al momento di decidere di mostrare una parte di contenuto. Come puoi immaginare, il tuo database crescerà molto rapidamente, specialmente con la crescita di utenti e contenuti.
In questo caso, un falso negativo (ad esempio non mostrare un pezzo di contenuto non visto) ha conseguenze limitate, rendendo i filtri Bloom un'opzione praticabile. A prima vista, potresti pensare che avresti bisogno di un filtro Bloom per ogni utente, ma useremo una semplice concatenazione dell'identificatore utente e dell'identificatore del contenuto, e quindi inseriremo quella stringa nel nostro filtro. In questo modo possiamo utilizzare un unico filtro per tutti gli utenti.
In questo esempio, creiamo un altro server Express di base che mostri il contenuto. Ogni volta che visiti il percorso / Show-content / qualsiasi-username (con qualsiasi-username essendo un valore sicuro per l'URL), verrà mostrato un nuovo contenuto finché il sito non sarà esaurito. Nell'esempio, il contenuto è la prima riga dei primi dieci libri su Project Gutenberg.
Dovremo installare un altro modulo npm. Dal terminale, eseguire: npm install async --save
Il tuo nuovo file app.js:
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
app, client, filtro,
// Da Project Gutenberg - linee di apertura dei primi 10 ebooks di dominio pubblico // https://www.gutenberg.org/browse/scores/top openingLines = 'orgoglio-e-pregiudizio': 'È una verità universalmente riconosciuta , che un uomo solo in possesso di una buona fortuna, deve essere nel bisogno di una moglie. ',' Alice-avventure-nel-paese delle meraviglie ':' Alice stava cominciando a stancarsi di sedersi vicino alla sorella sulla riva, e di non aver niente da fare: una o due volte aveva sbirciato nel libro che sua sorella stava leggendo, ma non aveva immagini o conversazioni al suo interno, "e a che cosa serve un libro", pensò Alice "senza immagini o conversazioni?" , 'a-christmas-carol': 'Marley era morto: per cominciare', 'metamorfosi': 'Una mattina, quando Gregor Samsa si svegliò da sogni inquieti, si ritrovò trasformato nel suo letto in un orribile parassita.', 'frankenstein': 'Ti rallegri di sentire che nessun disastro ha accompagnato l'inizio di un'impresa che hai considerato con tali malvagi presagi.', 'adventur es-of-huckleberry-finn ':' TU non conosci me senza aver letto un libro di nome The Adventures of Tom Sawyer; ma non è questo il caso. ',' avventure-di-sherlock-holmes ':' Per Sherlock Holmes è sempre la donna ',' narrativa-della-vita-di-frederick-douglass ':' I è nato a Tuckahoe, vicino a Hillsborough, a circa dodici miglia da Easton, nella contea di Talbot, nel Maryland. "," il principe ":" Tutti gli stati, tutti i poteri, che hanno tenuto e tengono il potere sugli uomini sono stati e sono o repubbliche o principati. ',' avventure-di-tom-sawyer ':' TOM! ' ;
app = express (); client = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, chiave: '3content-bloom-filter', // la dimensione della chiave di Redis: 2875518, // ~ 350kb // size: 1024, numHashes: 20);
app.get ('/ show-content /: user', function (req, res, next) // stiamo andando in loop attraverso il contentIds, controllando per vedere se sono nel filtro. // Poiché questo passa il tempo su ogni contenuto Non sarebbe consigliabile fare un numero elevato di contentIds // Ma, in questo caso il numero di contentIds è piccolo / fisso e la nostra funzione filter.contains è veloce, va bene. var // crea una matrice delle chiavi definite in openingLines contentIds = Object.keys (openingLines), // ottenendo parte del percorso dall'utente URI = req.params.user, checkingContentId, found = false, done = false;
// poiché filter.contains è asincrono, stiamo usando la libreria async per eseguire il nostro ciclo async.whilst (// check function, dove il nostro ciclo asincrono terminerà function () return (! found &&! done);, function (cb) // ottiene il primo elemento dall'array di contentIds checkingContentId = contentIds.shift ();
Accentsconagua
// false significa che siamo sicuri che non si trovi nel filtro se (! checkingContentId) done = true; // questo sarà catturato dalla funzione di controllo sopra cb (); else // concatena l'utente (dall'URL) con l'id del contenuto filter.contains (user + checkingContentId, function (err, results) if (err) cb (err); else found =! risultati; cb ();); , function (err) if (err) next (err); else if (openingLines [checkingContentId]) // prima di inviare il nuovo contenutoId, aggiungiamolo al filtro per impedirgli di mostrare di nuovo filter.add (user + checkingContentId, function (err) if (err) next (err); else // invia la nuova citazione res.send (openingLines [checkingContentId]);); else res.send ('no nuovo contenuto!'); ); ); app.listen (8011);"
Se presti attenzione al tempo di andata e ritorno in Dev Tools, noterai che più richiedi un singolo percorso con un nome utente, più tempo è necessario. Durante la verifica del filtro richiede un tempo fisso, in questo esempio, stiamo controllando la presenza di più elementi. I filtri Bloom sono limitati in ciò che possono dirti, quindi stai testando la presenza di ciascun elemento. Naturalmente, nel nostro esempio è abbastanza semplice, ma testare centinaia di articoli sarebbe inefficiente.
In questo esempio, costruiremo un piccolo server Express che farà due cose: accettare nuovi dati tramite POST e visualizzare i dati correnti (con una richiesta GET). Quando i nuovi dati vengono POST sul server, l'applicazione controllerà la sua presenza nel filtro. Se non è presente, lo aggiungeremo a un set in Redis, altrimenti restituiremo null. La richiesta GET lo preleverà da Redis e lo invierà al client.
Questo è diverso rispetto alle precedenti due situazioni, in quanto i falsi positivi non andrebbero bene. Useremo il filtro Bloom come prima linea di difesa. Date le proprietà dei filtri Bloom, sapremo solo con certezza che qualcosa non è nel filtro, quindi in questo caso possiamo andare avanti e lasciare entrare i dati. Se il filtro Bloom restituisce che è probabilmente nel filtro, noi fare un controllo rispetto all'origine dati effettiva.
Quindi, cosa guadagniamo? Otteniamo la velocità di non dover controllare contro la fonte effettiva ogni volta. In situazioni in cui l'origine dei dati è lenta (API esterne, database pokey, metà di un file flat), l'aumento della velocità è davvero necessario. Per dimostrare la velocità, aggiungiamo un ritardo realistico di 150 ms nel nostro esempio. Useremo anche il console.time / console.timeEnd per registrare le differenze tra un controllo del filtro Bloom e un controllo del filtro non Bloom.
In questo esempio, utilizzeremo anche un numero estremamente limitato di bit: solo 1024. Si riempirà rapidamente. Mentre si riempie, mostrerà sempre più falsi positivi - vedrai aumentare il tempo di risposta quando il tasso di falsi positivi si riempie.
Questo server utilizza gli stessi moduli di prima, quindi imposta il app.js file in:
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), bodyParser = require ('body-parser'), express = require ('express'), redis = require ('redis' ),
app, client, filtro,
currentDataKey = 'current-data', usedDataKey = 'used-data';
app = express (); client = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, chiave: 'stale-bloom-filter', // a scopo illustrativo, questo è un filtro super piccolo che dovrebbe riempire circa 500 articoli, quindi per un carico di produzione, avresti bisogno di qualcosa di molto più grande! size: 1024, numHashes: 20);
app.post ('/', bodyParser.text (), function (req, res, next) var used;
console.log ('POST -', req.body); // registra i dati correnti che vengono pubblicati in console.time ('post'); // inizia a misurare il tempo necessario per completare il nostro filtro e il processo di verifica condizionale //async.series viene utilizzato per gestire più chiamate di funzioni asincrone. async.series ([function (cb) filter.contains (req.body, function (err, filterStatus) if (err) cb (err); else used = filterStatus; cb (err);) ;, function (cb) if (usato === false) // I filtri Bloom non hanno falsi negativi, quindi non abbiamo bisogno di ulteriori verifiche cb (null); else // it * may * essere nel filtro, quindi dobbiamo eseguire un controllo di follow-up // per gli scopi del tutorial, aggiungeremo un ritardo di 150 ms qui poiché Redis può essere abbastanza veloce da rendere difficile la misurazione e il ritardo simula un database lento o Chiamata API setTimeout (function () console.log ('possible falso positivo'); client.sismember (usedDataKey, req.body, function (err, membership) if (err) cb (err); else / / sismember restituisce 0 se un membro non fa parte del set e 1 se lo è. // Questo trasforma quei risultati in booleani per il confronto logico coerente usato = membership === 0? false: true; cb (err); );, 150);, function (cb) if (usato === false) console.log ('Aggiungi al filtro'); filter.a dd (req.body, cb); else console.log ('Aggiunta filtro saltata, [falso] positivo'); cb (null); , function (cb) if (used === false) client.multi () .set (currentDataKey, req.body) // i dati non utilizzati sono impostati per un facile accesso alla chiave 'current-data' .sadd (usedDataKey, req.body) // e aggiunto a un set per una facile verifica successiva .exec (cb); else cb (null); ], function (err, cb) if (err) next (err); else console.timeEnd ('post'); // registra la quantità di tempo trascorso dalla chiamata a console.time sopra res.send (saved:! used); // restituisce se l'elemento è stato salvato, true per i nuovi dati, false per i dati non aggiornati. ); ); app.get ('/', function (req, res, next) // restituisce appena i nuovi dati client.get (currentDataKey, function (err, data) if (err) next (err); else res.send (dati);););
app.listen (8012);"
Dal momento che il POST di un server può essere complicato con un browser, usiamo il ricciolo per testare.
curl --data "i tuoi dati vanno qui" --header "Content-Type: text / plain" http: // localhost: 8012 /
È possibile utilizzare un rapido script bash per mostrare come riempire l'intero aspetto del filtro:
bash #! / bin / bash per i in 'seq 1 500'; do curl --data "data $ i" --header "Content-Type: text / plain" http: // localhost: 8012 / done
Guardare un riempimento o un filtro completo è interessante. Dal momento che questo è piccolo, puoi facilmente vederlo con Redis-cli. Correndo redis-cli ottiene il filtro stantio dal terminale tra l'aggiunta di elementi, vedrai aumentare i singoli byte. Un filtro completo sarà \ XFF per ogni byte. A questo punto, il filtro tornerà sempre positivo.
I filtri Bloom non sono una soluzione di panacea, ma nella giusta situazione, un filtro Bloom può fornire un complemento rapido ed efficiente ad altre strutture di dati.
