Share
În cazul de utilizare potrivit, filtrele Bloom par a fi magice. Aceasta este o afirmație îndrăzneață, dar în acest tutorial vom explora structura curioasă a datelor, cât de bine să o folosim și câteva exemple practice folosind Redis și Node.js.
Filtrele Bloom sunt o structură probabilistică, într-o singură direcție. Cuvântul "filtru" poate fi confuz în acest context; filtru implică faptul că este un lucru activ, un verb, dar ar putea fi mai ușor să-l gândiți la acesta ca la un depozit, un substantiv. Cu un filtru simplu Bloom puteți face două lucruri:
Acestea sunt limitări importante pentru a înțelege - nu puteți elimina un element și nici nu puteți să listați elementele dintr-un filtru Bloom. De asemenea, nu puteți spune, cu certitudine, dacă un element a fost adăugat în filtru în trecut. Aici este posibilă natura probabilistică a unui filtru Bloom - false posibile sunt posibile, dar nu sunt false. Dacă filtrul este configurat corect, pozițiile false pot fi extrem de rare.
Există variante ale filtrelor Bloom și adaugă alte abilități, cum ar fi îndepărtarea sau scalarea, dar ele adaugă, de asemenea, complexități și limitări. Este important să înțelegeți mai întâi filtrele Bloom simple înainte de a trece la variante. Acest articol va acoperi doar filtrele Bloom simple.
Cu aceste limitări aveți mai multe avantaje: dimensiune fixă, criptare bazată pe hash și căutări rapide.
Când configurați un filtru Bloom, îi dați o dimensiune. Această dimensiune este fixă, deci dacă aveți un element sau un miliard de elemente în filtru, acesta nu va crește niciodată peste dimensiunea specificată. Pe măsură ce adăugați mai multe elemente la filtru, crește șansa de creștere a valorii false. Dacă ați specificat un filtru mai mic, această rată fals pozitivă va crește mai repede decât dacă aveți o dimensiune mai mare.
Filtrele Bloom sunt construite pe conceptul de hașurare cu sens unic. La fel ca păstrarea corectă a parolelor, filtrele Bloom utilizează un algoritm hash pentru a determina un identificator unic pentru elementele transmise în el. Hashes, prin natura lor, nu pot fi inversate și sunt reprezentate de un șir de caractere aparent aleatorii. Deci, dacă cineva obține acces la un filtru Bloom, acesta nu va dezvălui direct conținutul.
În cele din urmă, filtrele Bloom sunt rapide. Operația implică comparații mult mai puține decât alte metode și poate fi stocată cu ușurință în memorie, împiedicând loviturile bazei de date.
Acum că știți limitele și avantajele filtrelor Bloom, să aruncăm o privire asupra unor situații în care le puteți folosi.
Vom folosi Redis și Node.js pentru a ilustra filtrele Bloom. Redis este un mediu de stocare pentru filtrul dvs. Bloom; este rapid, în memorie și are câteva comenzi specifice (GETBIT, SETBIT) care fac implementarea eficientă. Voi presupune că aveți Node.js, npm și Redis instalate pe sistemul dvs. Serverul dvs. Redis trebuie să funcționeze gazdă locală la portul implicit pentru ca exemplele noastre să funcționeze.
În acest tutorial, nu vom implementa un filtru de la bază; în schimb, ne vom concentra pe utilizări practice cu un modul pre-construit în npm: bloom-redis. bloom-redis are un set foarte complex de metode: adăuga, conține și clar.
Așa cum am menționat mai devreme, filtrele Bloom au nevoie de un algoritm de hashing pentru identificatorii unici generați pentru un element. bloom-redis folosește bine-cunoscutul algoritm MD5, care, deși nu poate fi perfect potrivit pentru un filtru Bloom (un pic lent, overkill pe biți), va funcționa bine.
Numele de utilizator, mai ales cele care identifică un utilizator într-o adresă URL, trebuie să fie unice. Dacă construiți o aplicație care permite utilizatorilor să schimbe numele de utilizator, atunci veți dori probabil un nume de utilizator care are nu a fost folosit pentru a evita confuzia și confruntarea cu numele de utilizator.
Fără un filtru Bloom, va trebui să faceți referire la un tabel care are fiecare nume de utilizator folosit vreodată și la scară, acest lucru poate fi foarte costisitor. Filtrele Bloom vă permit să adăugați un element de fiecare dată când un utilizator adoptă un nume nou. Când un utilizator verifică dacă un nume de utilizator este luat, tot ce trebuie să faceți este să verificați filtrul Bloom. Va fi capabil să vă spună, cu certitudine absolută, dacă numele de utilizator solicitat a fost adăugat anterior. Este posibil ca filtrul să se întoarcă în mod fals că un nume de utilizator a fost folosit atunci când nu a fost folosit, dar acest lucru se întâmplă eronat de prudență și nu poate provoca răniri reale (în afară de faptul că un utilizator nu poate să pretindă "k3w1d00d47").
Pentru a ilustra acest lucru, să construim un server REST rapid cu Express. Mai întâi, creați-vă package.json fișier și apoi executați următoarele comenzi terminale.
npm install bloom-redis - salvați
npm install express - salvați
npm install redis - salvează
Opțiunile implicite pentru bloom-redis au dimensiunea stabilită la doi megabytes. Acest lucru este greșit de prudență, dar este destul de mare. Configurarea dimensiunii filtrului Bloom este critică: prea mare și pierdeți memoria, prea mică și rata fals pozitivă va fi prea mare. Matematica implicată în determinarea mărimii este destul de implicată și dincolo de scopul acestui tutorial, dar din fericire există un calculator de dimensiune a filtrului Bloom pentru a obține treaba fără a sparge un manual.
Acum, creați-vă app.js după cum urmează:
"javascript var Bloom = necesită (" bloom-redis "), express = necesită (" expres "), redis =,
aplicație, client, filtru;
// configurați serverul Express Express app = express ();
// crea conexiunea la client Redis = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, // asigurați-vă că modulul Bloom folosește noua conexiune creată la tasta Redis: 'username-bloom-filter', // tasta Redis
// dimensiunea calculată a filtrului Bloom. // Aici se fac compromisurile de mărime / probabilitate //http://hur.st/bloomfilter?n=100000&p=1.0E-6 dimensiune: 2875518, // ~ 350kb numHashes: 20);
app.get ('/ check', funcția (req, res, următorul) // verificați dacă șirul de interogare are 'username' dacă typeof req.query.username === 'undefined') // skip această rută, du-te la următoarea - va rezulta într-un 404 / nu găsită următor ('rută'); altceva filter.contains (req.query.username, // numele de utilizator din funcția șir de interogare ) if (err) next (err); // dacă se întâlnește o eroare, trimiteți-o clientului altceva res.send (username: req.query.username, știm că elementul are nu a fost utilizat // dacă rezultatul este adevărat, atunci putem presupune că elementul a fost folosit stare: rezultat? "folosit": "gratuit"); ); );
app.get ('/ save', functie (req, res, urmatoarea) if (typeof req.query.username === 'undefined') next ('route'); pentru a vă asigura că nu este încă în filtrul filter.contains (req.query.username, funcția (err, rezultat) if (err) next (err); else if (rezultat) acesta există deja, deci spuneți utilizatorului res.send (username: req.query.username, status: 'not-created'); altceva // vom adăuga numele de utilizator trecut în șirul de interogare la filtru filter.add (req.query.username, function (err) // Argumentele de apel invers la adăuga nu oferă informații utile, așa că vom verifica dacă nu s-a făcut nici o eroare dacă (err) next (err); altceva res.send (username: req.query.username, status: 'creat'); ); ); );
app.listen (8010);“
Pentru a rula acest server: nod app.js. Accesați browserul dvs. și indicați-l la: https: // localhost: 8010 / verifica numele de utilizator = kyle. Răspunsul ar trebui să fie: "Username": "Kyle", "statut": "liber".
Acum, să salvăm acest nume de utilizator indicând browserul dvs. la http: // localhost: 8010 / salveze numele de utilizator = kyle. Răspunsul va fi: "Username": "Kyle", "statut": "creat". Dacă te întorci la adresa http: // localhost: 8010 / verifica numele de utilizator = kyle, răspunsul va fi "Username": "kyle", "stare": "folosit". În mod similar, revenind la http: // localhost: 8010 / salveze numele de utilizator = kyle va avea ca rezultat "Username": "Kyle", "statut": "nu-creat".
Din terminal, puteți vedea dimensiunea filtrului: redis-cli strlen username-bloom-filtru.
Chiar acum, cu un singur element, ar trebui să arate 338622.
Acum, mergeți mai departe și încercați să adăugați mai multe nume de utilizator cu /Salvați traseu. Încearcă cât vrei.
Dacă apoi verificați dimensiunea din nou, este posibil să observați că dimensiunea dvs. a crescut ușor, dar nu pentru fiecare adăugare. Curios, nu? Pe plan intern, un filtru Bloom stabilește biți individuali (1's / 0's) în poziții diferite din șirul salvat la numele de utilizator-floare. Cu toate acestea, acestea nu sunt contigue, deci dacă setați un pic la indexul 0 și apoi unul la indexul de 10.000, totul va fi 0. Pentru utilizări practice, nu este inițial important să înțelegeți mecanica precisă a fiecărei operațiuni - știți doar că acest lucru este normal și stocarea dvs. în Redis nu va depăși niciodată valoarea pe care ați specificat-o.
Conținutul proaspăt de pe un site păstrează un utilizator înapoi, așa cum arată un utilizator ceva nou de fiecare dată? Folosind o abordare tradițională bazată pe baze de date, puteți adăuga un rând nou într-un tabel cu identificatorul utilizatorului și identificatorul povestirii și apoi veți interoga acest tabel atunci când decideți să afișați o bucată de conținut. Așa cum vă puteți imagina, baza dvs. de date va crește extrem de rapid, în special cu creșterea atât a utilizatorilor, cât și a conținutului.
În acest caz, un negativ negativ (de exemplu, care nu prezintă o bucată de conținut nevăzut) are foarte puțină importanță, făcând ca filtrele Bloom să fie o opțiune viabilă. În primul rând, puteți crede că veți avea nevoie de un filtru Bloom pentru fiecare utilizator, dar vom folosi o simplă concatenare a identificatorului de utilizator și a identificatorului de conținut și apoi vom insera acel șir în filtrul nostru. Astfel putem folosi un singur filtru pentru toți utilizatorii.
În acest exemplu, să construim un alt server de bază Express care afișează conținut. De fiecare dată când vizitezi traseul / Spectacol-content / orice nume de utilizator- (cu orice nume de utilizator- fiind orice valoare în condiții de siguranță a adresei URL), va fi afișată o nouă bucată de conținut până când site-ul nu mai este conținut. În exemplu, conținutul este prima linie a primelor zece cărți despre Proiectul Gutenberg.
Va trebui să instalăm încă un modul npm. Din terminal, rulați: npm instala async -
Noul fișier app.js:
"javascript var async = cere ('async'), Bloom = necesită ('bloom-redis'), express =,
aplicație, client, filtru,
// Din proiectul Gutenberg - deschiderea liniilor primelor 10 ebook-uri de domeniu public // https://www.gutenberg.org/browse/scores/top openingLines = 'pride-and-prejudice': "Este un adevăr universal recunoscut , că un singur om în posesia unei averi bune trebuie să fie în lipsa unei soții. "," alice-aventuri-în-wonderland ":" Alice începuse să se obosească foarte mult să stea lângă sora ei pe malul mării și de a nu avea nimic de a face: o dată sau de două ori se arătă în cartea pe care o citise sora ei, dar nu avea poze sau conversații în ea "și care este folosirea unei cărți", a gândit Alice "fără imagini sau conversații?" , un "crăciun-carol": "Marley a murit: pentru început", "metamorfoză": "Într-o dimineață, când Gregor Samsa sa trezit din vise tulburi, sa găsit transformat în patul său într- "frankenstein": "Vă veți bucura să auziți că niciun dezastru nu a însoțit începerea unei întreprinderi pe care ați avut-o cu o prefătire atât de rea", "adventur es-of-huckleberry-finn ":" Nu știți despre mine fără să citiți o carte cu numele Aventurile lui Tom Sawyer; dar acest lucru nu contează. "," aventuri-sherlock-holmes ":" Pentru Sherlock Holmes ea este întotdeauna femeia "," narațiune-a-vieții-frederick-douglass " sa nascut in Tuckahoe, langa Hillsborough si la aproximativ 12 de mile de la Easton, in judetul Talbot, Maryland. "," principele ":" Toate statele, toate puterile care au tinut si detin regula asupra barbatilor au fost si sunt fie republici sau domnii. "," aventuri-de-tom-sawyer ":" TOM! " ;
app = expres (); client = redis.createClient ();
filtru = nou Bloom.BloomFilter (client: client, cheie: '3content-bloom-filter', // dimensiunea cheii Redis: 2875518, // ~ 350kb // dimensiune: 1024, numHashes: 20);
app.get ('/ show-content /: user', functie (req, res, urmatoarea) // vom incerca prin contentIds, verificand daca sunt in filtru. petrece timp pe fiecare continut.Daca nu ar fi recomandabil sa faci peste un numar mare de contentIds // Dar, in acest caz, numarul contentIds este mic / fix si functia filter.contains este rapida, este ok. o serie de chei definite în openingLines contentIds = Object.keys (openingLines), // parcurgerea unei părți din calea utilizatorului URI = req.params.user, checkingContentId, found = false, done = false;
// din moment ce filter.contains este asincron, folosim biblioteca async pentru a face async-ul nostru de looping (// check function, unde bucla asincrone se va termina function () return ! found &&! done funcția (cb) // obține primul element din matricea contentIds checkingContentId = contentIds.shift ();
Accentsconagua
// false înseamnă că suntem siguri că nu este în filtru dacă (! checkingContentId) done = true; // aceasta va fi prinsă de funcția de verificare deasupra cb (); altfel // concatenarea utilizatorului (de la adresa URL) cu id-ul conținutului filter.contains (user + checkingContentId, funcția (err, results) if (err) cb (err); rezultate; cb ();); , funcția (err) if (err) next (err); altceva if (openLines [checkingContentId]) // înainte de a trimite conținutul proaspăt, adăugăm-l la filtru pentru a nu mai afișa filtrul.add (user + checkingContentId, function (err) if (err) următor (err); altceva // trimiteți citatul proaspăt res.send (openingLines [checkingContentId]);); altceva res.send ("nu conținut nou!"); ); ); app.listen (8011);“
Dacă acordați o atenție deosebită perioadei de călătorie în Dev Tools, veți observa că cu cât solicitați mai mult o singură cale cu un nume de utilizator, cu atât este mai lungă. În timp ce verificăm filtrul are o durată fixă, în acest exemplu, verificăm prezența mai multor elemente. Filtrele înfloresc sunt limitate în ceea ce vă pot spune, deci testați pentru prezența fiecărui element. Desigur, în exemplul nostru este destul de simplu, dar testarea a sute de articole ar fi ineficientă.
În acest exemplu, vom construi un mic server Express care va face două lucruri: să accepte date noi prin POST și să afișeze datele curente (cu o solicitare GET). Când noile date sunt postate pe server, aplicația va verifica prezența în filtru. Dacă nu este prezent, îl vom adăuga la un set în Redis, altfel ne vom întoarce la zero. Cererea GET o va prelua de la Redis și o va trimite clientului.
Acest lucru este diferit de cele două situații anterioare, deoarece falsurile pozitive nu ar fi în regulă. Vom folosi filtrul Bloom ca o primă linie de apărare. Având în vedere proprietățile filtrelor Bloom, vom ști doar sigur că ceva nu este în filtru, deci în acest caz putem merge mai departe și lăsăm datele înăuntru. Dacă filtrul Bloom revine probabil în filtru, noi "Voi face un cec în comparație cu sursa de date reală.
Deci, ce câștigăm? Câștigăm viteza de a nu trebui să verificăm de fiecare dată sursa actuală. În situațiile în care sursa de date este lentă (API-uri externe, baze de date, media unui fișier plat), creșterea vitezei este cu adevărat necesară. Pentru a demonstra viteza, să adăugăm o întârziere realistă de 150 ms în exemplul nostru. Vom folosi de asemenea console.time / console.timeEnd pentru a înregistra diferențele dintre o verificare a filtrului Bloom și o verificare a filtrului non-Bloom.
În acest exemplu, vom folosi și un număr extrem de limitat de biți: doar 1024. Se va umple rapid. Pe măsură ce se umple, va afișa tot mai multe poziții false - veți vedea creșterea timpului de răspuns, pe măsură ce rata fals pozitivă se va umple.
Acest server utilizează aceleași module ca înainte, deci setați app.js fișier la:
"javascript var async = necesită ('async'), Bloom = necesită ('bloom-redis'), bodyParser = ),
aplicație, client, filtru,
currentDataKey = 'date curente', usedDataKey = 'used-data';
app = expres (); client = redis.createClient ();
filter = new Bloom.BloomFilter (client: client, cheie: 'stale-bloom-filter', // pentru ilustrare, acesta este un filtru foarte mic. ai nevoie de ceva mult mai mare! dimensiune: 1024, numHashes: 20);
app.post ('/', bodyParser.text (), funcția (req, res, următorul) var folosit;
console.log ('POST -', req.body); // log datele curente fiind postate console.time ('post'); // începe măsurarea timpului necesar pentru finalizarea procesului de filtrare și verificare condiționată //async.series este utilizat pentru a gestiona mai multe apeluri cu funcții asincrone. async.series ([function (cb) filtru.contains (req.body, function (err, filterStatus) if (err) cb (err) ;, funcția (cb) if (used === false) // Filtrele Bloom nu au negative false, deci nu mai avem nevoie de verificare cb (null); altceva // acesta * poate * filtru, așa că trebuie să facem o verificare follow // pentru scopurile tutorialului, vom adăuga o întârziere de 150ms aici, deoarece Redis poate fi suficient de rapid pentru a face dificilă măsurarea și întârzierea va simula o bază de date lentă sau API call setTimeout (functie () console.log ('posibil fals pozitiv'); client.sismember (usedDataKey, req.body, function (err, membership) if (err) cb (err) / sismember returnează 0 dacă un membru nu este parte a setului și 1 dacă este. // Aceasta transformă aceste rezultate în booleani pentru o logică consistentă comparată folosită = membership === 0? false: true; cb (err); );, 150);, funcția (cb) if (used === false) console.log ("Adăugarea la filtru"); dd (req.body, cb); altceva console.log ("Adăugat filtru deasupra, [false] pozitiv"); cb (null); , funcția (cb) if (used === false) client.multi () .set (actualDataKey, req.body) // datele neutilizate sunt setate pentru accesul facil la cheia " (usedDataKey, req.body) // și adăugat la un set pentru verificare ușoară mai târziu .exec (cb); altceva cb (null); ], funcția (err, cb) if (err) next (err); altceva console.timeEnd ('post'); // înregistrează timpul de la apelul console.time de mai sus res.send (saved:! used); // returnează dacă articolul a fost salvat, este valabil pentru date proaspete, fals pentru datele învechite. ); ); app.get ('/', functie (req, res, urmatoarea) // returneaza data proaspata client.get (currentDataKey, function (err, data) if (err) next (err) res.send (date);););
app.listen (8012);“
Deoarece POSTing-ul unui server poate fi dificil cu un browser, să folosim curl pentru a testa.
curl -data "datele dvs. sunt aici" - capul "Content-Type: text / plain" http: // localhost: 8012 /
Un script de bash rapid poate fi folosit pentru a arăta cum arată umplerea întregului filtru:
bash #! / bin / bash pentru i în 'seq 1 500'; face curl - datele "$ i" - capul "Content-Type: text / plain" http: // localhost: 8012 / done
Privind la un filtru de umplere sau filtru complet este interesant. Deoarece acesta este mic, îl puteți vedea cu ușurință Redis-cli. Fugind redis-cli obține filtru vechi de la terminalul dintre adăugarea de elemente, veți vedea creșterea individuală a octeților. Un filtru complet va fi \ xff pentru fiecare octet. În acest moment, filtrul va întoarce întotdeauna pozitiv.
Filtrele de bloom nu sunt o soluție de panaceu, dar în situația potrivită, un filtru Bloom poate oferi o completare rapidă și eficientă altor structuri de date.
