streamalism.org

1. Oversigt

I denne artikel ser vi på Bloom-filterkonstruktionen fra Guava bibliotek. Et Bloom-filter er en hukommelseseffektiv, sandsynlig datastruktur, som vi kan bruge til at besvare spørgsmålet om om et givet element er i et sæt eller ej.

Der er ingen falske negativer med et Bloom-filter, så når det vender tilbage falsk, kan vi være 100% sikre på, at elementet ikke er i sættet.

Dog et Bloom-filter kan returnere falske positive, så når det vender tilbage rigtigt, der er stor sandsynlighed for, at elementet er i sættet, men vi kan ikke være 100% sikre.

For en mere dybdegående analyse af, hvordan et Bloom-filter fungerer, kan du gennemgå denne vejledning.

2. Maven-afhængighed

Vi bruger Guavas implementering af Bloom-filteret, så lad os tilføje guava afhængighed:

 com.google.guava guava 29.0-jre 

Den seneste version kan findes på Maven Central.

3. Hvorfor bruge Bloom Filter?

Bloom-filteret er designet til at være pladseffektiv og hurtig. Når vi bruger det, kan vi specificere sandsynligheden for falske positive svar, som vi kan acceptere og ifølge denne konfiguration optager Bloom-filteret så lidt hukommelse som muligt.

På grund af denne pladseffektivitet Bloom-filteret passer let i hukommelsen selv for et stort antal elementer. Nogle databaser, inklusive Cassandra og Oracle, bruger dette filter som den første kontrol, inden de går til disk eller cache, for eksempel når en anmodning om et specifikt ID kommer ind.

Hvis filteret returnerer, at ID'et ikke er til stede, kan databasen stoppe yderligere behandling af anmodningen og vende tilbage til klienten. Ellers går det til disken og returnerer elementet, hvis det findes på disken.

4. Oprettelse af et Bloom-filter

Antag, at vi vil oprette et Bloom-filter på op til 500 Heltal og at vi kan tåle en procent (0,01) sandsynlighed for falske positive.

Vi kan bruge BloomFilter klasse fra Guava bibliotek for at opnå dette. Vi er nødt til at videregive antallet af elementer, som vi forventer at blive indsat i filteret, og den ønskede falske positive sandsynlighed:

BloomFilter filter = BloomFilter.create (Funnels.integerFunnel (), 500, 0.01);

Lad os nu tilføje nogle tal til filteret:

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

Vi tilføjede kun tre elementer, og vi definerede, at det maksimale antal indsættelser vil være 500, så vores Bloom-filter skulle give meget nøjagtige resultater. Lad os teste det ved hjælp af mightContain () metode:

assertThat (filter.mightContain (1)). er sand (); assertThat (filter.mightContain (2)). er sand (); assertThat (filter.mightContain (3)). er sand (); assertThat (filter.mightContain (100)). er Falsk ();

Som navnet antyder, kan vi ikke være 100% sikre på, at et givet element faktisk er i filteret, når metoden vender tilbage rigtigt.

Hvornår mightContain () vender tilbage rigtigt i vores eksempel kan vi være 99% sikre på, at elementet er i filteret, og der er sandsynlighed for en procent, at resultatet er falsk positivt. Når filteret vender tilbage falsk, kan vi være 100% sikre på, at elementet ikke er til stede.

5. Overmættet blomstringsfilter

Når vi designer vores Bloom-filter, det er vigtigt, at vi giver en rimelig nøjagtig værdi for det forventede antal elementer. Ellers returnerer vores filter falske positive med en meget højere hastighed end ønsket. Lad os se et eksempel.

Antag at vi oprettede et filter med en ønsket falsk-positiv sandsynlighed på en procent og forventede nogle elementer svarende til fem, men så indsatte vi 100.000 elementer:

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

Da det forventede antal elementer er så lille, optager filteret meget lidt hukommelse.

Da vi imidlertid tilføjer flere varer end forventet, filter bliver overmættet og har en meget højere sandsynlighed for at returnere falske positive resultater end den ønskede procent:

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

Bemærk, at måskeContatin () metode vendt tilbage rigtigt selv for en værdi, som vi ikke indsatte ind i filteret tidligere.

6. Konklusion

I denne hurtige vejledning kiggede vi på den sandsynlige karakter af Bloom-filterdatastrukturen - ved hjælp af Guava implementering.

Du kan finde implementeringen af ​​alle disse eksempler og kodestykker i GitHub-projektet.

Dette er et Maven-projekt, så det skal være let at importere og køre som det er.