streamalism.org

1. Oversikt

I denne artikkelen ser vi på Bloom-filterkonstruksjonen fra Guava bibliotek. Et Bloom-filter er en minneeffektiv, sannsynlig datastruktur som vi kan bruke til å svare på spørsmålet om om et gitt element er i et sett eller ikke.

Det er ingen falske negativer med et Bloom-filter, så når det kommer tilbake falsk, kan vi være 100% sikre på at elementet ikke er i settet.

Imidlertid et Bloom-filter kan returnere falske positive, så når den kommer tilbake ekte, det er stor sannsynlighet for at elementet er i settet, men vi kan ikke være 100% sikre.

For en mer inngående analyse av hvordan et Bloom-filter fungerer, kan du gå gjennom denne veiledningen.

2. Maven avhengighet

Vi bruker Guavas implementering av Bloom-filteret, så la oss legge til guava avhengighet:

 com.google.guava guava 29.0-jre 

Den siste versjonen finner du på Maven Central.

3. Hvorfor bruke Bloom Filter?

Bloom-filteret er designet for å være plasseffektiv og rask. Når vi bruker den, kan vi spesifiser sannsynligheten for falske positive svar som vi kan akseptere og ifølge den konfigurasjonen vil Bloom-filteret oppta så lite minne som mulig.

På grunn av denne plasseffektiviteten, Bloom-filteret passer lett i minnet selv for et stort antall elementer. Noen databaser, inkludert Cassandra og Oracle, bruker dette filteret som den første kontrollen før du går til disk eller cache, for eksempel når en forespørsel om en spesifikk ID kommer inn.

Hvis filteret returnerer at ID-en ikke er tilstede, kan databasen stoppe videre behandling av forespørselen og gå tilbake til klienten. Ellers går den til disken og returnerer elementet hvis den finnes på disken.

4. Lage et Bloom-filter

Anta at vi vil lage et Bloom-filter for opptil 500 Heltall og at vi tåler en prosent (0,01) sannsynlighet for falske positive.

Vi kan bruke BloomFilter klasse fra Guava bibliotek for å oppnå dette. Vi må passere antall elementer som vi forventer å bli satt inn i filteret og ønsket falsk positiv sannsynlighet:

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

La oss nå legge til noen tall i filteret:

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

Vi la bare til tre elementer, og vi definerte at det maksimale antallet innsettinger vil være 500, så Bloom-filteret vårt skal gi veldig nøyaktige resultater. La oss teste det ved hjelp av mightContain () metode:

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

Som navnet antyder, kan vi ikke være 100% sikre på at et gitt element faktisk er i filteret når metoden returnerer ekte.

Når mightContain () returnerer ekte i vårt eksempel kan vi være 99% sikre på at elementet er i filteret, og det er en prosent sannsynlighet for at resultatet er falskt positivt. Når filteret kommer tilbake falsk, kan vi være 100% sikre på at elementet ikke er til stede.

5. Over-saturated Bloom Filter

Når vi designer Bloom-filteret vårt, det er viktig at vi gir en rimelig nøyaktig verdi for forventet antall elementer. Ellers vil filteret vårt returnere falske positive med en mye høyere hastighet enn ønsket. La oss se et eksempel.

Anta at vi opprettet et filter med en ønsket falsk-positiv sannsynlighet på en prosent og forventet noen elementer lik fem, men så satte vi inn 100.000 elementer:

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

Fordi det forventede antall elementer er så lite, vil filteret oppta veldig lite minne.

Når vi imidlertid legger til flere varer enn forventet, vil filteret blir overmettet og har mye større sannsynlighet for å returnere falske positive resultater enn ønsket en prosent:

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

Merk at mightContatin () metode returnert ekte selv for en verdi som vi ikke satte inn inn i filteret tidligere.

6. Konklusjon

I denne raske opplæringen så vi på den sannsynlige naturen til Bloom-filterets datastruktur - ved å bruke Guava gjennomføring.

Du finner implementeringen av alle disse eksemplene og kodebitene i GitHub-prosjektet.

Dette er et Maven-prosjekt, så det skal være enkelt å importere og kjøre som det er.