Share
In de juiste use case lijken Bloom-filters op magie. Dat is een gewaagde verklaring, maar in deze zelfstudie zullen we de merkwaardige gegevensstructuur verkennen, hoe deze het beste kan worden gebruikt en enkele praktische voorbeelden met Redis en Node.js.
Bloeifilters zijn een probabilistische eenrichtingsgegevensstructuur. Het woord 'filter' kan in deze context verwarrend zijn; filter houdt in dat het een actief iets is, een werkwoord, maar het kan gemakkelijker zijn om het te zien als opslag, een zelfstandig naamwoord. Met een eenvoudig Bloom-filter kunt u twee dingen doen:
Dit zijn belangrijke beperkingen om te begrijpen - u kunt een item niet verwijderen en evenmin kunt u de items in een Bloom-filter vermelden. Ook kun je niet met zekerheid zeggen of een item in het verleden aan het filter is toegevoegd. Dit is waar de probabilistische aard van een Bloom-filter binnenkomt-valse positieven zijn mogelijk, maar valse negatieven zijn dat niet. Als het filter correct is ingesteld, kunnen valse positieven uiterst zeldzaam zijn.
Er bestaan varianten van Bloom-filters en deze voegen andere mogelijkheden toe, zoals verwijdering of schaalvergroting, maar ze voegen ook complexiteit en beperkingen toe. Het is belangrijk om eerst eenvoudige Bloom-filters te begrijpen voordat u doorgaat naar de varianten. Dit artikel heeft alleen betrekking op de eenvoudige Bloom-filters.
Met deze beperkingen heeft u een aantal voordelen: vaste grootte, hash-gebaseerde codering en snelle opzoekingen.
Wanneer je een Bloom-filter instelt, geef je het een maat. Deze grootte is vast, dus als je een item of een miljard items in het filter hebt, zal het nooit groter worden dan de opgegeven grootte. Naarmate u meer items aan uw filter toevoegt, neemt de kans op een vals positief toe. Als u een kleiner filter hebt opgegeven, neemt dit percentage vals positieven sneller toe dan wanneer u een groter formaat gebruikt.
Bloom-filters zijn gebaseerd op het concept van hashing in één richting. Net zoals het correct opslaan van wachtwoorden, gebruiken Bloom-filters een hash-algoritme om een unieke identificatie te bepalen voor de items die erin worden doorgegeven. Hashes kunnen van nature niet worden teruggedraaid en worden vertegenwoordigd door een schijnbaar willekeurige reeks tekens. Dus als iemand toegang krijgt tot een Bloom-filter, zal het niet direct de inhoud onthullen.
Ten slotte zijn Bloom-filters snel. De bewerking bevat veel minder vergelijkingen dan andere methoden en kan eenvoudig in het geheugen worden opgeslagen, waardoor databasebezettingen die de performance storen, worden voorkomen.
Nu u de beperkingen en voordelen van Bloom-filters kent, laten we eens kijken naar enkele situaties waarin u ze kunt gebruiken.
We zullen Redis en Node.js gebruiken om Bloom-filters te illustreren. Redis is een opslagmedium voor uw Bloom-filter; het is snel, in het geheugen en heeft een paar specifieke commando's (GETBIT, SETBIT) die de implementatie efficiënt maken. Ik neem aan dat u Node.js, npm en Redis op uw systeem hebt geïnstalleerd. Uw Redis-server moet worden uitgevoerd localhost bij de standaardpoort om onze voorbeelden te laten werken.
In deze zelfstudie implementeren we geen filter vanaf de basis; in plaats daarvan concentreren we ons op praktisch gebruik met een vooraf gebouwde module in npm: bloedselding. bloom-redis heeft een zeer beknopte set van methoden: toevoegen, bevat en duidelijk.
Zoals eerder vermeld, hebben Bloom-filters een hash-algoritme nodig om unieke id's voor een item te genereren. bloom-redis maakt gebruik van het bekende MD5-algoritme, dat, hoewel misschien niet de perfecte pasvorm voor een Bloom-filter (een beetje traag, overkill aan bits), prima werkt.
Gebruikersnamen, vooral die welke een gebruiker in een URL identificeren, moeten uniek zijn. Als u een toepassing maakt waarmee gebruikers de gebruikersnaam kunnen wijzigen, wilt u waarschijnlijk een gebruikersnaam hebben nooit gebruikt om verwarring en sluipen van gebruikersnamen te voorkomen.
Zonder een Bloom-filter zou je moeten verwijzen naar een tabel die elke gebruikersnaam ooit heeft gebruikt, en op schaal kan dit erg duur zijn. Met bloeifilters kunt u een item toevoegen elke keer dat een gebruiker een nieuwe naam aanneemt. Wanneer een gebruiker controleert of een gebruikersnaam is gemaakt, hoeft u alleen maar het Bloom-filter te controleren. Hij kan u met absolute zekerheid vertellen of de gevraagde gebruikersnaam eerder is toegevoegd. Het is mogelijk dat het filter onterecht retourneert dat een gebruikersnaam is gebruikt wanneer dat niet het geval is, maar dit vergist zich voorzichtigheid en kan geen echte schade aanrichten (afgezien van het feit dat een gebruiker 'k3w1d00d47' niet kan claimen).
Laten we dit illustreren door een snelle REST-server te bouwen met Express. Maak eerst uw package.json bestand en voer vervolgens de volgende terminalopdrachten uit.
npm install bloom-redis --save
npm install express --save
npm install redis --save
De standaardopties voor bloode-redis hebben de grootte ingesteld op twee megabytes. Dit vergissingen vanwege de voorzichtigheid, maar het is vrij groot. Het instellen van de grootte van het Bloom-filter is van cruciaal belang: te groot en u verspilt geheugen, te klein en uw fout-positieve snelheid zal te hoog zijn. De wiskunde die betrokken is bij het bepalen van de grootte is behoorlijk betrokken en buiten het kader van deze tutorial, maar gelukkig is er een Bloom filtergrootte calculator om de klus te klaren zonder een studieboek te kraken.
Maak nu je app.js als volgt:
"javascript var Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
app, client, filter;
// stel onze Express server-app in = express ();
// maak de verbinding met Redis-client = redis.createClient ();
filter = nieuwe Bloom.BloomFilter (client: client, // zorg ervoor dat de Bloom-module onze nieuw gemaakte verbinding gebruikt met de Redis-toets: 'gebruikersnaam-bloom-filter', // de Redis-toets
// berekende grootte van het Bloom-filter. // Dit is waar uw afmeting / waarschijnlijkheid afwegingen zijn gemaakt //http://hur.st/bloomfilter?n=100000&p=1.0E-6 size: 2875518, // ~ 350kb numHashes: 20);
app.get ('/ check', functie (req, res, next) // controleer om zeker te zijn dat de querystring 'gebruikersnaam' heeft als (typeof req.query.username === 'undefined') // overslaan deze route, ga naar de volgende - zal resulteren in een 404 / niet gevonden volgende ('route'); else filter.contains (req.query.username, // de gebruikersnaam uit de query string-functie (err, resultaat ) if (err) next (err); // als een fout wordt aangetroffen, verzendt u deze naar de client else res.send (gebruikersnaam: req.query.username, // als het resultaat false is, dan we weten dat het item heeft niet gebruikt // als het resultaat waar is, kunnen we aannemen dat het item status is gebruikt: resultaat? 'gebruikt': 'gratis'); ); );
app.get ('/ save', functie (req, res, next) if (typeof req.query.username === 'undefined') next ('route'); else // eerst moeten we om er zeker van te zijn dat het nog niet in het filter filter zit (req.query.username, function (err, result) if (err) next (err); else if (result) // true resultaat betekent het bestaat al, dus vertel de gebruiker res.send (gebruikersnaam: req.query.username, status: 'not-created'); else // we zullen de gebruikersnaam die in de querystring is doorgegeven aan het filter toevoegen filter.add (req.query.username, function (err) // De callback-argumenten naar toevoegen biedt geen bruikbare informatie, dus we controleren of er geen fout is overschreden als (err) next (err); else res.send (gebruikersnaam: req.query.username, status: 'created'); ); ); );
app.listen (8010);"
Om deze server te draaien: knooppunt app.js. Ga naar je browser en wijs het naar: https: // localhost: 8010 / check username = Kyle. Het antwoord zou moeten zijn: "Username": "kyle", "status": "gratis".
Laten we nu die gebruikersnaam opslaan door uw browser naar te wijzen http: // localhost: 8010 / opslaan username = Kyle. Het antwoord zal zijn: "Username": "kyle", "status": "gecreëerd". Als je teruggaat naar het adres http: // localhost: 8010 / check username = Kyle, het antwoord zal zijn "Gebruikersnaam": "kyle", "Status": "gebruikt". Evenzo, teruggaan naar http: // localhost: 8010 / opslaan username = Kyle zal resulteren in "Username": "kyle", "status": "niet-geschapen".
Vanaf de terminal ziet u de grootte van het filter: redis-cli strlen gebruikersnaam-bloom-filter.
Op dit moment, met één item, zou het moeten verschijnen 338.622.
Nu, ga je gang en probeer meer gebruikersnamen toe te voegen met de /opslaan route. Probeer zoveel als je wilt.
Als u vervolgens de maat opnieuw controleert, merkt u misschien dat uw maat iets is gestegen, maar niet voor elke toevoeging. Nieuwsgierig, toch? Intern stelt een Bloom-filter individuele bits (1's / 0's) in op verschillende posities in de reeks die is opgeslagen bij gebruikersnaam-bloom. Deze zijn echter niet aangrenzend, dus als u een beetje instelt op index 0 en vervolgens één op index 10.000, is alles tussen nul 0. Voor praktisch gebruik is het niet in eerste instantie belangrijk om de precieze werking van elke bewerking te begrijpen - weet alleen dat dit is normaal en dat uw opslag in Redis nooit de waarde zal overschrijden die u hebt opgegeven.
Nieuwe inhoud op een website zorgt ervoor dat een gebruiker terugkomt, dus hoe toon je een gebruiker elke keer iets nieuws? Met behulp van een traditionele databaseaanpak kunt u een nieuwe rij aan een tabel toevoegen met de gebruikers-ID en de ID van het artikel en vervolgens zou u naar die tabel vragen wanneer u besluit een stuk inhoud weer te geven. Zoals u misschien denkt, zal uw database extreem snel groeien, vooral met de groei van zowel gebruikers als inhoud.
In dit geval heeft een vals-negatief (bijvoorbeeld niet een onzichtbaar stukje inhoud) zeer weinig consequentie, waardoor Bloom-filters een haalbare optie zijn. Op het eerste gezicht denkt u misschien dat u voor elke gebruiker een Bloom-filter nodig heeft, maar we gebruiken een eenvoudige aaneenschakeling van de gebruikers-ID en de inhoudsidentificatie en voegen die tekenreeks toe aan onze filter. Op deze manier kunnen we voor alle gebruikers één filter gebruiken.
Laten we in dit voorbeeld een andere standaard Express-server maken die inhoud weergeeft. Elke keer dat je de route bezoekt / Show-content / any-gebruikersnaam (met any-gebruikersnaam omdat het een URL-veilige waarde is), wordt er een nieuw stuk inhoud weergegeven totdat de site geen content meer bevat. In het voorbeeld is de inhoud de eerste regel van de tien beste boeken over Project Gutenberg.
We moeten nog een npm-module installeren. Vanaf de terminal: npm installeer async --save
Uw nieuwe app.js-bestand:
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), express = require ('express'), redis = require ('redis'),
app, client, filter,
// Van Project Gutenberg - openingsregels van de top 10 van e-mails in het publieke domein // https://www.gutenberg.org/browse/scores/top openingLines = 'pride-and-prejudice': 'Het is een waarheid die universeel wordt erkend , dat een enkele man in het bezit van een fortuin, een vrouw moet missen. ',' alices-adventures-in-wonderland ':' Alice begon het zat te worden door haar zus op de bank te zitten, en niets te doen: een paar keer had ze in het boek gekeken dat haar zus aan het lezen was, maar er stonden geen foto's of gesprekken in, 'en wat is het gebruik van een boek,' dacht Alice 'zonder foto's of gesprekken?' , 'a-christmas-carol': 'Marley was dood: om te beginnen.', 'metamorfose': 'Op een ochtend, toen Gregor Samsa ontwaakte uit verwarde dromen, werd hij in zijn bed veranderd in een vreselijk ongedierte.', 'Frankenstein': 'Je zult blij zijn om te horen dat er geen ramp gepaard is gegaan met het begin van een onderneming die je met zulke slechte voorgevoelens hebt beschouwd.', 'adventur es-of-huckleberry-finn ':' JIJ weet niets over mij zonder dat je een boek hebt gelezen met de naam The Adventures of Tom Sawyer; maar dat maakt niet uit. ',' avonturen-van-sherlock-holmes ':' Voor Sherlock Holmes is zij altijd de vrouw. ',' narratief-van-het-leven-van-frederiek-douglass ':' I werd geboren in Tuckahoe, in de buurt van Hillsborough, en ongeveer twaalf mijl van Easton, in het graafschap Talbot, Maryland. ',' de prins ':' Alle staten, alle machten, die de heerschappij over mannen hebben gehouden en hebben vastgehouden, zijn en zijn of republieken of vorstendommen. ',' adventures-of-tom-sawyer ':' TOM! ' ;
app = express (); client = redis.createClient ();
filter = nieuwe Bloom.BloomFilter (client: client, sleutel: '3content-bloom-filter', // de Redis-sleutelgrootte: 2875518, // ~ 350kb // grootte: 1024, numHashes: 20);
app.get ('/ show-content /: user', function (req, res, next) // we gaan de contentIds doorlopen om te kijken of deze in het filter voorkomen // Vanaf nu besteedt tijd aan elke contentId zou niet raadzaam zijn om over een groot aantal contentIds te doen // Maar in dit geval is het aantal contentIds klein / vast en onze filter.contains-functie is snel, het is goed. een array met de sleutels die zijn gedefinieerd in de openingsregels contentIds = Object.keys (openingsregels), // een deel van het pad ophalen van de URI-gebruiker = req.params.user, checkingContentId, found = false, done = false;
// aangezien filter.contains asynchroon is, gebruiken we de asynchrone bibliotheek om asynchrone looping uit te voeren (while-functie, waarbij onze asynchrone lus functie beëindigt () return (! found &&! done);, functie (cb) // haal het eerste item uit de array van contentIds checkingContentId = contentIds.shift ();
Accentsconagua
// false betekent dat we zeker weten dat het niet in het filter voorkomt als (! checkingContentId) done = true; // dit wordt opgevangen door de controlefunctie hierboven cb (); else // aaneenschakelen van de gebruiker (uit de URL) met de id van de inhoud filter.bevat (gebruiker + checkingContentId, functie (err, resultaten) if (err) cb (err); else found =! resultaten; cb ();); , functie (err) if (err) next (err); else if (openingsregels [checkingContentId]) // voordat we de nieuwe contentId versturen, laten we het toevoegen aan het filter om te voorkomen dat het opnieuw filter.add toont (user + checkingContentId, function (err) if (err) next (err); else // stuur het nieuwe citaat res.send (openingsregels [checkingContentId]);); else res.send ('geen nieuwe inhoud!'); ); ); app.listen (8011);"
Als je in Dev Tools goed let op de rondetijd, zul je merken dat hoe langer je een enkel pad met een gebruikersnaam aanvraagt, hoe langer het duurt. Terwijl het controleren van het filter een vaste tijd in beslag neemt, controleren we in dit voorbeeld op de aanwezigheid van meer items. Bloeifilters zijn beperkt in wat ze je kunnen vertellen, dus je test op de aanwezigheid van elk item. Natuurlijk, in ons voorbeeld is het vrij eenvoudig, maar het testen van honderden items zou inefficiënt zijn.
In dit voorbeeld bouwen we een kleine Express-server die twee dingen doet: nieuwe gegevens accepteren via POST en de huidige gegevens weergeven (met een GET-verzoek). Wanneer de nieuwe gegevens worden POST'ed naar de server, zal de toepassing controleren op zijn aanwezigheid in het filter. Als het niet aanwezig is, voegen we het toe aan een set in Redis, anders zullen we null retourneren. Het GET-verzoek haalt het op van Redis en stuurt het naar de client.
Dit is anders dan de vorige twee situaties, omdat valse positieven niet goed zouden zijn. We zullen het Bloom-filter gebruiken als een eerste verdedigingslinie. Gezien de eigenschappen van Bloom-filters, weten we alleen zeker dat er iets niet in het filter staat, dus in dit geval kunnen we doorgaan en de gegevens erin laten. Als het Bloom-filter terugkeert dat waarschijnlijk in het filter zit, dan doe een controle versus de eigenlijke gegevensbron.
Dus, wat hebben we te winnen? We krijgen de snelheid dat we niet elke keer hoeven te checken tegenover de werkelijke bron. In situaties waar de gegevensbron langzaam is (externe API's, kleine databases, het midden van een plat bestand), is de snelheidsverhoging echt nodig. Om de snelheid aan te tonen, voegen we een realistische vertraging van 150ms toe in ons voorbeeld. We zullen ook de console.time / console.timeEnd om de verschillen tussen een Bloom-filtercontrole en een niet-Bloom-filtercontrole te loggen.
In dit voorbeeld gebruiken we ook een extreem beperkt aantal bits: slechts 1024. Het vult zich snel. Als het vult, zal het steeds meer valse positieven vertonen - u zult zien dat de responstijd toeneemt naarmate de fout-positieve score vult.
Deze server gebruikt dezelfde modules als voorheen, dus stel de app.js bestand naar:
"javascript var async = require ('async'), Bloom = require ('bloom-redis'), bodyParser = require ('body-parser'), express = require ('express'), redis = require ('redis' ),
app, client, filter,
currentDataKey = 'current-data', usedDataKey = 'gebruikte-gegevens';
app = express (); client = redis.createClient ();
filter = nieuwe Bloom.BloomFilter (client: client, sleutel: 'stale-bloom-filter', // ter illustratie, dit is een super klein filter. Het moet ongeveer 500 items vullen, dus voor een productiebelasting, je hebt iets veel groter nodig! grootte: 1024, numHashes: 20);
app.post ('/', bodyParser.text (), functie (req, res, next) var used;
console.log ('POST -', req.body); // registreer de huidige gegevens die worden gepost console.time ('post'); // begin met het meten van de tijd die het kost om ons filter en voorwaardelijk verificatieproces uit te voeren //async.series wordt gebruikt om meerdere asynchrone functieaanroepen te beheren. async.series ([functie (cb) filter.contains (req.body, function (err, filterStatus) if (err) cb (err); else used = filterStatus; cb (err);) ;, functie (cb) if (used === false) // Bloom-filters hebben geen fout-negatieven, dus we hebben geen verdere verificatie nodig cb (null); else // it * may * be in the filter, dus we moeten een vervolgcontrole uitvoeren // voor de doeleinden van de zelfstudie voegen we hier een vertraging van 150ms toe, omdat Redis snel genoeg kan zijn om het moeilijk te meten te maken en de vertraging een langzame database of API-aanroep setTimeout (function () console.log ('mogelijk fout-positief'); client.sismember (usedDataKey, req.body, function (err, membership) if (err) cb (err); else / / sismember retourneert 0 als een lid geen deel uitmaakt van de set en 1 als dat het is. // Dit transformeert die resultaten in booleans voor consistente logische vergelijking used = membership === 0? false: true; cb (err); );, 150);, functie (cb) if (gebruikt === false) console.log ('Toevoegen aan filter'); filter.a dd (req.body, cb); else console.log ('Overgeslagen filteroptie, [false] positief'); Deu (null); , functie (cb) if (used === false) client.multi () .set (currentDataKey, req.body) // ongebruikte gegevens zijn ingesteld voor eenvoudige toegang tot de sleutel 'current-data' .sadd (usedDataKey, req.body) // en toegevoegd aan een set voor eenvoudige verificatie later .exec (cb); else cb (null); ], functie (err, cb) if (err) next (err); else console.timeEnd ('post'); // logt de hoeveelheid tijd sinds de console.time oproep boven res.send (saved:! used); // retourneert als het item is opgeslagen, waar voor verse gegevens, false voor verouderde gegevens. ); ); app.get ('/', functie (req, res, next) // retourneer de nieuwe data client.get (currentDataKey, functie (err, data) if (err) next (err); else res.send (data);););
app.listen (8012);"
Omdat POSTing naar een server lastig kan zijn met een browser, laten we krullen gebruiken om te testen.
krul - gegevens "uw gegevens komen hier" --kop "Inhoudstype: tekst / gewoon" http: // localhost: 8012 /
Een snel bash-script kan worden gebruikt om te laten zien hoe het volledige filter eruitziet:
bash #! / bin / bash voor i in 'seq 1 500'; do curl --data "data $ i" --header "Content-Type: text / plain" http: // localhost: 8012 / done
Het is interessant om naar een vullende of een volledige filter te kijken. Omdat deze klein is, kunt u deze eenvoudig bekijken met redis-cli. Door rennen redis-cli wordt oud filter vanaf de terminal tussen het toevoegen van items, zult u de individuele bytes zien toenemen. Een volledig filter zal zijn \ xff voor elke byte. Op dit punt zal het filter altijd positief terugkeren.
Bloom-filters zijn geen wondermiddel, maar in de juiste situatie kan een Bloom-filter een snelle, efficiënte aanvulling zijn op andere datastructuren..
