Ik lees over bloeifilters en ze lijken gewoon dwaas. Alles wat je kunt bereiken met een bloeifilter, zou je kunnen bereiken in minder ruimte, efficiënter, met een enkele hashfunctie in plaats van meerdere, of dat is wat het lijkt. Waarom zou je een bloeifilter gebruiken en wat is het nut ervan?
Antwoord 1, autoriteit 100%
Alex heeft het vrij goed uitgelegd. Voor degenen die het nog steeds niet helemaal begrijpen, hopelijk helpt dit voorbeeld je om het te begrijpen:
Stel dat ik voor Google werk, in het Chrome-team, en dat ik een functie aan de browser wil toevoegen die de gebruiker waarschuwt als de URL die hij heeft ingevoerd een kwaadaardige URL is. Dus ik heb een dataset van ongeveer 1 miljoen kwaadaardige URL’s, de grootte van dit bestand is ongeveer 25 MB. Omdat de grootte vrij groot is (groot in vergelijking met de grootte van de browser zelf), bewaar ik deze gegevens op een externe server.
Geval 1: ik gebruik een hash-functie met een hash-tabel. Ik beslis over een efficiënte hash-functie en laat alle 1 miljoen URL’s door de hash-functie lopen om hash-sleutels te krijgen. Ik maak dan een hash-tabel (een array), waar de hash-sleutel me de index zou geven om die URL te plaatsen. Dus als ik de hashtabel eenmaal heb gehasht en gevuld, controleer ik de grootte ervan. Ik heb alle 1 miljoen URL’s samen met hun sleutels in de hashtabel opgeslagen. De grootte is dus minimaal 25 MB. Deze hashtabel wordt vanwege zijn grootte opgeslagen op een externe server. Wanneer een gebruiker langskomt en een URL in de adresbalk invoert, moet ik controleren of het kwaadaardig is. Dus ik voer de URL door de hash-functie (de browser zelf kan dit doen) en ik krijg een hash-sleutel voor die URL. Ik moet nu een verzoek indienen bij mijn externe server met die hash-sleutel, om te controleren of de specifieke URL in mijn hash-tabel met die specifieke sleutel hetzelfde is als wat de gebruiker heeft ingevoerd. Zo ja, dan is het kwaadaardig en zo nee, dan is het niet kwaadaardig. Dus elke keer dat de gebruiker een URL invoert, moet een verzoek aan de externe server worden gedaan om te controleren of het een kwaadaardige URL is. Dit zou veel tijd kosten en dus mijn browser traag maken.
Geval 2: ik gebruik een bloeifilter. De volledige lijst van 1 miljoen URL’s wordt door het bloom-filter geleid met behulp van meerdere hash-functies en de respectieve posities worden gemarkeerd als 1, in een enorme reeks van nullen. Laten we zeggen dat we een fout-positief percentage van 1% willen, met behulp van een bloeifiltercalculator (http:/ /hur.st/bloomfilter?n=1000000&p=0.01), krijgen we de vereiste grootte van het bloeifilter als slechts 1,13 MB. Deze kleine omvang wordt verwacht omdat, hoewel de grootte van de array enorm is, we alleen 1s of 0s opslaan en niet de URL’s zoals in het geval van de hashtabel. Deze array kan worden behandeld als een bitarray. Dat wil zeggen, aangezien we slechts twee waarden 1 en 0 hebben, kunnen we individuele bits instellen in plaats van bytes. Dit zou de ruimte die in beslag wordt genomen met 8 keer verminderen. Dit bloeifilter van 1,13 MB kan door zijn kleine formaat in de webbrowser zelf worden opgeslagen !! Dus wanneer een gebruiker langskomt en een URL invoert, passen we eenvoudig de vereiste hash-functies toe (in de browser zelf) en controleren we alle posities in het bloom-filter (dat is opgeslagen in de browser). Een waarde van 0 in een van de posities vertelt ons dat deze URL ZEKER NIET in de lijst met kwaadaardige URL’s staat en dat de gebruiker vrij kan doorgaan. We hebben dus niet naar de server gebeld en dus tijd bespaard. Een waarde van 1 vertelt ons dat de URL MOGELIJK in de lijst met kwaadaardige URL’s staat. In deze gevallen doen we een oproep naar de externe server en daar kunnen we een andere hash-functie gebruiken met een hash-tabel zoals in het eerste geval om op te halen en te controleren of de URL daadwerkelijk aanwezig is.
Aangezien het meestal niet zo is dat een URL kwaadaardig is, komt het kleine bloeifilter in de browser erachter en bespaart het tijd door oproepen naar de externe server te vermijden. Alleen in sommige gevallen, als het bloom-filter ons vertelt dat de URL KAN kwaadaardig zijn, alleen in die gevallen bellen we naar de server. Dat ‘MACHT’ is voor 99% juist.
Dus door een klein bloeifilter in de browser te gebruiken, hebben we veel tijd bespaard omdat we niet voor elke ingevoerde URL serveraanroepen hoeven te doen.
We kunnen zien dat een hashtabel met een enkele hashfunctie voor een heel ander doel wordt gebruikt dan een bloeifilter. Hopelijk neemt dit je twijfel weg 🙂
bewerken:
Ik heb een bloom-filter geïmplementeerd voor het testen van kwaadaardige URL’s in Python. De code is hier te vinden – https://github.com/tarunsharma1/Bloom-Filter
De code is heel eenvoudig te begrijpen en een gedetailleerde beschrijving wordt gegeven in het leesmij-bestand.
Antwoord 2, autoriteit 95%
Van Wikipedia:
Bloomfilters hebben een sterke ruimte
voordeel ten opzichte van andere datastructuren
voor het vertegenwoordigen van sets, zoals
zelfbalancerende binaire zoekbomen,
pogingen, hashtabellen of eenvoudige arrays
of gekoppelde lijsten van de vermeldingen. Meest
hiervan vereisen het opslaan van ten minste de
gegevensitems zelf, die kunnen
overal nodig hebben vanaf een klein aantal
van bits, voor kleine gehele getallen, naar an
willekeurig aantal bits, zoals for
strings (pogingen zijn een uitzondering, aangezien
ze kunnen opslagruimte delen tussen
elementen met gelijke voorvoegsels). Gelinkt
structuren hebben een extra linear
ruimte boven het hoofd voor wijzers. een bloei
filter met 1% fout en een optimale
waarde van k, aan de andere kant,
vereist slechts ongeveer 9,6 bits per
element — ongeacht de grootte van
de elementen. Dit voordeel komt
deels door zijn compactheid, geërfd
van arrays, en gedeeltelijk van zijn
probabilistische aard. Als een 1% fout
positief tarief lijkt te hoog, elk
keer voegen we ongeveer 4,8 bits per element toe
we verlagen het met tien keer.
Voor mij vrij duidelijk.
Een bloeifilter slaat de elementen zelf niet op, dit is het cruciale punt. Je gebruikt een bloom-filter niet om te testen of een element aanwezig is, je gebruikt het om te testen of het zeker nietaanwezig is, aangezien het geen valse negatieven garandeert. Hierdoor kun je geen extra werk doen voor elementen die niet in een set voorkomen (zoals disk IO om ze op te zoeken).
En dat alles in aanzienlijk minder ruimte dan zoiets als een hashtabel (die waarschijnlijk gedeeltelijk op schijf zal staan voor grote datasets). Hoewel je een bloom-filter in combinatiekunt gebruiken met een structuur zoals een hash-tabel, als je er eenmaal zeker van bent dat het element een kans heeft om aanwezig te zijn.
Dus een voorbeeld van een gebruikspatroon kan zijn:
Je hebt veel data op schijf — jij bepaalt welke foutgrens je wilt (bijv. 1%), die de waarde van mvoorschrijft. Vervolgens wordt de optimale kbepaald (uit de formule in het artikel). U vult uw filter één keer uit deze schijfgebonden gegevens.
Nu heb je het filter in RAM. Wanneer u een element moet verwerken, bevraagt u uw filter om te zien of het een kans maakt om in uw dataset te voorkomen. Als dat niet het geval is, wordt er geen extra werk verricht. Geen schijflezingen, enz. (Wat u zou moeten doen als het een hash of boom was, enz.).
Anders, als het filter zegt “Ja, het zit erin”, is er een kans van 1% dat het fout is, dus je doet het nodige werk om erachter te komen. 99% van de tijd zal heter echt zijn, dus het werk was niet voor niets.
Antwoord 3, autoriteit 16%
Ik zal beginnen met de uitleg van wat een bloeifilter is, wat het wel en niet kan doen, waarom hebben we het nodig, een intuïtieve beschrijving laten zien hoe het werkt en dan een voorbeeld geven wanneer ze nuttig kunnen zijn.
Dus een standaard bloeifilteris een probabilistische gegevensstructuurdie kan*:
- element toevoegen aan een set
- controleer of een element in de set zit door
definitely not in the setofpossibly in the set
te vertellen
Deze possibly in the setis precies waarom het probabilistisch wordt genoemd. Door slimme woorden te gebruiken, betekent dit dat false positivemogelijk zijn (er kunnen gevallen zijn waarin het ten onrechte denkt dat de element is positief) maar vals-negatief is onmogelijk.
Maar het kan niet*:
- een item uit de set verwijderen
- geef je een lijst van alle elementen die momenteel in je set zitten
*Deze set van can/can’t is voor een basisbloeifilter. Omdat het een nuttige gegevensstructuur is die lang geleden is gemaakt, hebben mensen gevonden hoe ze vergroothet met andere handigefuncties.
Maar wacht even: we kennen al een datastructuur die dit allemaal kan beantwoorden zonder vaag ‘mogelijk’ en ook zonder alle beperkingen (kan niet verwijderen, kan niet alles tonen). En het wordt een setgenoemd. En hier komt een belangrijk voordeel van een bloeifilter: het is ruimtebesparend en ruimteconstante.
Dit betekent dat het niet uitmaakt hoeveel elementen we daar opslaan, de ruimte zal hetzelfde zijn. Ja, een bloom-filter met 10^6-elementen (nutteloos bloom-filter) neemt dezelfde hoeveelheid ruimte in beslag als een bloom-filter met 10^20-elementen en dezelfde ruimte als bloom filter met 0elementen. Dus hoeveel ruimte zal het in beslag nemen? Het is aan jou om te beslissen (maar er is een ruil van: hoe meer elementen je hebt, hoe onzekerder je bent met je possibly in the setantwoord.
Een ander cool ding is dat het ruimteconstant is. Wanneer u de gegevens opslaat in een set, moet u deze gegevens ook daadwerkelijk opslaan. Dus als je this long string in the setopslaat, moet je minimaal 27 bytes aan ruimte gebruiken. Maar voor een fout van 1% en een optimale waarde van k **, heb je ~ 9,6 bits ( < 2 bytes) per elk element nodig (of het nu een korte int is of een enorme muur van tekst ).
Een andere eigenschap is dat alle bewerkingen constante tijd in beslag nemen, wat absoluut niet hetzelfde is als afgeschreven constante tijd in het geval van sets (onthoud dat als de set botsingen heeft, deze kan verslechteren in O(n)tijd).
**k is een waarde van hash-functies die worden gebruikt in het bloeifilter
Ik zal niet beschrijven hoe de bloomfilters werken(wikipedia-artikel legt heel goed uit alles). Hier zal ik kort de basis vertellen.
- je start een lege bit-array met de lengte
m - je selecteert
kverschillende hash-functies (hoe onafhankelijker hoe beter) - als je een element wilt toevoegen, bereken je alle
khashes van deze waarde en stel je de bijbehorende bits in op 1 - als je wilt controleren of een element bestaat, bereken je ook alle
khashes en als er tenminste één niet is ingesteld, zit het zeker niet in de set. Anders kan het in de set zitten.
Zelfs deze beschrijving is voldoende om te begrijpen waarom we niet zeker kunnen zijn (je kunt alle bits instellen van verschillende andere waarden). Hier is een heel mooie visualisatie van hoe het werkt.
Dus wanneer kunnen bloeifilters nuttig zijn? Het korte antwoord is overal waar valse positieven acceptabel zijn en waar je zou willen controleren of er iets in de set zit, maar zelfs als dat niet het geval is, kan het een eerste verdedigingslinie zijn om duur uit te sluiten oproepen naar verificateurs.
Hier is een lijst met meer concrete beschrijvingen:
- een standaardvoorbeeld van kwaadaardige websites en een browserwordt beschreven in bijna elke plaatswaar mensen praten over bloeifilters
- is een zwak wachtwoord: in plaats van een enorme set van alle mogelijke zwakke wachtwoorden te hebben, kun je gewoon controleren of het wachtwoord zeker niet zwak is met een veel kleiner bloeifilter
- als je een lijst met artikelen en een lijst met gebruikers hebt, kun je de bloom-filter gebruiken om de artikelen van gebruikers te tonen die ze niet hebben gelezen. Interessant is dat je maar één filter kunt hebben (je controleert of de combinatie user_id + article_id er is)
- bitcoin gebruikt bloom-filter voor portemonnee-synchronisatie
- Akamai’s webservers gebruiken Bloom-filters om te voorkomen dat “one-hit-wonders” worden opgeslagen in de schijfcaches. One-hit-wonders zijn webobjecten die slechts één keer door gebruikers worden aangevraagd, iets dat volgens Akamai werd toegepast op bijna driekwart van hun caching-infrastructuur. Het gebruik van een Bloom-filter om het tweede verzoek voor een webobject te detecteren en dat object pas bij het tweede verzoek in de cache op te slaan, voorkomt dat one-hit wonders de schijfcache binnendringen, waardoor de schijfwerkbelasting aanzienlijk wordt verminderd en de hitfrequenties van de schijfcache toenemen (uit voorbeelden in het filter van bloom artikel op wiki)
Antwoord 4, autoriteit 8%
Bloomfilters zijn erg handig in de bio-informatica. Ze kunnen ruimtebesparend zijn in vergelijking met het gebruik van een gewone hash, vooral wanneer de tekenreeksen waarmee u werkt honderden miljoenen letters kunnen zijn met een heel klein alfabet, namelijk {A,G,T,C} . Ze worden meestal gebruikt om te beoordelen of een bepaald k-meer aanwezig of afwezig is in een genoom. Er is hiereen voorbeeld van een gebruikt voor iets relevants.
BEWERKEN:
De meerdere hash-functies worden gebruikt om valse positieven te minimaliseren. De hoop is dat tussen alle k-hash-functies elke waarde een unieke handtekening in de bit-array zal hebben in vergelijking met elke andere mogelijke waarde. Valse positieven bestaan echter wel, maar deze kunnen tot een beheersbaar niveau worden geminimaliseerd. Met deze techniek hash je elementen onafhankelijkvan hun grootte. Wanneer u ernaar zoekt, gebruikt u elke hash-functie en controleert u of hun bitwaarden allemaal 1 zijn.
Vergelijk dit met het menselijk genoom, waar een toename in de grootte van het element de grootte van de hash-tabel aanzienlijk vergroot (de grootte van de tabel is 4*4k). Dit gaat ervan uit dat je de elementen codeert met 2 bits / letter.
Antwoord 5, autoriteit 4%
Als een Bloom-filter retourneert dat een item deel uitmaakt van de set, is er een zekere kans op een false positive. Als er slechts één hashfunctie zou worden gebruikt om het lidmaatschap van de set aan te geven, zou de kans op een fout-positief groter zijn dan bij het gebruik van meerdere hashfuncties.
Antwoord 6
Bloom-filters worden gebruikt voor caching, maar worden niet overal gebruikt. Als u enkele toepassingen van bloeifilters kent, zult u zien hoe nuttig ze zijn:
Routers
Moderne routers hebben beperkte ruimte en, gezien de hoeveelheid pakketten die ze per seconde verwerken, hebben ze extreem snelle algoritmen nodig. Ze zijn dus de perfecte ontvanger voor Bloom-filters, voor al die bewerkingen die een klein aantal fouten aankunnen. Naast caching gebruiken routers vaak Bloom-filters om verboden IP’s bij te houden en om statistieken bij te houden die zullen worden gebruikt om DoS-aanvallen te onthullen.
Crawlers
Crawlers zijn geautomatiseerde softwareagenten die een netwerk scannen en op zoek zijn naar inhoud, die alles wat ze vinden, ontleden en indexeren. Wanneer een crawler links op een pagina of document vindt, is deze meestal geprogrammeerd om deze te volgen en recursief de bestemming van de link te crawlen.
Er zijn enkele uitzonderingen: voor
Zo worden de meeste bestandstypen genegeerd door crawlers, net als koppelingen die zijn gemaakt met tags
met een attribuut rel="nofollow".
Het is eigenlijk aan te raden om op deze manier elk anker te markeren met een
link naar een actie met bijwerkingen. Anders zullen de crawlers van zoekmachines, zelfs als ze dit beleid respecteren, onvoorspelbaar gedrag veroorzaken.
Wat er kan gebeuren is dat als je je eigen crawler schrijft en je niet voorzichtig bent, deze in een eindeloze lus terecht kan komen tussen twee of meer pagina’s met wederzijdse links (of keten van links) naar elkaar. Om dergelijke loops te voorkomen, moeten crawlers de pagina’s bijhouden die ze al hebben bezocht.
Bloom-filters zijn de beste manier om dit te doen, omdat ze URL’s op een compacte manier kunnen opslaan en de URL’s constant kunnen controleren en opslaan.
IO-ophaler
Bloom-filtergebaseerde caching helpt bij het verminderen van onnodige
ophalen/opslag van dure IO-resources. Het mechanisme is hetzelfde als bij crawlen: de bewerking wordt alleen uitgevoerd als we een “miss” hebben, terwijl “hits” meestal een meer diepgaande vergelijking veroorzaken (bijvoorbeeld bij een hit, alleen de eerste paar regels van schijf ophalen of het eerste blok van een document, en deze te vergelijken).
Spellingcontrole
Eenvoudigere versies van spellingcontrole die werden gebruikt om Bloom-filters als woordenboeken te gebruiken. Voor elk woord van de onderzochte tekst zou een zoekopdracht op een Bloom-filter het woord valideren als correct of het markeren als een spelfout. Natuurlijk zouden de fout-positieve gebeurtenissen ervoor zorgen dat sommige spelfouten onopgemerkt blijven, maar de kans dat dit gebeurt
vooraf kon worden gecontroleerd. Tegenwoordig maken spellingcontrolers echter meestal gebruik van pogingen: deze gegevensstructuren leveren goede prestaties bij het zoeken naar tekst zonder valse positieven.
Gedistribueerde databases en bestandssystemen
Cassandra gebruikt Bloom-filters voor indexscans om te bepalen of een SSTable gegevens heeft voor een bepaalde rij. Evenzo gebruikt Apache HBase Bloom-filters als een efficiënt mechanisme om te testen of een StoreFile een specifieke rij- of rij-col-cel bevat. Dit verhoogt op zijn beurt de algehele leessnelheid, door onnodige schijflezingen van HFile-blokken die geen bepaalde rij of rijkolom bevatten, uit te filteren.