streamalism.org

1. Pregled

U ovom ćemo članku pogledati konstrukciju Bloom filtra iz Guava knjižnica. Bloomov filtar memorijski je učinkovita, vjerojatnosna struktura podataka pomoću koje možemo odgovoriti na pitanje bez obzira nalazi li se zadani element u skupu.

Nema lažnih negativa s Bloom filtrom, pa kad se vrati lažno, možemo biti 100% sigurni da element nije u skupu.

Međutim, Bloomov filter može vratiti lažno pozitivne, pa kad se vrati pravi, postoji velika vjerojatnost da je element u skupu, ali ne možemo biti 100% sigurni.

Za detaljniju analizu rada Bloom filtra možete proći kroz ovaj vodič.

2. Ovisnost Mavena

Koristit ćemo Guavinu implementaciju Bloom filtra, pa dodajmo guava ovisnost:

 com.google.guava guava 29,0-jre 

Najnoviju verziju možete pronaći na Maven Central.

3. Zašto koristiti Bloom Filter?

Bloom filter je dizajniran da bude prostorno učinkovit i brz. Kad ga koristimo, možemo odredite vjerojatnost lažno pozitivnih odgovora koje možemo prihvatiti i, prema toj konfiguraciji, Bloom filtar zauzet će što manje memorije.

Zbog ove svemirske učinkovitosti, Bloom filter lako će se smjestiti u memoriju čak i za ogroman broj elemenata. Neke baze podataka, uključujući Cassandru i Oracle, koriste ovaj filtar kao prvu provjeru prije odlaska na disk ili u predmemoriju, na primjer, kada stigne zahtjev za određenim ID-om.

Ako filtar vrati da ID nije prisutan, baza podataka može zaustaviti daljnju obradu zahtjeva i vratiti se klijentu. U suprotnom, ide na disk i vraća element ako je pronađen na disku.

4. Stvaranje Bloom filtra

Pretpostavimo da želimo stvoriti Bloom filter za do 500 Cijeli brojevi i da možemo tolerirati jednoprocentnu (0,01) vjerojatnost lažno pozitivnih rezultata.

Možemo koristiti BloomFilter razred iz Guava knjižnica da to postigne. Moramo proslijediti broj elemenata za koje očekujemo da će biti umetnuti u filtar i željenu lažno pozitivnu vjerojatnost:

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

Sada dodamo neke brojeve u filtar:

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

Dodali smo samo tri elementa i definirali smo da će maksimalan broj umetanja biti 500, pa naš Bloom filter treba dati vrlo precizne rezultate. Isprobajmo ga pomoću mightContain () metoda:

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

Kao što i samo ime govori, ne možemo biti 100% sigurni da je zadani element zapravo u filtru kada se metoda vrati pravi.

Kada mightContain () vraća se pravi u našem primjeru možemo biti 99% sigurni da je element u filtru i postoji postotak vjerojatnosti da je rezultat lažno pozitivan. Kad se filtar vrati lažno, možemo biti 100% sigurni da element nije prisutan.

5. Prezasićeni filtar cvjetanja

Kada dizajniramo naš Bloom filter, važno je da pružimo razumno točnu vrijednost za očekivani broj elemenata. U suprotnom, naš će filtar vratiti lažne pozitivne rezultate mnogo većom brzinom od željene. Pogledajmo primjer.

Pretpostavimo da smo stvorili filtar sa željenom lažno pozitivnom vjerojatnosti od jedan posto i očekivanim elementima jednakim pet, ali onda smo umetnuli 100 000 elemenata:

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

Budući da je očekivani broj elemenata tako malen, filtar će zauzeti vrlo malo memorije.

Međutim, kako dodamo više stavki nego što se očekivalo, filtar postaje prenasićen i ima mnogo veću vjerojatnost vraćanja lažno pozitivnih rezultata od željenog jedan posto:

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

Imajte na umu da mightContatin () metoda vratio pravi čak i za vrijednost koju nismo ubacili prethodno u filter.

6. Zaključak

U ovom smo brzom vodiču pogledali vjerojatnosnu prirodu strukture podataka Bloom filtra - koristeći se Guava provedba.

Implementaciju svih ovih primjera i isječaka koda možete pronaći u projektu GitHub.

Ovo je Maven projekt, pa bi ga trebalo biti lako uvesti i pokrenuti kakav jest.