streamalism.org

1. Overzicht

In dit artikel zullen we kijken naar de Bloom-filterconstructie van de Guave bibliotheek. Een Bloom-filter is een geheugenefficiënte, probabilistische datastructuur waarmee we de vraag kunnen beantwoorden of een bepaald element al dan niet in een set zit.

Er zijn geen valse negatieven met een Bloom-filter, dus als het terugkeert falsekunnen we er 100% zeker van zijn dat het element niet in de set zit.

Wel een Bloom-filter kan valse positieven retourneren, dus als het terugkeert waar, is de kans groot dat het element in de set zit, maar we kunnen er niet 100% zeker van zijn.

Voor een meer diepgaande analyse van hoe een Bloom-filter werkt, kunt u deze tutorial doorlopen.

2. Maven Afhankelijkheid

We zullen Guava's implementatie van het Bloom-filter gebruiken, dus laten we de guave afhankelijkheid:

 com.google.guava guave 29.0-jre 

De nieuwste versie is te vinden op Maven Central.

3. Waarom een ​​bloeifilter gebruiken?

Het Bloom-filter is ontworpen om ruimte-efficiënt en snel te zijn. Als we het gebruiken, kunnen we dat specificeer de kans op vals-positieve reacties die we kunnen accepteren en volgens die configuratie neemt het Bloom-filter zo min mogelijk geheugen in beslag.

Vanwege deze ruimte-efficiëntie, het Bloom-filter past gemakkelijk in het geheugen zelfs voor grote aantallen elementen. Sommige databases, waaronder Cassandra en Oracle, gebruiken dit filter als eerste controle voordat ze naar schijf of cache gaan, bijvoorbeeld wanneer een verzoek om een ​​specifieke ID binnenkomt.

Als het filter aangeeft dat het ID niet aanwezig is, kan de database de verdere verwerking van het verzoek stoppen en terugkeren naar de client. Anders gaat het naar de schijf en geeft het het element terug als het op de schijf wordt gevonden.

4. Een bloeifilter maken

Stel dat we een Bloom-filter willen maken voor maximaal 500 Gehele getallen en dat we een kans van één procent (0,01) op valse positieven kunnen tolereren.

We kunnen de BloomFilter klasse uit de Guave bibliotheek om dit te bereiken. We moeten het aantal elementen dat we verwachten te worden ingevoegd in het filter en de gewenste vals-positieve waarschijnlijkheid doorgeven:

BloomFilter-filter = BloomFilter.create (Funnels.integerFunnel (), 500, 0,01);

Laten we nu wat getallen aan het filter toevoegen:

filter.put (1); filter.put (2); filter.put (3);

We hebben slechts drie elementen toegevoegd en we hebben bepaald dat het maximale aantal invoegingen 500 zal zijn, dus ons Bloom-filter zou zeer nauwkeurige resultaten moeten opleveren. Laten we het testen met behulp van de mightContain () methode:

assertThat (filter.mightContain (1)). isTrue (); assertThat (filter.mightContain (2)). isTrue (); assertThat (filter.mightContain (3)). isTrue (); assertThat (filter.mightContain (100)). isFalse ();

Zoals de naam suggereert, kunnen we er niet 100% zeker van zijn dat een bepaald element daadwerkelijk in het filter zit wanneer de methode terugkeert waar.

Wanneer mightContain () geeft terug waar in ons voorbeeld kunnen we er 99% zeker van zijn dat het element in het filter zit, en er is een kans van één procent dat het resultaat een vals positief resultaat is. Wanneer het filter terugkeert falsekunnen we er 100% zeker van zijn dat het element niet aanwezig is.

5. Oververzadigde bloeifilter

Wanneer we ons Bloom-filter ontwerpen, het is belangrijk dat we een redelijk nauwkeurige waarde geven voor het verwachte aantal elementen. Anders retourneert ons filter valse positieven met een veel hoger tarief dan gewenst. Laten we een voorbeeld bekijken.

Stel dat we een filter hebben gemaakt met een gewenste fout-positieve waarschijnlijkheid van één procent en een aantal elementen verwacht dat gelijk is aan vijf, maar dan hebben we 100.000 elementen ingevoegd:

BloomFilter-filter = BloomFilter.create (Funnels.integerFunnel (), 5, 0,01); IntStream.range (0, 100_000) .forEach (filter :: put); 

Omdat het verwachte aantal elementen zo klein is, neemt het filter weinig geheugen in beslag.

Omdat we echter meer items toevoegen dan verwacht, is de filter raakt oververzadigd en heeft een veel grotere kans op het retourneren van fout-positieve resultaten dan de gewenste procent:

assertThat (filter.mightContain (1)). isTrue (); assertThat (filter.mightContain (2)). isTrue (); assertThat (filter.mightContain (3)). isTrue (); assertThat (filter.mightContain (1_000_000)). isTrue ();

Merk op dat de mightContatin () methode keerde terug waar zelfs voor een waarde die we niet hebben ingevoegd eerder in het filter.

6. Conclusie

In deze korte tutorial hebben we gekeken naar de probabilistische aard van de Bloom-filtergegevensstructuur - gebruikmakend van de Guave implementatie.

Je kunt de implementatie van al deze voorbeelden en codefragmenten vinden in het GitHub-project.

Dit is een Maven-project, dus het moet gemakkelijk te importeren en uit te voeren zijn zoals het is.