Share
I riktig brukstilfelle virker Bloom-filtre som magi. Det er en dristig uttalelse, men i denne opplæringen vil vi utforske den nysgjerrige datastrukturen, hvor best å bruke den, og noen få praktiske eksempler ved hjelp av Redis og Node.js.
Blomfiltre er en probabilistisk, enveis datastruktur. Ordet "filter" kan være forvirrende i denne konteksten; filter innebærer at det er en aktiv ting, et verb, men det kan være lettere å tenke på det som lagring, et substantiv. Med et enkelt Bloom filter kan du gjøre to ting:
Dette er viktige begrensninger for å forstå. Du kan ikke fjerne et element, og du kan heller ikke liste opp elementene i et Bloom-filter. Du kan heller ikke med sikkerhet si om et element har blitt lagt til i filteret tidligere. Det er her den probabilistiske naturen til et Bloom-filter kommer inn - falske positiver er mulige, men falske negativer er ikke. Hvis filteret er satt opp riktig, kan falske positiver være svært sjeldne.
Varianter av Bloom-filter finnes, og de legger til andre evner, som fjerning eller skalering, men de legger også til kompleksitet og begrensninger. Det er viktig å først forstå enkle Bloom-filtre før du går videre til varianter. Denne artikkelen vil bare dekke de enkle Bloom-filtrene.
Med disse begrensningene har du en rekke fordeler: Fast størrelse, hashbasert kryptering og hurtige søk.
Når du setter opp et Bloom filter, gir du det en størrelse. Denne størrelsen er fast, så hvis du har ett element eller en milliard elementer i filteret, vil det aldri vokse utover den angitte størrelsen. Når du legger til flere elementer i filteret ditt, øker sjansen for falsk positiv. Hvis du angav et mindre filter, vil denne falske positive hastigheten øke raskere enn hvis du har en større størrelse.
Blomstfiltre er bygget på konseptet med enveis hashing. I likhet med riktig lagring av passord bruker Bloom-filtre en hash-algoritme for å bestemme en unik identifikator for elementene som er sendt inn i den. Hashes, av natur, kan ikke reverseres og er representert av en tilsynelatende tilfeldig streng av tegn. Så, hvis noen får tilgang til et Bloom-filter, vil det ikke direkte avsløre noe av innholdet.
Endelig er Bloom-filtre raske. Operasjonen innebærer langt færre sammenligninger enn andre metoder, og det kan enkelt lagres i minnet, og forhindrer ytelsesberøvelse av database hits.
Nå som du kjenner grensene og fordelene med Bloom-filtre, la oss ta en titt på noen situasjoner hvor du kan bruke dem.
Vi bruker Redis og Node.js for å illustrere Bloom-filtre. Redis er et lagringsmedium for Bloom-filteret ditt; det er raskt, i minnet, og har noen spesifikke kommandoer (GETBIT, SETBIT) som gjør implementeringen effektiv. Jeg antar at du har Node.js, npm og Redis installert på systemet ditt. Din Redis-server skal kjøres på lokal vert på standardporten for eksemplene våre til arbeid.
I denne opplæringen vil vi ikke implementere et filter fra grunnen opp; I stedet fokuserer vi på praktiske bruksområder med en forhåndsbygd modul i npm: bloom-redis. bloom-redis har et veldig kortfattet sett med metoder: Legg til, inneholder og klar.
Som nevnt tidligere trenger Bloom-filtre en hashing-algoritme for å generere unike identifikatorer for et element. bloom-redis bruker den kjente MD5-algoritmen, som, selv om det kanskje ikke er den perfekte passformen for et Bloom-filter (litt tregt, overkill på biter), vil fungere fint.
Brukernavn, spesielt de som identifiserer en bruker i en nettadresse, må være unike. Hvis du bygger et program som lar brukerne endre brukernavnet, vil du sannsynligvis ha et brukernavn som har aldri blitt brukt for å unngå forvirring og sniping av brukernavn.
Uten et Bloom-filter, må du referere til et bord som har hvert brukernavn noensinne brukt, og i skala kan dette være svært dyrt. Blomstfiltre lar deg legge til et element hver gang en bruker vedtar et nytt navn. Når en bruker sjekker for å se om et brukernavn er tatt, er alt du trenger å gjøre, å sjekke Bloom-filteret. Det vil kunne fortelle deg, med absolutt sikkerhet, om det forespurte brukernavnet tidligere er lagt til. Det er mulig at filteret feilaktig returnerer at et brukernavn har blitt brukt når det ikke har, men det er feil på forsiktighetssiden og kan ikke forårsake noen reell skade (bortsett fra at en bruker kanskje ikke kan kreve "k3w1d00d47").
For å illustrere dette, la oss bygge en rask REST-server med Express. Først opprett din package.json fil og kjør deretter følgende terminalkommandoer.
npm installere blom-redis - save
npm installere ekspress - lagre
npm installere redis - save
Standardalternativene for blom-redis har størrelsen satt til to megabyte. Dette err på forsiktighetssiden, men det er ganske stort. Å sette opp størrelsen på Bloom-filteret er kritisk: For stor og du sliter bort minne, for lite og din falske positive hastighet blir for høy. Matematikken som er involvert i å bestemme størrelsen, er ganske involvert og utover omfanget av denne opplæringen, men heldigvis er det en Bloom-filterkalkulator for å få jobben gjort uten å knekke en lærebok.
Nå lager din app.js som følger:
"javascript var Bloom = krever ('bloom-redis'), express = krever ('express'), redis = krever ('redis'),
app, klient, filter;
// sett inn vår Express server app = express ();
// opprett forbindelsen til Redis klient = redis.createClient ();
filter = ny Bloom.BloomFilter (klient: klient, // sørg for at Bloom-modulen bruker vår nyopprettede forbindelse til Redis-nøkkelen: 'brukernavn-blomstfilter', // Redis-nøkkelen
// Beregnet størrelse på Bloom-filteret. // Dette er hvor størrelsen / sannsynligheten avviks er laget //http://hur.st/bloomfilter?n=100000&p=1.0E-6 størrelse: 2875518, // ~ 350kb numHashes: 20);
app.get ('/ check', funksjon (req, res, neste) // merk av for å sikre at spørringsstrengen har 'brukernavn' hvis (typeof req.query.username === 'undefined') // skip denne ruten går til neste - vil resultere i en 404 / ikke funnet neste ('rute'); else filter.contains (req.query.username, // brukernavnet fra søketrådsfunksjonen (feil, resultat ) hvis (err) neste (feil); // hvis det oppdages en feil, send den til klienten annet res.send (brukernavn: req.query.username, // hvis resultatet er feil, så Vi vet at varen har ikke blitt brukt // hvis resultatet er sant, kan vi anta at varen har blitt brukt status: resultat? 'brukt': 'gratis'); ); );
app.get ('/ save', funksjon (req, res, neste) if (typeof req.query.username === 'undefined') neste ('rute'); else // først trenger vi for å sørge for at det ikke er i filterfilteret. Contains (req.query.usnavn, funksjon (feil, resultat) hvis (err) neste (err); annet hvis (resultat) // sant resultat betyr den eksisterer allerede, så fortell brukeren res.send (brukernavn: req.query.username, status: 'not-created';; else // vi legger til brukernavnet som er passert i spørringsstrengen til filteret filter.add (req.query.username, function (err) // Tilbakekallingsargumentene til Legg til gir ingen nyttig informasjon, så vi vil bare sjekke for å sikre at ingen feil ble sendt hvis (feil) neste (feil); annet res.send (brukernavn: req.query.username, status: 'created'); ); ); );
app.listen (8010);"
Slik kjører du denne serveren: node app.js. Gå til nettleseren din og pek den til: https: // localhost: 8010 / sjekk brukernavn = kyle. Svaret skal være: "Brukernavn": "kyle", "status": "gratis".
La oss nå lagre det brukernavnet ved å peke på nettleseren din på http: // localhost: 8010 / lagre brukernavn = kyle. Svaret vil være: "Brukernavn": "kyle", "status": "laget". Hvis du går tilbake til adressen http: // localhost: 8010 / sjekk brukernavn = kyle, svaret vil være "Brukernavn": "kyle", "status": "brukt". Tilsvarende, går tilbake til http: // localhost: 8010 / lagre brukernavn = kyle vil resultere i "Brukernavn": "kyle", "status": "ikke-laget".
Fra terminalen kan du se filterets størrelse: redis-cli strlen brukernavn-blomstfilter.
Akkurat nå, med ett element, skal det vise 338622.
Nå, fortsett og prøv å legge til flere brukernavn med /lagre rute. Prøv så mange du vil.
Hvis du deretter sjekker størrelsen på nytt, kan du merke at størrelsen din har gått opp litt, men ikke for hvert tillegg. Nysgjerrig, ikke sant? Internt setter et blomstfilter individuelle biter (1 s / 0) på forskjellige stillinger i strengen lagret ved brukernavn-blomst. Imidlertid er disse ikke sammenhengende, så hvis du setter litt på indeks 0 og deretter en på indeksen 10.000, vil alt mellom være 0. For praktisk bruk er det ikke først viktig å forstå den presise mekanikken til enhver operasjon - bare vet at dette er normalt og at lagringen din i Redis aldri vil overstige verdien du angav.
Fersk innhold på et nettsted holder en bruker tilbake, så hvordan viser du en bruker noe nytt hver gang? Ved å bruke en tradisjonell database tilnærming, kan du legge til en ny rad til et bord med brukeridentifikatoren og identifiseringen av historien, og du vil spørre det tabellen når du bestemmer deg for å vise innhold. Som du kanskje tror, vil databasen din vokse ekstremt raskt, spesielt med vekst av både brukere og innhold.
I dette tilfellet har en falsk negativ (for eksempel ikke noe usett innhold) svært liten konsekvens, noe som gjør Bloom filters et levedyktig alternativ. Ved første rødme kan du tenke at du vil trenge et blomstfilter for hver bruker, men vi bruker en enkel sammenkobling av brukeridentifikatoren og innholdsidentifikatoren, og deretter sette den inn i filteret. På denne måten kan vi bruke et enkelt filter for alle brukere.
I dette eksemplet la vi bygge en annen grunnleggende Express-server som viser innhold. Hver gang du besøker ruten / Show-content / alle-brukernavn (med alle-brukernavn å være en URL-sikker verdi), vil et nytt innhold bli vist til nettstedet er tom for innhold. I eksemplet er innholdet den første linjen av de ti beste bøkene på Project Gutenberg.
Vi må installere en ny npm-modul. Fra terminalen, kjøre: npm installere async - save
Din nye app.js-fil:
"javascript var async = krever ('async'), Bloom = krever ('bloom-redis'), express = krever ('express'), redis = krever ('redis'),
app, klient, filter,
// Fra Project Gutenberg - åpningslinjer av de 10 beste offentlige e-bøkene // https://www.gutenberg.org/browse/scores/top openingLines = 'pride and prejudice': 'Det er en sannhet som er universelt anerkjent , at en eneste mann som er i besittelse av en formue, må være i lyst på en kone. '' Alice-eventyr-i Wonderland ':' Alice begynte å bli veldig lei av å sitte ved søsteren hennes på banken, og av å ha ingenting å gjøre: en eller to ganger hadde hun kikket inn i boken hennes søster leser, men det hadde ingen bilder eller samtaler i det, "og hva er bruk av en bok, tenkte Alice uten bilder eller samtaler?" , "a-christmas-carol": "Marley var død: til å begynne med.", "metamorphosis": "En morgen, da Gregor Samsa våknet fra urolige drømmer, fant han sig omgjort i sengen til en fryktelig skadedyr. 'frankenstein': 'Du vil glede deg over å høre at ingen katastrofe har ledsaget en virksomhet som du har sett med slike onde forhindringer.', 'eventyr es-of-huckleberry-finn ':' Du vet ikke om meg uten at du har lest en bok med navnet The Adventures of Tom Sawyer; men det er ikke uansett. ',' eventyr-of-sherlock-holmes ':' Til Sherlock Holmes er hun alltid kvinnen. ',' Fortell-of-the-life-of-frederick-douglass ':' Jeg ble født i Tuckahoe, i nærheten av Hillsborough, og omtrent tolv miles fra Easton, i Talbot fylke, Maryland. ',' The Prince ':' Alle stater, alle krefter som har holdt og holdt styre over menn, har vært og er enten republikker eller prinsipper. ',' eventyr-av-tom-sawyer ':' TOM! ' ;
app = express (); klient = redis.createClient ();
filter = ny Bloom.BloomFilter (klient: klient, nøkkel: '3content-bloom-filter', // Redis nøkkelstørrelse: 2875518, // ~ 350kb // størrelse: 1024, numHashes: 20);
app.get ('/ show-content /: user', funksjon (req, res, neste) // vi skal løpe gjennom contentIds, kontroller for å se om de er i filteret. // Siden dette tilbringer tid på hvert innhold. Det ville ikke være tilrådelig å gjøre over et stort antall contentIds // Men i dette tilfellet er antall contentIds liten / fast og vårt filter. inneholder funksjonen er rask, det er greit. var // skaper et utvalg av nøklene som er definert i openingLines contentIds = Object.keys (openingLines), // får en del av banen fra URI-brukeren = req.params.user, checkingContentId, found = false, done = false;
// siden filter.contains er asynkron, bruker vi async biblioteket til å gjøre vår looping async.whilst (// sjekk funksjon, der vår asynkrone sløyfe slutter funksjonen () return (! found &&! done);, funksjon (cb) // få det første elementet fra mengden contentIds checkingContentId = contentIds.shift ();
Accentsconagua
// false betyr at vi er sikre på at det ikke er i filteret hvis (! checkingContentId) done = true; // dette vil bli fanget av sjekkfunksjonen over cb (); annet // sammenkoble brukeren (fra nettadressen) med innholdsfilterets innhold. inneholder (bruker + kontrollinnhold, funksjon (feil, resultater) hvis (err) cb (err); else found =! resultater; cb ();); , funksjon (err) hvis (feil) neste (feil); ellers if (opensLines [checkContentId]) // før vi sender det friske innholdet, la oss legge det til filteret for å hindre at det vises igjen filter.add (bruker + checkContentId, funksjon (err) hvis (err) neste (feil); else // send det friske tilbudet res.send (openingLines [checkContentId]);); else res.send ('ingen nytt innhold!'); ); ); app.listen (8011);"
Hvis du nøye tar hensyn til rundtur i Dev Tools, vil du legge merke til at jo mer du ber om en enkelt sti med et brukernavn, jo lengre det tar. Mens du sjekker filteret, tar det en fast tid, i dette eksempelet ser vi etter tilstedeværelsen av flere elementer. Blomfiltre er begrenset til hva de kan fortelle deg, så du tester for tilstedeværelsen av hvert element. Selvfølgelig, i vårt eksempel er det ganske enkelt, men testing for hundrevis av gjenstander ville være ineffektiv.
I dette eksemplet bygger vi en liten Express-server som vil gjøre to ting: godta nye data via POST, og vise gjeldende data (med en GET-forespørsel). Når de nye dataene er POST'et til serveren, vil applikasjonen sjekke at den er til stede i filteret. Hvis den ikke er til stede, legger vi den til et sett i Redis, ellers returnerer vi null. GET-forespørselen henter den fra Redis og sender den til klienten.
Dette er annerledes enn de to foregående situasjonene, da falske positiver ikke ville være i orden. Vi bruker Bloom-filteret som en første forsvarslinje. Gitt egenskapene til Bloom-filtre, vet vi bare sikkert at noe ikke er i filteret, så i dette tilfellet kan vi gå videre og la dataene inn. Hvis Bloom-filteret returnerer det som sannsynligvis er i filteret, vi Jeg vil gjøre en sjekk i forhold til den faktiske datakilden.
Så, hva får vi? Vi får fart på å ikke sjekke mot den faktiske kilden hver gang. I situasjoner der datakilden er treg (eksterne APIer, pokey databaser, midt i en flatfil), er hastighetsøkningen virkelig nødvendig. For å demonstrere hastigheten, la oss legge til en realistisk forsinkelse på 150 ms i vårt eksempel. Vi bruker også console.time / console.timeEnd for å logge forskjellene mellom en Bloom filter sjekk og en ikke-Bloom filter sjekk.
I dette eksemplet bruker vi også et ekstremt begrenset antall biter: bare 1024. Det vil fylle opp raskt. Når det fylles, vil det vise flere og flere falske positiver - du vil se responstiden øke ettersom den falske positive frekvensen fyller opp.
Denne serveren bruker de samme modulene som før, så sett inn app.js fil til:
"javascript var async = krever ('async'), Bloom = krever ('bloom-redis'), bodyParser = krever ('body-parser'), express = krever ('express'), redis = ),
app, klient, filter,
currentDataKey = 'nåværende data', usedDataKey = 'used-data';
app = express (); klient = redis.createClient ();
filter = ny Bloom.BloomFilter (klient: klient, nøkkel: 'stale-bloom-filter', // for illustrasjonsformål, dette er et super lite filter. Det skal fylles på rundt 500 elementer, så for en produksjonsbelastning, du vil trenge noe mye større! størrelse: 1024, numHashes: 20);
app.post ('/', bodyParser.text (), funksjon (req, res, neste) var brukt;
console.log ('POST -', req.body); // logg gjeldende data som blir lagt inn console.time ('post'); // begynn å måle tiden det tar å fullføre vårt filter og betinget verifikasjonsprosess //async.series brukes til å håndtere flere asynkronfunksjonssamtaler. async.series ([funksjon (cb) filter.contains (req.body, function (err, filterStatus) hvis (err) cb (err); else used = filterStatus; cb (err);) ;, funksjon (cb) if (used === false) // Blomstfilter har ikke falske negativer, så vi trenger ingen ytterligere verifikasjon cb (null); else // it * may * være i filter, så vi må gjøre en oppfølgingskontroll. // Med tanke på opplæringen legger vi til en 150ms forsinkelse her, siden Redis kan være rask nok til å gjøre det vanskelig å måle og forsinkelsen vil simulere en langsom database eller API-anrop setTimeout (funksjon () console.log ('mulig falsk positiv'); client.sismember (usedDataKey, req.body, funksjon (feil, medlemskap) if (err) cb (err); else / / sismember returnerer 0 hvis et medlem ikke er en del av settet og 1 hvis det er. // Dette forvandler disse resultatene til booleans for konsistent logikk sammenligning brukes = medlemskap === 0? false: true; cb (err); );, 150);, funksjon (cb) hvis (brukt === falsk) console.log ('Adding to filter'); filter.a dd (req.body, cb); else console.log ('hoppet over filtertilsetning, [falskt] positivt'); cb (null); , funksjon (cb) if (used === false) client.multi () .set (currentDataKey, req.body) // ubrukte data er satt for enkel tilgang til 'nåværende data'-tasten. (usedDataKey, req.body) // og lagt til et sett for enkel verifisering senere .exec (cb); ellers cb (null); ], funksjon (feil, cb) hvis (err) neste (feil); else console.timeEnd ('post'); // logger hvor mye tid siden konsoll.tidssamtalen ovenfor res.send (saved:! used); // returnerer om varen ble lagret, sant for friske data, falsk for uaktuelle data. ); ); app.get ('/', funksjon (req, res, neste) // bare returner den friske data client.get (currentDataKey, funksjon (feil, data) hvis (err) next (err); else res.send (data);););
app.listen (8012);"
Siden POSTing til en server kan være vanskelig med en nettleser, la oss bruke krøll for å teste.
curl - data "dataene dine går her" --header "Content-Type: text / plain" http: // localhost: 8012 /
Et raskt bash script kan brukes til å vise hvordan fylle opp hele filteret ser ut:
bash #! / bin / bash for jeg i 'seq 1 500'; gjør krøll - data "data $ i" --header "Content-Type: text / plain" http: // localhost: 8012 / done
Ser på en fylling eller fullt filter er interessant. Siden denne er liten, kan du enkelt se den med Redis-cli. Ved å kjøre redis-cli få foreldet filter fra terminalen mellom å legge til elementer, vil du se at de enkelte byteene øker. Et fullt filter vil være \ XFF for hver byte. På dette tidspunktet vil filteret alltid returnere positivt.
Blomstfiltre er ikke en panacea-løsning, men i riktig situasjon kan et blomstfilter gi et raskt og effektivt komplement til andre datastrukturer.
